Re: Combinatorics QUESTION

this is not calculus ... thread moved to Discrete Math

Re: Combinatorics QUESTION

Quote:

Originally Posted by

**maximus101** Let $\displaystyle A = {a_1, a_2, . . . , a_k}$ be an alphabet, and let n_i denote the number of appearances of

letter a_i in a word. How many words of length n in the alphabet A are there for which

$\displaystyle k = 3, n = 10, n_1 = n_2 + n_3$ and $\displaystyle n_2$ is even?

"let n_i denote the number of appearances of letter a_i in a word"? Which word? Are you saying that there's a single unknown-yet-fixed word in the alphabet A which defined the numbers $\displaystyle n_1, n_2, n_3,... , n_k ?$

OR, are you treating $\displaystyle n_1, n_2, n_3,... , n_k$ as k distinct functions functions from the domain of all possible finite words in A into the non-negative integers?

I would guess the later, but I'm not sure.

With that assumption:

$\displaystyle 10 = n_1+n_2 + n_3 = (n_2+n_3) + n_2 + n_3 = 2(n_2 + n_3).$

$\displaystyle \text{Thus } n_3 = 5-n_2 \text{ and } n_1 = n_2 + n_3 = 5.$

$\displaystyle \text{Case }n_2 = 0:$

$\displaystyle \text{Thus } n_1 = 5, n_3 = 5 - n_2 = 5 - 0 = 5.$

$\displaystyle \text{Case }n_2 = 2:$

$\displaystyle \text{Thus } n_1 = 5, n_3 = 5 - n_2 = 5 - 2 = 3.$

$\displaystyle \text{Case }n_2 = 4:$

$\displaystyle \text{Thus } n_1 = 5, n_3 = 5 - n_2 = 5 - 4 = 1.$

$\displaystyle \text{So ANSWER } = \text{ number of ways} (n_1 = 5, n_2 = 0, n_3 = 5)$

$\displaystyle + \text{number of ways}(n_1 = 5, n_2 = 2, n_3 = 3)$

$\displaystyle + \text{number of ways}(n_1 = 5, n_2 = 4, n_3 = 1),$

$\displaystyle \text{and each term there is a clearer combinatorial problem.}$

$\displaystyle \text{So ANSWER } = \text{ number of distinguishable permutations of } "AAAAACCCCC"$

$\displaystyle + \text{ number of distinguishable permutations of } "AAAAABBCCC"$

$\displaystyle + \text{ number of distinguishable permutations of } "AAAAABBBBC".$

For the middle example: imagine there are 10 slots, numbered 1 through 10, that you need to fill with those letters to make your word. Choose 5 slots to fill with the A's, and then, from the 5 remaining slots, choose 2 to fill with the B's (Obviously the rest are then filled in with C's.) The number of ways to do that will be the number of distinguishable length 10 words using 5 A's, 2 B's and 3 C's.