Given an alphabet of k symbols, {s_1,s_2,…,s_k}, how many words of length n, w(n), can be generated knowing that, Only two of the k available symbols participate; The symbol si must appear exactly ni times and the symbol sj must appear exactly nj times and ni+nj=n (the length of the word); To ilustrate the problem suppose that the alphabet is {A,B,C} and that I want words of length 4 with two A and two B. With the stated restrictions all of the possible words are {AABB,ABAB,ABBA,BBAA,BAAB,BABA}

skystasvs

skystasvs

Answered question

2022-09-15

Given an alphabet of k symbols, { s 1 , s 2 , , s k }, how many words of length n, w ( n ), can be generated knowing that,
Only two of the k available symbols participate;
The symbol s i must appear exactly n i times and the symbol s j must appear exactly n j times and n i + n j = n (the length of the word);
To ilustrate the problem suppose that the alphabet is { A , B , C } and that I want words of length 4 with two A and two B. With the stated restrictions all of the possible words are
{ A A B B , A B A B , A B B A , B B A A , B A A B , B A B A }
So, I need to know what this w ( n ) = w ( n i , n j ) is. Some references on aproaches on how to solve this kind of problems and related algorithms to generate such words would be apreciated.

Answer & Explanation

nizkem0c

nizkem0c

Beginner2022-09-16Added 13 answers

Hint: For this problem, you first have to select two of the symbols from your list. How many ways can that be done? Should the order matter? Second, you have to select which n 1 positions in the word can take the first of the two symbols. How many ways can that be done? As the two selections are independent, you then multiply the two numbers. You also have to worry about factors of 2-is there some way that interchanging the selected letters in the first choice and interchanging the selected positions in the second can get you to the same word in different ways? This is particularly a problem when n 1 = n 2 .
dizxindlert7

dizxindlert7

Beginner2022-09-17Added 2 answers

This is kind of late, but the correct approach would be to use binomial coefficients.
For instance, here we have words of length 4 and we're looking for a binary chain with 2 "1"s and 2 "0"s which would translate to C(4,2), which is 6.
And with the number of different pairs of symbols you'd have k x (k-1) different combinations.
So the answer would be k x (k-1) x C(n,r) where k is your "alphabet", and C(n,r) is your binomial coefficient of a mathematical word of n letters and r instances of a letter.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?