Problem 10
How many cards, from a regular deck, do we need to pick up in order to guarantee that at least 3 of them are of the same suit?
Problem 11
Assume that in a group of six people, each pair of two people consists either of 2 friends or 2 enemies. Show that there are either 3 mutual friends or 3 mutual enemies in the group.
Permutations and Combinations
Problem 12
From a class of 20 students, how many ways are there to form a committee of 3 students with named positions (President, VP, Secretary)?
Permutations
Definition
An k-permutation of a set with n elements is an ordered arrangement of k elements from that set. The number of such k-permutations is denoted P(n,k), or sometimes nPk. An n-permutation is simply called a permutation.
Problem 13
How many permutations of the set S = {1, 2, 3, 4, 5} are there?
Problem 14
From a class of 20 students, how many ways are there to form a committee of 3 students without named positions?
Combinations Definition
An k-combination of a set with n elements is k-elements subset from that set. The number of such k-combinations is denoted C(n,k), or sometimes nCk or �kn� (also
called binomial coefficient).
Problem 15
A chocolate box contains chocolates in 7 flavours: black, white, cherry, milk, nuts, orange and truffles. Assuming that there are at least 4 of each, in how many different ways can we pick 4 chocolates? (The order does not count…)
Problem16 �n� � n � Prove the following combinatorial identity: k = n − k .
Problem17 �n+1� � n � �n� Give combinatorial proof of Pascal’s Identity: k = k − 1 + k .
Pascal’s Triangle
�n+1� � n � �n� k =k−1+k
� �
�n� = �n� = 1 0 n
�20� �21� �2� �3� �3� �3� �3�
0 �10��1�
�4�0 �4�1 �4�2 �4�3 �4�
�5�0 �5�1 �5�2 �5�3 �5�4 �5�
�6�0 �6�1 �6�2 �6�3 �6�4 �6�5 �6�
�7�0 �7�1 �7�2 �7�3 �7�4 �7�5 �7�6 �7�
�8�0 �8�1 �8�2 �8�3 �8�4 �8�5 �8�6 �8�7 �8� �9�0 �9�1 �9�2 �9�3 �9�4 �9�5 �9�6 �9�7 �9�8 �9�
�10�0 �10�1 �10�2 �10�3 �10�4 �10�5 �10�6 �10�7 �10�8 �10�9 �10� 0 1 2 3 4 5 6 7 8 9 10
Binomial Theorem
(x+y)2 = (x + y)3 = (x + y)4 =
.
(x + y)n =
= �n0�xny0 +�n1�xn−1y +�n2�xn−2y2 +…+�n�x0yn
x2+2xy+y2
x3 +3x2y +3xy2 +y3
x4 +4x3y +6x2y2 +4xy3 +y4
�n �kn�xn−kyk
k=0
Problem 18
What is the coefficient of x12y13 in the expression of (2x + y)25?