Please explain logic behind a given solution

X-man

New Member
#1
The following example is from Ryser's book Combinatorial Mathematics:

"The number of 12-letter words that can be formed from 4 A's, 4 B's, 2 C's and 2 D's is 12!/(4!4!2!2!) = 207,900."

I assume the reasoning behind this is that the 12 letters available can be permuted in 12! ways, but the 4 A's are indistinguishable as are the 4 B's, 2 C's and 2 D's, and that's why we divide by the product of 4!, 4!, 2!, and 2!.

Right after that Ryser gives this example: "The number of 5-letter words that can be formed from the letters A, B, C in which A appears at most twice, B at most once, and C at most three times is

5!/(2!0!3!) + 5!/(2!1!2!) + 5!/(1!1!3!) = 60."

I don't understand Ryser's solution. I solve it following the logic of the first example given above. I reason:

1) Since A appears at most twice, B at most once, and C at most three times, we're really asking: how many 5-letter words can we form from two A's, one B, and three C's = six letters?

2) Thus we count the number of permutations of five letters taken from the six letters, which is 6!/( 6–5 )! = 6!

3) But since the two A's are indistinguishable as are the three C's, we have to divide this by 2!3! to get

6!/(2!3!) = 60.

Can someone explain the reasoning that leads to Ryser's answer, which is a sum of three addends?
 

BGM

TS Contributor
#2
1) Since A appears at most twice, B at most once, and C at most three times, we're really asking: how many 5-letter words can we form from two A's, one B, and three C's = six letters?
Not really; The question is still asking for a 5 letter permutation. But now the question gives 1 extra letter of "freedom" so you have 3 possible scenarios

\( \{(2,1,2), (2,0,3), (1,1,3)\} \)

under the constraint \( a \leq 2, b \leq 1, c \leq 3, a + b + c = 5, a, b, c \in \mathbb{Z}^+\cup\{0\} \)
 

X-man

New Member
#3
Hi, BGM,

The "not really" distinction you make is too subtle for my brain. Can you formulate a problem where Ryser's approach and mine would result in different answers?

But thanks for the reply. I'd thought Ryser might be using multinomial coefficients, but couldn't quite work that out.
 

Dason

Ambassador to the humans
#4
Consider making a 2 letter word with at most 2 As, 1 B, and 1C.

Your method says that we look at the number of permutations of 2 letters out of the 4: 4!/2! = 12 then divide by 2! since there are 2 As. So we get an answer of 6.

But if you work through it the alternative way you get an answer of 7 and indeed these are the possibilities:
"aa" "ac" "ca" "ab" "ba" "bc" "cb"