Illinois State University Mathematics Department


MAT 305: Combinatorics Topics for K-8 Teachers



Possible Solutions: Supplementary Problems Set D


Possible Solutions
return to problems

1.

Determine the number of 50-digit sets we can create, choosing from {0,1,...9} and assuring that all digits are represented.

This problem is analogous to determining the number of positive-integer solutions to the equation x0+x1+...+x9 = 50. We refer to 50 as the total number of items (in general represented by n) and 10 as the number of different types of items (in general represented by k). There are C(n-1,k-1) = C(50-1,10-1) = C(49,9) solutions.

2.

How many 100-letter sets can be made using letters from {A,B,...,Z}, assuring that each letter occurs at least once?

Similar to Question 1, with n = 100 and k = 26. We get C(100-1,26-1) = C(99,25) such sets.

3.

Repeat problem (1) from Set D with the additional requirement that each digit occur at least twice.

If each digit is to occur at least twice, then we essentially have already accounted for 20 of the objects, i.e., 10 digits each appearing twice. This leaves us n = 30 total objects to place, still having k = 10 different types of objects. Now, however, with the 20 objects accounted for, we no longer need to assure that each digit is further represented.

We thus are solving a new problem: Determine the number of nonnegative-integer solutions to the equation x0+x1+...+x9 = 30. In general, this is C(n + k - 1, k - 1), so here we have C(30 + 10 - 1, 10 - 1) = C(39,9) sets that can be created.

4.

How many 20-letter sets can be made using letters from {A,B,C} and requiring that there be at least one A, at least two Bs, and at least three Cs?

With n = 20 and k = 3, we use 6 of the 20 objects to meet the requirements for appearances of A, B, and C. We are left with 14 total objects to place of 3 different types, solved over the nonnegative integers. This is C(14 + 3 - 1,3 - 1) different sets.

5.

Determine the number of three-letter sets that can be made choosing from among {A,B,C,D,E} and allowing repetition. Note that missing elements are allowed.

We are determining the number of nonnegative-integer solutions to the equation x1 + x2 + x3 + x4 + x5 = 3, so n = 3 and k = 5. The number of three-letter sets is C(3 + 5 - 1, 5 - 1) = C(7,4).

6.

How many n-element sets can be created from among {a1, a2,...,ak}, allowing repetition as well as missing elements?

This is the generalization to several of the questions posed already. The number of sets is C(n+ k - 1, k - 1).

7.

Devise a scenario that can be completed in exactly 1001 ways.

Many solutions exist for this. We note that 1001 = 7*11*13 and that 1001 = C(14,4). We can show that there are 1001 nonnegative-integer solutions to the equation a + b + c + d + e = 10.

8.

Five pairs of shoes are displayed.
(a) How many ways can three shoes be selected?
(b) How many of those in (a) contain a matched pair?
(c) When four shoes are selected from the five pairs, what portion of the selections include two matched pairs?

(a) C(10,3)
(b) C(5,1)*C(8,1)
Here, we must get a matched pair, so we select 1pair from the 5 pairs. This leaves us with 8 shoes and we select 1 of them.
(c) C(5,2)/C(10,4)
There are C(10,4) total ways to select 4 shows from the 10 available. To get two matched pairs, we again consider them as pairs when selecting, so we could get two matched pairs in C(5,2) ways. The desired ratio is C(5,2)/C(10,4).

9.

Seven coins are flipped simultaneously. What portion of the possible results include getting three heads and four tails?

Row 7 of Pascal's Triangle shows ways to get various combinations of heads and tails:

1
7
21
35
35
21
7
1

Reading from the left, the table shows there is 1 way to getting 7H, 0T, 7 ways to get 6H,1T, 21 ways to get 5H,2T, and so on. The sum of these entries is 1+7+21+...+1=2^7=128. Exactly 35 of these result in 3H,4T. Thus, the desired ratio is 35/128.

10.

(a) Consider the expansion of (x+y)^13. What is the coefficient of the collected term containing x^8y^5 ?
(b) Repeat the question in (a) for (2x-y)^13.

(a) C(13,5) = C(13,8)
(b) C(13,5)*(2^8)*(-1)^5 = -C(13,5)*(2^8)

11.

Determine the number of 8-letter words that use letters from {A,B,C} and contain exactly three As.

With exactly 3 As among the 8 letters in each word, the Bs and Cs together represent 5 letters in each word. The table here shows the possible number of Bs and Cs to go with the 3 As.

number of As
number of Bs
number of Cs
total letters
arrangements
for each
3
5
0
8
8!/(3!*5!*0!)
3
4
1
8
8!/(3!*4!*1!)
3
3
2
8
8!/(3!*3!*2!)
3
2
3
8
8!/(3!*2!*3!)
3
1
4
8
8!/(3!*1!*4!)
3
0
5
8
8!/(3!*0!*5!)
.

The answer to our question is the sum of the values in the right column of the table.

12.

A certain state lottery requires participants to select 6 distinct numbers from the set {1,2,...,50}.
(a) How many ways can such a selection take place?
(b) Determine the probability that a participant has selected exactly k winning numbers, where k ranges from 0 to 6.

(a) Assuming that the selection 1-2-3-4-5-6 is the same as the selection 6-5-4-3-2-1, there are C(50,6) selections a participant can make. Note that C(50,6) is 15,890,700.
(b) Here is a table showing the desired probabilities. The critical calculation occurs in the middle column, where we multiple two combinations, that required to select k of the 6 correct digits and (6-k) of the incorrect digits. You can check your work by summing the values in the middle column.

k
ways to select k correct digits
probability of selecting k correct digits
6
C(6,6)*C(44,0) = 1*1 = 1
1/15,890,700 = 0.0000000629
5
C(6,5)*C(44,1) = 264
264 /15,890,700 = 0.0000166
4
C(6,4)*C(44,2) = 14,190
14,190/15,890,700 = 0.000893
3
C(6,3)*C(44,3) = 264,880
264,880 /15,890,700 = 0.0166689
2
C(6,2)*C(44,4) = 2,036,265
2,036,265 /15,890,700 = 0.128142
1
C(6,1)*C(44,5) = 6,516,048
6,516,048 /15,890,700 = 0.4100542
0
C(6,0)*C(44,6) = 7,059,052
7,059,052 /15,890,700 = 0.444225

13.

We know that m dogs and n cats are to be arranged in a row. How many ways can this be done so that the cats are separated from each other?

We assume that the dogs are distinguishable from one another as are the cats. Begin by arranging the m dogs. This can be done in P(m,m) = m! ways. Now imagine the (m + 1) spots among and outside the line-up of dogs. Permute the n cats within these (m + 1) spots. This can be done in P(m + 1, n) ways. Note that this result is positive only when (m + 1) is greater than or equal to n. If that condition does not hold, the cats cannot be separated from each other.

14.

Determine the number of 10-letter sets, with repetition allowed, from the set {X,Y,Z} that contain:
(a) at least one of each letter;
(b) at least two of each letter;
(c) at least one Z, two Ys, and three Xs;
(d) any number of each letter;
(e) at least one Y and at least two Xs.

(a) C(10 - 1,3 - 1) = C(9,2)
(b) C(4 + 3 - 1, 3 - 1) = C(6,2)
(c) C(6,2)
(d) C(10 + 3 - 1, 3 - 1) = C(12,2)
(e) C(7 + 3 - 1, 3 - 1) = C(9,2)

15.

Show that C(2n,n) is divisible by n+1.

Syllabus
Grades & Grading
Session Notes
Assignments and Problem Sets
Tests and Quizzes