Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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