Solution Manual for Combinatorial Mathematics 1st Edition by Douglas B. West by welldoneassistant

Chapter 1: Combinatorial Arguments

1. COMBINATORIAL ARGUMENTS ©Douglas B. West

1.1. CLASSICAL MODELS 1.1.1. When rolling n dice, the probability that the sum is even is 1/2. No matter what is rolled on thefirst n — 1 dice, the last die has three even values and three odd values, so in each case the probability of ending with an even total is 1/2.

1.1.2. There are (’})(5) rectangles with positive area formed by segments in a grid of m horizontallines and n vertical lines. Positive area requires two distinct horizontal boundaries and two distinct vertical boundaries. 1.1.3. There are (""°)2175s words consisting of r consonants and s vowels.

There are ("**) ways to allocate the positions to consonants and vowels and then 21”5* waystofill those positions. 1.1.4. There are (2 ) outcomesof an election with 30 voters and four candidates, (°° ) — 4(7,') with no candidate having more than half of the votes. If

the votes are considered distinct, then there are 4°° outcomes. However, votes go into a ballot box, so an outcomeis determined just by the number of votes for each candidate. Thus we want the numberof nonnegative

integer solutions to x1 + x2 + x3 + x4 = 30, whichis (°"7*"). Whenone candidate receives at least 16 votes, the outcomes are the ways to distribute the remaining 14 votes arbitrarily, since votes areindistinguishable. Only one candidate can have a majority, but that can be any one of the four, so there are 4(7,') outcomes we exclude. 1.1.5. For n €N, the expression (n° — 5n? + 4n)/120 is a integer. Since

n®—5n?+4n = n(n?—1)(n? —4) = (n+2)(n+1)n(n—-1)(n—2), the expression equals ("!*), which is the numberof wasto choosefive objects from a set of size n + 2. This by definition is an integer. 1.1.6. 13!40! orderings of a deck of cards such that the spade suit appears consecutively. There are 13! ways to order the spade suit and 39! ways to

Section 1.1: Classical Models

order the remaining cards. There are then 40 waysto insert the ordered spade suit among the other cards. Alternatively, condense the spadesuit to a single item, order the items in 40! ways, and the expand the spade into 13! orderings of the spadesuit. 1.1.7. The probability of having at least three cards with the same rank in a set of five ordinary cardsis aw: Amongfive cards, only one rank can appearat least three times; pick it in 13 ways. Whenall four cards of this rank appear, there are 48 ways to pick the remaining card. When only three appear, there are four waysto pick the missing suit of this rank and (4 ) waysto pick the other two cards. Hence there are 13-48-(1+4-47/2) suitable sets of five cards. The desired probability is the ratio of this to

(°*). Canceling factors in 434895120 yields the claimed probability. 1.1.8. From a standard 52-card deck, There are 13+ - 304 sets of six cards having at least one card in every suit. We may have three cardsin one suit and one in each otherin 4: (3138 ways. We mayhave two cards in each

of two suits and one card in the other twoin (2)(23)°182 ways. These are the only choices; we sum them. 1.1.9. There are 10:9-8-142 integers from 0 to 99 , 999 in which each digit appears at most twice (counting leading Os as appearances. Consider cases by how manydifferent digits are used. There are 10,5) integers usingfive digits. There are 10( >) 93) integers using four digits; first pick and place the repeated digit. When three digits are used, two are used twice; hence the numberof integers of this type is 10:5-9- (5) -8. Summing the three cases yields the answer. 1.1.10. There are 11 ( ) (*) distinguishable ways to orderthe letters of “Mississippi’. Choosing positions for the types of letters in stages, always the number of ways to do the next stage does not depend on how the previous stages were done. We place “M”in 11 ways, then choosefour positionsfor “i” among the remaining 10 in ( ) ways, then choose four positions for 6 s” among the remaining6 in (7) ways, the put ae) “p” in the remaining two

“9

positions. The rule of product then yields the answer. 1.1.11. From four colors of marbles, there are (3) distinguishable ways to have 12 marbles. There are 4!” ways to have 12 of the marbles in a row. For distinguishable selections with repetition, we use the multiset formula: (en *). The numberof ways to arrange a multiset depends on the number of elements of each type. However, when weput the elements in a row we are just making words: each position may have one of the four types, and all such wordsare distinguishable.

Chapter 1: Combinatorial Arguments

1.1.12. If each New York City resident has a jar of 100 coins chosen from five types, then some two residents have equivalent jars. The numberof distinguishable jars of coins is the numberof multisets of size 100 from

five types. Using the formula ary for selections of k elements from n types, the value is on , which equals 4,598,126. Without being precise, cancelling factors yields 13-103-34-101, whichis clearly less than 5-10°. Since New York City has more than 7- 10° residents, the claim follows.

1.1.13. When k is even, there are 2*/2-! compositions of k with every part even (there are none when k is odd). Halving each part yields a composition of k/2, and the mapis reversible. There are 2”! compositionsofn. 1.1.14. Families of subsets. a) There are 2” — 2!"/2! subsets of [n] that contain at least one odd number. There are 2” subsetsof [n]. Among these, 2!”/2! subsets are restricted to the set of even numbers. The remainder have at least one odd number.

b) There are (”{*') k-elementsubsets of [n] that have no two consecutive integers.

Proof 1. When choosing k elements, the remaining n — k mustdistribute among them to have at least one between each successive pair of chosen elements. Knowing how manygo in each slot determines the k elements selected. Hence the legal choices correspond to solutions to Xo $xXy +--+: +x, = n—k such that x,,...,x4_1 are positive and xo, xz are nonnegative. Subtracting 1 from the variables required to be positive transforms these into nonnegative integer solutions of yo +:::+y,% = n—2k+1. By the selections with repetition model, the numberof solu-

tionsis ("7At1***1"1) which simplifies to (”"{*"). Proof 2. View the n—k unchosenintegers as dots in arow. We choose

places for the selected integers between the dots (and on the ends), but avoidance of consecutive integers requires that no spaceis selected twice. We have n—k+1 allowable places and choose k of them for bars. The bars now mark thepositions of k selected numbers. c) There are n! choices of subsets Ag, A, ...An of [n] such that Ap C A; C-:-C A,. There are (n + 2)” choices such that Ap GC Ay C--: C Ap. Whenthesets have distinct sizes, we have |A;| = 7, since all the sizes are between 0 and n. Hence Ag = @, and the elementsof [n] are added one by one in some order. The n! possible orders correspond to the chains. To determinea chain of the second type, it suffices to specify for each x € [n] the index i such that x first appears in the chain at A;. Not appearing at all is also an option. Hence there are n + 2 choices available for each x, and the choice made for x is not restricted by the choices made for other elements.

Section 1.1: Classical Models

1.1.15. The exponent on a primep in the prime factorization of (*”) is the

number of powers p* of p such that | 2n/p*| is odd. We use the formula

‘ai Gry In m!, | m/p| factors are divisible by p. In | m/p?| of these, we have an extra factor of p. In | m/p° | , we have yet anotherfactorof p, and so on. Hence the highest powerof p that divides m! is }),., | m/p* | ,

When | 2n/p* | is even, the numberof multiples of p* in [2n] is twice the numberin [n]; for example | 10/2| = 4, and | 5/2 | = 2. When | 2n/p*| is odd, we get one extra: | 6/2| = 8, but | 3/2| = 1. The latter case occurs

if and only if the remainderof n upon division by p* is at least p*/2. Sincethe factorsof p in the factorization of n! are used (twice) to can-

cel factors of p in the factorization of (2n)!, we thus find that (2n)! keeps an extra factor of p for each k where | 2n/p* | is odd.

Prime factorsof (‘5) and ({}). A prime p will be a factorif | 2n/p*| is odd for some k. We have | 18/2| = 9 and | 20/4| = 5, so 2 divides both.

Since | 18/3| = | 20/3] = 6 and | 18/9| = | 20/9| = 2, 3 divides neither. For higher primes, the squares are too big to give a nonzero contri-

bution. We have | 18/5| = 3 but | 20/5| = 4, so 5 divides () but not (79).

Since | 18/7| = | 20/7| = 2, 7 divides neither. However, 11, 13, and 17 yield 1 in each case, as does 19 in the latter case. Hence the primedivisors

of (j) are {2,5,11, 13,17}, and thoseof(7) are {2,11,13,17, 19}.

1.1.16. Given v(a, b) = ((,7,)- (3). (451)), there do not exist distinct pairs

(a, b) and (c, d) ofpositive integers such that v(c, d) is a multiple of v(a, b). Suppose u(c, d) = xv(a, b). We have (5) = x(%), and then

d c\_( ¢ \_,f @ )L, b a\ | b c c-d+1\d}) \d-1) “\b-1) “~“a-b+1\b) a-b+i1\d c—df(c\ [

_,(

_ 2-6 a\ a-b[c

d+1\d) \d+1) “\b+1) “b+1\b) b+1\d Thus (a -—b+1)d = (c—d+1)b and (6+ 1)(c —d) = (d + 1)(a— b). The difference of these two equations yields d—a+b = b—c+d, and hence a =

c. Now,since (,°,) = #2(¢) and (,°,) = $4(5), and the ratiosof($) to (5) and (71) to (464) are the same, we have a” = a | Thus (d + 1)(a — b) = (6+ 1)(e—d) =(b+1)(a—d). We obtain (a + 1)(d — b) = 0, so alsod = b. 1.1.17. There are (%;)(";") lists of m 1s and n 0s having k runsof1s. Proof1 (case analysis). The numberof runs of 0s may be k — 1 (start and end with 1s), k + 1 (start and end with Os), or k (two cases, starting with Os or with 1s). In each of these four cases, forming compositions of m and n with the right numberof parts completely specifies thelist.

Chapter 1: Combinatorial Arguments

For the 1s, we have (1) compositions of m with k parts. For the 0s, the factor is (7-3) or ("2") or (775), the last in two cases. Summing these

and applying Pascal’s Formula three timesyields (7; )("z"). Proof 2 (direct arguments). After forming a composition with k parts in (71) ways for the 1s, these k nonempty runs are put inton+1 possible locations among the Os (or at the ends). Runsof 1s go into dis-

tinct locations amongthe 0s, so there are (";) ways to place them. [One can also place the 0s, with repetition allowed, among the runsof Is, ensuring that the k — 1 interior locations are nonempty. The numberof ways is then the numberof multisets of size n —k+1 from k + types. | 1.1.18. Runs in subsets. n+1

a) The numberof subsets of [n] with k runs is ( Ok ). The runs ina subset correspondto runsof 1s in the incidence vector, separated by runs of Os. We can specify the runs by inserting a bar before and after each run, separating it from the neighboring positions. Since thereis at least one 0 between two runsof 1s in the incidence vector, the bars are placed in distinct positions. The allowable positions are between entries of the incidencevector, plus at the beginning or end. To specify k runs, we pick

2k of these n + 1 positions, so the answeris ("3,'). Comment: Thereis also an analysis that considers cases depending on whetherthefirst and/or last element is used or not. The cases yield

binomialcoefficients that combine to ("3,') by Pascal’s Formula. b) The numberof t-element subsets of [n] with k runsis( Maen | Garena» Determining the length of each run and the distances between runsdetermines the subset. Again consider the 2k bars specifying the runs; this time we must distribute ¢t positions within the runs and n — t outside them. By adding positions 0 and n+ 1 as extra positions before the first run andafter the last, we guarantee k+1 nonemptybins outside the runs and have two composition problems. We need a composition of t with k parts to specify the lengths of the runs and a composition of n + 2 —t

with k + 1 parts to specify the locations of the runs. Thereare (;_;) of the former and ( n+2-t-1 k+1-1 ) of the latter, and we choose them independently. c) The numberof t-element subsets of [n] having exactly r; runs oflength

s; for 1 <i<m,wherek =o", ri, and t =)", risi, is meap): Now we are given the lengths of the runs of 1s. To form the incidence vector, we permute them and position them. There are again k runs with total length t, so the factor (rr) for separating the runs of 1s remains. The runs can come in any order. However, all r;! ways of ordering the r; runs

of length i produce the same subsetof [n] (we assume that s;,..., Sm are distinct). Thus there are k!/[];", ri! ways to order the runsof1s.

Section 1.1: Classical Models

1.1.19. The numberof binary strings of length n in which the number of copies of 00 is the same as the numberof copies of 11 is 2 when n = 1 and

is 2( p71) when n > 1. For n= 1, both strings are counted. Consider n > 1. Let a and b be the numberof Os and numberof |1s, respectively. If there are i runs of 0 and j runs of 1, then there are a —i copies of 00 and 6 — j copies of 11. If the first and last bits differ, then i = 7, and the desired condition holds if and only if a = b, which requires n even. If the first and last bits are 0, then i = 7 +1, and we need a = 6+ 1, which requires n odd. Similarly, we need a+ 1 = b and n odd whenthefirst and last bits are 1. The needed property of the first and last bits holds in two ways. Af-

