Math. 55 Three Problems about Combinatorial Coefficients April 26, 1999 6:57 am Prof. W. Kahan Page 1 The combinatorial coefficient n C k := n ! /(k ! (n–k) ! ) = n C n–k . It can be generated in Pascal’s triangle by setting 0 C 0 = 1 C 0 = 1 C 1 = 1 and then obtaining n+1 C k = n C k + n C k–1 recursively: k = 0 1 2 3 4 5 6 7 … n=0: 1 1: 1 1 n C k-1 + n C k 2: 1 2 1 = n+1 C k 3: 1 3 3 1 4: 1 4 6 4 1 Pascal’s Triangle 5: 1 5 10 10 5 1 6: 1 6 15 20 15 6 1 7: 1 7 21 35 35 21 7 1 The following three problems are HARD; they are not for everybody. 1 : Prove that if n > k > 0 and GCD(n, k) = 1 , then n C k is divisible by n . ( H.W. Lenstra )1st Proof: Let m := n–k > 0 . Since 1 = GCD(n, k) = GCD(m+k, k) , so is GCD(m, k) = 1 ; this means that integers i and j ( not both positive ) must exist satisfying j·m + i·k = 1 . Then n C k = 1· m+k C k = (j·m + i·k)· m+k C k = j·m· m+k C m + i·k· m+k C k = j·(m+k)· m+k–1 C m–1 + i·(m+k)· m+k–1 C k–1 = n·(j· n–1 C m–1 + i· n–1 C k–1 ) is evidently divisible by n .This is H.W. Lenstra’s proof.2nd Proof: n C k is the number of n-bit strings with k bits set to 1 and n–k bits 0 . Put these strings into boxes (“equivalence classes”) as follows: Into each box put just those strings each obtainable from any other in the box by fewer than n one-bit circular shifts. For example, if n = 5 and k = 3 one box will hold the strings 1o1o1 , o1o11 , 1o11o , o11o1 and 11o1o . In general each box must hold n strings because no two circularly shifted versions of the same string can match; otherwise the number of one-bit circular shifts required to turn this string into a copy of itself would have to divide both n and k , and this is ruled out by GCD(n, k) = 1 . Therefore the number n C k of strings is the product of n by the number of boxes. This is Charles Holton’s proof.3rd Proof: n C k = n· n–1 C k / (n–k) is an integer. GCD(n, n–k) = GCD(n, k) = 1 , so n–1 C k / (n–k) must be an integer too, so n must divide n C k . This proof makes Problem 1 look too easy. This document was created with FrameMaker404Math. 55 Three Problems about Combinatorial Coefficients April 26, 1999 6:57 am Prof. W. Kahan Page 2 4th Proof: To show that n C k / n = (n–1)·(n–2)·(…)·(n–k+1) / k ! is an integer we must show for every prime p and integer exponent K > 0 that whenever p K divides the denominator k ! it divides the numerator too. The exponent K of this prime p in the prime factorization of denominator k ! isK :=  k / p  +  k / p 2  +  k / p 3  + … +  k / p K  +  k /pK+1 + … because each term k/pm in the series is the number of integers among {1, 2, 3, …, k} that is divisible by pm . ( This series contains only finitely many positive terms beyond the last of which all terms vanish.) The numerator (n–1)·(n–2)·(…)·(n–k+1) is a product of k–1 consecutive integer factors among which the number divisible by pm is at least (k–1)/pm because the first and last factors can both be divisible by pm ; therefore the exponent of p in the numerator’s prime factorization is at least L := (k–1)/p + (k–1)/p2 + (k–1)/p3 + … (k–1)/pL + (k–1)/pL+1 + … .Now we must consider two cases according as prime p divides k or doesn’t:• If p does not divide k then every (k–1)/pm = k/pm and therefore L = K , which implies that the largest pK that divides the denominator k! divides the numerator too, as claimed.• If p divides k then p cannot divide n since GCD(n, k) = 1 . Now the largest pK that divides the denominator k! divides the numerator (n–1)·(n–2)·(…)·(n–k+1) too because nCk = n·((n–1)·(n–2)·(…)·(n–k+1))/k! is an integer.Therefore nCk/n = (n–1)·(n–2)·(…)·(n–k+1)/k! is an integer as claimed. End of proof.2 : For k = 1, 2, 3, 4, … prove that 2k–1Ck is an odd integer just when k = 2K is a power of 2 .Proof: The simplest proof is a pictorial proof, due to Prof. Raimund Seidel, based upon Pascal’s recurrence n+1Ck = nCk + nCk–1 in arithmetic mod 2 , which means 0+0 = 1+1 = 0 and 1+0 = 0+1 = 1 . The picture is shown on the next page. In this picture the odd values of nCk are plotted as 1’s ( or I’s when n = 2K+1 – 1 and k = 2K – 1 or 2K ) and the even values as • ’s ( or o ’s when k = n/2 or (n±1)/2 ). The idea behind the picture is that it is composed recursively of triangles within triangles within triangles … . If ∆ is a triangle whose sides and bottom row are made up entirely of 1 ’s , and if its top vertex corresponds to n = k = 0 while its bottom corresponds to n = 2K – 1 , then three such triangles can be assembled into the next larger triangle of twice the height thus: ∆ ∆∆Between the lower two triangles all plotted values are even. So ends the proof-by-picture.An algebraic proof will be presented after the picture; and a third proof will come about because this problem 2 is a special case of the next problem 3.Math. 55 Three Problems about Combinatorial Coefficients April 26, 1999 6:57 amProf. W. Kahan Page 3 k = 0 1 2 3 4 5 6 7 8 9 ... n=0: 1 1: I I nCk-1 + nCk 2: 1 o 1 = n+1Ck mod 2 3: 1 I I 1 <——— 4: 1 • o • 1 5: 1 1 o o 1 1 o = • = 0 I = 1 6: 1 • 1 o 1 • 1 7: 1 1 1 I I 1 1 1