[Math] How many words of length $n$ can be generated from an alphabet of $k$ symbols with restrictions on the number of symbols

combinatorics

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.

Thanks.

Best Answer

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

Related Question