4.3. GENERALIZED PERMUTATIONS AND COMBINATIONS 674.3. Generalized Permutations and Combinations4.3.1. Permutations with Repeated Elements. Assume thatwe have an alphabet with k letters and we want to write all possiblewords containing n1times the first letter of the alphabet, n2times thesecond letter,. . . , nktimes the kth letter. How many words can wewrite? We call this number P (n; n1, n2, . . . , nk), where n = n1+ n2+··· + nk.Example: With 3 a’s and 2 b’s we can write the following 5-letterwords: aaabb, aabab, abaab, baaab, aabba, ababa, baaba, abbaa, babaa,bbaaa.Wemay solve this problem in the following way, as illustrated withthe example above. Let us distinguish the different copies of a letterwith subscripts: a1a2a3b1b2. Next, generate each permutation of thisfive elements by choosing 1) the position of each kind of letter, then 2)thesubscripts to place on the 3 a’s, then 3) these subscripts to place onthe 2 b’s. Task 1)can be performed in P (5; 3, 2) ways, task 2) can beperformed in3! ways, task 3) can be performed in 2!. By the productrule we have 5! = P(5; 3, 2) × 3! × 2!, hence P (5; 3, 2) = 5!/3! 2!.In general the formula is:P (n; n1, n2, . . . , nk) =n!n1! n2! . . . nk!.4.3.2. Combinations with Repetition. Assume that we have aset A with n elements. Any selection of r objects from A, where eachobject can be selected more than once, is called a combination of nobjects takenr at a time with repetition. For instance, the combinationsof the letters a, b, c, d taken 3 at a time with repetition are: aaa, aab,aac, aad, abb, abc, abd, acc, acd, add, bbb, bbc, bbd, bcc, bcd, bdd, ccc, ccd,cdd, ddd. Two combinations with repetition are considered identicalif they have the same elements repeated the same number of times,regardless of their order.Note that the following are equivalent:1. The numberof combinations of n objects taken r at a time withrepetition.4.3. GENERALIZED PERMUTATIONS AND COMBINATIONS 682. The number of ways r identical objects can be distributed amongndistinct containers.3. The number of nonnegative integer solutions of the equation:x1+ x2+ ··· + xn= r .Example: Assume that we have 3 different (empty) milk containersand 7 quarts of milk that we can measure with a one quart measuringcup. In how many ways can we distribute the milk among the threecontainers? We solve the problem in the following way. Let x1, x2, x3bethe quarts of milk to put in containers number 1, 2 and 3 respectively.The number of possible distributionsof milk equals the number of nonnegative integer solutions for the equation x1+ x2+ x3= 7. Insteadof using numbers forwriting the solutions, we will use strokes, so forinstance we represent the solution x1= 2, x2= 1, x3= 4, or 2 + 1 + 4,likethis: ||+ |+ ||||. Now, each possible solution is an arrangement of 7strokesand 2 plus signs, so the number of arrangements is P (9; 7, 2) =9!/7! 2! =¡97¢.The general solution is:P (n + r − 1; r, n − 1) =(n + r −1)!r! (n − 1)!=µn +r − 1r¶.4.4. BINOMIAL COEFFICIENTS 694.4. Binomial Coefficients4.4.1. Binomial Theorem. The following identities can be easilychecked:(x + y)0= 1(x + y)1= x + y(x + y)2= x2+ 2 xy + y2(x + y)3= x3+ 3 x2y + 3 xy2+ y3They can be generalized by the following formula, called the BinomialTheorem:(x + y)n=nXk=0µnk¶xn−kyk=µn0¶xn+µn1¶xn−1y +µn2¶xn−2y2+ ···+µnn − 1¶xyn−1+µnn¶yn.We can find this formula bywriting(x + y)n= (x + y) × (x + y) ×(n factors)··· × (x + y) ,expanding, and grouping terms of the form xayb. Since there are nfactors of the form (x + y), we have a + b = n, hence the terms mustbe of the form xn−kyk. The coefficient of xn−kykwill be equal to thenumber of ways in which we can select the y from any k of the factors(and the x from the remaining n − k factors), which is C(n, k) =¡nk¢.The expression¡nk¢is often called binomial coefficient.Exercise: ProvenXk=0µnk¶= 2nandnXk=0(−1)kµnk¶= 0 .Hint: Applythe binomial theorem to (1 + 1)2and (1 − 1)2.4.4.2. Properties of Binomial Coefficients. The binomial co-efficients have the following properties:1.µnk¶=µnn − k¶4.4. BINOMIAL COEFFICIENTS 702.µn + 1k + 1¶=µnk¶+µnk + 1¶The first property follows easily fromµnk¶=n!k!(n − k)!.The second property can be proved by choosing a distinguishedelement a in a set A of n + 1 elements. The set A has¡n+1k+1¢subsetsof size k + 1. Those subsets can be partitioned into two classes: thatof the subsets containing a, and that of the subsets not containing a.The number of subsets containing a equals the number of subsets ofA − {a} of size k,i.e.,¡nk¢. The number of subsets not containing a isthe number of subsets of A − {a} of size k + 1, i.e.,¡nk+1¢. Using thesum principle we find that in fact¡n+1k+1¢=¡nk¢+¡nk+1¢.4.4.3. Pascal’s Triangle. The properties shown in the previoussection allow us to compute binomial coefficients in a simple way. Lookat the following triangular arrangement of binomialcoefficients:¡00¢¡10¢ ¡11¢¡20¢ ¡21¢ ¡22¢¡30¢ ¡31¢ ¡32¢ ¡33¢¡40¢ ¡41¢ ¡42¢ ¡43¢ ¡44¢We notice that each binomial coefficient on this arrangement mustbe the sum of the two closest binomial coefficients on the line above it.This together with¡n0¢=¡nn¢= 1, allows us to compute very quicklythe values of the binomial coefficients on the arrangement:11 11 2 113 3 11 4 6 4 1This arrangementof binomial coefficients is called Pascal’s Trian-gle.11Although it was already known by the Chinese in the XIV century.4.5. THE PIGEONHOLE PRINCIPLE 714.5. The Pigeonhole Principle4.5.1. The Pigeonhole Principle. The pigeonhole principle isused for proving that a certain situation must actually occur. It saysthe following: If n pigeonholes are occupied by m pigeons and m > n,then at least one pigeonhole is occupied by more than one pigeon.1Example: In any given set of 13 people at least two of them havetheir birthday during the same month.Example: Let S be a set of eleven 2-digit numbers. Prove thatS must have two elements whose digits have the same difference (forinstance in S = {10, 14, 19, 22, 26, 28, 49, 53, 70, 90, 93}, the digits ofthe numbers 28 and 93have the same difference: 8 − 2 = 6, 9 − 3 =6.) Answer: The digits ofa two-digit number can have 10 possibledifferences (from 0 to 9). So, ina list of 11 numbers there must be twowith the same difference.Example:Assume that we choose three different digits from 1 to9 and write all permutations ofthose digits. Prove that among