Given an alphabet of $k$ symbols, $\lbrace s_1,s_2, \ldots,s_k \rbrace$, how many words of length $n$, $w(n)$, can be generated knowing that,

  1. Only two of the $k$ available symbols participate;
  2. 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 $\lbrace A, B, C\rbrace$ and that I want words of length $4$ with two $A$ and two $B$. With the stated restrictions all of the possible words are

$\lbrace AABB, ABAB,ABBA, BBAA, BAAB, BABA \rbrace$

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.



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$.


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.

I hope I'm clear enough.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.