permutations/combinations

Stochastic_Jimmy

New member
Joined
Jan 10, 2013
Messages
27
So I'm struggling a bit with the following question:

How many 5 digit numbers can be made from the numbers 1 to 9, where no number can appear more than 3 times and at least one number must appear exactly twice?

I was thinking that there are 3 different cases that satisfy these requirements:


  1. 3 of one number and 2 of a different number (e.g. 11133 or 13311, etc.)
  2. 2 of one number, 2 of another number, and 1 other (e.g. 22334)
  3. 2 of one number and then 3 different numbers (e.g. 22345)

For Case 1 my thought was there are \(\displaystyle 9 \times 8 \) ways to get the two different numbers and then \(\displaystyle \binom{5}{3,2} \) arrangements for a total of \(\displaystyle 9 \times 8 \times \binom{5}{3,2}. \)

For Case 2 there are \(\displaystyle 9 \times 8 \times 7 \) ways to select the three different numbers and then \(\displaystyle \binom{5}{2,2,1} \) arrangements for a total of \(\displaystyle 9 \times 8 \times 7 \times \binom{5}{2,2,1}. \)

And for Case 3 there are \(\displaystyle 9 \times 8 \times \times 7 \times 6 \) ways to select the 4 different numbers and \(\displaystyle \binom{5}{2,1,1,1}. \) arrangements for a total of \(\displaystyle 9 \times 8 \times 7 \times 6 \times \binom{5}{2,1,1,1}. \)

Then the answer would just be the sum of the totals from these 3 cases.

Is this right or am I making an error somewhere?

Thanks so much!
 
Hello, Stochastic_Jimmy!

Your reasoning is quite good,
. . with a bit of overcounting, indicated with *.


How many 5-digit numbers can be made from the numbers 1 to 9,
where no number can appear more than 3 times
and at least one number must appear exactly twice?


I was thinking that there are 3 different cases that satisfy these requirements:

  1. 3 of one number and 2 of a different number (aaabb)
  2. 2 of one number, 2 of another number, and 1 other (aabbc)
  3. 2 of one number and then 3 different numbers (aabcd)

Case 1
There are \(\displaystyle 9 \times 8 \) ways to get the two different numbers and then \(\displaystyle \binom{5}{3,2} \) arrangements
for a total of: \(\displaystyle 9 \times 8 \times \binom{5}{3,2}.\) . Correct!

Case 2
There are \(\displaystyle 9 \times 8 \times 7 \) ways to select the three different numbers and then \(\displaystyle \binom{5}{2,2,1} \) arrangements
for a total of: \(\displaystyle 9 \times 8 \times 7 \times \binom{5}{2,2,1}.\) . Too big.

Case 3
T
here are \(\displaystyle 9 \times 8 \times 7 \times 6 \) ways to select the 4 different numbers and \(\displaystyle \binom{5}{2,1,1,1}. \) arrangements
for a total of: \(\displaystyle 9 \times 8 \times 7 \times 6 \times \binom{5}{2,1,1,1}.\) . Too big.

Then the answer would just be the sum of the totals from these 3 cases.

Is this right or am I making an error somewhere?

Think of the three cases as Poker hands: Full House, Two Pair, One Pair.

Full House: a Triple and a Pair.
There are 9 choices for the Triple; 8 choices for the Pair.
There are \(\displaystyle {5\choose3,2}\) arrangements of the 5 digits.

Two Pair: two Pairs and a Singleton.
There are \(\displaystyle {9\choose2}\) choices for the Two Pair. *
There are 7 choices for the Singleton.
There are \(\displaystyle {5\choose2,2,1}\) arrangements of the 5 digits.

One Pair: one Pair and three Singletons.
There are 9 choices for the Pair.
There are \(\displaystyle {8\choose3}\) choices for the 3 Singletons. *
There are \(\displaystyle {5\choose2,1,1,1}\) arrangements of the 5 digits.
 
Top