ter ensuring this, the needed condition on a and is satisfied in (22/2) strings when n is even and in ( (n-152) when n is odd. Thus the answeris n-

2( n)2]) in both cases. The formula is not valid when n = 1 because the first and last bits are the same.

1.1.20. The numberofelements of |3]|" with k odd entries having no 1 next

toa3 is >x5 (ret) (1) 24. Let j be the numberof runsof odd entries. Each runis all-1 or all-3, independently, since any two successive runs of odd entries are separated by at least one 2. With k odd entries in j runs, the run lengths of odd entries form a composition of k with j parts. Hence there are (“772 ways to form the sublist of odd entries. Altogether there are n—k copies of 2. These are distributed into j7+1 buckets, andall but thefirst and last must be nonempty(the list may or may not start or end with a 2). Hence there are (7) waysto distribute the copiesof 2. Summingover the possibilities for 7 completes the proof.

1.1.21. Inside a convex n-gon, (1) pairs of chords cross. Proof 1 (brute force). Let a, be the answer. Let v;,...,0Un be the vertices in order. The vertices v,,...,U,_1 forma convex (n — 1)-gon, and within it a,_; pairs of chords cross. To this we add the crossings involving chords at v,. The chord from v, to vg crosses (k — 1)(n — k — 1) other

chords, so a, = Qn-1 + ok —1)(n-—k- 1). With a3 = 0, we have an=>4 ar (k —1)(r7 —-k—1). Proof by induction after guessing the answerfrom data, or application of identities from Section 1.2, may lead you to the answer (").

Proof 2 (combinatorial understanding). Each crossing involves two chords. Those two chords involve four endpoints. Thus every crossingcorrespondsto four points on the n-gon. Furthermore, each set of four points on the n-gonis the set of endpoints for exactly one pair of crossing chords.

Hence the numberofcrossingpairsis(7).

Chapter 1: Combinatorial Arguments

1.1.22. If no three chords have a common internal point in the picture formed by drawingall (5) chords of a convex n-gon, then the numberoftri-

angles is (3) + 4(7) + 5(Z) + (%). We count the triangles according to how many corners lie on the boundary of the n-gon. A triangle with three boundary cornersis determined by choosing three vertices of the n-gon. A triangle with two boundary cornershas a full chord as oneside, and the other two sides extend to form full chords. The endpoints of these three chords are four points on the boundary. Hence such triangleis associated with four vertices of the n-gon, chosen in (7) ways. On the other hand, each choice of four vertices yields four such triangles. A triangle with one boundary corner is determined by two chords from that point and one chord that crosses both of them. This leads to five vertices on the boundary. Each choice of five vertices determinesfive triangles in this way, so the numberof triangles of this type is 5(Z). A triangle with no boundary cornersis determined by three chords with nocommon endpoints, obtained by extending the sides. Thussix vertices must be chosen from the boundary to draw the chords. Each choice of six yields exactly one such triangle, with opposite pairs formingpairwise crossing chords.

Dee ye

Comment: Other ways to group and count the triangles produce more complicated formulas, which can be simplified to that above via identities. Having obtained a simple formula, one seeks a simple proof.... 1.1.23. Rolling dice. Six dice each have three red faces, two green faces, and one blue face. The probability that three red faces, two green faces, and one blue face will show whenall six are rolled is 5/36. The six dice are objects; each shows some face. The numberofar-

rangements of RRRGGBis ($)(;), which equals 60. Each has probability (3)3(2)?(4)' of occurring. Hencethe desired probability is 60-(27-4-1)/6°. 1.1.24. In poker, a straight is more likely than a flush. The numberofsets

of five cards from onesuit is 4(’?). For the numberofsetsoffive cards with consecutive values, the lowest value can be any numberfrom 1 to 10

(an ace can be considered high or low). Hence there are 10 - 4° such sets. After canceling commonfactors, the ratio of the numberof straights to

numberofflushes simplifies to #2#?%, which is about 1.989. 1.1.25. The numberof trapezoids defined by vertices of a regular n-gon is

n(\"")?)if n is odd and (n — 8)("4”) if n is even. It suffices to count the

Section 1.1: Classical Models

pairs of parallel chords. Chords are parallel to a side or (when n is even) perpendicular to a diametric chord. Whenn is odd, the numberof chords parallel to a given sideis (n — 1)/2. Picking a side and picking two such chordsyields the answer. The resulting trapezoids are distinct, because none are parallelogramssince any two parallel chords have different lengths. When is even, the same analysis gives 2 (7/2) pairs of chords parallel to sides. For any diametric chord, there are (n — 2)/2 chords perpendicular to it, yielding nm ((n~2)/*) pairs of such chords. Every parallelogram has been counted twice. Each parallelogram is determined by having

two specified corners amongthefirst n/2 vertices, so there are (",”) par-

alleograms. Thus the numberoftrapezoids is 3(")") + 2(51) — ("?), which equals (n — 3)(”,”). 1.1.26. The largest displacement d(x) of a permutation of |n] is | n?/2|,

where d(x) = >-"_, |i—(i)|. Define z’ from x by switching the elements in positions i andi+1. If these elements are both at most i or both at

least i+ 1, then d(x’) = d(z). In the remaining case, one elementis at most i and the otheris at least i+ 1. Now the displacementis greater (by 2) in the permutation in which the largerof the entries in positions i and i+ 1 is in position 7. We conclude that if any two adjacent entries are in increasing order, then transposing them does not decrease the displacement. Hence the displacement is maximized by a permutation in which no two consecutive elements are in increasing order. The only such permutation is the reverse of the identity permutation. The displacement of this permuta-

tion is ye 2(n — i), which equals| n?/2]. 1.1.27. Bijection from the set A ofpermutations of |n] to the set B of n-tuples (b;,...,6,) such that 1 < b; <i foreach i. EFacha = aj,...,a,€ Aisa list of numbers. For each i, let 6; be the position of i in the sublist of a

formed by the elements of [i]. Let f(a) be the resulting list b,,..., bn. By construction, 1 < b; <i, so f(a) € B. To prove that f is a bijection, we describe a function g: B — A. We build g(b) from an emptylist by inserting numbers in the orderl,...,n. Before inserting i, the list consists of {1,...,i—1}. We insert i to have

position b;. After processing b, we have a permutation of [n]. To prove that f and g are bijections, it suffices to show that they are

injective (in fact g = f~'), since A and B are finite and have the same size. First consider f. Given distinct permutations in A, there is some least value 7 such that the subpermutations using elements1,..., 7 are different. Since they are the sameearlier but differ at the jth step, the

Chapter 1: Combinatorial Arguments

correspondingvaluesof b; are different.

For g, if two elementsof B differ first at the jth index (b; # b’), then the subpermutations of 1,..., 7 inthe two image permutationsdiffer. This bijection can also be described inductively. 1.1.28. The number of exchanges of elements in a permutation needed to break all original adjacencies is | (n — 1)/4], for n => 6. Numberto elements from 1 to n in order. Since two elements are moved, at most four original adjacencies can be broken by each exchange. There are n — 1 original adjacencies; this proves the lower bound.

To achieve the bound, exchange 2i with 2|(n — 1)/4| + 2, for1 <i< r, where r = | (n - 1)/4|. When 4 | (n — 1), the first 27 even numbers are moved, while all odd numbers remain fixed, and all adjacencies are broken. When 4 ¢{ (n — 1), element 27 + 2 has been skipped and remains adjacent to 2r — 1 and 2r +1. For the last switch, exchange 2r + 2 with n when 4 | n, and exchange 2r + 2 with 1 when 4 divides n — 2 or n— 3. 1.1.29. There are (n!)?” 0, 1-matrices with n? rows and n? columns such that (1) each row and column hasexactly one 1, and (2) when the matrix is partitioned into n? blocks of n consecutive rows and n consecutive columns, each block contains exactly one 1. Choose the position of the 1 in each n-by-n tile successively, going across a row oftiles from left to right, processing rows in order from top

to bottom. There are (n —i+ 1)(n — j + 1) choices available when dealing with the jth tile in the ith row, due to the i—1 tiles above it and the j —-1 tiles to its left. In the ith row, the product of the numbers of choices is

(n —it+1)"n!, so over all rows we obtain (m!)"(n!)”. More generally, when a square of size mn is divided into mn rectangular tiles of width m and height n (globally, m rowsof n tiles), the same argument shows that the number of permutation matrics of order mn having exactly one 1 in eachtile is (m!)”(n!)”.

1.1.30. There are 2”! permutations x of [n] such that x(i+1) < x(i)+1 for 1 <i<n-—1. We view permutations as words. Call such a permutation good. Listing thepossibilities for small n suggests the answer 2”.

Proof 1 (induction on n). There is one good permutation of [1]. For n > 1, note that the constraint on the value following value n always holds. Hence if z(1) = n, then we can ignore n, and the remaining constraints are precisely those for a permutation of [n — 1]. Hence there are 2”-2 good permutations starting with n. If not at the beginning, then n must immediately follow element n — 1; following any other would violate a constraint. Deleting n yields a good permutation of |n—1], since the element now following n—1 (if any) is less

Section 1.1: Classical Models

than n— 1. On the other hand, n can be inserted immediately following

n—1 in any good permutation of |n—1] to form such a good permutation of [n]. Both of these maps are injective, so the numberof good permutations

of [n] in which n is not at the beginning is 2”~?. Combining thecases yields 2”"!. Proof 2 (combinatorial argument). We map good permutations into

subsets of [n — 1]. Given a good permutation 7, let f(z) = {i: z(i) > x(it+ 1)}. To show that f is a bijection, we show that for each S C [n—1], there

is a unique permutation z of [n] such that f(z) = S. In a good permutation, the runs of increasing steps are consecutive numbers. Furthermore, the element after the end of a run must be smaller than the element starting it. Thus the elements of each run are smaller than the elements of each preceding run. Hence knowing the boundaries of the runs determines the permutation. For example, if the first run has k elements, then the permutation must start n—-k+1,n—k+2,...,n,and the next element will be just small enough to allow the next run to end at n— k. Thus the set S of locations of descents determines exactly one good permutation. This is indeed the permutation z such that f(z) = S. 1.1.31. If the set of elements in even-indexed positions of a graceful permutation of [2n] is |n], then the first and last elements differ by n, where a permutation is graceful if the absolute differences between successive elementsare distinct. Call1,...,n “small” andn+1,...,2n “large”. For a gracefulpermutation, the differences between neighboring elements sum to (2),

which equals 2n? — n. When the small numbersoccupy the even positions, each absolute difference is a large number minus a small number. Each number appears in two differences, except that the first number x and last numbery only appear once. Hence the differences sum to 2X —x—(2Y —y), where X and Y are the sumsof the large numbers and the small numbers, respectively.

Since X — Y = n?, we have 2n? — n = 2n? — (x — y); hence x — y =n. Comment: The converse also holds. Suppose that 6; = be, +n. In computing T = ye |b; — b;-1| as asum ofpositive differences, each 6; for

2 <i <2n-1 is weighted by 6; € {-2,0, +2}. We extend this to b; and bo, by adding (b; — be,) —n = 0. We further observe ye 0; = 0, so 2n

T = QO 6;b;) —-n = DD, d;(b; —n)|—n

(gi —n)-2) (s;—n)—n = 2G- 28 —n = 2n?—n=T. i=1

i=l

pia

Chapter 1: Combinatorial Arguments

Thus equality holds throughout. In particular, if 6; is small, then 0; = —2. It follows that none of the terms|b;,; — b;| has the form |s;,1 —s;]. Hence the terms alternate between small and large. Since bo, is small, the result follows. 1.1.32. Counting necklaces. a) (n—1)!/2 necklaces with n beads can be madefrom n distinct beads, for n > 3. Starting from a given point, there are n! ways to list the beads. Each necklace corresponds to 2n such listings, since we can start the list at any bead and go in either direction without changing the necklace. b) i + k crowns with n beads can be made from k types of beads when n is prime. Starting from a given point, there are k” waysto list beads forming a circular pattern. A circular pattern arises n times in this way unless some string repeats with period less than n. For example, 111111000 would yield a circular pattern that arises nine times, while 110110110 would yield a circular pattern that arises only three times. However, the length of the repeating string must divide n. Since n is prime, the only divisors are 1 and n. The & circular patterns made using only one bead arises only once amongthe k” lists. The otherlists all group into classes of size n; each giving one circular pattern. 1.1.33. [fa polynomial pin k variablesis 0 at all points in TI, S;, where |S;| = d; + 1 and p has degree d; in variable x;, for 1 < i < k, then pis identically 0. The base case k = 1 is the given hypothesis. Now consider k > 1. Fixing any choice (x1,..., xg-1) € I: S; defines a polynomial in the one variable x;,. By hypothesis, its value is 0 for x; € S;. By the case k = 1, its value is 0 everywhere. Now any value of x;, not necessarily in S;, defines a polynomial g in the variables x,,..., x,_-1 that is O when (x1, ...,Xp-1) € Ti, S;. By the induction hypothesis, this polynomial is 0 everywhere. Hence the original polynomial p is 0 everywhere.

1.1.34. Combinatorial proof of (x + yn) = ¥, ({)x@¥n—-~ When z is an integer, the falling factorial z(, counts the simple n-words from an alphabet Z of size z. When Z is the disjoint union of an x-set X and a y-set Y, the words can also be formedbyfirst choosing positions among the n positions in which to use letters from X. When there are k such positions, there are x(,) waysto fill them with a simple k-word from X, and each can be paired with any simple (n — k)-word from Y to form a simple n-word from Z. Summing over k counts each simple n-word from Z exactly once. The Polynomial Principle extends to any numberof variables, by in-

duction on the numberofvariables (keep all but one variable fixed). Thus equality of two polynomials (in two variables) at all positive integer arguments implies equality as polynomials (and at all real arguments).

Section 1.1: Classical Models

1.1.35. Flags on poles. a) There are r™ways to put m distinct flags on r flagpoles in a row. Proof 1. Place flag 1, then flag 2, etc. Each placement of a flag effectively splits its location into two locations, since later flags may go above or below it. With the numberof choices iteratively rising, there

are r(r + 1)---(r +m-—1) ways to complete the full process. Proof 2. We obtain a permutation ofthe flags by listing in order the flags from thefirst pole, then the second, and so on. Each permutation can be associated with any nonnegative integer solution to x; +:::+x, = m to specify how manyflags go on each pole; the resulting arrangements

are all distinct. Hence the answeris m!(”*’;*), simplifying to r™. The permutation and the distribution amounts for the poles can be chosen in either order, yielding the same computation.

b) The real numberidentity (x + y)" =, (Z)x”y"). When x and y are nonnegative integers, the left side counts the arrangementsofn flags onto x+y flagpoles. To count the sameset in pieces, let k be the numberof flags placed on thefirst x flagpoles. We can choose these flags in (9) ways and then place theseflags on thefirst x poles in x“ ways and the remain-

ing flags on the remaining poles in y~*) ways. Since each arrangement has some numberof flags on thefirst x poles, each arrangementis counted exactly once when we sum overk. Hence the identity holds for infinitely many choices of both x and y. By the Polynomial Principle, it holds for all real numbers x and y.

1.1.86. There are (n—1)!(2”—-1) ways to arrange n distinctflags on nonempty flagpoles in a rotating circle. Proof 1. Writing the flags in order from each flagpole yields a “cir-

cular permutation”, listing [n] in a circle. Since there are n possible starting points for writing down a circular permutation as a linear permutation, there are (n — 1)! circular permutations. Any position in the circular permutation can be the last flag on a pole; we obtain the arrangements on poles by choosing any subset of the n flags to be the last flags on their poles. Since we choose each position in the circular permutation at most once, the poles we use are all nonempty. The numberof poles is the numberof positions chosen. Thereis no constraint on the numberof positions chosen, except that we must choose at least one, because the flags must be placed. We have shown that the arrangements correspondto a circular permutation of [n] and a nonempty subset of the n flags; the product rule now completes the proof. Proof 2. One can also apply circularity after placing the poles. There are n! ways to writeall the flags in order. There are (777) waysto

Chapter 1: Combinatorial Arguments

choose breakpoints to put these onto r poles, including the last position. Since rotating the circle does not change the arrangement, each circular arrangement using r poles arises in r ways by this procedure. Summing over r to count them all and applying the Committee-Chair Identity and the Binomial Theorem yields n-1

yy) =(n-y°2("~ 1) =(n=°(") = (n— 1)!(2” — 1). r

r=1

1.1.37. When pis prime, ("*e*) = (*) is divisible by n, for all n. The quan-

tity ("*e*) is the number of multisets of size p from n types of elements.

Since (”) is the numberofp-subsetsof[n], the difference is the number of multisets in which some element is repeated. Group these multisets into groupsof size n as follows; two multisets A and B are in the same group if B can be obtained from A by adding a constant to each element andreducing the values modulo n. Because p is prime, iteratively adding 1 to each element cannot repeat the multiset until n steps have been taken (that is, the pattern of multiplicities has no shorter period), so all the groups havesize n. The reason for subtracting (*) is that this quantity is not divisible by n when p divides n. When p distinct elements are equally spaced modulo n, the grouping described above yields one group with only n/p sets. In that case ("*e*) differs from a multiple of n by n/p. 1.1.38. The probability that a spinner with equally likely outcomes 1,...,n sumsto n in three spins is eo) There are n® equally likely outcomes of the experiment. The numberof outcomes with sum n is the numberof compositions of n with three parts. The numberof these is (","). 1.1.39. Both sides of the identity below count the sameset of ternary lists.

Sl) (ae —

2s+1])\k

Both sides count the ternary (n + 1)-tuples having a 2 in exactly k positions such that the copies of 2 separate the copies of 1 into k+ 1 portions of odd length. On theleft, start with n+ 1 positions, and chose an odd number (at least 2k +1) to be nonzero. Chose k of the positions that are even-indexed relative to this sublist to receive 2. Between any two such positions, the number of copies of 1 is odd, and the number at the beginning or endis also odd.

Section 1.1: Classical Models

On the right, begin with any ternarylist of length n — k having ex-

actly k copies of 2. There are (”,”)2”-?* such lists; copies of 2 may be consecutive. Now insert one position immediately before each 2 and at the end. This position receives 1 or 0 as needed so that the numberof copies of 1 in that portion between copies of 2 is odd. This choice is unique, so we obtain exactly one of the desired lists for each of the ("* )ar-2k original lists of length n — k. 1.1.40. Compositions of integers. a) There are ( ) solutions in positive integers to ~".i=1 x; <k. There are

("—;) solutions in positive integers to )”_, x; = r; summing over r with 0<r<kand applying the Summation Identity yields the answer (*). Directly, the solutions are determined by choosing n spaces to mark the partial sums, from the k spaces following k dots in a row. The value x; correspondsto the distance from the (i — 1)th chosen space to the ith, where by convention the Oth chosen spaceis before thefirst dot. Anotherdirect proof puts the desired solutions in bijective correspondence with the solutions to ye x; = k+1, by adding a positive variable Xn+1 representing the slack in the inequality. These solutions correspond

to the compositions of k+1 withn+1 parts; the numberofthem is (+13). b) There are 2*-! compositions of k. There are (*75) compositions of k with n parts. Sum over n and apply the Binomial Theorem. Bijective proof: Group dots to build a composition. From a row of k indistinguishable dots, thefirst dot goes into the first part. Each subsequent dot can start a new part or enlarge the current part. Thus compositions are formed by making binary choices for k — 1 dots, and each

(k — 1)-tuple of choices arises from exactly one composition of k. c) For k > 1, there are equally many compositions of k with an even numberofparts and with an odd numberofparts. A compositionis determined by choosing a subset S of the spaces among k dots; the resulting

numberof parts is |S|+ 1. When k > 1, half the subsets of a set of size k —1 have each parity (toggle the presence of the last element). Comment: There are many natural bijections from A to B, where A and B are the sets of compositions of k having an even number and an odd numberof parts, respectively. Essentially, they pair up odd and even subsets of the spaces between dots. For example, consider the map that combines the last two parts if the last part is 1 and splits 1 off the last part to form a new last part if the original last part exceeds 1. d) For k > 2, the numberof compositions of k with an even number of even parts equals the number of compositions of k with an odd number of even parts. Let A and B be the sets of compositions of k with an even number of even parts and an odd numberof even parts, respectively. Define

Chapter 1: Combinatorial Arguments

f: A — Basfollows. For x € A, consider thefirst part, p. If p = 1, combine p with the second part. If p > 1, split off 1 from p to make a new first part. The 1 that appears or disappears does not affect the number of even parts. The other changed part changesby 1, so its parity changes. Hence the numberof even parts changes by 1, which changesits parity. Note that the first part in f(x) is 1 if and only if the first part in x is not 1. Continuing through the other parts shows that the first difference

between elements x and y of A causes a difference in f(x) and f(y). Hence f is injective. By the same argument, the function g: B — A defined in

the same wayis also injective. Hence |A| = |B]. 1.1.41. Compositions of integers. a) Over all compositions of k, the total number ofparts is (k + 1) Qk-2 The compositions correspond to the subsets of the k — 1 spaces in a row of k dots. Each j-element subset yields a composition with j + 1 parts. The first dot starts a part in each composition. Each remaining dot starts a part in half of the compositions. Since the number of compositionsis

2*-1 the total numberof parts is 2*-!+(k—1)2*-?. (The same answercan be obtained by computing yi (j+ 1)(5-1) using techniquesor identities from Section 1.2.) Proof 1 (summation).

k-1 Since there are ( 71) compositions with 7

parts, the total equals ean i( i): By summing the Committee-Chair Identity over the committee size, we obtain Yea j (7-1) = Yo ("77) +

ai U — 1(*}) = a1 + (k- 12"? = (kh + 12, Proof 2 (bijection). Alternatively, compositions correspond to subsets of the spaces amongk dots. b) Over all the compositions of k, there are (k — m + 3)2*-™parts equal to m, where 1 <m<k. Elementsof the set A; ,. being counted are expressible as the pairs (C, 7), where C is a composition of k and j isa marked copy of min C. Subtracting 1 from the markedcopy of m yields a pair (C’, 7’) in Ax_1,m-1. The mapis injective and surjective, so the sets have the samesize, as desired. This leaves the problem of counting A; 1. Proof 1 (direct argument using part (a)). Skipping any 1 in a composition of k leaves a composition of k — 1, and each composition of k — 1 with j parts arises in 7 + 1 ways by doing this. That is, each composition of k—1 with j parts yields 7 + 1 parts of size 1 among compositionsof k. The answeris thus 1 for each composition of k— 1 plus the answerof part

(a) for k — 1: 24-2 + k2*-8 = (k + 2)2*-3. Theresult is the special case of the claimed formula for m = 1.

Proof 2 (induction on k). Let ag, = |Ag_;|. Note that ag = 2 = (2—1+8)2?-!* = 2. For k > 2, group the compositions by thelast part.

Section 1.1: Classical Models

With last part 1, the total numberof1s is ag_; + 2*~”, since there are 2*~? compositions of k — 1. With last part 7, where 2 < j < k — 2, the totalis a,—;, and there is 1 with last part k-—1. Thus a, = 1+ Qk-2 4 Yi Ap}. We can apply the induction hypothesis and then perform the sum. To avoid performing the sum, subtract consecutive instances to obtain for

k >8 that az, — az_) = 2°? — 2°? + a;z_1. Now the induction hypothesis

yields a; = 2(k + 1)2*-4 + 2'-3 = (k + 2)2*°3. Proof 3 (induction variation). For k > 2, reduce the last part by 1 to obtain a composition of k — 1. Each such composition arises twice, by deleting a final 1 or by reducing final part larger than 1. Counting 1s over all resulting compositions thus yields 2a,_;, but we lost one for each of the 2*-? compositions of k ending in 1, and wegainedonefor each of

the 2*-° compositions of k ending in 2. Hence a; = 2a,z_; + 24-2 — 24-3 = (k + 2)2*-3, Proof 4 (overall induction, sketch). One can also do the whole problem by induction on k for fixed m. The inductive ideais like that in Proof 2 or Proof 3, with adjustments for the copies of m that arise or disappear. The computations are not as clean as above, so we omit them.

ec) 1+ yk —m+8)2*-™? = (k + 1)2*-*. By parts (a) and (b), both sides countall parts in all compositions of k (the extra 1 counts the composition whose only partis k). 1.1.42. The Weights Problem. The set S, = {1,3,...,3*+} permits the checking of all integer weights from 1 through (3* — 1)/2 ona balancescale, and no otherchoice of k known weights permits more values to be checked.

Let f(k) = (3* — 1)/2. We first prove that S; permits us to balance object A, of integer weight n for 1 <n f(k). It suffices to express n as yo 6;3', where each b; € {-1, 0,1}, because then interpreting —1,0,1 for 6; to mean “sameside as A,,”, “off the balance”, and “side opposite to A,,” yields an explicit configuration of the weights that balances A,.

Wefind the desired numbers {b;} using the ternary expansion of the number n’ = n+ f(k). The equation n = yo b;3' holds if and only if the equation n’ = yo (b; + 1)3’ holds, because the geometric sum yields (3*-1)/2 = yo 3’. Since n < f(k), we haven’ < 2f(k) = 3*—1. Ternary

expansion guarantees a (unique) expression of n’ as n’ = yo a;3' with each a; € {0,1, 2}. Setting b; = a; — 1 yields an explicit way to weigh n. Wealso must prove that no other set of weights can balance morevalues. We count the possible configurations: each weight can be placed on the left, on the right, or omitted, generating 3’ possible configurations. The configuration that omits all weights balances no nonzero weight. Of the remaining 3*—1 configurations, each balances the same weight as the

Chapter 1: Combinatorial Arguments

configuration obtained by switching the left pan and right pan. Henceat

most (3* — 1)/2 distinct values can be weighed. The construction for the lower bound can also be established using induction on k. The advantage of the bijective proof is that it gives an explicit description of the configuration used to balance a given weight. 1.1.43. Using weights w, < --: < w, on a two-pan balance, where S; = >), Wi, every integer weight from 1 to S,, can be weighedifand only if w; =

1 and wj41 < 2S; +1 for 1 < j <n. For sufficiency, we use induction on n. When n = 1, the condition forces w; = 1, and the weight 1 can be balanced. For the induction step, consider n > 1, and suppose that the condition is sufficient for n — 1 weights. For 1 <i < S — wy, the

induction hypothesis implies that we can weigh i using {w,,...,W,_1}. With w, also available, we can also weigh w, — i and w, + i, so we can weigh every weight from wy, — S,_1 to Wn + Sn_-1 = Sy, using {w1,..., Wn}. Since wy, — Sn-1 < Sy-1 + 1 by hypothesis, we can weigh every weight up to S,. For necessity, suppose we can balance all weights from 1 to S,. The second largest possibility is S, — w1, required to be S, — 1, sow, = 1.

If wj41 > 2S; + 1 for some j, then let W = S, — 2S; — 1; we claim that W cannot be weighed. The largest weight achievable without putting all

of {wj+1,...,Wn} in one pan is S, — wj+1 < W, but the smallest weight achievable usingall of {wj+1,..., Wn} in one pan is S, — 2S;, which exceeds W. 1.1.44. Regions in cevian arrangements. From the three points x, y, z on acircle, chords emerge and reach the circle between the other two points. When counting regions, we can view this as chords from a vertex ofa tri-

angle to the opposite side (these are called cevians in geometry). From each cevian arrangement with i, 7,k chords emerging from x,y,z, respectively, we can reach every other such arrangement byiteratively sliding the foot of one chord. When a chord reaches the intersection of two other chords, we temporarily lose a region, but the count is restored when the chord emerges from the intersection. Thus every configuration without triple intersection points achieves the maximum numberof regions. Proof 1. The regions become easy to count when the chords from each vertex reach the circle near the next vertex, cyclically. The chords from x and y then form a small grid of ij regions near y. Near the xy edge, the chords from x formi regions. Repeating this cyclically counts all the regions except one central region, and the total isij + jk+kit+i+t J+k+1.

Section 1.1: Classical Models

Proof 2. Having observed that the maximum occurs whenthere are no triple-points and that each chord intersects every other, one can count the regions formed as chordsare placed. First chords from x each split 1 region when added. Then the chords from y split i + 1 regions each. Finally the chords from z split i+ 7 + 1 regions each. Starting from a single initial region, the total becomes

1+i(1)+ jG+1)+kGt+74+1) =ij+ik+jkt+it+j+k+1. Proof 3. Having observed that the maximum occurs when there are no triple-points and that each chord intersects every other, one can treat the configuration as a planar graph and apply Euler’s Formula. Here the computations are a bit more complicated, and we are not assuming Euler’s Formula. 1.1.45. When n is divisible by r, and a k-set is chosen from |n] uniform at random, where gced(k, r) = 1, the probability that the sum ofthe k-set is divisible by ris 1/r. We prove more generally that the sum is equally distributed over the congruence classes modulo r. For any k-set, adding 1 to each element (n turns into 1) produces another k-set whose sum modulo r is larger by k. Since gcd(k, r) = 1, the original congruenceclassis not revisited until r steps later, after one k-set has been found in each congruence class. Since n is divisible by r, the translates of a given k-set contribute equally to the r congruence classes. Since translation partitions the k-sets into disjoint classes, and the claim holdsfor eachclass, the distribution overall the k-sets is also uniform. 1.1.46. Forn,m,k € N with k <n, >i=0 mite = 1. Consider a deck of n blue cards and m red cards. A player pulls cards at random without replacement and wins when k blue cards are obtained. The probability of winning is 1, since k < n. We compute the probability that the player wins after drawing exactly 7 red cards, where 0 < j < m. Theprobability that exactly k of the first k + j cards are blue is (Z)(") / (Ey) The probability that the last card is blue given that exactly k of the first k+ /

Chapter 1: Combinatorial Arguments

cards are blueis k/(k+,j). Hence the probability of winning after drawing exactly 7 red cardsis me: Summing over j completes the proof. +7

1.1.47. If f: A— Band g: B > Aare injections, then there exists a bijection h: A —> B, and hence A and B have the same cardinality. (SchroederBernstein Theorem) We view A and B asdisjoint sets, making two copies of commonele-

ments. For each element z of AU B, we define the successorof z to be f(z) if z € A, and g(z) if z € B. The descendants of z are the elements that can be reached by repeating the successor operation. We say that z is a predecessor of w if w is the successor of z. Because f and g are injective, every element of A U B has at most one predecessor. The ancestors of z are the elements that can be reached by repeating the predecessor operation. The family of z consists of z together with all its ancestors and descendants; call this F(z). We use the structure of families to define a oneto-one correspondence between A and B. The successor operation defines a function f’ on A U B; below we show several possibilities for families using a graphical description of f’.

First suppose that z is a descendant of z. Because every element has at most one predecessor, in this case F(z) is finite (repeatedly composing the successor function leads to a “cycle” of elements involving z). Apply-

ing f’ alternates between A and B, and thus F(z) has even size. For every x € Ain F(z), we pair x with f(x); because F(z) has even size, this is a

one-to-one correspondence between F(z) A and F(z)N B. Otherwise, F(z) is infinite. In this case, the set S(z) of ancestors of

z maybe finite or infinite. When S(z)is finite, it contains an origin that has no predecessor(all elements of F(z) have the same origin). If S(z) has an origin in B, then for every x € AN F(z) we pair x with its predecessor

g(x); because B containstheorigin, g~!(x) exists. When S(z)is infinite or has an origin in A, we pair x with its successor f(x).

Section 1.2: Identities

Because every element has at most one predecessor, the pairing we have defined is a one-to-one correspondence between the elements of A and

the elements of B within F(z). Since the families are pairwise disjoint, it is also a one-to-one correspondence between A and B. In moretechnical language, we have defined the function h: A — B by h(x) = g™}(x)

when the family of x has an origin in B, and h(x) = f(x) otherwise. The function h is the desired bijection.

1.2. IDENTITIES 1.2.1. Combinatorial proofs of (,",) = %*(j) and (min) (meh) = (™"")(2). To choose k + 1 elements from [n], one can first choose k and then choose one element from the remaining n—k. This marks one element asspecial,

which could be any of the k + 1 chosen elements, so each (k + 1)-set has been counted k + 1 times. For the second equality, both sides are 0 unless 0 < k <n. Both sides count the ternarylists of length m+n in which m positions are 0 and k of the remaining n positions are 1. On the right side, choose the positions for Os and then the positions for 1s. On theleft side, first choose all the positions for 0s and 1s, and then among them choose the positionsforIs.

1.2.2. Wiig ("f*) = (2241). After applying complementation to convert m+1 the summandto (th ), the Summation Identity evaluates the sum. 1.2.3. (9) - (",”) = (1) + CO*). Using Pascal’s Formula twice,

n\ _[(n-1l 1 n-1\ [n-1 1 n—-2 4 n-2

k) \k-1

\k-1

k-1

kk}

1.2.4. Pascal’s Formula holds for the extended binomial coefficient. We

take the coefficient (%) to be 0 when k < 0, so the formula holds when k =1. Fork >1, we use (2) = 4%! Th,vu-j=e vof+i(°,) with v equal to u—1 and then u to compute

(a) (ta) = elem) (ema) = eta) =e} 1.2.5. >,(,",)(,°.)=(3). mtn

Setting 1 = n—k, the sum becomes

~, (.-))(;), and the value is given immediately by the Vandermonde convolution.

Zl.

Chapter 1: Combinatorial Arguments

1.2.6. a=0 (er ‘)= ke=0 (er*) and ae\(-re) = (er): For thefirst

equality, applying complementation to convert the summandsto (”**;') and ("**1) allows the Summation Identity to evaluate the two sides to

(""") and (”*"), which are equal. Applying complementation to the second factor in the summandcon-

verts the sum to >>, (7)(,,”_;), which evaluates by the Vandermondeconr—k volution to (""”), whichequals em) 1.2.7. Evaluationof (|). Using the definition,

—1

k-1

(-1)4

k-1

( k )- allo-9= Sr [[e+n=Co*

1.2.8. Summingthefirst npositive numbers. Inthe formulas i” = 2(3)+({) and i? = 6(3)+6(5)+(j{), the left side counts k-tuples from an i-set, where k € {2,3}. On the right for k = 2, we can choose two distinct elements in is) ways andlist them in either order, while if we use the sameelement twice there are i choices. For k = 3, there are six orders in which we can list three distinct elements. When using only two elements, we choose them, pick which of the two to use only once, andpick its location, yielding 6(5). Again there are i ways to use only one element. We use the Summation Identity to perform the sums.

Se sS( (5!)=m yi). (nt+1\_ nti)

i=1

d= Dafa} (i) =2("5!)*("a |) = r= Dofs)*s)*()=e( a )ee("s Je | “2 CO,

o(n+1

nt+1\_ n(n+1)(2n-2+8)

(n+l

n+1

= n(n 1) (C= VED 1) 45) = nine 1)E™ As an application, n

> (2 + 372 —5i) = i=1

n2(n+1)?

2. -

n(n+1)(2n+1)

rn + 1)

2n+1 5 = nin + 1)( n(n+1) wo ~ 5) = nin + Din Din +4)

Section 1.2: Identities

1.2.9. There are dp, ways to put m white and n black marbles into boxes if each box has at most one marble of each color and no box is empty until all marbles are used. The boxes in order correspond to steps in a Delannoy

path. The steps can be horizontal (white marble) or vertical (black marble) or diagonal (one marble of each color). When all marbles are used, the path will reach (m, n). 1.2.10. A triple product identity. We use the Committee-Chair Identity twice, reorder the factors, and use it two more times.

n—-1l

n+1\ (n-1\

[n-1\n+1/[

(alana) k )= (hoa) al k (21) _[n-1\|n+1n(n-1

\_ (n-1\/n+1

-( k eT ta) = ( k erate) 1.2.11. Identities by induction, using Pascal’ Formula. a) The binomial coefficient formula (7 )= En Br The formula holdsfor n = 0 under the convention that the “factorial” of a negative numberis infinite. For n > 1, Pascal’s Formula and the induction hypothesis yield

(n=l 1) (n-1)! (n-1)! _ n-k nl kn! ! Q=C(e) +e) = nab + Gee= a mone + nee! = AG

1.2.12. When flipping 100 fair coins, the number of heads andtails are morelikely to differ by 2 than be equal. Proof 1 (computation with factorials). The probability of equal num-

bers is (‘{)’)/21°. The probability of differing by 2 is 2(7j)’)/2!°, sinceeither heads or tails may be extra. For the ratio, we cancel like factors and

compute sygmsit = gag <1.

Proof 2 (combinatorial argument). Given any string with 50 heads and 50 tails, switching the last flip yields a string in which the numbers differ by 2. Distinct strings get mappedto distinct strings, so the mapis injective. Furthermore, strings in which the last entry is in the minority do not arise, since flipping it from equal weight makesits new value occur 51 times. Hence there are strictly more differing by 2.

b) The Summation Identity \", (;.) = (f1;) forn, k = 0. For n = 0, the identity reduces to (?) = (,,,); both sides equal 1 if k = 0 and 0 if k>0. Forn> 1, the induction hypothesis and Pascal’s Formula yield

or(i) = (8) + DE (i) =) + (a) = (RE).

c) The Binomial Theorem (x + y)” = Yo (Z)x*y""*. For n = 0, we

have (x + y)° = 1 = (})x°y®. For n > 0, the induction hypothesis gives (xt yl = mo (",*)x*y"-I-k| We multiply both sides by (x + y) and simplify the resulting expansion. To combine terms where the exponents agree on x and agree on y, we shift the index in the first summation. We

Chapter 1: Combinatorial Arguments

then use Pascal’s Formula to combine corresponding terms. For the extra

terms, (”;) = 1 = (”) and (”)') = 1 = (G); these become the top and bottom terms of the desired summation. The full computationis n—-1

noe rRyn’

* ‘elee)-te!“s“e (ie n—-1

—

n—-1

n—1

k,,n—-k

n _

k=1

k,n—-k

k=0

d) An alternating sum: Yeo(-1)(i;) = (";'). We prove this for n, k > 0. For n = 0, the conventionsfor binomial coefficients yield 0 on both sides unless k = 0 (where they equal 1). For n > 0, the induction hypothesis and Pascal’s Formula yield {on

-|{(n-1

n-1l

doo, ‘ ~ dv lé - ) r (, ~j- :)| :

(n-1

({

n-l

~ yooh ) r den,” 1- :)

("a") (ea)=("i') _(n-2

n-2\

[n-1l

1.2.13. Combinatorial transformations for summing min{i, j} and max{i, j}.

a) Viet Veja Min{i, J} = Var Fe. Proof 1.

Consider an arrangement of unit cubes piled atop the

square with opposite corners (0,0) and (n,n) in the plane. Thepile of cubes in position (i, 7) (that is, with upper right corner(i, 7)) has height min{i, 7}. Thus the sum on the left counts the cubes. The numberof positions wherethe pile has height at least (n—k+1) isthe numberofpairs

(i, 7) such that both i and j belong to the set {n —k+1,...,n}. There are k? such pairs, so grouping the cubesby the height of their position yields the sum an k?. (Without geometry, this argument is the same as summingthe entries of a matrix with min{i, 7} in position (i, /).) Proof 2. Both sums count the squares with positive integer sidelengths formed by the lines y = 0,...,y =nandx=0,...,x =n. There

j}.

Section 1.2: Identities

are k? such squares with side-length n + 1 — k, so the sum on the right counts them by size. The sum on the left groups them by the upperright corner. The numberof squares in the set whose upperright corneris the

point (i, 7) is precisely min{i, 7}, and we sum overall choices for i and /. Proof 3. Both sums count the 3-tuples of integers from [n]| in which the third element is smallest. When thefirst two elements are (i, 7), there are min{i, 7} choices for the third element. When the third elementis r, there are n —r+1 choices for each of the first two elements. Letting

k=n-r+1 again yields thesum )°7_, k’.

b) yr, kh? = 2("3")+("3"). Both sides count 3-tuples(r, s, t) € [n+1]? such that t > max{r, s}. The sum on theleft counts the triples according to the value of t; when t = k+1, there are k? ways to specify r and s. The terms on the right group the triples according to whether r = s. If so, then we pick two elements and put the larger in ¢t. If not, then we pick three, put the largest in t, and choose either orderfor r ands.

ce) yey Vijay Min{i, j} = gn(n+1)(2n+ 1) and Yr, Y_, max{i, j} = an(n + 1)(4n — 1). For the first sum, we invoke parts(a) and (b) and then compute 2("3")+("3") = 3(n+1)n(n—-1)+ $(n4+1)n = (n+ I)n[2n-2+3]. For the second, since min{i, 7} + max{i, 7} =i+ 7, we subtract thefirst

sum from }Yy_, );-,(i+ j), which equals n }Y_,i +n i, J, or 2n(”5"). Thefinal value is (n+ 1)n[n— £(2n+1)], which yields the desired formula. Comment: These identities can also be obtained by algebraic manipulation of known identities involving things like sums of squares.

1.2.14. 0\(m— j)2i-! = 2" —m-1. Proof 1 (induction). Let f(m) denote the given sum. Note that f(m)- f(m-1) = an 2/-1=2™1_1, Also f(0) = 0, since the sum is empty. Therefore,

f(m) =D",(F@- f@-D) = OM4-1) = 2" -1-m. Proof 2 (counting two ways). The family of all subsets of [m] with size at least two has size 2” — 1—m. The given sum countsthis by the position of the next-to-last 1 in the incidence vector. When the next-tolast 1 is in position 7, there are m — j choices for the rightmost 1 and 2/-! waystofill the first 7 — 1 positions. The sum counts precisely the incidence vectors with at least two 1s, because those are the vectors that have a next-to-last 1. 1.2.15. Combinatorial argumentsfor identities.

a) (*”) = 2(°"|'). To pick a set of size n from [2n], one can use element n and choose n — 1 from the remaining 2n — 1 elements to add, or omit element n and choosen — 1 from the remaining 2n — 1 elements to omit.

Chapter 1: Combinatorial Arguments

b) ©, (7)(7) = (7)2”-). The kth term in the sum counts the ways to form a committee of size k with a subcommittee of size / from a set of n people, choosing the committee first and then the subcommittee. When we sum over k, we are consideringall possible sizes for the committee, so the sum countsall possible committees with a subcommitteeofsize /. Selecting the subcommittee first can be done in (a) ways, and then the rest of the committee can befilled by choosing an arbitrary subset of the people that remain. Thus the right side also counts this set. The proof can equivalently be phrased by saying that both sides count the ternary n-tuples with / zeros. c) HI gel= 7 forg,n€N. Consider a tournament with q” players in which gamesinvolve q players and exactly one survives. In thefirst round, there are gq”! games. In the jth round, g”/*+ players remain and there are g”/ games. In the nth round, there is one game, and the winning survives. Setting k = n+1-— / shows that the left side of the identity is the total number of games. On the other hand, gq” — 1 players must be eliminated, and each game eliminates g—1 players, so the right side also counts the games.

d) \*_, i(n—i) = “_, (). Both sides count the 3-element subsets of [n+1]. The left side groups them according to the middle element; there

are i(n — i) triples in which the middle element isi+1. The right side groups them according to the top element; there are ( 5) triples in which the top element is i+ 1.

1.2.16. Strehl’s Identity: ©, (”) (*) =O, (%)”. Proof 1 (Vandermonde convolution). Special cases of the Vander-

mondeconvolution include )*, (7)(;) = ("*°) and ©, (“)(,",) = (7). With these (at the beginning and end), the Subcommittee Identity, and reversing the sum on k, we compute

(2) = SOY) - xX QOZWH)

EE(NOI)-20)ECE

Ele)ECMO)EHO “E(i) () Proof 2 (counting two ways). Given n distinct red cards and n dis-

Section 1.2: Identities

tinct black cards, let S be the numberof ways to have the same numberof cards of each color be bad and choose n bad cards to burn. By Leta choosing

k bad cards ofeachcolor (with k > n/2), we have S = >, (7)° (**). On the other hand, if we first choose the n burned cards, with j red and n — 7 black, we must also determine the unburned bad cards. Pick j of the unburned n cards. Let the chosen red cards be good and the chosen black cards be bad (but unburned). If i of these 7 chosen cards are red, then the numberof bad red cards is n —i, and the numberof bad black cards is (n — j) + (j — i), which also equals n — i. Asi runs from 0 to min{j, n — j}, the numberof bad cards of each color runs from n down to max{n — j, j}, as needed, since this many of one color were burned. The sum is unrestricted, since (7) = 0 wheni > j. Thus

S=)) (”")) =>, (")’. (This combinatorial proof was described by Grigory M. on math.stackexchange.)

1.2.17. 7, amVG- 1)(k-i-—1) = (4), algebraically and combinatorially. Algebraic proof The inner sum is an instance of Theorem 1.2.3(5):

k-11 (At) (Ad) — (“tH+1) — (*;'). Replacing the inner sum with @1) turns the outer sum into an instance of the Summation Identity:

the sum is (7). Combinatorial proof. Note that (7) counts the 4-sets in [n]. Viewing each 4-tuple as four numbersin increasing order, let k be the valueof the largest and i be the value of the second smallest. We must have 1 <i < k < n, which agrees with the limits of summation. For each choice of these parameters, we complete a 4-set by choosing a numberless than i

and a numberbetween and k. This can be donein (i — 1)(k —i — 1) ways. 1.2.18. For m,r EN, always 1,54 k(71) =221"). Algebraic proof. We expand the binomial coefficient on the left into a sum using the identity in Theorem 1.2.3(5b), setting n in that identity to 0 and s tok, and letting the index i be the negative of the summation index in the identity (if m > r+k, then we have nonzero terms, while if m <r+k, then the original binomial coefficient and all terms in the sum equal 0). We then interchange the order of summation, apply the Committee-Chair Identity, and sum over k.

yeeer= oa, Mid= dol", DEA) k>1

k>1 i=0

i=1

k>1

"EG ye") _ “(mi=1

i—1

k>1

No-1(m-i

i=1

Combinatorial proof. The left side counts the waysof choosing at least

Chapter 1: Combinatorial Arguments

r +2 numbers from [m+ 1] and marking one chosen numberthat is not among the smallest r + 1 numbers chosen. The term for k in the sum counts the ways whenr+1+k numbers are chosen. The right side groups

the set according to the (r + 1)th smallest chosen number. If that number is m + 1 —i, then r unmarked numbersare chosen from the m — i smaller numbers, a marked numberis chosen from the i numbers higher than m+1-—i, and an arbitrary set of unmarked numbersis chosen from among the remaining i — 1 higher numbers. 1.2.19. Summations.

a) The value of Y°4.. gz(;) is 4y(2"*1 — 1). We use the CommitteeChair Identity and the Binomial Theorem to compute RDO Eat (a) = DEO att (eed = aT (27+ ~ 1) . b) The value of > p-9(-1)* (7) n+1-k 1_ jg Ch" Successively using the n+1° Complementation Identity, the Committee-Chair Identity, the substitution k =n+1-—~j, and the Binomial Theorem yields n

nt+1

Yori) 1-k~ rev,” a 1-k yew, 1- ari k=0 _—

LQ _4)\n+1-J oa [ntl _— 1 —_ 4)\nt+l1 _ —] n+1] — (-1)" n+ 2u' ) ( j ) nae OD CO = a J=

1.2.20. A variation on the Vandermonde Convolution (Theorem 1.2.3(6)):

> ((e2|)(fe) = (fw) £4 k/2|

)\| k/2]

| 2/2|

yield >’, ("") (1-7) = (™*m) = (”,). Hence the sum has value (”) + nny. (."1)» which by Pascal’s Formula equals the claimed value (”* m-1 1.2.21. Relations between binomial coefficients and harmonic numbers.

Let H,, = °_, + (so Ho = 0). Suppose 0 < k <n. a) yDia=ke(-1yt yy = (;)(An — Hy). Let f(n, k) denote the sum on the left, so we prove f(n, k) = (1)(An — H;,). We use induction on n. For

— a

For convenience, let m = | 72/2| and m’ = | n/2 | . To apply the Vandermonde Convolution, we separate the sum into two pieces, over k = 27 and over k = 27 +1 for integer 7. The even index is highest when k = 2m’; the odd is highest when k = 2m’ + 1. However, in each case the sum extends over all 7 without adding any nonzero terms. The even terms yield Di (” Von) = (rm) = ("). The odd terms

Section 1.2: Identities

n=k, the sum is empty, hence 0, and the right side is also0. Forn > k, we separate the top term and use Pascal’s Formula. After regrouping terms and shifting the index on the second sum, weapply the induction hypothesis. Finally, we must manipulate the harmonic numbersand the binomial coefficients.

fin.) = Yr eayre(")2 J=kt+1

jr rc 0

f(n-1 ("

Ze 1)et

}+ @ i) J- ko

n—k

(—1)-D-(t-1)-1

= f(n—1,k)+ s (1 0- (") \me )’ @-b-€@-D i=(k-1)+1 = f(n-1, k) + f(n-1, k-1) = ("tn — H;,) + (7 1) Hs _ — Hy_1)

= (:) ~1 — Hy-1) - (" Fi '\; = (/:) — Hx), where atthe last step we use (”,')¢ = (7)2=* = (7) (4-2).

b) yo (-1)-*1 (Jes = (7)(A, — Hy-«). This can be proved using induction like part (a), but also it is equivalent to part (a). Letting i = n—j, we use part (a) to compute

CY <

jJ=0

1)-A-1

("5 YD 1

1)2—i-Fk-1

(") aw 1

i=n—k+1

= f(nyn—h)= (2)(Fy — Haw 1.2.22. Reciprocal powers in sums.

a) If by = 7, a4(”) for n = 1, then Ye_, * =

Yi, &(2). We use

induction on n. The claim is immediate for n = 1. For n > 1 we have i

vel) Dele Lela Le teal Le b) > Rok = an co C1 (), where the sum on the left is over all (k1,.... h,,) such that L<k, <~. -<ky <n.

Wegeneralize part (a), proving )° i =

YrEj), with the sum

on the left again over (k,,...,km) such that 1 < ky <---< ky <n. It then suffices to set a, = (—1)*~!, since using n > 1 this yields

Chapter 1: Combinatorial Arguments

by = Dpa(-DE*() = 1- Deg(-DA(") =1-G- 1)" = 1. We prove the generalization by induction on m. The pase casem=1

is the statement derived in part (a). For m > 1, let cx, = z:4,, and let d, an ce(;): By the induction hypothesis, d, = >> i. By part (a)

hai E(h) =

Ded aaa Substituting the value of d;,, from the induction

hypothesis (using summands such that 1 < ky <--- < km_1 < km, where

km is fixed) yields

a(n) _ yrex(n) _ Sr din Deli) Dele) ma

=n ~ ow -he -= yh 1.2.23. A sum for the reciprocal of an integer power.

a) Pras (-D* (GR) = C1 Uo). Applying Pascal’s Formula yields a telescoping sum: ye t=j( 1)*(Z) = ej (- 1) (73) + ("%")] = (-1)/(""1). (The identity can also be proved by induction or inclusion-exclusion.) b) YC(D> ms = =, where the inner sum is over all (i1,...,lm) such that 1 < iy < +--+ < im < k. We use induction on m.

When m = 0, the claim reduces to the statement of part (a) with j = 1. For m > O, we reverse the order of summation and then evaluate the innermost sum using part (a) and the Committee-Chair Identity. This brings a factor of 1/n out front. We then reintroduce k as a new name for im. This yields the expression for the problem with m — 1 indices instead of m, with the order of summation already reversed. Applying the induction hypothesis now compreves the proof.

do() ines 2 Lm

~yol

“.

ij=1

lm=lm-1

Ini ~~ oe,

nN « y=

414

Lm =im

1Ilfn-1

LaDe ye(t oat “1 ijy=1

1 k+1

Y tm-1=lm-2

im-1 se , )

“.

[(n

lm=lm-1

11 (7) = nnmt

1.2.24. Counting dots. In the hexagonal arrangement S, consisting of n rings of dots, the central ring has 1 dot, and fori > 1 the ith ring has

6(i — 1) dots. Thus S, has a, = 1+ )*., 6(i — 1) = 1+ 6(5) dots.

Section 1.2: Identities

Using the Summation Identity for binomial coefficients, we compute ee ay =n+6 ye ke1 faa =nrt 6("3") =n+(n+1)n(n—-1)=7n?. To obtain this directly, we view S; as the visible three faces of a cube of dots with k on each side. The central dot corresponds to the corner of

the cube closest to us. We view this as the point (k, k, k), in which case the visible dots are the triples with maximum coordinate k. Counted by which coordinate values equal k, the numberof these is 1+ 3(k—1)+3(k-

1)? = 1+3(k-1)k = ax. Thus summingthe “shells” countsall the dots in the cube with n dots on eachside.

1.2.25. )okk! =(n+1)!-1. Algebraic proof. The values of the sum for 1 <n <4arel1,5, 23,119, which suggests strongly that the value in general is(n+1)!—1. It is easy to prove by induction that this guess is correct. Basis: 1-1! = 2! —1. Induction step: When n > 1, suppose that the formula holds for smaller values. We split off the last term of the sum and apply the induction hypothesis to obtain n

n-1

S keklan-nt+) ke kanenl+(t—-DY=(ntV!-1. k=1

k=1

Alternatively, observe that k-k! =(k+1)!—k!. The sum telescopes, and yy, kk! = Se (A +)! -— Ye, A! = (t+ 1)! - 1. Combinatorial proof. The formula (n+1)!—1 counts the permutations

of [n+ 1] except for the identity permutation. The summation counts the same set, partitioned by letting k+1 be the highest i such that element i is not in positioni. For such a permutation, elements k+2,...,n+1are in positions k+2,...,n+1(onechoice only), andelements1,...,k+1 are in positions 1,...,k +1, with k +1 not at the end. Such permutations arise by inserting k + 1 immediately before one of the k elements in a

permutation of [k]. There are k- k! waysto do this. The identity permutation has no element out of place, so it is not counted in this sum. Any other permutation has an elementout of place, and k is uniquely defined for it. Thus each non-identity permutation of

[n + 1] is counted exactly once in the set, as desired. 1.2.26. Combinatorial proof of ¥)acta) Vacin IAM Bl = n4”-!, Let S be the set of triples (x, A, B) such that A, B C [n] and x € AN B. For each choice of A, B € [n], there are|A M B| ways to choose x to complete triple in S, so the sum counts S. For each of the n ways to choose an element x € [n], there are 2”! choices of A containing x and 2”! choices of B

containing x, so also |S| = n4”~!. Since both sides of the formula count S, they are equal.

Chapter 1: Combinatorial Arguments

1.2.27. Sums over products.

a) sca [ies 1/i = n +1. Consider the productJ];_,(1+1/i). The expansionof this product has 2” terms, since the ith factor can contribute 1

or 1/i. For eachS € [n], there is aterm ],¢,1]],-g 1/i. Thus the desired

sum equals []'_,(1 + 1/i) = J]j_, =n+1. b) ~sctn)(- 1) [Leg 1/i = 0. Consider the product []7_,(1 — 1/i). By the same argument as above, this product expands to the desired sum, but the first factor in this productis 0.

1.2.28. (n—r)(")() = (I). The algebraic proofis

AMC) =(nmol) = (Eolas) (SC) by successively using complementation, the Committee-Chair Identity, complementation again, and the Subcommittee Identity. The combinatorial proof observes that both sides count the (n + r)tuples from {0,1,2} with r 0s, r 1s, and n —r 2s such that thefirst position is nonzero and some 2 is marked. On the left, we choose positions for the Os, then choose positions for the 1s, then mark a 2; the stages are

done in (”*”~"), (”), and n —r ways, respectively. On the right, we form such (n + r)-tuples by putting a 2 in thefirst position, picking positions for Os (or 1s) from those after the first, and then marking a nonzeroposition. If the marked position is a 1, we switch that 1 with the 2 in position 1; this is how we generate the n-tuples that have 1 in position 1. If the marked position is a 2, then we leave the ntuple unchanged.

1.2.29. >> (Fl) (naijg) 2* = (°"), where the sum is overall k with the same parity as m. We count m-subsets of {x1,...,%n}U {91,...,9¥n}. Group the selections by how manyof the pairs(x;, y;) contribute exactly one element. If there are k such pairs, then k has the same parity as m, since the remaining elements comein twos. To form a selection of m elements, we pick the k pairs that contribute singly in (9) ways, choose the contributions from these pairs in 2* ways, and obtain the remaining m — k

elements by choosing (m — k)/2 of the remaining n — k pairs. Summing over k countsall the selections and completes the proof.

0 (E) (man)/9) = (*"*"). To the 2n elements used above, add a special singleton element z. The right side is the numberof selections of m elements from this set of size 2n + 1. The selections that don’t use z

Section 1.2: Identities

are those counted previously. Those using z must select m — 1 from the remaining 2n elements. By part (a), the numberof those selectionsis

- cn4j2), Where k and m — 1 have the sameparity; these are precisely the remaining termsin the sum. Alternatively, the left side sums the instances of part (a) for (n, m)

and (n, m — 1), yielding (*”) + (,°",) = (°"**) by Pascal’s Formula. m-1 m 1.2.30. Given p,q,m,n, the numberofnondecreasing sequences of m+n+ 1 integers indexed from a_» to ay, and satisfying

—p < din <--<a_1 <0 <a, <--- <a, is (™*?) ("45") 4(*P)("*9). Partition the sequences into twosets: (1) ao > 0, or (2) agp < —1. In each case, the desired sequencesare built by solving

problemsof selection with repetition. In Cases (1) and (2), respectively, we have —ps<a_-m<-+::<a_-1<Oand0<ap <a, <:::<a, <q. —p<ad_m<-::S ay Sajp<—-landO<a,<:::<a,<4q.

In Case (1), we take m elements from p+ 1 types andn+1 from q +1; in Case (2), we take m+ 1 elements from p+ 1 types and n from q+ 1. Together, we have the formula claimed.

1.2.31. Yiso(i)(e) = Laso (4) (%)3"*a) Combinatorial proof. Consider a country with n states, in which each state has a senior senator and a junior senator (distinguishable). Each senator is Democratic, Republican, or Independent. States areeither independent (both senators Independent) orpartisan (neither senator Independent); no state has exactly one Independent senator. A balanced senate is an assignment of parties to the 2n senators so that the number of Republican senators equals the number of Democratic senators. We show that both sides of the equation count the balanced senates.

Left side: There are (7) ways to choose k states to be partisan. There are (7*) ways to allocate their senators to Democrats and Republicans.

Thus there are )°,., (7) (7) balanced senates. Right side: The numberof states with two Republicans equals the number with two Democrats; let this number be k. There are (Ji) ways to choose these states, and there are (7*) ways to assign their senators to parties. Each remaining state is Republican/Democrat, Democrat/Republican, or Independent/Independent; these can be assigned in

3”-2k ways. Thus there are ),., (<),)(4)38”* balanced senates.

Chapter 1: Combinatorial Arguments

b) Algebraic proof. Both sides equalthecoefficient of x” in (1 + 3x + x7)", On the left, expand

(a+etear=>(%Ja + x)x”se yy")(!\sn—j+k J=0 k=0

and extract the coefficient of x” by restricting to terms with 7 = k. On the right, expand _— S. »("lfJsJ _ ~(;Ja + x2)3B"-Sy2-I = ((1 + x7) + 3x)" =

n—j+2k x

jJ=0 k=0

and restrict the sum to terms with j = 2k. c) The two proofs above are essentially the same. Modify the second proof by expanding (x~!+3+ <x)” and extract the constant term. The contribution to the number of Republicans minus the number of Democrats is always even; there is one way for the Republicans to gain, one way for the Democrats to gain, and three waysfor the state to be balanced.

1.2.32. Combinatorial proofof ar (arity) (breaT) = (crore) L

The quantity (crore*) counts the multisets of total size k from a+b types of elements. Group these multisets according to the number of elements used from thefirst a types. When there are i elements from thefirst a

types, there are (“*!"') ways to obtain them and (°*%'"') ways to obtain the remaining k —i elements from the last 6 types. Each way of obtaining elements from thefirst a types can be paired with each way of obtaining elements from thelast 6 types to form a multiset of size k. Thus summing the product over k counts each multiset exactly once. Summation Identity as a special case. In the identity of this problem, set b= 1 andr=a-—1. Also apply Theorem 1.2.3(1). The identity then

becomes )**_y ("*") = ("*1**). Setting n = r+k rewrites this as >-(2) = r+1 ("*+), which is the Summation Identity. Equivalence to Vandermonde’s Theorem. By the polynomial identity

(5") = (-1)*(““F') that results immediately from the definition of the extended binomial coefficient, the right side of the identity above equals

(-1)*(~%°), and the left side equals (—1)* ye (~*)(,.°.). Renaming the

1.2.33. For nonnegative integers m, n, r, ands,

(ME = SE MG

om KA

arguments of the polynomials by setting m = —a and n = —b showsthat the identity above is equivalent to Vandermonde’s Theorem.

Section 1.2: Identities

Letting A(r,s) = Deg (7) ("F")(Z), we prove A(r, s) = A(s,r). By the

) E O E E O R

Vandermondeconvolution and symmetry,

) E M N I C L O S Y O M E S ) a9 S(

SOOMOIEOMe}

The second equality uses the Subcommittee Identity, while the last again applies the Vandermonde convolution. The final form is symmetric in r

and s, so A(r, s) = A(s,7r). 1.2.34. An application of the Vandermonde convolution.

The identity ¥, (,,..)(,.4) = (..5,,). The complementation identity nt+k r—m+n replaces Ca) with (7_,). Setting /=n+k then yields >), (5) (men) on the left. Since the initial sum wasoverall values of k yielding nonzero terms, so is the new sum. The new sum is simply the Vandermondeconvolution, and its value immediately is the right side. (Comment: One can also give a combinatorial argument that is essentially the same as

the argument for the Vandermondeconvolution.) Evaluation of sum: ¥., k(*)(?) = (a+ b- 1)(“",”). The CommitteeChair Identity replaces the first two factors with a(¢_;). Now the constant a factors out, and what remains inside the sum is the identity proved above, with (r,s,m,n) set to (a—1,b,-—-1,0). Hence the value of

the sum is (,“7172,), which simplifies to (“"1*°). Multiplying by a yields a

a(*tet). Applying the Committee-Chair Identity again yields the more

symmetric (a + b— 1)(7"7*) as the value of the sum. 1.2.35. The identity s*(?" k=0

2n+1 LS

k=n+1

2n+1

k-1} \

[(4n+1 + 2n\"

n}-

Using complementations, it suffices to show S. 2n i k

2n+1 iS 2n+1 J\2n+1-k wots k

2n _ 2n\(2n\ (4n+1 2n-—k+1 n}\ nn} \2n4+1)'

We count the ways of choosing 2n + 1 objects from {1,...,4n +1}. Thefirst sum counts the choices with at most n objects from thefirst 2n.

Chapter 1: Combinatorial Arguments

The second counts those having at least n+ 1 objects from thefirst 2n+1. Each choice is counted in at least one of these sums. Those counted twice are the choices having exactly n from the first 2n, plus n from thelast 2n,

plus the element 2n + 1. There are thus (7”) choices counted twice.

1.2.36. 9, (7)/(%) = n—m+1 4k. We use induction on m. Usingthefalling

factorial, rewrite the sum as )°,. m)/nq) and call it f(m, n). Note that

f(0,n) = 1, as desired. The term for k = 0 inthe sum is 1. For m> 0, f(m,n)-1=S>™® =)me me Dewy = — f(n- 1,m-1).

= k=

4 Mes)

(n—-1)%)

n+1 Using the induction hypothesis, f(n,m)=1+2 n nomi = = tT:

1.2.37. Evaluation of >), (rthy Wepegin by proving )),55 a = ne when 6 > a+ 1. It suffices to a®) _—_q(*1)

prove 52745 — Lio B® — G-1-a)bM? because with b > a+ the rightside vanishes in the limit as n — ov, since the large factors in the numerator are less than corresponding small factors in the denominator. _ xO) q™)

For n > 0, the induction hypothesis yields

b—-1

b-1

Ga®

a ©

a”)

i”)

b-1-a 2,90 b-1-a 2,5 BM G-1-aowD Hw — a™(b+n-1)-—aM(b-1-a)_ aMnta) a (b-—1-a)b™

(b-1-a)b™

Now we compute n+k

nik!

>("; ) - Lint hl DU Ge = n—-1' k>0

1.2.38. °P_9 (Z)cKen-k = CnCn+1, Where cn = (11.72))* Proof 1 (combinatorial argument). A group of 2n + 1 people, consisting of n male/female pairs and one extra male, wish to split into two teamsof about equal size that also split the men and women about equally. Team 1 will have n people, consisting of | n/2 | women and | (n + 1)/2|

men, while Team 2 will have n+ 1 people, consisting of| n/2] women and | (n + 1)/2| men. The numberof ways to do this by selecting Team 1 is CnCn+1, picking the women and the men separately.

Section 1.2: Identities

The summation on the left also counts these selections, grouped by the number of pairs that are split between the two teams. Thesplit

pairs can be chosen in (7) ways. The extra man winds up on Team 1 if and only if k and n have opposite parity. From the remaining n—k pairs, the numberto be chosen for Team 1 is | (n —k)/2 | , which can be chosen

in c,_~ ways. Since these pairs contribute| (mn — k)/2| women to Team 1, the number of women from the & split pairs that join Team 1 must be | n/2 | — | (n —k)/ 2 | , Which equals | k/ 2 | or | &/2| depending on the parity of n. Since ( Kye) = (j4/21)> these women can be chosen in cz ways. Choosing which womenfrom thesplit pairs go to Team 1 completes the distribution; their partners go to Team 2, and in the remainingsplit pairs the men go to Team 1 and the women go to Team 2. Thustheleft side also counts the choices. Proof 2 (factorial formulas). In all parity classes for n and k, the

value | k/2| can be added to one of {|(n — k)/2| ; | (n — k)/2|} to obtain | n/2 | , and | &/2| can be added to the other to obtain | 2/2]. Thus expansion into factorials yields

(n—k)) (ee (ior)

(:}en- = aanTET ([er2|) fn

It therefore suffices to prove )>;_, (ea )( een = Cn+1, Whichis the result of Exercise 1.2.20. 1.2.39. Direct combinatorial proof of >, (”)("**) = ¥, (7)(7) 27. Let M and N be sets with sizes m and n. Let S be the family of ordered pairs (A, B) such that A is a subset of M and B is an m-subset of N U A, as illustrated below. We show that both sides of the identity count S.

Grouping the pairs by the choice of A, let k = |A|. For fixed k, we have (a) ways to choose A and then ("** ) ways to choose B. Hence theleft side counts S. On the right, group the pairs by the choice of BM N, letting j =

|B N|. For fixed j, there are (") ways to choose BM N. Since |B| = m, there are Cr) ways to complete B by choosing BN M. This factor equals ("), by complementation. Now form A by adding to BM M any subset of M — B; there are 2/ such subsets. Hence theright side also counts S.

“CED

Chapter 1: Combinatorial Arguments

1.2.40. A polynomialidentity

Di)nL) Grary k

By the Polynomial Principle, it suffices to give a combinatorial argument for equality of the two formulas when x € N. Weelaborate the set

S from Exercise 1.2.39. Again let M and N bedisjoint sets, with m = |M| and n = |N|, and let S be the family of ordered pairs (A, B) such that A is a subset of M and B is an m-subset of N U A, as illustrated below. The

set S’ is the set of triples (A, B, d) such that (A, B) € S and ¢ is a coloring that assigns to each element of A one of x colors. We show that both sides of the identity count S’. Grouping the triples by the choice of A, let k = |A|. For fixed k, we

have (”") ways to choose A and then ("**) ways to choose B and x* waysto choose ¢ to color A. Hence the left side counts S’. On the right, group the pairs by the choice of BN N, letting j =

|B N|. For fixed 7, there are (”) ways to choose BM N. Since |B| = m, there are Cmi) ways to complete B by choosing BN M. This factor equals

(”’) by complementation. The elements of BM M need to becolored; the values of ¢ on them can be chosen in x”/ ways. To complete A, each element of M — B can be omitted or can be included with one of x colors attached to it. Hence we must make one of 1+. choices for each of the remaining j elements, which can be made in (1+ x)/ ways. Hence theright side also counts S’.

“ch

1.2.41. The numberofways to select n pairs from x1,...,Xmtn>V1>+++>»¥m+tn of the form {x;, yi} for 1 <i<m+nor {x;,xj41} forl1 <i<m+n-l1is the Delannoy number dm,n. We have defined the Delannoy numberas the

numberof paths from (0,0) to dm,» using steps in {(0, 1), (1,1), (1, 0)}. Weestablish a bijection { from the specified set of selections to this set of paths. Consider a 2-by-(m + n) grid, with points x,,..., m+n in thefirst row and yj,...,Ym+n in the second. When wereach a new x;, there are three possibilities: an empty columnprovides a “free move”to the right,

Section 1.2: Identities

a horizontal pair providesa selection plus a free move to the right, anda vertical pair gives us a pair but no extra moveto the right. Visiting x1,...,Xm+n in order, we mapa legal set of pairs into a Delannoy path as follows. When the next x; to be processed is vertically paired, horizontally paired, or unpaired, the next step in the path is

(0,1), (1,1), or (1, 0), respectively. Since there are n selected pairs, the path moves n vertical units. Since reaching x,4, with n selections requires m free movesto the right, the path moves m horizontal units. Thus the resulting path reaches (m,n) via legal steps, and the function maps into the set of Delannoy paths.

The steps of a Delannoy path to (m,n) can be viewed as a list from {selected vertical pair, selected horizontal pair, empty column}. There are n selected pairs, and this produces in one way a selectionthat f takes to the given path. 1.2.42. The augmented Aztec diamond of order n (with 2n + 1 rows and 2n columns of squares) has d,,, tilings by dominos, where d,,y is the nth central Delannoy number. From each tiling we extract a path. We follow a path throughspecial dominos, each having a start square and an end square and generating one step in a Delannoy path. The step in the domino movesfrom the left midpoint of the start square to the right midpoint of the end square. The start squareof the first domino is the middle square of the first column. When leaving a domino, the start square of the next domino in the path is the one whose left midpoint is the right midpoint of the end of the current domino. Note in the example that to complete the tiling all remaining dominos must be horizontal.

HHVDV The path moves 2n units rightward, crossing 2n columnsof squares. Similarly, a Delannoy path counted by d,,,, moves n horizontal and n vertical units to reach (n,n), with diagonal steps providing one unit of each type. Encode a Delannoypath as a string in the alphabet {H, V, D}. Whena dominoin the path is horizontal, it crosses two columns from start to end, remaining at the samevertical position. Such movescorrespond to D in the Delannoy path. When the next dominois vertical, its

Chapter 1: Combinatorial Arguments

end point is one vertical unit below its start point (H in the Delannoy

path) or one vertical unit above its start point (V in the Delannoy path). In this way we generate path from a tiling, step by step from left to right across the diamond. The path moves 2n units and yields a Delannoy path if and only if it ends in the middle of the last column; that is the condition for having an equal number of H and V and moving 2n units. It is not obvious that the path will end there or that the mapis bijective. In order to obtain an easy inductive proof, we define a more general region B,,,, whose tilings correspond to Delannoy paths from (0,0) to

(m,n). There will be m + n columns of squares. When m = 0, the n columns have two squares each, arranged in an ascending staircase; this is a degenerate case not having three squares in the leftmost and rightmost column. To obtain B,,,, from By,-1,, when m > 0, we add to the top of thefirst n columns and introduce a new Oth column. Column n receives one new square at the top, columns n — 1 through 1 receive two new squares at the top, and the new column 0 has three squares. The added squares form a path as indicated below. We can obtain B,,,, similarly from B,,,,-1 by adding squares on the bottoms of columns; B,, » is just the reflection of B,,, in a horizontal axis.

Bo.3

Bi 3

Bo 3

Weclaim that the tilings of B,,,, correspond to the Delannoy paths

from (0, 0) to (m, n) via the map extracting paths from tilings that we defined earlier. We prove this by induction on m+n. When m = 0, there is only onetiling of the degenerate region Bo,,, with all verticaltiles. The path extracted consists of n vertical steps. Similarly, for its reflection B,.o in a horizontal line, again all the tiles are vertical, and the extracted path maps to m horizontal steps. Now suppose m,n > 0, so the first columnof B,, , has three squares. If a tiling uses a vertical domino on the bottom two squaresofthefirst column, then thefirst step of the extracted path is horizontal, since the end square is below the start square. In addition, the top square in thefirst column must be covered by a horizontal domino, which means the same is true for the next column and so on up to the nth column. Thisfixes the portion of the tiling covering what was added to form B,,,, from Bn-_i.n.

Section 1.2: Identities

In addition, the path cannot enter this region, since it can only rise one unit with each column. Finally, note the position of the path at the end of the first domino. The remainderof the path is the path extracted from the remainderof the tiling. It is a tiling of B,,-1,,, and by the induction hypothesis the extracted path is a Delannoy path that moves m — 1 steps right and n steps up. Furthermore, the induction hypothesis also say that in the smaller region it is a bijection: every such Delannoy path is obtained from exactly one tiling. Since these tilings of the full board are forced on the upper strip Addingthe first step completes the proof for this portion of the set of tilings. Whenthefirst domino in the tiling is vertical and covers the top two squares in the first column, the argument is symmetric to that above, and paths starting with a vertical step are generated.

Finally, the first domino may be horizontal. This forces both the tops of the first n columns and the bottomsof the first m columnsto be covered by horizontal dominos that cannot be reached by the path. Deleting these forced dominos leaves a tiling of B,,-1,,-1, with the path ready to continue from the usual starting point there. Adding a diagonal step on the beginning of the resulting paths completes the proof for the paths starting with a diagonalstep.

Bo 3 > Bi 2

1.2.48. An expression for the kth smallest element of a set.

For A =

{Q1,.-.,@n} C Rwith a, <-::<a,, andi € [n], let S; be the family ofielement subsets of A. For k € [n], the value a, equals yr(-1)*" (7-3 or,

where 0; = ))peg, max(B). There are exactly (7) k-subsets of A in which a,, is the largest el-

ement, soo, =)”_, (7,)am for 1 < k <n. The following computation expresses a; as a linear combination of o;,...,0n, where the final step

uses that )\”_,(-1)"(_{) = 0 except when m = k.

Chapter 1: Combinatorial Arguments

Yoo(e i) = (-1)* Ss am root _ 1} m=1

=UYom(ET(TE) = (-1)! > ame) Yeon‘) = ay, Comment: The main step is an inversion formula, the essence of which is inverting a matrix of binomial coefficients. For a more general viewpoint on such inversion relationships, see Exercises 3.2.7-8. 1.2.44. An identity for reciprocal products. Let S, be the set of permuta-

tions of [n]. For positive real d,,...,d,, we prove »

dada) + day) (Aqay tee7 + dyn)

di-++dn

by induction on n. Let d = (d;,...,d,), and let R(d) denote the sum on the left. For n = 1, the equality is trivial. For n > 1, the last factor in the denominatorin each term in R(d) is the same, so we can factorit out. We then group the termsby the value of z(n). Let d; denote thelist of all

the entries of d except d;. The termsfor permutations z with z(n) = k togetheryield R(d;). The computation is R(d)= = Td, 1ds eet R(d;). By the induction hypothesis, R(ds) = R(d) then yields R(d) =

wes me ro.“Tp where S = {w € [N]": iw; < N} and T = {w € [N]": wy,..., Wy are distinct}. For w € T with valuesin increasing order, let dj = w; — w;-1 for 1 <i<n. Thus wj,...,wW, are the partial sums of the entries in d. When we permute the elements of w to obtain some w’, there must be a corresponding permutation of d, so [Tj wt = daay(daay + day) °° (d,(1) +--+ + dn) for appropriate z. Note also that d,,...,d, are positive real numbers with sum at most N, since the largest entry in w is at most N. There are n! members of T using a particular set of values. When we consider such a subset 7’, they generate all permutations of a given vector din S. For this d, we apply the identity above to obtain _ \ w’ET’

oe d1)(dq(1) + Aq(2))*** (daa) °° + Aqny)

die++dn

The vectors (d;,...,d,) in S correspond bijectively to the sets of values in [N] obtained as their partial sums. We obtain one such vector

Section 1.2: Identities

for each group of n! members of T considered above. Summing over the groups thusyields equality between the sumsoverreciprocal products in T andinS.

1.2.45. 2 ye ip/q| = (p— 1)(q—1)+ ged(p, gq) — 1. Let R be the rectangular arrangement |q—1]|X[p—1] of points inthe plane. Draw a segment L from (0, 0) to(q, p). For 1 <i<q-—1, the point of L on the line x =i is ip/q. Hence there are | ip/q| points of R on this line at or below L, witha point on L if and only if ip/q is an integer. In addition, there are | ip/q| points of R on or above L on the line x = p—i. Hence the sum on theleft counts all (p—1)(q —1) points of R, except that it counts twice the points of R that line on L. The point ip/q is an integer if and only if i is a multiple of g/d. The number of multiples of g/d from 1 to gq — 1 is exactly d—1.

1.2.46. A combinatorial proofof ¥",| “| = Dol i). Both sumscount the lattice points in thefirst quadrant (including the axes) that are below

the line joining (m, 0) and (0, n). The term for i counts such points with x = m-—i, and the term for j counts such points with y = n— /. To see this, note that the equation of the line is my + nx = mn, sym-

metrically. When x = m-i, the vertical coordinate satisfies my+n(m-—i) = mn, or y = in/m. Since we take the integer values starting with 0 and

stay below the line, the numberoflattice pointsis | in/m|. The argument for the rows of points is symmetric. 1.2.47. Binomial coefficients as polynomials.

a) Let fi,(n) = k\(7) —n* + (§)n*1. For k > 3, the function fy, is a polynomial of degree k — 2. Note that fo is identically 0. Expanding the product, we compute

AM) = may = Tico(2 8) = nk — YZp in+ a(n), with h; a polynomial of degree k—2. Since yO i = (5), we have f, = hy. b) With 9;(n) = >°"_, i*, the function g, is a polynomialin n with leading terms ~+;n**1 + in*. Note that i* = k!(/) + (§)i*1 — fi. Weuse induction on k. In the computation, we use O(n*—!) to denote any polynomialof degree k— 1. For k = 1, the formula }\"_, i = sn” + $n agrees with the claim. For k > 1, we have yizt i* = k! Dizt (i) + (5) vizt i — Dizi fx (i). By the induction hypothesis, any nonzero term of degree j in f;(i) con-

tributes a polynomial of degree j +1 to Di=4 Ff; (i), and part (a) says that f;, has degree k — 2. Thus )°_, fx(i) = O(n*- ). Also, the induction hypoth-

Chapter 1: Combinatorial Arguments

esis yields ($) )"_, i1 = (§)inK+ O(n*-!), and the Summation Identity

yields k! YY", (;) = M(t). These three formulasyield °”_, i* = k!(77;)+S'n*+O(n*-!). By the Committee-Chair Identity and expanding the falling factorial, we obtain

a; * i} = att,

+ O(n**) k+1”° tt k+i1 [! — (3) 2

kt+1)

~ k+1-

k+1 _

k-1

ceils)" + Ey” FO).

To complete the induction step, we simplify the coefficient of n*:

1 [,_(*\], #et _ 2a eMk-D+(k+IR-1) _ 2tk-1 _ 1 k+1 2 2 2(k +1) ~ 2k+1) 2 1.2.48. Polynomials with rational coefficients that map integersto integers. Let I be the set of polynomials with this property. a) Every polynomial f of degree k with rational coefficients has exactly

one expression as ear bj (*) such that each coefficient b; is rational. There is a unique expression of f(x) as a linear combination of {(%): J = 0}, because those polynomials form a basis for the space of polynomials. We must also show that the coefficients are rational.

Let f(x) = ~;=0 ¢/x7; by hypothesis, each c; is rational. If k = 0, then f(x) = co(5). For k > 0, we complete the proof by induction on k. Let by = cxk!, so that f(x) — by (Z) is a polynomialof degree at most k — 1. By the induction hypothesis, we can choose rational numbers bo, ... , b¢—1

so that f(x) — b.(Z) = ye9 Oj (|). Since b; as defined is also a rational number, we have f(x) = an b; () , a formula of the desired form.

b) f € Lifand only if f(x) = >9 oj (*), wherethe coefficients are integers. Since (*) is an integer whenx is a positive integer, the condition is sufficient, by the polynomial principle. Conversely, suppose f € J, and

let k be the degree of f. By part (c), we know that f(x) = an b;(*), whereeach 0; is rational. We prove that each 6, is in fact an integer, by induction on r. For r = 0, evaluate f at 0; the result, which is an integer because f € J, also equals >»9 0;i (‘), whichis just bp. Hence bg is an integer.

For 0 <r<k, suppose we have proved that bo,..., 6,_; are integers.

Now f(r) = ys7=0 OFj(’). The only nonzero termsare those with j <r, so

we have f(r) = )j-9 5;(), or b = f(r) - ar b;(’). The right side is J

Section 1.3: Applications

a sum of products of integers, so 6, is an integer, which completes the induction step. 1.2.49. Combinatorial proof of >), (5..)( eee S (%..)- We make an up/downlist with n — 2r copies of U (up) and n + 2r copies of D (down). Since the total length of such lists is 2n and they are determinedby placing the lists, the numberoflists is (7. The length of a list is even; we group the entries in successive pairs. Pairs UD and DU don’t change the balance between U and D, but UU and DD do. There must be 2r more DD pairs than UU pairs, since the total numberof Ds is 4r more than the numberof Us; therefore the total numberof these pairs is even. Whenpositions are knownfor the UD and DU pairs, UD or DU is chosen for each such position without regard to any other conditions. There are 2”-2* ways to do this if there are n—2k such positions, which suggests letting 2k denote the total number of UU and DDpairs. Now the counting of the piece indexed by k is easy. We pick 2k positions among thelist of n pairs to be UU or DD, in (5,) ways. For each such choice, we pick k — r of these positions to be UU and the remaining

k +r to be DD, in (/“.) ways. Finally, wefill in the UD and DU pairs in the n — 2k other positions in 2”-?* ways. Thus the summandcounts the lists in the piece of the set indexed by k.

1.2.50. 5,5, 2%") = 47 - y"_,J=1 (741). The identity counts in two m+n mt+j ways the subsets of |[2m+1] with size at least m+n+1. Such asubset may be constructed by picking an element z to be the (m+ n+ 1)th-smallest element chosen, picking m+n elements below z, and picking any subset of the elements above z. With k = 2m+1 -—z, the value of k indexes the choices for z. Since there are 2m —k elements below z from whichto pick m+n, and k elements above z from which topick arbitrarily, the left side of the equation counts the specified subsets. To count another way, note that exactly half of the 2 - 4” subsets of {1,...,2m+1} have size at least m+ 1. From these, we eliminate those with sizes from m+ 1 to m+n by subtracting the sum on the right side.

1.2.51. Combinatorial proof of yi (2°)(@) = (%*)2"-**. We prove that both sides count the ternary (n+ 1)-tuples having a 2 in exactly k positions such that the copies of 2 separate the copies of 1 into k+1 portions of odd length. On the left, start with n+1 positions, and chose an odd number 2s+1 (at least 2k + 1) to be nonzero. Choose k of the s positions that are evenindexed relative to this sublist to receive 2. The copies of 2 separate the list into segments having an odd numberof Ls.

Chapter 1: Combinatorial Arguments

On the right, begin with any ternarylist of length n — k having ex-

actly k copies of 2. There are (”,")2”-* suchlists; copies of 2 may be consecutive. Now insert one position immediately before each 2 and at the end. This position receives 1 or 0 as needed so that the numberof copies of 1 in that portion betweencopies of 2 is odd. This choice is unique, so we obtain exactly one of the desired lists for each of the ("*)an-2k original lists of length n — k.

1.8. APPLICATIONS 1.3.1. Given k; letters oftype i, for 1 <i < n, the number wordsusingall let-

ters in the box that have no twoletters oftype n adjacentis (,, vie_) (et ), where N = et k;. First arrange the letters other than type n; the num-

ber of ways is the multinomialcoefficient (,’~j"_,). Now insert theletters of type n into k,, distinct locations among the N —k,, +1 gaps (includ-

ing the beginning and the end); the numberofwaysis (~pe). 1.3.2. Given positive integers k,,..., km, the numberof ways to partition a

set of n distinct objects so that there are k; blocksof size i is n!/[ |”, (i!)* kil. Index the objects as positions 1,...,n, and let b = )°", k;. Temporarily index the blocks as 1,...,6. A partition consists of assigning the positions to blocks, which corresponds to a word in the alphabet [|b] such that k; of these letters appear i times. Using arrangements with repetition,

the numberof wordsis n!/[]™,(i!)*. In fact, we do not care about the labels indicating the blocks; switching the labels on two blocks of the same size does not change the partition. Hence we also must divide by IT k;!. 1.3.3. Sets counted by the Catalan numbers.

a) Nondecreasing functions f: [n] — [n] such that f(i) < i for all i. To map these functions to lattice paths, use f to specify the heights of the horizontal edges, i.e. the lengths of the vertical runs. To get a lat-

tice path from (0,0) to (n,n), fori = 1,...,n take one step right and f(@i +1) — f(i) steps up, where we set f(n + 1) = n+ by convention.

The position after the ith iteration of this is (i, f(i+1)—1), which is the highest position in columni. Since f(i+ 1) <i+1, we get a ballot path. Note that the specification is cleaner for a mapping to paths from (1,1) to

(n+1,n+1); then the highest points in the columns are (i, f(i)). Ineither case, note that the numberof vertical steps (0’s) before the ith horizon-

tal step (1’s) is f(i) — 1, which specifies a ballot sequence since f(i) < i. To prove that this is a bijection we must invert the map. Given a ballot

Section 1.3: Applications

sequence, define f(i) by f(i) = 1+k;, where k; is the numberof 0’s before the ith 1 in the sequence. b) Non-negative integer sequences of length 2n + 1 in which consecutive entries differ by 1 and a, = dan+1 = 0. Since the first and last entries are the same, there must be the same numberof positive steps as negative steps. Converting positive steps to 1’s and negative steps to 0’s therefore yields a ballot sequence, since the fact that a; is non-negative means that at least 7 positive steps must precede the jth negative step. The inverse function turns 1’s into positive differences and 0’s into negative

differences. c) Arrangements of 2n people in 2 rows of n so that heights are increasing in each row and column. Index the peopleas P;,..., Ps, in increasing order of height. Let a; = 1 if P; isin row 1, a; = 0 if P; isin row 2. This yields a ballot list, because for P; to be the jth shortest person in row 2, there must be at least 7 people shorter than P; that appear in row 1, i.e. at least 7 1’s preceding the jth 0. The mapis invertible; given a ballot list a,,...,a2,, put P; in row 1 or 2 according as a; is 1 or 0. There is a unique way to place the resulting population of each row into increasing order. Because the jth 1 ina precedes the jth 0, the resulting columnsare increasing. This yields the unique arrangementin the original set that mapsto a. Hence the number of arrangements is the same as the number of ballot lists, and the set of ballot lists is a basic model for the Catalan numbers, which have the given formula. 1.3.4. When b,,...,6, are chosen so that each b; is chosen uniformly at random from [k] (independently), the probability that the resulting sequence is nondecreasing is GD (*”). The nondecreasing sequencescan be viewed as

ballot paths from (1, 1) to(n+1,n+1), where 0; is the maximum height reached by the path when x = i before moving onto x =i+1. These paths have length 2n. The numberof ballot paths of length 2n is the Catalan numberC,,, which equals — (*”). The total numberof possible sequences is n!, and the probability is the ratio of these. 1.3.5. Bertrand’s Ballot Problem with outcome (a,b). If a > b, then the probability that A is always aheadof B is a? and the probability that the score is tied at some pointis 20 The two probabilities must sum to 1 when a > b. A fails to be always ahead if and only if B has at least as much at some point. Since A winds up ahead, B hasat least as much at some point if and only if there is a tie at some point. Thus it suffices to find the probability that A is always ahead. If A is always ahead of B, then A mustgetthe first vote, and A must get at least as many votes as B in every initial segment of the remain-