Issuu

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™)

Weuse induction on n. For n = 0, we have ;2+- —fo =1= (b—1—a)b©°

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-

Chapter 1: Combinatorial Arguments

der. The probability that A gets the first vote is a/(a + 6). Given that A gets the first vote, the probability that A nevertrails in the remaining portion of the election is the solution to the Ballot Problem for an elec-

tion ending at (a —1,b). We have computed this to be (a — b)/a. Since both these events must occur, the probability that A is always ahead is —b _ a-b

a+b a = atb

1.3.6. When a fair coin is flipped 2n times consecutively, ending with n heads and tails, the probability that the lead changesis nt The probability that the lead does not changeis the probability that the list of flips is a ballot list of length 2n, whether with heads never trailing or with tails never trailing. By Theorem 1.3.13, the probability that heads never trails is 1/(n+1). The probability that tails never trails is the same. Since one of them winsthefirst flip, these events are mutually exclusive.

Hence the probability that the lead changesis 1 — 2/(n + 1). 1.3.7. Proofs of identities using the Catalan numbers.

Sv, ACE) (P) = (?"""). The right side countsall lattice paths from (0, 0) to(n,n+1). For each such path, there is a unique time whenit

first rises above the line y = x, by moving from (k, k) to (k, k+1) for some k. Group the paths according to this value k. The portion of the path up to reaching (k, k) is a ballot path of length 2k. Each such path can be paired with any lattice path from (k,k +1) to (n,n+ 1) to completea path in group k, and this generates all such paths. The numberoflattice paths from (k,k +1) to(n,n+1) is (oar F since there are n — k steps in each direction. Since the Catalan number C; is cy (*), the numberof paths in group k is the summandon the left. Summing over k completes the proof.

b) Yee ee CC") = (7",). The right side counts all lattice

paths from (0,0) to (nm —1,n+1). For each such path, there is a unique time whenit first rises above the line y = x, by moving from (kK—1, k—-1)

to (k —1,k) for some k with k > 1. Group the paths according to this value k. The portion of the path up to reaching (k — 1, k — 1) is a ballot path of length 2k —2. Each such path can be paired with any lattice path from (k —1,k) to (n—1,n+ 1) to complete a path in group k, and this generates all such paths. The numberof lattice paths from (k — 1, k) to (n—1,n+1)is (preety since there are n—k horizontal steps and n—k+1 n—k vertical steps, in any order. Since the Catalan number C,_; is ;+ (oe7), the numberof paths in group k is the summand on the left. Summing over k completes the proof. 1.3.8. For n > 1, there are ("2") even graphs with a fixed vertex set of size n-1

n. Let A be the set of even graphs with vertex set v1,...,U,. Since 9("2")

Section 1.3: Applications

is the size of the set B of simple graphs with vertex set v,,...,Un_-1, we establish a bijection from A to B. Given a graph in A, we obtain a graph in B by deleting v,. To show that each graph in B arises exactly once, consider a graph G € B. We form a new graph Q’ by adding a vertex v, and making it adjacent to each vertex with odd degree in G, as illustrated below. The vertices with odd degree in G have even degree in G’. Also, uv, itself has even degree because the numberof vertices of odd degree in G is even. Thus G’ € A. Furthermore, G is the graph obtained from G’ by deleting v,, and every even graph in which deleting v, yields G must have v, adjacent to the same vertices as in G’. Since there is a bijection from A to B, the two sets have the same size.

G 1.3.9. Amongthe trees with vertex set [n], there are (5)(2”-* — 2) trees with n—2 leaves and n!/2 trees with two leaves. By Corollary 1.3.7, the number of trees with vertex set [n] in which vertex i has degree d;, for 1 <i < n, is ey The trees with n — 2 leaves are double-stars: two vertices have degrees summingto n (each degree at least two), and the rest have degree 1. Pick the two special vertices, and pick the degree of the lower

one. The formula thenyields (9)

oe ae The ratio of factorials

is just (7-7), choosing the k — 1 neighbors for the lower-indexed central vertex. The sum is 2”-?—2, corresponding to choosing a nontrivial subset of the leaves to be adjacent to that vertex. The trees with two leaves are paths and have n — 2 vertices of degree 2. After picking the two leaves, the numberof trees with these degrees

is eo which equals (n — 2)!. Multiplying by (5) to choose the leaves, the answeris n!/2, which can also be obtained directly. 1.3.10. The number of trees on |[n| with the degree of i equal to d; for each i is ( a1d,-1) (alternative derivation of results in the text). Let a(d;,...,d,) be the numberof these trees. When n = 2, there is only one tree, and we have 1 = a(1,1) = (00): This forms the basis step for induction; now consider n > 3. Since n-vertex trees are connected and have n—1 edges, a(d,,...,dn) = 0 unlessall d; are positive and }),d; = 2n— 2. Since the averaged;is less

Chapter 1: Combinatorial Arguments

than 2 and all are positive, we have d; = 1 for some j. Thus / is a leaf in all trees with degrees d,,...,d,. Group these according to the neighbor of 7. By the induction hypothesis, the number of these with j adjacent

to k is the multinomialcoefficient (age 1) where {d/} is obtained from {d;} by deleting d; and reducing d, by 1. There are no such trees when d; = 1, and the induction hypothesis agrees with this, because the multinomial coefficient is 0 when a term on the bottom is negative.

By the generalization of Pascal’s Formula (Remark 1.3.11), the sum of the formulas obtained from the induction hypothesis is (dy-ld,-1)?

except that it lacks the term d; — 1 on the bottom. Since 0! = 1, adding a 0 to the list of numbers on the bottom of the multinomial coefficient does not change the value, and we obtain the desired formula for a(d1,..., dn).

By the Multinomial Theorem, >> (aaa,-1) ITi_1 git = (erx)”, where the sum on the left runs over choices of nonnegative integers d,;-—1,...,d,—1 summing ton — 2. Setting all x; = 1 counts the trees

with vertex set [n], partitioned according to the list of vertex degrees. Setting all x; = 1 on the right yields n”~?. 1.3.11. K; has (n — 2)n""? spanning trees. By Cayley’s Formula, K,, has

n”~2 spanning trees. Each has n — 1 edges, so there are (n — 1)n”? pairs (e, T) such that T is a spanning tree in K, ande € E(T). By symmetry, each edge appears in the same numberof spanning trees. Hence the

numberof spanningtrees containing a particular edge is (n—1)n”~? (”) , which equals 2n”~?. To count the spanningtrees in K, , we subtract from the total number of spanning trees in K, the number that contain the particular edge

e. Subtracting 2n”"? from n”~? leaves (n — 2)n”~° spanningtrees in K,, that do not contain e.

1.3.12. Priifer’s bijection. For a tree T with vertex set [n], the Priifer code g(T')is formed by repeatedly deleting the least leaf in the remaining tree and recording its neighbor, n — 2 times.

a) g is a bijection fromtheset of trees with vertex set [n] to the set [n] n—2 We generalize the correspondence by applying the algorithm to an arbitrary vertex set S C N with |S| = n. We show that for a = (a1,..., @n—2) €

S”-? exactly one tree T with vertex set S satisfies 9(T) = a. We prove this by induction on n. For n = 2, there is only one tree. The Prtifer code is a list of length 0, and it is the only suchlist. Consider n > 2. Computing g(T') reduces each vertex to degree 1 and then possibly deletes it. Thus every nonleaf vertex in T appears in g(T). No leaf appears, because recording a leaf as a neighbor of a leaf would require reducing the tree to one vertex. Hence the leaves of T are the

Section 1.3: Applications

elements of S not in g(T). If g(T) = a, then thefirst leaf deleted is the

least element of S not in a (call it x), and the neighborof x is aj. We are given a € S”-? and seekall solutions to 9g(T) = a. We have shown that every such tree has x as its least leaf and has the edge xa}. Deleting x leaves a tree with vertex set S’ = S — {x}. Its Priifer codeis a’ = (ag,..., An_2), an n — 3-tuple formed from S’. By the induction hypothesis, there exists exactly one tree T’ having vertex set S’ and Priifer code a’. Since every tree with Priifer code a is formed by adding the edge xa, to such a tree, there is at most one solution to 9(T) = a. Furthermore, adding xa, to T’ does create a tree with vertex set S and Prtifer code a, so thereis at least one solution.

b) A tree T with vertex set [n] has {n—1, n} as an edgeifand only ifthe last entry in 9(T)isn—lorn. Ifn—1andnare adjacent in T, then the edge joining them is the final edge when the algorithm is applied (since previously there is always a smaller leaf), and the last label recordedis n—-lorn. Suppose that they are not adjacent. In the algorithm to generating the Priifer code of a tree with vertex set [n], we never delete vertex n. Also, we do not delete vertex n—1 until n—1 and are the only leaves, in which case the remaining tree at that time is a path (a tree with only two leaves). We then peel offvertices from the end opposite vertex n until only the edge containing n remains. Neither n nor n—1 is recorded during this process. In particular, the final label is not n —1 orn. The graph obtained from K,, by deleting one edge has (n — 2)n”~3 spanning trees. Label the vertices from |[n] so that n and n—1 are the vertices not adjacent. The spanningtrees of K, are then the trees with vertex set

[n] having n and n — 1 nonadjacent. The Priifer codes of these trees are the ones that do not end with n or n—1. There are (n — 2)n”-? suchlists. 1.3.13. An n-vertex tree T whose Priifer code g(T) differs from the list

f(2),..., f(n — 1) correspondingto it in Theorem 1.3.4. Let g’(T) be the list obtained from g(T) by adding 1 at the beginning and n at the end. We construct T such that o(g’(T')) # T, where o is the map taking functions to trees in Theorem 1.3.4. There are many such T’; we present an easily checked family. Let T be obtained from the path with vertices 1 through n in order by cutting the edge from 1 to 2 and making the leaf 1 adjacent to n instead. The tree is still a path, but with 1 moved to the other end. The leaves are 1 adjacent to n and 2 adjacent to 3. The Prifer code first deletes 1 and records n, and then it peels leaves 2 through n — 2 from the other end, recording 3 through n-—1. Thus

g(T) = (n,3,...,n—1). The leaves 1 and 2 do not appear.

Chapter 1: Combinatorial Arguments

Now g’(T) = (1,n,3,...,n—1,n), increasing in the middle. In the functional digraph of g’, all elements are loops except for an edge from 2 to n. Thus there are n — 1 cycles, arranged in decreasing order to form

o(g’(T)), with also the edge from 2 ton. The resulting tree is a path with leaves 1 adjacent to 3 and 2 adjacent to n. It differs from the path T by switching the identity of the two leaves.

1.3.14. The numbert,, oftrees with vertex set [n] satisfies t, =

ha k(i-7)tetn—k-

Given a tree with vertex set [n], delete the edge incident to vertex n on the path to vertex 1. This yields labeled trees on sets of k and n — k vertices for some k, where 1 belongs to the tree on k vertices and n to the tree on n — k vertices. To count the trees, we reverse the process. First choose k — 1 other vertices to complete the vertex set S for the tree containing vertex 1. Next, choose a tree with vertex set S and another with vertex set [n]—S, in tytn, ways. Finally, connect the tree by adding an edge from vertex n to any one of the k vertices in S. This counts the trees such that the subtree containing v; has k vertices The trees so generated are distinct, and every tree with vertex set

[n] arises in this way. Summingoverk yieldsfy. 1.3.15. Combinatorial proof of 2(n — 1)n”~? =

mt (ike(n — ket,

The numberof trees with vertex set [n] is n”-?. The numberof rooted trees with vertex set [n] is n”"!, since any vertex can be distinguished as the root. We show that both sides of the identity count the ordered pairs

of disjoint rooted trees with vertex set [n]. We obtain a tree with vertex set [n] by adding an edge joining the roots. Each tree arises from exactly 2(n — 1) ordered pairs by this process, since any edge can be the added edge, and the two rooted trees can be listed in either order. Since there are n”? trees with vertex set [n]

(Cayley’s Formula), there are thus 2(n — 1)n”~? orderedpairs. We can instead count the ordered pairs by building the components. Group them by to the numberof vertices in the first component; call this

k. After picking the verticesfor thefirst tree (in (7) ways), there are k*~1 choices for the first rooted tree and (n — k)""*~! choices for the second. Summing over k completes the count. tn = 5

ha (24 )tatn—k where t, is the numberof trees with vertex set

[n]. Since (7) = (7-7) oe , we can cancelfactors in the formula proved above, divide by 2, and invoke Cayley’s Formula to obtain this equation.

1.3.16. Combinatorial proof of n” =

O (i)k*(n — k)”-*1. Let S be the

set of rooted trees with vertex set [n] in which one vertex is marked. There

Section 1.3: Applications

are n”~? trees, we can choose a root in n ways, and we can marka vertex

in n ways. Thus|S| = n”. The number of such structures in which the marked vertex is the root is n”—!; this corresponds to the term k = 0 on therightside. We also count the part of S where the marked vertex is not the root by combining two structures. The factor k* suggests forming a rooted

tree T with k vertices and marking a vertex (here k # 0). There are k*

waysto do this for a specified set of k vertices. The factor (7) counts the choices of which k vertices to use. We also form a rooted tree T’ on the

remaining vertices; there are (n — k)”-*~! waysto do this. To form one element of S from the twotrees, let the root of T bea child of the root in TJ’. The root of the combined tree U is the root of T’. The marked vertex of U is the marked vertex of T; thus the root and marked vertex of U are different. To show that each element of S with marked and root vertices different arises exactly once, note that there is a unique child of the root on the path from the root to the marked vertex. This child is the root of T in the pair (7, T’) that correspondsto U. There is another bijection that works butis slightly less clean. 1.3.17. Cayley’s Formula generalized: an, = kn”-*"!, where an.x is the numberof rooted forests with vertex set [n| in which the roots of the components are the vertices 1,...,k. Since a tree can be rooted at any vertex, Cayley’s Formula is the special case k = 1. We give three proofs. a) Using induction on n, with basis ayn.» = 1. Let an,, be the specified value. We use induction on n; for n = 1 we must have k = 1, and there is one forest, as claimed. The numberof forests and the formula also equal 1 when n= k. Consider n and k with 1 < k < n. Whenall the roots are deleted, what remainsis a forest with some specified roots, which are the neighbors of the original roots. If altogether there are r neighbors, then they can be chosen in ("*) ways. Note that by symmetry, a,_;,- is the number of forests that can be formed no matter what the specified set of r roots is. From each such choice, a forest counted by a, , can be obtained byassigning each root to be a neighbor of one of the specified original roots.

Using the induction hypothesis and (”) = @(”;'), we compute daa n—k Jian = n—k Jarra - krr—1 -y(") -> (" r=1 —k

A ( (n—-k-1 4 Jer lin- ky 1-(r-1) _ = k(k + n— k)—k-1 r=1

Chapter 1: Combinatorial Arguments

b) Using recurrence (k+1)!an,4 = k!nkan,441, with ann = 1. We relate forests with k components androots in [k] to forests with k + 1 components and roots in [k +1]. When F has k components, we obtain F’ with k+1 components by cutting the edge from vertex k+1 on the path to the root of its component. However, a given F’will arise from n—nz+; choices of F, where n;z+1 is the order of the componentof F’ containing k + 1.

To overcome this asymmetry, we considerall permutationsof [k+1]. For a given F’, first permute the roots, then add the edge. Vertex k +1 gets permuted into each component T;; of F’ exactly k! times, so the number of times the operation generates n — n; forests with k componentsis k!. With a, 441 choices for F’, the numberoflistings of resulting forests with k componentsis k! an (n — ni)An,~+1, Which equals k!nkay 441. On the other hand, each forest with k components havingrootset [k] arises exactly (k + 1)! times, because its vertices 1 through k + 1 could have been under any permutation as k + 1 roots before being permuted to the positions where applying the addition of an edge from vertex k+ 1 to another component produced the present tree. Hence the numberof listings of resulting forests is (k + 1)!a, x. With (k + 1)!an., = k!nkan 441, we have ay ~ = Nz> An, k+1- Starting with an,, = 1, this inductively yields a,,, = kn”-*'. In particular, from An,k+1 we replace k+ 1 with k and introduce another factor of n to obtain the desired formula for a,,,. When we reach k = 1, we have another proof of Cayley’s Formula. c) By generalizing Priifer codes (Exercise 1.3.12). Let S be the set of

rooted forests on [n] with root set [k]. For F € S, forma list by iteratively deleting the largest (nonroot) leaf and recording its neighbor, until only the roots remain. Let f(F’) denote the resultinglist.

For F € S, the list f(F) has length n — k. Its first n —k —1 terms lie in [n], and its last term lies in [k]. Hence f(F) € [n]”-*"! x [k]. We prove that f is a bijection by reconstructing the unique forest F’ such

that f(F) =a, wherea € [n]”-*! x [k]. With each step in applying f toa forest, we delete one leaf and forbid that label from the rest of the list. To obtain the unique forest F such that f(F) = a, it suffices to determine the leaf that must be deleted when putting a; into the list while computing f/f.

Begin with a forest with vertex set [n] and no edges, declaringall of [n] “unmarked”. Each component has one unmarked vertex. For 1 <

i <n-—k, let x be the largest unmarked element of [n] not appearing in (a;,...,Qn—-z%), add the edge xa; to the graph being formed, and markx. Weshow by induction on i that after step i the graph has n — i components, each with one unmarked vertex. We have noted that this holds after i = 0. Since a; appears in position i, this label is not marked at or

Section 1.3: Applications

before step i. Hence the edge added in step i joins two as yet unmarked vertices. Since each component has one unmarkedvertex, this combines two components into one, and marking x leaves the new component with one unmarked vertex, a; With n —i+ 1 unmarked vertices entering step i, andi < n—k, there are more than k unmarkedvertices, so the largest exceeds k, and

no vertex in [k] is ever marked. Hence these vertices remain in distinct components. In step n—k, the one remaining unmarked vertex exceeding k is made adjacent to a,_; to complete a forest with the desired roots. Whenapplying f toa forest, the forest is stripped to its roots. Thus a non-root label fails to appear in a;,...,a,_, only if it has already been deleted or is a leaf in what remains after deleting i — 1 edges. Thus the edge xa; we introduce at step zi in reconstructing F is the only edge that could have been deleted at step i if a was produced from a forest by f/f. 1.3.18. For a forest F with vertex set [n] whose components have orders N1,..., 1%, exactly n*? IL-1 n; trees with vertex set |n| contain F. Let T be a tree obtained by adding edges to F. The added edgesare copies of the edges in the tree T’ obtained from T by contracting each component of F to a single vertex. The numberof trees T that reduce to a particular

tree T’ is [],,,,carry MiNj, Which equals T= nari), To count all the trees that extend Ff’, we sum this overall choices of T’. By Corollary 1.3.7, the number of trees with vertex set v1,...,U; such that v; has degree d; for 1 < i < t is the multinomial coefficient

(‘1d,-1)" To obtain the final answer, we sum overall choices of positive d,,...,d, such that y-4 (di —1) =t-—2 and use the Multinomial Formula to compute

Dla aa) T=D(a aa)

ToSwy"-To i=1

i=1

Cayley’s Formulais the special case where ¢t = n and all n; equal 1. 1.3.19. A bijection between matchings and binarytrees.

a) The number of matchings on 2n labeled vertices is (2n)!/(n!2”). Let an be the desired number. Since the vertex 2n can match to any other, leaving a smaller problem, we have a, = (2n—1)a,_1, which by induction satisfies the formula claimed. b) The set M of matchings on 2n labeled vertices has the same size as the set T of rooted binary trees with n + 1 labeled leaves (unchanged by in-

Chapter 1: Combinatorial Arguments

terchanging left subtree and right subtree of any vertex). Assume that the leavesof the trees are labeled from 1 ton+1 and the vertices to be matched are labeled from 1 to 2n. We construct ¢: T— Mand y: MT. It will be clear from the construction that these are inverse functions. Given T € T, we successively assign the labels n+ 2,...,2n to the nonleaf vertices other than the root as follows: having assigned labels up to 7-1, assign j to the unlabeled vertex among those whose children are both labeled that has the child with the smallest label. Such a vertex exists, since we begin with all leaves labeled and there are exactly n — 1

nonleaf vertices to be labeled. Define ¢(T) to be the matching that pairs each vertex with its sibling. Conversely, given a matching M, we successively assign to the vertices n + 2 through 2n a matched pair of children as follows: having assigned pairs to vertices up to 7 —1, assign to 7 the unassigned pair among those whoselabels are both less than 7 that has the vertex with the smallest label. Such a pair exists, since when j < 2n at most 2n —(j — 1) pairs

are ineligible by having a numberat least j and exactly (j — 1) —(n + 1) pairs are ineligible by being already assigned, leaving at least one of the n pairs available. Define y~(m) to be the tree such that the root has the only unassigned pair as its children and any other nonleaf vertex with label 7 has the pair assigned to j as its children. 1.3.20. Congruence of binomialcoefficients. Let p be a prime, andlet the p-ary expansionsof positive integers n and k be given by n = )\ a;p' and k= > b;p'.

a) (:) = II (%) (modp). When two polynomials are equal, corresponding coefficients are equal modulo any prime.

Hence (x + 1)? =

(x? + 1) (mod p). We apply this to (x + 1)”, operating modulo p:

(x+1)"=(x+ 124% = | ]@+n=] [@? +n" =[] 3 (“0 L

j=0

The coefficient of x* on the left is (7). On the right, the exponents accumulate multiples of p’ to reach k. This requires taking b; timesp’ for each i. Hence thecoefficient of k on the rightis [, (f). b) Setting p = 2, we have (‘) odd if and only if b; = 1 implies a; = 1 for alli. Furthermore,all of (5) pees (”) are odd if andonly if n is one less

than a power of 2. Since (;) has the same parity as |]; ($'), having ({) odd requires each (¥*) odd, which requires a; = 1 whenever 6; = 1. If this holdsfor all & from 0 to n, then all a; in the expansion of n must be 1, and hence is one less than a powerof 2.

1.3.21. When p is prime, (?") and (7) are congruent modulo p”. There

Section 1.3: Applications

are (Pr) ways to choose pl points from an m-by-p grid of points. Among

these, ("’) waysselect entire rows. It suffices to group the remaining ways into sets of size p?. Whenthe points are not all chosen by entire rows, at least two rowsare partially chosen. Put selections in the same groupif one can be obtained from the other by independently rotating the top two partially chosen rows. This puts all the selections using partial rows into

groupsofsize p?. 1.3.22. Ifpisa prime andais positive integer, then p divides a®—a. The

set [a]? of p-tuples from [a] has size a?. To obtain a set S of size a? —a, discard [a]? all the p-tuples that use only one value; there are a. We prove the claim by grouping S into subsets of size p.

Let R be the relation on [a]? defined by putting (x, y) € Rif y arises from x by a cyclic shift. Since the identity, inverses of cyclic shifts, and compositions of cyclic shifts are cyclic shifts, R is reflexive, symmetric, and transitive. Hence R is an equivalence relation and partitions [a]? into equivalence classes. The discarded p-tuples are unchanged undercyclic shifts; they form equivalence classes of size 1. Since there are p possible cyclic shifts, each class has size at most p. If someclass hassize less than p, then some two shifts produce the same p-tuple. If y appears when weshift x by i or by Jj, then shifting y by 7 —i positions leaves y unchanged. Since j — is relatively prime to p, its multiples run through all congruenceclasses modulo p. Following a single entry of y through repeated shifts by 7 —i thus implies that all entries of y are the same, but we explicitly excluded such p-tuples. Thus all equivalence classes havesize p. 1.3.23. Divisibility of multinomial coefficients.

Given a prime p, let

N1,...,Nm beintegers summing ton with p-ary expansions n = ear a;p’

and n; = ar ai,jp’. a) The multinomialcoefficient (mm ) is not divisible by p ifand only

ifa; = "ai; for 0 < j < k. In the expression n!/[]™, ni!, we need to determine when the numberoffactors of p in the denominatoris the same as the numberof factors of p in the numerator. The exponent on

pinn! is Yi-1| n/p! |. With n = an a;p’, the coefficient a; contributes a; >-/—) p” to the count. If a; = >", ai,;, then the sumsof the contributions from each j, over all n;, is the same: )°", ai,; yo p’. Otherwise, find the largest 7 such

that a; # }\", ai,;. Since "nj = n, it must be that aj > ", aij. The resulting extra factors ofp (at least >> j 5 p’) cannot be made up from the smalle values of 7. Each unit moved lower, which contributes ar p r

Chapter 1: Combinatorial Arguments

factors of p to n!, can contribute at most p(>) JJ~* p’) factors of p to zn;!, and this is smallerby 1. b) The numberof terms in the expansion of (x1 +++: + Xm)" whose co-

efficients are not divisible by p is |], iia*), By part (a), the coefficient (1mp) is not divisible by p if and only if the units in the p-ary expansion of n are distributed over the p-ary expansions of nj,..., Nm in the same positions. That is, view the p-ary expansion of n as the row vector (aj,...,@,). Put the p-ary expansions of n,,..., Mm as the rows in an m-by-k matrix. We count the choices of (n1,..., %m) such that this matrix has column-sumsas the row vector (ap, ..., a@;). In the jth column, we must distribute a; units over the rows, with multiplicity. That is, we seek a solution to )*"”, x; = a; in nonnegative integers. The number of such solutions is (en *) , and we must pick one such solution in each columnto specify a desired list (n1,..., Mm). 1.3.24. In the expansion of (, x;)", the coefficients of the terms in which each exponentis | n/ k| or | / k| are the largest. In each term, the exponents sum to n. When the exponents are e;,... , ex, the coefficient is the number of words consisting of e; copies of i, for 1 < i < k. It suffices to show that we get more words when we bring two exponentsclosertogether. Given e; = a and e; = bwitha > 6+1, we group the words into subsets with a fixed set S of positions occupied by the a + b copies of i and j and a fixed subword on the other letters outside S. The size of each such set is the number of ways to arrange the copies of i and 7 in S. There are (“*°) ways whenthere are a copies of i and 6 of 7. With a—1 copies of i, the

numberof waysis a-1 (“*°). Since (7*°) = 21(%*°) moving the multiplicities a a \a-1 closer together makes each such set larger when a> 6+1.

1.3.25. The numberofregions formed by n pairwise-intersecting line in the plane (no three at a point) is 1+n+ ( Ds Fix any point x in the plane not on one of the lines; x is in one region. Weassociate each other region witha set of one or twolines, bijectively. Every region has a unique pointclosest to x. It is a corneror lies along an edge between corners. Conversely, any one of the lines contains a unique point closest to x. That point is on the boundary of one region on the otherside of the line from x; this region choosesthis line as described above. Any pairof lines intersects at one point z, forming acorner of four unbounded areas; let A be the area opposite the one containing x. The region contained in A that has z as a corner chooses this pair of lines as described above, because z is its closest point to x. 1.3.26. The numberof regions in R@ formed by n hyperplanes in general position is yo ("). For d = 1, the line is cut into n + 1 portions by n i

Section 1.3: Applications

points. For d > 1, every set of d hyperplanes has exactly one common point. Let P be the set of these CHnd intersection points for the given hyperplanes H,,...,H,. Take a reference hyperplane Ho that hasall of P on oneside andis not parallel to any hyperplane in the given set. By the induction hypothesis, the given hyperlanes H,,...,H, cut Hp into YD ”) regions, which correspond to the same numberof regions they form in the portion of R?% on the otherside of Hp from P. Now sweep Ho through P until all of P is on the other side. With each point of P encountered, a new region is discovered. All the regions are discoveredinitially by one such point, because Hp is not parallel to any given hyperplane. Hence we add (") regions. 1.3.27. In an election where A receives a votes and B receives b votes, the probability that A never trails B by more than k votes during the counting is Note that nonzero probability requires a > b—k. With all vote orders equally likely, the probability is the fraction of the lattice paths from

(0, 0) that do not rise above the line y= x+k. A bad path reachesa point of the form (i,i +k +1) for somei. Reflecting the subsequent portion of the path after thefirst such point adds a —i tothe vertical coordinate and 6 —i — k — 1 to the horizontal coordinate, reaching the point (b-— k-—1,a+k+1). Conversely, every lattice

path to (b—k-—1,a+k+1) reaches such a point, since a > b—k implies a+k+1>(b-—k-1)+(k+1), and reflecting the portion of the path af-

ter the first such point yields a bad path to (a, b) that correspondstoit. Thus thereis a one-to-one correspondence betweenthe bad pathsto (a, b) and the paths to(b—k-1,a+k+1). Generalizing the Ballot Problem, we thus compute the desired probability via

(a2)= (esi) ppb (“*°)

a+l1+i

1.3.28. Bijection from the set of binary trees with n + 1 leavesto the set of ordered trees with n+ 1 vertices. Given a binary tree B, contract the edge from each parentto its right child. Since a binary tree with n+ 1 leaves has n non-leaves and thus 2n edges, the contractions reduce the number of edges to n, yielding an ordered tree o(B) with n edges and hence n+ 1 vertices.

Weprove by induction on n that this is a bijection. For n = 0, we have o(¢) = e, and each set has size 1. For n > 0, let B, and By be the binary trees rooted at the left and right children of the root of B. Since o operates independently at each internal vertex, o(B) is the ordered tree

Chapter 1: Combinatorial Arguments

in which o(B}) is the tree rooted at the leftmost child of the root and o(B2) is the rooted tree that remains when that subtree of o(B) is deleted. The

root of o(Bz) is contracted into the root of o(B). Given an ordered tree T with n+ 1 vertices, let T,; be the subtree rooted at the leftmost child of the root, and let Tz be the subtree (with the same root as T) obtained by deleting T,;. Each vertex of T appears in exactly one of T; and JT»); let T; have k + 1 vertices and Ty haven —k vertices. Since n > 0, the root of T has a leftmost child, so0 < k <n. By the induction hypothesis, there are unique binary trees B) and

Bs such that o(B}) = T; and o(Bj) = T2. By the way that o operates at the root, we have T = o(B) if and only if B,; = Bi, and By. = Bj. Hence each ordered tree with n + 1 vertices arises exactly once undero. Another inductive specification of o explicitly converts one leaf of B to become the root of o(B). Let v1,...,v, be the vertices reached along a sequence of right edges from the root, with B,,...,B, being the corresponding left subtrees. Let o(B) have root v, and subtrees o(B,),...,0(B,) in order from left to right. The modification madein processing the root here has the sameeffect as contracting the edges reaching V1,...,U,, So induction showsthat this is the sameas thefirst mapping. 1.3.29. Over all —> L(?”) ordered trees with n+ vertices, exactly halfof the

(*”) vertices are leaves. Proof 1 (from the number of ordered trees). We count the pairs (T, v), where T is an ordered tree T with n+ vertices and v is a marked leaf of T. Note that T — v is an ordered tree with n vertices. We claim that T lies in 2n — 1 such pairs. Hence the total numberof leaves is

(2n — 1)+(*"*). The Committee-Chair and Complementation Identities then yield Bn 1 (77?) = _ one 1 xt : (?"*) = _— -"') = —1 Aer).

To provethe claim, consider adding a (marked) leaf vu to T. Any vertex u of T can receive v as achild. If u has d, children in 7, then it has

d, + 1 places for v. Hence there are ))-y;7)(du + 1) ways to add v. The second term gives n since each vertex contributes once, and thefirst gives n—1since T has n — 1 descending edges.

Proof 2 (using ballot lists). We use the bijection developed in Example 1.3.25 from the orderedtrees to ballot lists. Under it, a leaf corresponds to 10 in the ballot list. Hence the ordered trees with k leaves correspondto the ballot lists with k runs of 1s and k runs of Os. By the argument in Corollary 1.3.19, these correspond to cyclic arrangements of nisandn+1 0s with k runs of each. We need compositions of n andn+1 with k parts each to arrange the 1s and arrange the 0s. Without loss of generality, the first run of 0s can start immediately after the first run of ls. This allows each circular arrangement to appear exactly k times,

Section 1.3: Applications

for the k linear arrangements obtained by simultaneously rotating the

two compositions. Therefore, there are +(”,)(,”,) ordered trees with k leaves. To count the leaves, we compute

Dea) a)= Dlralle a) = (nor) a(n) :

k\k-1]\k-1

n—k]\k-1

n-1

2\n]}

Proof 3 (binary trees, sketch). There are C, binary trees with n+ 1 leaves and C,, ordered trees with n+ 1 vertices. Given a binary tree B, contract the edge from each parentto its right child. Since a binary tree with n+ 1 leaves has n non-leaves and thus 2n edges, the contractions

reduce the numberof edges to n, yielding an ordered tree o(B) with n edges and hence n + 1 vertices. In fact, o is a bijection (proof omitted). Underthe bijection o, leaves that are right children of their parents are pulled into internal vertices, while leaves that are left children of their parents remain as leaves. Since o is a bijection, leaves of ordered trees correspondto left-child leaves of binary trees, while non-leaves of ordered trees correspond to right-child leaves of binary trees (each nonleaf vertex x in o(B) receives exactly oneleaf of B, namely the one reached from x by successively following edges to right children. Henceit suffices to show that overall binary trees with n+ 1 leaves, exactly half of the leaves are left-child leaves and half are right-child leaves. This is immediate, because interchanging theroles of left and right maps each binary tree T into a binary tree T’ (perhaps T' = T’) such that the numberofleft-child leaves in T' is the numberof right-child leaves in T’, and the numberof right-child leaves in T is the numberof left-child leaves in T’. 1.3.30. The map suggested in Example 1.3.24 is a bijection from the set of triangulations of a convex (n + 2)-gon to the set of binary trees with n+ 1 leaves, implying that there are C,, such triangulations. Fix a root edge of

the (n + 2)-gon, and label the other edges in order with labels that will correspondto the leaves of the tree. We construct and check the bijection by induction on n. When n = 0, the 2-gon is a single edge. It is the root edge, and it correspondsto the only label; no leaves are combined. For n > 0, the root edge lies on a triangle T' with a third vertex, say v; when the vertices are indexed Up, ... , U;41 with the root edge joining Vo and vyz+1. The other two edges of T are the root edge of a (k + 1)-gon on Uo,..., Uz and the root edge of an (n—k+2)-gon on uz, ..., Unt1. Since 1 < k <n, both of these polygons are smaller. By the induction hypothesis, the two other edges of 7 are the root parenthesizations for binary trees on the k leaves labeling the edges from vg to v; and on the n—k +1 leaves labeling the edges from v; to vy+, (in the illustration, k = 1).

Chapter 1: Combinatorial Arguments

The tree for the full (n+ 2)-gon combines these two parenthesizations

at the root. Since the maps on the triangulations of the (k + 1)-gon and (n—k+2)-gon are bijections, we have a bijection for the triangulations in which the root edge forms a triangle with v;. Each triangulation determinesone value of k, so letting k vary from 1 ton yields thefull bijection.

a((bc)(de)) 1.3.31. Bijection from noncrossingpairings of 2n points on a circle to ballot lists oflength 2n. Label the points x,,..., x2, inorder. Consider a pairing P. Starting with x,, record 1 in position i when x; is the first endpoint of its chord encountered, otherwise 0. For each initial segment, we have seen the second endpoint of a chord only if we have also seen thefirst, so

the resulting list f(P) is a ballot list of length 2n. Each ballot list L with n 1s and n Os begins with 1 and ends with 0. Thus somewherea 1 is followed immediately by a 0; considerthefirst instance. Pair the two points at those positions. Delete the corresponding paired 1 and 0; the result is a shorter ballot list. Repeat this process to pair the points. Since we paired a 1 with a 0 only wheneverything between them wasalready paired, the pairing g(L) is noncrossing. One can describe f by the same process. A noncrossing pairing must pair two consecutive points, whosepositionsreceive 1 followed by 0. With this description, it follows immediately by induction on n that g = f7!. 1.3.32. Letting E, and O,, respectively, be the number ofDyck n-paths having an even or an odd numberofpeaks at even height, we have E, = On = 5Cy when nis even. When n is odd, we have E,, = $(C, + Cjn/2}) and O, =

$(Cn—C\n/2)). Here a Dyck n-pathis a path from (0, 0) to (27, 0) that never falls below y = 0 and takes n upsteps of the form (1, 1) and n downsteps of the form (1,—1), a peak is an up-down subpath, and the height of a peak is the vertical coordinate of its midpoint. Dyck n-paths correspond bijectively to ballot paths; hence the numberof them is the nth Catalan number C,,. Since every Dyck n-path has an odd or an even number of peaks at even height, we have E, + O, = C,, for all n. A valley is a down-up subpath; its height is the vertical coordinate of its midpoint. Let C} be the numberof Dyck n-paths havingat least one

Section 1.3: Applications

peak orvalley at even height, and let C° be the numberof paths having no peaksor valleys at even height. Changing thefirst peak or valley at even height into a two-step subpath of the other type changesthe parity of the numberof peaks at even height, pairing paths counted by E, and On. Thus C} contributes equally to E, and O,. The remaining paths, in C°, have no peaksat even height, so they all contribute to E,. Thus

On=402=1(C,-C®)

and

E, = 402+ C9=1(C, + C2).

If a Dyck path has no peaksor valleys at even height, then the number of consecutive upsteps at the beginning (and downsteps at the end) is odd, and otherwise it is even for each run of the same type. This requires an odd numberof upsteps and an odd numberof downsteps, which

requires n to be odd. Thus C® = 0 when is even, which completes the proof for even n. Whenn is odd, having no valley at even height implies that the path does not touch the horizontal axis between 0 and 2n. Hence wecan delete the first and last step and collapse the other steps in pairs to obtain a Dyck | n/2| -path. The process is reversible, so the correspondenceis a

bijection. Thus C? = C,,/2;, which completes the prooffor odd n. 1.3.33. There are (1272)) symmetric ballot lists of length 2n. Consider the lattice path interpretation of the ballot lists. It suffices to enumerate the paths consisting of the first n steps of a symmetric Catalan path. These will be all lattice paths of length n that remain in the region y < x. The end of such a path is on the line y + x = n. The numberof paths ending at points (n—k, k) with k < n/2 is ye2| (i). Any path that reaches such a point but rises above y = x does so for thefirst time at somestep, say at (j, 7+1). Reflecting the portion of the path after that step by interchanging up and right produces a path that ends at (k—1,n—k+1). Conversely, every path ending at a point (K-—1,n—k+1)with1<k< | n/ 2 | steps above y = x, and thereflection after the first such step yields a bad path to the good point (re k, k). Since these are both injections, the number

of good pathsis 77 Ln/2| (i) -

Ln/2! (.”,), which telescopes to (.72))-

1.3.34. Lattice walks.

a) The numberofpositive lattice walks oflength k is = (‘ GHigo". Group the walks by the numberof vertical steps, and view each asa list from {U, D, R, L} (up, down, right, left). A walk with j vertical steps is formed by choosing the j positions for vertical steps, entering a U, Dlist there in which every initial portion has at least as many Us as Ds, and entering any R, L-list in the remaining positions. The numbersof waysto do these three phases, independently, are the factors in the sum-

Chapter 1: Combinatorial Arguments

mand, since the U, D-lists correspond to lattice paths of length k that don’t rise above the line y = x by converting U to H (horizontal) and D to V (vertical). Lemma 1.3.14 shows that there are (1707) such lattice paths. b) The total numberofpositive lattice walks of length n in three dimen-

sions (notgoing below the horizontal plane) is Yj, (7)(""*')2"-*. The steps in the last two coordinates combine to form a positive lattice walk in two dimensions, since the third coordinate remains nonnegative. When there

are k such steps, the number of such walks is computed in part (a), and the value of that sum has been givento us (from Exercise 1.2.29) as (7** *). The steps in the first coordinate can then be madearbitrarily. Grouping the walks by the numberk of steps taken in the last two coordinates, we choose the positions of those steps among the n steps, place a positive lattice walk of length k in those positions, and place positive or negative steps arbitrarily for the first coordinate in the remaining positions. 1.3.35. Generalization of ballot paths.

a) The numberof lattice paths from (0, 0) to (n,n + k) that do not rise above the line y =x + kis +1, (?"**). Without the constraint, thereare (nt ) such paths to the destination. Each bad path reaches y = x+k+1 at somefirst time x = j. If we reflect the subsequent portion of the path through the line y = x +k +1, we obtain a path from (0, 0) to(n-—1,n+ k+1). Furthermore, each path to (n—1,n+k+1) arises from exactly one

bad path to (n,n + k). Hence there are, (24k) bad paths in theoriginal set, yielding (7"**) — (2”**) good paths. Since (7"**) = n+k+1 —2,(7"**), the n

k+1 (2nt+k difference equals er n )

b) If each particle of type i produces particles of types 1,...,i+1 in the next generation, then a single particle of type k in generation 0 leads to

+1_(?"**) particles in generation n. We prove that the particles in generation n correspond to the paths in part (a). There is one particle in generation n for each sequence of integers ao,...,a, such that ajp = k and 1 <a; < a;-; + 1 fori > 1. Letting b; = k+i-aj;, we have bo = 0 and 6;-; < 6; < k+i-—1 fori > 1. Each such sequence bo, ... , b, yields an

up/right lattice path from (0, 0) to (n,n + k) that does not go above the line y = x+k, given by taking the step from x =i-—1tox=iaty = bj. Furthermore, the transformation is reversible, so each such path maps back to a single particle.

1.3.36. For q € N, the numberof lattice paths from (0, 0) to (n, qn) not rising above the line y = qx is the q-Catalan number al —— mn (thn), Proof 1 (paths with relatively prime movements). Appendinga ver-

tical step at the end yields a path from (0,0) to (n, gn + 1) not rising above ny = (qn +1)x. All such paths end with a vertical step after a

Section 1.3: Applications

desired path, since an integer point (a,b) above y = qx and not above

ny = (qn +1)x requires b > ga +1 and nb < (qn + l)a, a contradiction. With gcd(n, gn +1) = 1, by Theorem 1.3.17 the numberof pathsis

cae (“rt ‘), which simplifies by the Committee-Chair and Complementation Identities to the desired value. Proof2 (bijection). With horizontal steps as 1s and vertical steps as Os, the desired paths correspond to the binary lists in which each prefix has at most g times as many Os as Is. Since the total numberofOsis exactly g times the numberof 1s, the reversals of such lists are those where each prefix has at least g times as many Os as 1s. Complementing Os and 1s converts these to the q-ballot lists. By Corollary 1.3.19, the size of the set is as claimed. 1.3.37. The Cycle Lemma (Theorem 1.3.18): If m => kn, then every cyclic arrangement of n Os and m Is has exactly m — kn positions such that every clockwise segment starting there has more than k times as many 1s as Os. The statement is immediate for n = 0; we proceed by induction. For n >

0, let a be an (n, m)-arrangement. By the Pigeonhole Principle, there are at least k 1s between some two successive 0s ina. Let S bea set of k+1 consecutive positions consisting of k 1s followed immediately by a 0. No position in S is good; the 0 comes too soon. A position outside S is good if and only if it is goodin the (n—1,m-—k)-arrangement a’ obtained from a by deleting S. The numberof k-dominating starting places in a thus equals the numberof k-dominating starting places in a’, which by

the induction hypothesis is m— k —k(n-—1) =m-—kn.

1.3.38. Solution ofBallot Problem by Cycle Lemma. Weseekthe fraction of all lists of a 1s and b Os such that every initial segment has at least as many 1s as 0s. With a 1 prependedat the front, every initial segment has more 1s than Os. From eachelection list, good or not, form a cyclic arrangement of a+ 1 1s and b Os byfirst prepending a 1. Each cyclic arrangement of a+ 1 1s and 6 Os arises in a+ 1 ways by prepending a 1 to a list of a 1s and b Os and viewing it cyclically. The Cycle Lemma implies that there are a + 1 — 6 places to break such an

Chapter 1: Combinatorial Arguments

arrangement to obtain a good list. The fraction of good lists amongall lists corresponding to a given cyclic arrangementis thus ai| This ratio holds for every cyclic arrangement, whether periodic or ag Thus without counting the cyclic arrangements or weighting by their probability, the overall probability of a good election is 1 — b/(a + 1), as desired. Note that when a = J, this reduces to 1/(a+1), as expected from comparison with the Catalan number. Comment. When a+ and dare relatively prime, one can mimic the argument in the text. Cutting a(b, a+ 1)-arrangement in a+1+b places

yields aFiTo (ary?) = at ( “*°) cyclic arrangements. Multiplying by a + at+1 a 1 — b to count the good elections and dividing by (7*°) yields the desired probability a+ 1-—ba+1, but one still must obtain the same ratio from the periodic arrangements.

1.3.39. For n €N,there are an/a]F Sn (ee) lists (a1,..., Qn) ofpositive integers with a; = 1 such that a; — a;-; is odd and at most 1 fori > 1. Let S, be theset of lists, and let m = | n/2| . Wefirst encode each memberof S,, as a string consisting of n copies

of 1 and m copies of —2. With ap = 0, let 6; = a; —aj;-1 for 1 <j <n. Replace each 6; with (1 —b,)/2 copies of —2 followed by one 1; this does not change the sum. The full sum is a,, which is positive. Append enough copies of —2 to the end to makethe full sum equal to 1 or 0. Since there are n copies of 1, the total numberof copies of —2 is now m. Theoriginal list can be retrieved uniquely, since it ends at the last 1. Because )-/_, b; = aj = 1, the partial sumsof the resulting strings are nonnegative. That is, in every prefix the numberof Is is at least twice as large as the numberof copies of —2. Treating each —2 as 0, wecan thus

view each instanceas a lattice path from (0, 0) to (n, m) that does not rise above the line 2y = x. Whenn is odd, we add one more 0 at the end to reach (n, m+ 1), and the path does not rise above the line ny = (m+ 1)x. Furthermore, such a path must end with a vertical step, so such paths correspondto ourlists. Also, n and m + 1 are relatively prime. By Theorem 1.3.17, the number

of paths is + ("*"7"), which simplifies to +, ("*”") When is even, this argument and formula fail, but we can use the Cycle Lemma. Having added enoughcopies of —2 at the end to return to 0, we have a list of m copies of 0 and 2m copies of 1 such that every prefix has at least twice as manycopies of 1 as copies of 0. Prepending a 1 means every prefix has more than twice as many 1s as Os. By the Cycle Lemma, every cyclic arrangement of m copies of 0 and 2m+1 copies of 1 has exactly one place to cut and linearize such that every prefix has more than twice as many 1s as Os. Hence the desired paths are in 1-to-1 correspondence

Section 1.3: Applications

with the cyclic arrangements. Since m and 2m 1 are relatively prime, the 3m + 1 rotations of an arrangementare distinct. Avenee the number

of desired paths is —1_("*”*"), which simplifies to +(”"*”). The claimed formula agrees with each parity case. 1.3.40. Parenthesizations of x) +x1 +:::+Xn. Valid parenthesizationscorrespond to binary trees with n+1 leaves; there are C,, of them. Each such expression evaluates to a fraction with some variables in the numerator

(including xo) and the others (including x;) in the denominator. a) For n €N,the mostfrequentis eet uniquely when nis odd, and with the same frequency as the fraction“Sbtained by moving x, to the denominator when n is even. A valid expression consists of one variable or (a+ fB), where a and f are valid expressions on consecutively indexedvariables. Thus a valid expression on x9,...,X, has n pairs of left and right parentheses and evaluates to a fraction as described above. Furthermore, a valid expression is determined by the positions of the right parentheses alone, satisfying the feasibility constraint: pj < i-1 for 1 < i < n, where p; is the numberof right parentheses preceding x;. Inductively, every placement of right parentheses satisfying the feasibility constraint arises from a unique valid expression; the final operation groups a parenthesization of xo, ..., x,_1 with a parenthesization of Xk,.-.,Xn, Where k is the largest i such that p; =i-—1. Again by induction, x; is in the numeratorof the resulting fraction if and only if i+ p; is even. Hence if a valid expression has two right parentheses immediately following a variable, they can move to the right end without changing the resulting fraction. The feasibility constraint remainssatisfied, so the new expressionis valid. Thus each fraction corresponds to a unique rightmost expression a in which some right parentheses follow x, and the remainder appear alone following the elements of some subset S(qa) of x1,...,Xn-1. Note that there are 2”! such expressions, correspondingto the 2”! fractions that have xp in the numerator, x; in the denominator, and x2,... , X» distributed in any way to numerator and denominator. The valid expressions yielding a given fraction are obtained from its rightmost expression by movingpairs of right parentheses leftward to obtain a vector (p;,..., Pn) satisfying the feasibility constraint. The number of vectors obtained from a rightmost expression in this way is maximized by maximizing the numberof trailing parentheses in the rightmost expression, because if S(f) C S(a) for rightmost expressions a and £, then every leftward movementof pairs that yields a valid expression from a also yields a valid expression from f. The expression a* with all right parentheses at the end evaluates

Chapter 1: Combinatorial Arguments

to Reg? by induction on n.

(Including the left parentheses, a* =

(xq + (x1 +°°+(Xn_-1 + Xn)+++).) When n is even, the rightward expression having oneacts parentheses after x,_; and the others after x, has the samefeasible leftward movementsof pairs as a*; it yields ae

With S(a*) = ©, we have argued that **2~ occurs most frequently. For every rightmost expression a other than a* and the alternate when n is even, the leftward movement putting one pair after each x9; with 2i < nis infeasible for a but feasible for a*. Hence **2“4~ hasstrictly more realizations and we have determined the optimalfractions. b) The numberofoccurrencesof the most frequent fractions is the number ofnondecreasing nonnegative integerlists by, ... , b,-1 such that b; < i/2 for0 <i<n-—1. To count the expressions equivalent to a*, we count the feasible leftward distributions of pairs. For 0 <i < n—1, let 6; denote the total numberof pairs moved before x;,;. Since S(a*) = @, the feasi-

bility inequality is equivalent to b; < i/2, so the occurrencesofHaat are equivalent to theselists. c) The numberofthe lists in part (b) (and occurrences of the mostfrequentfractions) is 1, a) when n is even and sy (Ore) when n is odd. Let m = | n/ 2 | . We convert (b9,..., bn-1) to a lattice path whose horizon-

tal steps are from (j, b;) to (7 +1,6;) forO < 7 <n-1. With b; < i/2, the path does not rise above the line 2y = x. At the end, we add vertical

steps to reach (n, | n/2)). When n is odd, n = 2m+1,so0nand m+1 are relatively prime, and the path does not rise above the line ny = (m+ 1)x. By Theorem 1.3.17,

the numberof pathsis n+m+1\ nim*t) which simplifies to a +. ( ("*”") m+1 m

Whenn is even, we use the Cycle Lemma. The path correspondsto a list of m copies of 0 and n copies of 1 such that every prefix has at least twice as manycopies of 1 ascopies of 0. Prepending a 1 meanseveryprefix has more than twice as many Is as Os. Since n = 2m, by the Cycle Lemma every cyclic arrangement of m copies of 0 and n+ 1 copies of 1 has exactly one place to cut and linearize such that every prefix has more than twice as many 1s as Os. Hence the desired paths are in 1-to-1 correspondence with the cyclic arrangements. Since m and 2m + 1 are relatively prime, the 3m +1 rotations of an arrangement are distinct. Hence the number

of desired paths is —("*"""), which simplifies to 4, ("*”) 1.3.41. Non-crossing partitions of |n]. These are the partitions of [n] with no a < 6 <c <dsuch that a and ¢ are in one block and b and d are in another block. Note that non-crossing partitions can be “read” with a single stack. When we encounter a new block, it may be bracketed by the block currently being read. We push it onto a stack, hiding the current block. The lack of crossings implies that we must finish the new block

Section 1.3: Applications

(and pop it from the stack) before we need to read another memberof the current stack. a) Bijection to ballot lists of length 2n. Given a non-crossing parti-

tion of [n], process the elements in increasing order, adding to a (ballot) sequence being constructed. If the current elementi is the first (least) element in a block of size k, record k copies of 1 followed by one 0. If i is not the first element in its part, record 0. For each element, we get 1 at the beginning of the block containing it and 0 when wereadit, so the resulting sequenceis a ballot list of length 2n. For the inverse map, consider reading a ballot sequence by the “stack” procedure suggested above. At the beginning of a run of 1s, push the current block onto the stack and open a newblock of size equal to the length of the run. When reading a 0, decrease the (remaining)size of the current block. If this is the ith 0, place element i in the current block. Whenthe size of the current block reaches0, it is finished; pop it from the stack. Since we see as manyOs as the total size we create, and since we never add an elementto a block that started earlier than the current block until we finish the current block, the result is a non-crossing partition of [n]. This map undoesthe operationsof the earlier one. This is a “refined” bijection. We generate a runof 1s (ended by a 0) each time we start a new part, so this bijection maps non-crossing par-

titions of [n] with k parts to ballot lists with k runs of 1s. Hence the number of non-crossing partitions of [n] with k blocks is the numberof ballot lists with k runs of 1 (k left turns), which is the numberof ordered trees with n edges and k leaves, which by Theorem 1.3.26 is the Narayana n n—-1 number N,,,;, which equals ¢(,”,)(7-3).

1.3.42. Forn, k € N, the numberofnondecreasing integerlists (a1, ..., An)

such that 1 < a; < ti for1 <i < nis 1 (er Dtt)2), Let bp = 0 and b; = a; -—1 for 1 <j <n. Each suchlist a,,...,a, converts to a lattice path from (0,0) to (n+ 1, t(n + 1) — 1) whose horizontal steps are from

(j, b;) to (7 +1,6,;) for 0 < j <n. The constraint a; < qj keeps the lattice path below the line y = tx after the start. Since the endis one vertical step from that line, the path also does not rise above the line (n + 1)y =

[t(n + 1) —1]x. Each such path arises from exactly one of the desiredlists by this process, so the mapis a bijection. The endpoint has the form (p, q) with p and g relatively prime. By Theorem 1.3.17, the numberof lattice

paths from (0, 0) to (p, qg) that do not rise above py = qx is arg ("5"): This equals (PT), which becomes the expression claimed when p = n+ 1 and g=t(n+1)-1. 1.3.43. Bijection from the set of q-ballot lists of length (q + 1)n to the set of (q + 1)-ary trees with qn + 1 leaves. A q-ballot list of length (¢+1)n isa

Chapter 1: Combinatorial Arguments

list of n copies of 0 and qn copies of 1 such that before the ith 0 there are at least gi copies of 1. A (q+ 1)-ary tree gathers g + 1 children at each internal node, reducing them to one item. Thus with n internal nodes including the single root, there will be 1 + gn leaves. We expresstheelements of each set as unique “operation stacks”.

bed

((abc)de) — abc|de|

e¢

(a(bed)e)< abcdle|

bed

(ab(cde)) © abcdel|

A (q + 1)-ary tree can be expressed as a parenthesization describing the iterative collapsing of g+1 items to 1 at each internal node. The information can be captured by dropping the left parentheses and just keeping a vertical bar at the place of each right parenthesis. As the string is read from left to right, when a leaf data item arrives, it is place on the stack. Whenanoperation bar arrives, the g + 1 top items on the stack are combined into a single item that replaces them on the stack. The operations are describing exactly the combinations in the tree. Any list with n bars and gn+1 data items such that at least gi+ 1 data items precede the ith bar specifies such a computation and tree. Given a g-ballot list, add a 1 at the beginning, treat each 1 as adata item, and make each 0 a vertical bar. This process is reversible, so it gives a one-to-one correspondence between the g-ballot lists and the stacks describe above, since at least gi copies of 1 precede the ith 0 in a g-ballot list. Hence both desired sets correspond to the operation stacks. 1.3.44. In an election where A receives kn votes and B receives n votes, the probability p that the number of votes recorded for A is always at most k times the numberof votes recorded for B, throughout the counting, is equal to the probability q of the analogous event where “at most” is replaced with “at least”. A vote sequence contributes to p if and only if the reverse sequence contributesto gq. 1.3.45. Generalized Narayana numbers. a) For relatively prime positive integers r and s, the numberoflattice

paths from (0, 0) to (r, s) that turn exactly 2k —1 times and do notrise above the line ry = sx is +('_;)(%_)). By Theorem 1.3.17, the total numberof paths overall k is (7F), The paths correspond to binary lists with r copies of 1 and s copies of 0, starting with 1 and ending with 0. The paths with 2k —1 turns have k runs of 1 and k runsof 0.

Section 1.3: Applications

By the argument in Theorem 1.3.17, the paths correspondto circular arrangements of r copies of 1 and s copies of 0. The list for the path is obtained by breaking the circular arrangement between a run of 0 and the next run of 1. Hence it suffices to count the circular arrangementsin which the copies of each digit are split into k runs. To makelinearlists, place the parts of the composition of s following the parts of the composition of r; we have (4) (53) ways to make such an arrangement. Since r and s are relatively prime, these linear arrangementsare distinct. Each circular arrangementarises k times, starting at each part in the composition of r. Hence the answeris + (5-1) (h21)-

b) For q €N, the numberoflattice paths from (0,0) to (n, gn) that do not rise above the line y = qx and turn exactly 2k—1 timesis ¢(7_;)({“,). To apply (a), add a vertical step at the end of the path. This does not change the numberof turns. The new path does not rise above ny = (qn + 1)x. Applying part (a) with r= n ands = qn +1 yields the claimed formula. 1.3.46. Positive partial sums. Let x1,...,x, be a cyclic arrangement of integers with sum 1. a) For all r € [nl], there is exactly one place to break the cycle into a linear arrangement with exactly r positive partial sums. Plot the partial sums as a path of segmentsin the plane, starting at (0,0) and then us-

ing the points {(j, }°’_, x:)} as the successive endpoints for 1 < j <n. The path ends at (n,1). Continuing the path through successive periods by

translation, ending at (2n, 2), (8n, 3), etc. The lines passing throughcorresponding points from each period are parallel, with slope 1/n. If the line through the point with horizontal coordinate j is at or belowr points in each period, then there are r positive partial sums starting with the numberin position 7 + 1. As we raise the parallel line from the bottom to the top, we pass fromr =ntor=1. Furthermore, these values occur for distinct positions; we cannot have two points in a period on one of the lines because their heights are at integers and thelines slope up only by 1 over an entire period. Ifr > s, then the positions ending positive partial sums from position p, include all the positions ending positive partial sums from ps, where p; be the position from which j partial sumsare positive. It suffices to show that for any two positions, the positions ending positive partial sums from one include all the positions ending positive partial sums from the other. Cut the cycle into two segments A and B, with A starting at a and B starting at b. Since the total sum is 1, one of {A, B} has positive sum, and the other has nonpositive sum. By symmetry, suppose that A has positive sum. For any position in B, the partial sum from a ending thereis greater than the partial sum from b ending there, since it adds A. For

Chapter 1: Combinatorial Arguments

any position in A, the partial sum from a endingthereis at least as large as the partial sum from b ending there, since it subtracts the nonpositive total in B. Thusfor every position, the partial sum ending thereis at least as large starting from a as from b. Henceall the positions that end positive partial sums from also end positive partial sums from a. b) Whenall lists of n As and n Bs are equally likely, the number X of values i such that the ith A precedesthe ith B is a uniformly distributed ran-

dom variable, with Prob(X = l) = 1/(n +1) foreach 1 € {0,...,n}. View each A as +1 and each B as —1. Putting a 1 at the end and viewing the positions cyclically yields an arrangementof 2n + 1 integers with sum 1. 1 (*”) such cyclic arrangements. Since each has n+1 1s, there There are +.

are (~”) ways to linearize endingat a position with 1 and removethefinal 1. The resulting 2n-lists are distinct, since they can only be the sameif they come from the samecyclic arrangement, and thereis no periodicity in the cyclic arrangements. In the resulting 2n-list, the ith copy of 1 precedes the ith copy of —1 if and only if the partial sum ending at the ith copy of 1 is positive. In order to consider only the positions containing 1, collapse the list by incorporating all copies of —1 between two copies of 1 into the later 1. Including a final 1 and viewing cyclically, for example [-1,-1,-1,1,1,-1,1,1,1] becomes [—2,1,0,1,1]. When there are r positive partial sumsstarting from a position, we don’t care about the last one, since it ends at the (n+ 1)th of the n copies of 1 in the resulting linear list. Hence the linear list has r — 1 copies of 1 that are instances of the ith copy of 1 preceding the ith copy of —1. By part (a), each cyclic arrangement yields one 2n-list on which X has value r —1, for 1 <r<n+1. Overall cyclic arrangements weobtain all the 2n-lists, in groups that contribute equally to each event X = /. Hence X is uniformly distributed.

1.3.47. A function f: [n] — [n] is a parking function if and only there exists a permutation o of {n| such that f(i) < o(i) for alli. Here f is defined to be a parking function if drivers 1 through n whoin orderstart looking for parking at spaces given by /f(i) for driver i are all able to park in spaces 1 through n. The condition is obviously necessary. If f is a parking function, then

let o(i) be the location of the space in which driver i parks. Since all drivers park, o is a permutation of [n]. Since a driver cannot park in a

space before s/hestarts looking, f(i) < o(i) for alli. For sufficiency, we use induction on n; the statementis trivial for

n= 1. For n> 1, let o be a permutation of [n] such that f(i) < o(i) for alli. Driver 1 parks in space f(1). We map the remainderof the process into an instanceof the process on [n—1] by eliminating space f(1). Define

Section 1.3: Applications

f’: [n-1] - [n-1] by letting f’(i) = f(i+1)—e, wheree = Oif f(i+1) < f(1) ande = 1if fi +1) > f(1). Also define o’ by o’(i) = ofi+ 1) -€’, where ¢’ = 0 if o(i+ 1) < o(1) and &’ = 1 if o(i+ 1) > o(1). By eliminating 1 from the domain and o(1) from the range, o’ is a permutation of |[n—1]. To prove f’(i) < o’(i), observe that the only difficulty would be if o’(i) = o(i+1)—1 but f’(i) = f(it+1). However, this requires f(i+1) < f(1) and o(i+1) > o(1). Since f(1) < o(1), inthis case we have f(i+1) < o(i+1)-2 and there is enough room to absorb the decrease. By the induction hypothesis, the remaining drivers can park on the adjusted board. Returning to the original process, those who parked in

positions from f(1) ton—1 under f/f’ park in positions from f(1)+1 ton. 1.3.48. The numberofparking functions on [n] is (n+ 1)"~+. Add a parking place n + 1 and consider functions f: [n] — [n+ 1]. Driver i starts looking for parking at space f(i). Arrange the spacescyclically. If Driver i looks at n andit is full, then n+1 is considered, and then Driveri starts looking at space 1. Hence all drivers will park, and one spacewill beleft open. If there is a failure under the original problem, then space n + 1 will be filled. Hence the number of parking functions is the numberof functions in the cyclic problem such that space n + 1 is left open. Whenthe parking procedureis treated cyclically in this way, we can group the functions in sets of size n + 1 under rotation of the image. In particular, if function f leads to a parking vector a with Driver i in space

a;, then adding 1 (modulo n + 1) to each f(i) yields a new function f’ where Driveri will be parked in space a; + 1 (modn +1). In the resulting group of n + 1 functions, exactly one will be a parking function. Hence

the numberof parking functions is (n+ 1)"/(n + 1).

Chapter 2: Recurrence Relations

2. RECURRENCE RELATIONS ©Douglas B. West

2.1. OBTAINING RECURRENCES 2.1.1. The numbera, ofwaysto tile a 2-uby-n checkerboard with n identical dominoessatisfies An = An—1 + An_2, With ay = a, = 1. The rightmost column can be covered with one vertical domino (there are a,_; such tilings) or with two horizontal dominoes that also cover the column next to it

(there are ap_2 such tilings). 2.1.2. The number a, ofpairings of 2n people satisfies a, = (2n — 1)an-1, with ag = 1. To form a pairing, the mate of the person numbered 2n can be chosen in 2n — 1 ways. No matter how this is chosen, there are a,—1 pairings of the remaining 2n — 2 people to complete the pairing of all 2n. 2.1.3. The numbera, of regions in the plane formed by n linesin the plane such that r are parallel and no three meet at a point satisfies an = an-1 +n forn>r, with a, =r+1. After the initial r lines forming r+ 1 regions, adding the nth line crosses n — 1 earlier lines. These crossing cut the line into n sections, each of which splits a region into two regions. Thus An = QAn-1 +N.

2.1.4. The numbera,of binary n-tuples in which every run has odd length is 2F,, where F, is the classical Fibonacci number. Note that a; = ag = 2. For n > 3, there are a,_; such binary n-tuples in which the last bit isa

run by itself (delete the last element) and a,_» such binary n-tuples in which the last run has length at least 3 (delete the last two elements). 2.1.5. The number of symmetric 1, 2-lists with sum n is Fave when n is odd, Fyjo41 when nis even. When n is odd, pairing terms from the beginning and the end leaves a 1 in the middle. The list before the middle 1 determines the full list and sums to (n — 1)/2. Since F,, is the total numberof 1, 2-lists with sum n, the answerhereis thus Fn-1)/2Whenn is even, we can use a list with sum n/2 for the first half and reflect it for the second half, or we can have a 2 in the middle and reflected lists around it that have sum n/2 — 1. Hence the answeris Fyjo-1 + Fiyo, which equals Fy/241-

Section 2.1: Obtaining Recurrences

2.1.6. Growth of a club, with size a; at time t. Letting m; and w; be the numbers of men and womenat time ¢, respectively, we are given m;4, = Ww; and Wi41 = mM+ w; for t > 0, with mp = 1 and wo = 0. Substituting m; = w;_; into the equation for w yields wi11 = w;y_-1+u; fort > 1. With wo = 0 and w; = 1, we thus have w; equal to the classical Fibonacci number PF+. Next m; = uw; = F;-1. Together, a; = m+ w; = Fy + Fy= Fes = Ft. 2.1.7. If (a) satisfes an = An—1 + An—2 + Anz for n > 3, then an < 2”? for n> 2ifa;=1fori€ {1,2,3}, anda, < 2” ifa; =ifori € {1, 2, 3}.

If a; = 1 fori € {1, 2, 3}, then a4 = 3, soa, < 2”? for2<n< 4. For

n> 5, inductively a, < 273+ 2744275 =Qr-25 4344) <2", If a; = i fori € {1,2,3}, thena, < 2” forn < 3. For n > 4, induc-

tively a, < 27142724273 = a(S +445) <2”.

2.1.8. Recurrences for (or)/(})- Let an, = (o7)/(;). Note that a, = 1 and ax, = 1. With these as initial conditions, we have _ (i _ oh)(2n—2k+1)(2n—2k+2) __ on-2k+1

Ank = (C) ~

_ 9) _

G)GEDaNm=eI)

BRT an -.-1 for k > 0 and

oR)(2n—1)(2n)(n—k+1)

nk (?) ~~ (1)\n(Qn—2k+1)(2n—2k+2)

-On-1

2n—Z+1 Qn-1,z forn>k.

2.1.9. Letting D, count the derangements of |n| and E,, the permutations of [n] with exactly one fixed point, D, — E, = (—1)". Note that E, = nD,y_1. Using the derangement recurrence, for n > 2 we have D, — E, = (n — 1)(Dn-1 + D,-2) — nD,-1 = —|Dn-1 — (n — 1)D,-2].

Letting a, = D, — En, we thus have ay = —ay_; for n > 2. Also, ap = 1 and a; = —1. Thus a, = (—1)”, by induction on n. 2.1.10. There are (n + 1)! diagrams on binary n-tuples with arcs joining unequal bits such that each bit is the left end of at most one arc. Let g(n)

count the diagrams onn bits. We obtain the recurrence g(n) = (n+1)9(n— 1), from which a proof by induction yields g(n) = (n+ 1)!, since g(1) = 2. Consider a diagram on n bits. Removing the leftmost bit and any arc emanating from it leaves a diagram on n-—1 bits. Each diagram on n-—1 bits arises in n + 1 ways, since when one vertex is added to theleft of the others, the diagram is completed either by adding an arc from it to another vertex (in n—1 ways, with each determining the label of the new vertex) or by adding no new arcs and labeling the new vertex 0 or 1 (two

more choices). Thus g(n) = (n+ 1)g(n — 1).

Chapter 2: Recurrence Relations

2.1.11. For fixed r, the numbera, oflists of n coin flips with r headssatisfies an = ="-ap-1 for n > Tr, with a, = 1. Considerlists of r heads and n-r tails in which onetail is marked. Such lists can be obtained by marking

one tail ina list of r heads and n —r tails in (n—r)a, ways. Alternatively, they can be obtained from lists of r heads and n —r — 1 tails by inserting

a markedtail in na,_; ways. Thus (n —r)an = nan_1. Of course, it is easy to compute a, directly: just choose the positions for the r heads. Thus a,, = (”) 2.1.12. System of recurrences to count binary n-tuples not containing the consecutive list 011. Let a, be the total numberof such lists, with b,, ending in 0, c, ending in 01, and d, ending in 11. Initially, (a1, b,,¢1, d1) = (2,1,0,0). For n > 2, we have a, = bn +n + dn, Dn = An—-1, Cn = bn-1, and dn = An—-1 — bn-1 —Cn_-1. These recurrencesare not valid at n = 1, because lists counted by c, and d, require at least two positions. Substitution leads to an = An_1 + An_2 + (An_-1 — An_2 — An—-3) = 2An-1 — An—3, With (ag, a1, ag) = (1, 2, 4). This can also be obtained directly, since any list of length n—1 can be extended in two ways except the ones ending in 01, and the numberof thoseis a,_3. 2.1.13. Schroder paths of order n with 1 or n— 1 upruns. Paths of order n run from (0,0) to (2n,0) in the first quadrant using steps in

{(1, 1), (2,0),(1,-1)}.

Record these as U (up), H (horizontal), or D

(down). An uprun is a maximal segment of Us. One Schréderpathof order n has no uprun, and one has n upruns. Let a, and 6b, be the number having one uprun and n—1 upruns, respectively. We derive twofirst-order

recurrencesfor (a) (they have the samesolution) and onefor (b). Qn = 2an-1 +n for n= 1, with ap = 0. The one path of order 0 has no uprun. For n > 1, let P be a path of order n with one uprun. If P ends with H, then therest is a path of order n — 1 with one uprun; there are a,-1 such paths. Otherwise, P ends with D. If the uprun in P has length at least 2, then deleting one U and the last D yields a path counted by Qn—1 (since P cannot return to the horizontal axis before the end without making another uprun). Also, each path counted by ay_; yields one such path (inverting the map) by lengthening the uprun and appending D. The remaining paths end in D and have one uprun of length 1. Such P consists of one U, n—1 copies of H, and the final D. There are n positions to place the U among the Hs to form P. Thus a, = 2ay,_1 +n. Qn = An-1 + 2” -1 forn=>1, with ay = 0. The path of order 0 has no uprun. For n > 1, Let P bea path of order n with one uprun. If P begins with H, then the rest has order n — 1 and one uprun; there are a,_, of these. Otherwise, P begins with an uprun of some length 7. The rest consists of 7 copies of D and n — j copies of H in some order. Summing

Section 2.1: Obtaining Recurrences

over j yields yj=1 (”) choices; the sum is 2”—1. Thus a, = a,_-1 + 2”-1. b, = bn-1+2n-1 for n => 1, with bp = 0. The one path of order 0 has no uprun. For n > 1, the numberof paths counted by 6, that end UD is b,_1; we consider the others. Having n — 1 upruns requires an arrangementof n—1 each of U and D and one H, orn each of U and D. If the path ends DD and thereis an H, then the earlier portion consists of n—1 Us, one H, and n —3 Ds, with no two Usconsecutive; there are n — 2 choices for the position of the H among thelist of Ds. If the path ends DD and thereis no H, then the earlier portion consists of n Us and n — 2 Ds, with two Us occurring consecutively once; there are n — 1 ways to choose which uprunhas length 2. The remainingpossibilities are ending H or HD. Each would be preceded by n — 1 copies of U separated by Ds, in one way. Hence the total numberof these paths is 2n — 1, and bn = by-1 + 2n-1.

2.1.14. Binary (n — 1)-tuples with no consecutive 1s. a) Recurrence for an, the numberof binary (n — 1)-tuples with no consecutive 1s. The empty string and singletons yield a; = 1 = Fand a, = 2 = F.. A final 1 must be preceded by 0, but a final 0 can be preceded by 0 or 1 with no restriction on other positions, so a, = An_2+Q@n_ for n => 2. b) Bijection from the set of 1,2-lists with sum n. Since the n units of the sum become n — 1 binary positions, we want each 1 or 2 in the sum to contribute 0 or 1 bits, except that one bit will be lost. Convert each 1 to a O and each 2 to a 10, but drop the last bit, since it is always 0 and provides no information. The 0 following each 1 ensures that there are no consecutive 1s, the resulting length is n—1, and the processis reversible. 2.1.15. Multiple images from two panes ofglass. We have the initial conditions ay = 1 and a; = 2 (or a; = 2 and ag = 3). Beyond this, consider the light as it emerges after the nth reflection. The last reflection could have been from the opposite edge or from the middle boundary. If from the opposite edge, then instead the light could pass through and be an image with n — 1 reflections; conversely, such paths could add a reflection at that boundary. Thus there are a,_; imagesof this type. If the light is last reflected from the middle, then immediately before that it was reflected from an outside edge. Eliminating these tworeflections transformsit into an image with n — 2 reflections, and again this is reversible. Thus the number of images that last reflect from the middle is @,-2, and the recurrenceis a, = An_-1 + An_2. 2.1.16. The numberof cycles in the square of the directed n-cycle is F, + F.,-2 + €, where F,, is the nth adjusted Fibonacci numberand¢ is 1 if n is odd, 0 if n is even. When n is odd, one cycle wraps around twice by steps of length 2. All other cycles go around oncebysteps of length 1 or

Chapter 2: Recurrence Relations

2 with total length n. We count separately the cycles that contain a fixed element v and those that do not. The cycles containing v correspond to the 1, 2-lists of length n, of which there are F’,,. The cycles not containing v skip vu by an edge of length 2 and complete the cycle viaa 1, 2-list of length n — 2. Hence the answeris F,, + F,_2, plus 1 if n is odd. 2.1.17. Identities for adjusted Fibonacci numbers (with Fy = F, = 1).

a) F,, =", ("""). Inductive proof. For i > n—i, the binomial coefficient is 0, so the sum

is )so ("""). When n € {0, 1}, both sides equal 1. In the induction step, n> 1, We use the recurrencefor F,,, the induction hypothesis for F-4 and F,,-2, and the binomial recurrence. The resulting computationis

F, = Fy+ Fr» = 2 i>0 ("F) + Diso (F") — ("5") + Dist (") + Dist oy — (9) + Dist (";") = Lizo (";"). Combinatorial proof. Again F,, counts the 1, 2-lists with sum n. Such a list with i 2s has n — 27 1s. Hence it has n — i terms, and choosing the positions for the 2s specifies it. Summing over the possible numbersof 2s countsall the lists. b) 1+ ng Fi = F40.

Inductive proof. Basis: 1 + Lies= =1+1=2=Fy,. Forn>O0, we compute 1+ )°"fi = =14+0%5'F)+F, = =Fi4i+F, =14+Fyi2. The induction step uses only one previous instance. Combinatorial proof. The right side counts the 1, 2-lists with sum n+ 2. One such list has no 2, counted by the term 1 on the left. The remaining lists have at most n 1s. The numberof lists that end with n—i 1s after their last 2 is the numberof lists that sum to i in the portion before that 2, which is F;. Summingover i counts theselists. 2.1.18. Identities for adjusted Fibonacci numbers (with Fy = F, = 1). a) an Fy, = Fonvt for n= 0.

Proof 1 (induction on n). For n = 0, both sides equal 1. For the induction step, A

-la

Fonsi = Fon + Fon-1 = Fon + Ying Poi = Yijeo FaiProof 2 (combinatorial proof). The right side counts the 1, 2-lists with sum 2n + 1. Every such list ends with some numberof 2s. The lists that end with exactly n —i 2s begin with a 1, 2-list summing to 2n + 1 —

2(n —i)—1, followed by a 1. Since 2n + 1 — 2(n —i) — 1 = 2i, the number of these lists is F5;. Summing over i from 0 to n countsall the 1, 2-lists, grouped by the numberof 2s at the end.

Section 2.1: Obtaining Recurrences

b) ye ‘(-1)' Poni

= F,,-,.

Grouping the terms in pairs and

applying part (a) yields an ‘(-1)'F2n-i = yO (Fan-2) —2n-2j-1) =

as Fon-2j-2 =

6 Foy = Fon-1.

2.1.19. The classical Fibonacci number F,, counts the compositions of n using odd parts and the compositions of n+ 1 using parts greater than 1. Let a, be the numberof compositions of n using only odd parts, and let b, be the number of compositions of n using only parts greater than 1. Note that ap = bb = O and a; = 5; = 1. A composition of n into odd parts has as the last part a 1 or an odd number greater than 1. There are a,_; compositions of the first type

(delete the last part) and aj,_2 compositionsof the second type (reduce the last part by 2). Hence a, = a,_1 + Apn_2 for n > 2. A composition of n into parts greater than 1 has as the last part a 2 or a numbergreater than 2. There are 6,» compositionsof the first type

(delete the last part) and b,_1 compositions of the second type (reduce the last part by 1). Hence b, = b,_1 + bn_2 for n> 2. 2.1.20. Cassini’s Identity: F? = F-1Fpai + (-1)", forn> 1. Inductive proof. For n = 1, we have fF? =1=2-1=F)F,+(-1)!. For n > 1, the Fibonacci recurrence and induction hypothesis yield Frat PFn-1 + (—1)” = (F', + Fy-1)Fn-1 + (—1)” = FFn-1 + F,-2F, + (—1)""? + (—1)” =

"(F 1+ F,_2) =F?

Combinatorial proof. Consider pairs (A, B) of 1, 2-lists with sum n.

We modify a pair (A, B) into (A’, B’) with sums n—-1 andn+1. If Aor B has a1, then let i be the least index ofa 1. If A; = 1, then movethis 1

from A to B (at position i) to obtain (A’, B’). If A; = 2 and B; = 1, then form (A’, B’) from (A, B) by exchanging the ith entries, so A; = 1 and B; = 2. In each case, the sums aren—1andn+ 1. If (A’, B’) hassums n—1 andn+1, and A’ or B’ containsa 1, thenlet i be the least index of a 1. If Bj = 1, then the (A’, B’) arises via the map above only from the pair (A, B) obtained by moving that 1 to position i in

A. If B; = 2 and A; = 1, then it arises only by switching the entries in position i. Thus the mapis a bijection on the set of pairs containing a 1. If nis even, then the pair (A, B) where neither has a 1 is an extra pair that does not get mapped, and all (A’, B’) must havea 1. If n is odd, then in the target set there is a pair (A’, B’) having no 1 that is unreached by

the map, and all (A, B) contain a 1. Hence the excessof the (n, n) case over the (n—1,n +1) case is (-1)”.

Chapter 2: Recurrence Relations

Explanation of 64 = 65. Form an F,,-by-F,, square. Cut it into two rectangles using F,, = F,,_; + F,-2. Cut the long side of the larger rectangle using the samerelation, and cut the smaller rectangle diagonally. This produces four pieces, each with a side of length F,_2. Combining these in pairs makes two right triangles with sides F,_; and F41. No, these are not triangles. The four pieces sum to area F?, but the two triangles sume to area Fr? —(-1)”. The pieces appear to form two triangles because a = fa | The ratio rapidly approaches (14V5)2,

2.1.21. d’Ocagne’s Identity: Fy,F'm = Fy—1F-m+1 + (—-1)"Fmn for m > n. Inductive proof. We use induction on n. For n = 1, FyFy = Fy = Frnvi — Fri = Piya Pinst + (-1)" Fin—n-

For n > 1, we compute Fy-aPFinst — Fy-aFm + FyaPFm1 = FoiFm + FoF'm + (-1)""Fy n-1) = FFmn —_ (-1)”Fin—n

Combinatorial proof. Let A and B be 1, 2-lists with sums n and m, respectively. Let i be the first position of a 1 in eitherlist, if there is one by the time sum is reached. If in A, shift it to position i in B; if in B,

exchange the ith termsof A (a 2) and B (a1). This produces A’ with sum n—1l1andB’ with sum m+ 1. If there is no 1 by the time sum n is reached, then n is even, and A consists of n/2 copies of 2, while B is one of F,_,, lists consisting of n/2 copies of 2 followed by a1, 2-list with sum m-—n. All other pairs (A’, B’) with sums n—1 and m+1 are generated exactly once. This completes the proof for even n. Whenn is odd, the mapfails to generatethe F,,_, pairs(A’, B’) where A’ consists of (n — 1)/2 copies of 2 and B’ consists of (n + 1)/2 copies of 2 followed by a 1, 2-list with sum m — n are unreached. All other pairs are generated exactly once.

2.1.22. Puron = PnP t+ Pm-i1Fn-1 form,n> 1. Inductive proof. We prove by induction on n the claim that the formula holds for all m. The basis step is n = 1. Since Fo = F, = 1, the

Section 2.1: Obtaining Recurrences

formula reduces to Fin+1 = Fim + Fm-1 when n = 1, which is true for m= 1 by the Fibonacci recurrence. For the induction step, consider n > 2. We use the Fibonacci recurrence twice and the induction hypothesis once to compute FFim + Fn1Fim-1 =F,i1F,+F -9Fim + Fy-1Fm1 — Py1Fmsi + Fy-2F'm — F(n—1)+(m+1) — Frm

Combinatorial proof. Let A; be the set of 1,2-lists with sum k. The left side of the identity is |A,+,,|. These lists can be distinguished by whether the partial sums include n or skip from n — 1 ton+1. Theformertype consist of an element of A, and an element of A,,, concatenated. The latter consist of an element of A,-; and an elementof A,,-; with one 2 between them. Thusthe right side also counts An+m. F,_, divides F;,-1. We use induction on k; the statementis trivial

for k = 1. For k > 1, part (a) yields Fyn-1 = Fan Fn-1 + Fy_tyn-1 PFn-2. By the induction hypothesis, F’,_; divides both terms on the right and hence also F;,_;. Since F,, = F,41, where (F) is the classical Fibonacci sequence, we conclude that F,, divides Fz,.

2.1.23. Catalan’s Identity: F? — Fy-aF5+ = (-1)°“F? fora <b.

With c = b—a, werewrite the identity as F?,, — F.Fesoq = (-1)°F?. Applying Fiona = Fins Prot t+ FmFn (Exercise 2.1.22) to Fe+g and Fosaq, and then to Fo,4; and Foe,, we compute

Fo. — FeFes2a = (FeFa+1 + Fe-1Fa)? — Fe(FeFati + Fe-1F2a) = F?(F?,, — Foasi) + F2.,F?2 + FFe-1(2Fa+1Fa — Foa) = —F?F? + FF? + FoF (FatiFa -— FoF o-1)

= Fi(Fe_, — Fi + F.F.-1) = Fj(Fi4 — FeFe-2) = (-1)°F% In the last step we used Cassini’s Identity F?, = Fy—1Fmsi +(-1)™1. 2.1.24. Vajda’s Identity. The adjusted Fibonacci number F,, counts the 1, 2-lists with sum n. We set F_, = 0 to extend the recurrence. a) For r < s, a combinatorial proof of F,.F,-, — F,.-,F's = (—1)" F._,-1. For clarity, we just write a, = F,,. The numberof lists with sum r + s — 1 that reach sum r witha 1 iS A;_1a;_1. These are the lists having a partial sum at r — 1 that do not follow it with a 2; also the lists having a partial sum at r that do not reach it with a2. Thus QAr—-1QAs — Ar—-1QAs—2 = Ar—-1QAs—1 = ArAs—1 — Ar—2QQs-1.

Rearrangingyields a,_1@s; — a,as_1 = (—1)(@,_2@s_1 — A;_1Qs_2). Iterating

r —1 times (and using a_; = 0) yields a,_jas — a-@s—1 = (—1)""!as_p-1.

Chapter 2: Recurrence Relations

b) Forr,s,t € Nwithr < s, acombinatorial proofof F.4#F.-FFeat = (-1)""!F,_,F,_--1. Consider a,+;a; — a;ds4;. Among the lists with sum r+s+tcounted by the two products, those not counted by both are those in the first set that do not break at r and those in the second that do not break at r+ t. After canceling lists counted by both products, Ar+tAs — Ap Ast+t = Arp—1 QAt-1 As — Ap At—-1 As—]1 _ _ r-1 — at-1|A;-14s ~ a;As—1| _ (—1) Qt-14s-r-1-

ce) Vajda’s Identity for i, j,n € N: FnsiFn+j — FnFn+i+; = (—1)"FiF;. Since F,,_, = F,, for all n, part (b) becomes Fritsi P41 — Frat PFsstti = (Hl) FFsr. Now set r= n-—1,t =i, ands = n+/j/-—1 to rewrite this identity as Vajda’s Identity. 2.1.25. With classical Fibonacci numbers extended to negative indices via the recurrence, F_, = (—1)""'F, forn €N. Since Fo = 0 and F; = 1, we set F_, = 1, sothe claim holds for n = 0 and n= 1. Weproceed by induction.

For n > 1, we compute F_p = F_(,-2)—F_(n—1) = (—1)""' Fn-2—-(- 1)"Fn-i = (-1)" 1 (Fh-2 + F,-1) = (—1)""'F,.

2.1.26. Every positive integer n has a unique expression as the sum of a set of nonconsecutive positive Fibonacci numbers. A set of nonconsecutive positive Fibonacci numbersis not allowed to use both 1 and 2, so 8 cannot also be expressed as 5+2+1. We view this restriction as starting the available values with F. We are given ar Fy, = Foxx, and 1 + yo F,; = F429. Subtracting

the first from the second yields 1 + ar Fy;-1 = Fo,. Thus ye Fy; < Fox41 and yy Foi-1 < Fox. We use induction on n. The numbers 1, 2,3 are Fibonacci numbers, and 1+2 is not allowed as an expression of 3, so the claim is valid for n < 3. For n > 4, let F, be the largest Fibonacci numberthat does not exceed n. If we do not use F’; in summingto n, then greedily the largest sum thatis allowed without exceeding n is less than F;, by the computationsabove. Hence we must use F’. If n = F, then we have obtained the unique expression. Otherwise, let n’ = n-—F;. Sincen < Fj4; = F, + Fi-1, we have n’ < F)_;. By the induction hypothesis, n’ has a unique expression as the sum ofa set of nonconsecutive Fibonacci numbersless than F)_;. Combined with F), we have the unique representationof n. 2.1.27. Lucas numbers satisfy Ly, = Fy, + Fni1 and Ly, = Fo,/F,. The definition is L, = Lyj_-1 + Ln_-2 for n => 3, with L; = 1 and Loy = 8.

Section 2.1: Obtaining Recurrences

Wefirst prove L, = Fy-1 + Fn+1. The basis is L} = 1 = Fo + Fe and Ly = 3 = F, + Fs3. For the induction step, Ln = Ly-1 + Ln-2 = Pn-g + Pn t+ Pn-3 + Pri = Fai + Fos.

For the second claim, we prove F,L, = Fo,. Note that F,-1F, + FF11 = Fon, since FoF,-1 + Fy»-1F, = Fen-1, which holds because 1, 2-lists summing to 2n — 1 may or may not have n — 1 asa partial sum (that is, a breakpoint). Hence F,,Ly = Fy(Fp-1 + Fnii) = Fon. 2.1.28. The numbera, ofcircularlists of n bits with no consecutive Is (fixed positions) is F’,_; + F,,,. Let 6, be the numberof linear n-bit lists having no consecutive 1s. Each such list corresponds to a binary n-tuple com-

posed of segments 0 and 01, or sucha binary (n—1)-tuple with 1 added at the front. Hence the numberof these is the numberof 1, 2-lists summing tonorn—1. Wecompute b, = F,+Fy-1 = Poet = Foreo.Suppose n = 8. Good n-bit circular lists ending in 0 may have any good linear list in the first n — 1 positions; there are b,_; of these. Good n-bit circular lists ending in 1 must have 0 in positions 1 and n—1. Hence they arise from good (n — 3)-bit linear lists by putting 0 at the beginning and 01 at the end; there are b,_3 of these. Hence ay = bn_-1 + bn-3 = Fray + Fn-1. 2.1.29. Partitions of |n| into same-difference arithmetic progressions. Fix n,de€Nwithd <n. The numberofpartitions of |n] into arithmetic progressions with constant difference d and length at least 1 is 2”-¢. The values 1,...,d must lie in different blocks. After that, each successive element i can start a new block or extend the block containing i — d. The numberofpartitions of {n] into arithmetic progressions with constant difference d and length at least 2 is Fr Fé where n = kd +r with

0<r<d-1. First consider d = 1. There is no such partition of [1] and one of [2]. For n > 2, such partitions of [n] with d = 1 arise by adding n to the last block in such a partition of [nm — 1] or by adding the block {n—1,n} to such a partition of [n— 2]. By induction, the numberof such partitionsof |n] is F,-1. For d > 1, partition [n] into congruence classes modulo d. There are r classes of size k+1 and d-r classes of size k. Each partition is obtained by combiningpartitions of the congruence classes, chosen independently.

2.1.30. For n €N,let an = Yh, ger, let bn = Ve [A(Z)I*, and let Cc, = 2nry k odd (")z, Prove that a, = 6, = c, for all n, by showing that each sequence satisfies 2nx, = nx,_1 + 2. Since ay = bo = Co = 0, it suffices to show that the sequencessatisfy

the samefirst-order linear recurrence. For(a),

Chapter 2: Recurrence Relations _ n 1 n(2an — An-1) — n( Dye kor-e1 ~

nm-l 1 _ 1 _ Luk=1 er | = Naot = 2

For (bd), n—-1

n(2by — bn—1) =2+ (n—1)! Z

[2(k —1)\(n —&)! — n(k-1)!\(n-1-4)]

941 |Pa_ ny ay Sa _1-pyl=2 =

(n- 1! | 2

(70

»,

The summationfor c, can be extended to all odd k, since () = 0 when r>m. Thus n

N(2Cn — Cyr-1) = Qn-2

[

1f/n

1f{n-1 |

n(n-1

» i(;) ~ 3 i( k odd k odd

}

gn-l

Qn-2 k», (; ) gn? » (;' ~ pre =? odd odd 2.1.31. Partitioning the n-by-n grid. a) Whenthe edges of the n-by-n grid are cut into 2n — 2 zig-zag paths

from upperleft to lower right, there are Wi F3,,1 ways to choose a subset without two consecutive edges on any path. Incidence vectors for sets of nonconsecutive edges along a path of length 27 correspond to binary 2/tuples with no consecutive 1s. Sucha k-tuple ending with 0 or 01 satisfies the same conditionsfor the earlier portion. Hence the numbera, of such binary k-tuples satisfies the recurrence a; = az_1 + az_2, With ag = 1 and a, = 2. This yields a, = F,,4;. Since the decomposition uses two paths of each even length from 2 through 2n — 2, and the choices on all the paths are made independently, the claim follows.

b) There are Ti F3,, ways to partition [n] X[n] into sets forminglattice paths. Since a vertex v of the grid goes into exactly one lattice path, at most two neighborsofv lie in its group. When two neighbors do appear, the two resulting edges cannot lie in the same zig-zag path as considered in part (a), by the lattice path requirement. Avoiding such pairsis also sufficient for edges incident to vertices in the sameset of the partition to combineinto a lattice path. Hence the ways to form a partition into lattice paths correspondbijectively to the selections of edge subsets counted

in part (a), and the answer formulas are the same. 2.1.32. Deterministic prefix reversals end after fewer than F.,flips. Our pile is a permutation of 1 through n. When the top card is m, we reverse

Section 2.1: Obtaining Recurrences

the first m cards. The largest card that ever appears on top goes immediately to its proper position, and nothing can make it come up again. The largest card that appears later likewise can only appear once later. Thus inductively the process always stops at some point with 1 at the top. Let a; be the maximum numberofflips given that at most k distinct cards appear at the top during the process. Let 7' be the numberof the flip on which the largest card m that appears reaches the top. Next it moves to position m and never returns. Afterwards, at most k — 1 different cards can appear, so there are at most 1+ a;_, flips after T’.

Before flip 7’, neither m nor 1 reaches the top, and neither does the card that starts in position m; call it 1. Switch cards 1 and m in theoriginal stack S to form a stack S’. The moves before T' will be the same in S and S’, meaning that the card reaching the top on corresponding flips is the same for both. Thus 1 reaches the top in T' flips for S’. If

1 #1, then / and m neverreach the top in flipping S’; thus T < a,z_2 and Ap < Az_g + az_1 + 1 in this case. If 1 = 1, then k — 1 values may reach the top in flipping S’, but now the flip after flip T in stack S brings 1 to the top, and in total there are at most a;z_; + 1 flips. Thus in each case ap < Ap-2 + az_-1 +1. Since a, = 0 and ag = 1, we obtain a; < F, -—1 by induction. Finally, at most n different cards appear at the top when processing a stack with n cards. 2.1.33. Generalized Fibonacci numbers. Let an+1 = An + Qn_-1 for n => 2, with a; and dzfixed.

a) Qn+2an + (-1)"T = a?,,, where T = aga; — a3. Applying the reCULTENCE, An42An — A7,, = —(Gn+1An-1 — a2). Inductively, ans2an — a7,, =

(—1)”"*(asa,—a3). Letting T = aga,—a3, we have ay+2a,+(-1)"T = a?,,. b) dna1 = Fn-101+ Fae, where (F) is the classical Fibonacci sequence. Since F'; = F2 = 1, the claim holds by definition when n = 2. For n > 2, Qn+1 = Ant+QAn-1 = F201 4+ Fy_1det+Fy_-3014+ Fy_2a2 = F,-1a,+Fy-2d2.

2.1.34. The Fibonacci numbersof order ¢ are defined by FO = 2”lif 1<n<t, and FO = vit Foi The binomial coefficient of order¢, C.,

counts the n-tuples with entries in {0,...,¢—1} and total sum k. a) FY counts binary (n — 1)-tuples with no t consecutive 1s. Let an,

count this set. For n < t, all binary (n — 1)-tuples have no ¢t consecutive 1s, soa, = 2”! forl<n<t. Forn >t, binary (n — 1)-tuples with no t consecutive 1s end with i 1s preceded by a 0, for some i with O <i < t—1. Thus a,+ = yi An-i,z- The initial conditions and recurrence are the same as for Fo. SO Ant = FO. b) co, _ co

n,(t-1)n—k

and CO. _ ye Cc

nl ki whenn > Oand0 <

Chapter 2: Recurrence Relations

k <n(t—1). If (x1,...,x,) has entries in {0,...,¢-—1} and sum k, then (¢-—1—x,,...,#-—1-—~,) has entriesin {0,...,¢—1} and sum (t¢—1)n—k. Repeating the map inverts it, so it is a bijection, and oe = Ch t-1)n-kFor the second statement, group the n-tuples counted by om, according to the value in the last coordinate. There are Cc) n—-1,k-i wherethe value is

i, with0 <i<k,soC?,=y7,C%, ,,.

ce) F= > i>0 c®,; We use induction on n. For 1 < n < t, we have FY = 2”-! by definition. We claim also yi>0 CO. ,= 2"! forl<n<t. When wecount (n — i)-tuples with sum i, having n < timpliesi<n<t (since n > 0 there is no contribution with i = n), so thereis no constraint on the entries used, since the total is already less than t. Over alli, the lists are thus formed by deciding, for each of n — 1 units after the start, whetherto add to the current part or start a new part. For n > t, we set r=i+j-—1 ands = j —1 and use the induction hypothesis to compute t t t Fy — yi FY)|= — Y= 1Dui>0 Ce —1,l — = Yisodss0 Cet, r-s = Vso Cer

d) Combinatorial proof ofpart (c). Given a binary list of length n — 1 with no ¢ consecutive 1s, add a single 0 at the beginning to reach length n. Then convert each 0 followed by a string of 7 1s into the integer 7. If the original list has sum 7, then the resulting list has length n —i with sum i. Since the original list has no t consecutive 1s, the image has no value greater than t — 1. The process is reversible, expanding each positive integer i into a O plusi 1s and deleting the initial 0. Overall i, this completes the bijective proof. The argumentspecializes to the sum for the Fibonacci numbers in terms of the binomialcoefficients. 2.1.35. Combinatorial proof that the solution to an = 2ayn_1 + An_2 for n = 2, with ay = land a, = 2,is ») ee, summedoverall nonnegative integer

triples (i, j,k) such thati+ j+2k =n. Proof 1. We show that a, is the number of Delannoy paths from the origin to the line x + y = n. For n = 0, there is one path with nosteps, and for n = 1 wecan step right or up. The recurrence holds because with n > 2, the last step can be horizontal, vertical, or diagonal. Directly, a path reaching the line x + y = n consists of some number i of horizontal steps, 7 of vertical steps, and k of diagonal steps. Once i,j,k withi+j+2k =n arefixed, the path is specified by arranging the steps in any order. The numberof orders in which they can be arranged

is the multinomialcoefficient(, *,). Proof 2. Let c, be the number of ways to park Rabbits, Cadillacs,

Section 2.1: Obtaining Recurrences

and Metrosto fill a parking lot of length n, where Metros and Rabbits have length 1 and Cadillacs have length 2. Since the last space may be occupied by any type of car, and theremaindercanbefilled by any list with the remaining sum, c, = 2c,_1+¢y_2 for n > 2. Also co = 1 and c, = 2, since when n = 1 we can use either short type. Hence (c) is the sequence determined by the recurrence. Each list counted by c, uses i Rabbits, 7 Metros, and k Cadillacs, for somei, j,k withi+j+2k =n. The numberof such lists is the multinomial coefficient counting the distinguishable orderings of i Rs, 7 Ms, and k Cs, which equals Sa. Summingoverall such choices of i, 7, k counts

all the possibilities, soc, = + ee te 2.1.36. Given a, = ye, An-c, forn > 0, with ag = landa, = 0 forn < 0,

where c,,...,c, €N,the formula for ay is An = Dri ae1 my , summedoverall nonnegative m,,..., mz such that yy cjm; = Nn. Let p, count the lists of objects of types 1,..., k whose lengths sum ton, where each object of typei has lengthc;. Note that pp = 1 and p, = 0 for n < 0. The sequence (p) satisfies the recurrence p, = an Pn-c, for n > O, since the last object in the list may be of any type. Since they

satisfy the same initial conditions and recurrence, (p) = (a). On the other hand, we computep, explicitly. Each list uses m; items of type i, where )),cjm; = n. For each such choice of mj;,..., mz, the numberof lists using m; items of type i is just the numberof lineararrangements of m; copies of i over 1 < i < k. This is the multinomial coefficient Ca’ 2m ). Thus a, is as claimed. peers ME

2.1.37. If bn; =n!(*), then bnj = Dig (47})bn-1,: for n = 1. Combinatorial proof. With k fixed, n/ (“) counts the (n + 1)-ary ktuples having 7 nonzero positions: just choose the nonzero positions and

fill them with nonzero values. On the otherside, (n — 1)'(*) counts ktuples in {0,...,2—1}* with inonzero positions. To form a list counted by n/ (*) , start with a k-tuple in {0,... , n—1}* having i nonzeropositions, and then choose j — i of the k —i positions having 0 to become positions

having n. Overall i, each of the k-tuples in {0,...,n—1}* with j nonzero positions appears exactly once. Summing over i completes the proof. Algebraic proof. By Subcommittee Identity and Binomial Formula,

0 (Oo) )bn-1,i =

yy(5Y)()(n- 1!

~ (5)

/ = (")n!.

Xi=o (j)(n- 1)’ = ()a +n—-1)

Chapter 2: Recurrence Relations

2.1.38. Combinatorial proofofMoessner’s Processfor generating pure powers by additions. Row 1 consists of the natural numbers. Row j + 1 arises from row j by crossing out every k + 1 — jth entry in row j and taking partial sums of the remaining elements, leaving blanks under the

crossed-out entries. Row k then consists of {n*} (for k = 2 this reducesto >, 2i- 1 = n?). The diagram belowillustrates the procedurefor k = 4. 123 1 3 6 1 4 1

5 11 15 16

6 17 32

7 24

9 33 65 81

10 43 108

11 54

Let a,,; be the number in row j of the nth full diagonal; we prove An,j = n/ (‘ ) by showing that both sides satisfy b,; = I (O75) Bn-1,i. For initial conditions, let a,,9 = 1. This is equivalent to adding a Oth row of all 1s; it still yields the first row as partial sums. The Oth wedgebe all 0

except ay.9 = 1. The initial conditionsfor n/ (‘) are the same: 0/ (‘ ) = dj. To see that {n/ (*)} satisfies the recurrence, let b,,; count the lists

in {0,...,n}* with 7 nonzero terms. Choosing andfilling the nonzero positionsyields b,; = (“)n! . The ith term in the sum counts among these the lists having i entries in {0,...,2—1}. To form suchlists, start with a k-tuple in {0,...,—1}* having i nonzero positions, and then choose j —iof the k —i positions having 0 to becomepositions having n. There

is also a short algebraic proof that )°’_, Can —l1j'= (“)n! , using the Subcommittee Identity and the Binomial Formula.

It remains to show ay,; =

)-/_, (Or) anti for n = 1. Each entry sums

the entry to its left and the entry above it. Thus each wedge behaveslike Pascal’s triangle, but with “inputs” from the previous wedge. We count the times a,_; ; contributes to a, ;. This equals the numberof paths from Qn-1,; to a,,; that move rightward or downwardat each step. Fori = 1, no element is below a,_1,;, so every path from a,_; ; steps first to the right. From there, the paths to a,,,; are lattice paths. They enter the nth wedge in the ith diagonal and end at the kth diagonal, so they take k —i steps. They take 7 —i downwardsteps, so there are ( 3) paths (i = 0 takes more care). This proves the formula for ay,;; setting j = k yields an, = n*. 2.1.39. Recurrence that gives the central Delannoy number dy, when m = n. Let ao.o = 1, and let am, = 0 when m <0 orn <0. Form,neEN,let a

_ mn

{Amn-1+4m-1.n

ifm+nis even,

Am,n-1 + 2Am-1,n

if m+n is odd.

The recurrence for a,,,, is quite asymmetric. Amazingly, an.» = Ann.

Section 2.1: Obtaining Recurrences

Recall that d,,, is the numberof paths from (0, 0) to (n, n) using horizontal steps H, vertical steps V and diagonal steps D. Each path is a string

in the alphabet {H, V, D}. If D occurs k times, then H and V each occur n —k times, and the string has length 2n — k. Since these steps can be in any order, the numberof paths with k diagonalstepsis (77| onanF

Thus dain = Deao ("EJnae)-

Similarly, a,,, is the numberof paths from (0, 0) to (n, n) using steps

of three types: horizontal steps H, vertical steps V, and special steps S that have the sameeffect as horizontal steps but can occur only when reaching a point (m, n) with m+n odd. Each path is thus a string in thealphabet {H, V, S}. If S occurs k times in such a string, then H occurs n—k times and V occurs n times, and the string has length 2n. However, S can occur only in the n odd-indexed positions in the string. Hence the number

of paths with k special steps is (7)(*""). Thus @njn = eg (ZC)Since (7",BY (Pn) = areal), the corresponding terms and full sums are equal.

2.1.40. Derangement recurrence D, = -7_,(k — 1)(7)Dn-z. We use the formula n! = )°7_, (7)Dn-« of Example 2.1.6 to compute

de v(;)Due =Y>M(p}Pe ¥0(p)Das -») ni 1) Pov — —(k-1) — » (;)}Pn- + Dn

k=0 _nin—-1)!—nl+D, =D, 2.1.41. Letting d(n, k) be the numberof derangements of |n| with k cycles, d(n, k) = (n-1)[d(n—-1,k)+d(n-—2,k-1)] forn => 2k (except d(2, 1) = 1) and d(n,k) = Owhenn < 2k ork <0. Theinitial conditions hold because each cycle must have at least two elements. Now suppose n > 2k. In a derangementof [n] with k cycles, let C be the cycle containing element n. If |C| > 2, then omitting n from C yields the cycles of a derangementof [n—1] with k cycles. Since each cycle in a derangement has length at least 2, each derangement of [n — 1] with k cycles yields n — 1 derangementsof this type, since n can be inserted after any element. When|C| = 2, omitting C yields a derangementof n — 2 objects with k—1 cycles. To form such a derangement, choose an element of [n — 1] to pair with n and then use one of the d(n — 2, k — 1) derangements of n — 2 objects with k — 1 cycles on the remaining n — 2 elements. Hence there

are (n — 2)d,,-1 derangementsof [nm] with k cycles in which |C| = 2 Note that summingover k yields D, = (n— 1)(Dyn_-1 + Dy_2).

Chapter 2: Recurrence Relations

2.1.42. D,(n) — D.(n) = n-1, where D,(n) and D,(n) are the numbers of derangements of |n| having an odd or an even numberofcycles, respectively.

We use induction on n. The derangementof [0] has no cycles, which is even. There are no derangements of [1]. Hence the values for n = 0 and n= 1 are —1 and 0, as desired.

The recurrence D(n) = (n — 1)[D(n — 1) + D(n — 2)] is proved by considering whether element n lies in a cycle of length more than 2 or in a cycle with just one other element. In the first case we keep the same numberof cycles; in the second welose one cycle. Thus D,(n) =

(n — 1)[D,(n — 1) + D.(n — 2)] and D,(n) = (n — 1)[D.(n — 1) + D,(n — 2)]. For the difference, we use the induction hypothesis to compute

D,(n) — D-(n) = (n — 1)[(Do(n — 1) — De(n — 1)) — (Do(n — 2) — De(n — 2))] = (n—-1)[(n—- 2) -(n-38)] =n-1. 2.1.43. The number of derangements x of [n]| satisfying the increase con-

dition (x(i + 1) — x(i) < 1 for alli € [n —1]) is (2” — 2)/3 when n is odd and (2” + 2”? — 2)/3 when n is even. Let P, denote the set of permutations of [n] satisfying the increase condition. Given a memberof P,_1, the element n can be added only at the beginning or immediately following n—1. Also, deleting n from a memberof P,, yields a memberof P,,_1.

Hence |P,,| = 2|P,-1|, which yields |P,,| = 2”~+ inductively. Let z be a memberof P,, that is not a derangement. Let i and j be the smallest and largest fixed points of zw. For i < k < j, the inequali-

ties m(k) < m(i) + k-i = kand j = aj) < w(k) +7 —& yield x(k) = k. Since 2(k) # k for k > j, we conclude x(k) < i for k > j, and similarly

m(k) > j for k < i. This yields zm({1,...,i-—1}) = {7 +1,...,n} and m{j+1,...,n})={1,...,i-1}, which impliesi+ j =n+1. Since all entries beforei are larger than i and all entries after j are smaller than j, the only constraints on the ordering with the initial of final segments of i — 1 elements are internal. In particular, each such

segment can be ordered in |P;_;| ways (let |Po| = 1). Summing over the choices for i, we obtain yin |P;-1|° as the numberof permutationsin P, that are not derangements.

The value of the sum is (22!!”/2I-)) + 2)/3. Subtracting this from 2”~1 (the size of P,,) completes the claimedsolution. 2.1.44. Restricted permutations. a) a, = D, + Dn-1, where ay is the numberofpermutationsof [n] with position i not containing i+ 1, for 1 <i<n-—1. Element 1 can go in any position; let A, ; be the set of good permutations with 1 in position /. Consider A,,; with 7 <n. Element i cannot go in position i — 1, for 2<i<jorj+2<i<n, but element 7 + 1 can go in any position other

Section 2.1: Obtaining Recurrences

than the position j filled by 1. Writing element 7 + 1 as 1 and decreas-

ing the higher elements (above j + 1) and higher positions (above j) by 1 establishes a bijection from A, ; to the set of all good permutations of

[x —1]. Thus |A,,;| = @n-1 when j < n. For 7 = n, decreasing the elements 2 through by 1 and keeping the same namesfor the positions establishes a bijection from A,,, to the set

of derangementsof [n — 1]. Thus |A,,,| = Dn-1. Now a, = (n—1)ayn_-1 + Dn_-1. With a, = 1 = D,, + D,-; for n € {1, 2}, for n > 3 the induction hypothesis and derangementrecurrenceyield an = (n—1)[Dn-1 + Dn-2] + Dn-1 = Dn + Dp-1.

b) b, = D, + D,_1 for n => 1, where b,, is the numberofpermutations of [n] such that no elementis followed immediately by the next larger element. We use induction on n. The empty list and the list “1” yield 6; = bg = 1. Using Do = Dz = 1 and D, = 0, the claim holds for n < 2. For the induction step with n > 3, we need a recurrence. We claim bn = (n— 1)bn_-1 + (n — 2)bn_-2 for n > 2, with bop = 1 and b;, = 1. For n > 2, we group the good permutations of [n| by whether element n appears between two elements with thefirst being one less than the second. If not, then deleting n leaves a good permutation of [n—1]. Each

such permutation of [n—1] generates n—1 good permutationsof [n], since n can be inserted at the beginning or after any element other than n—1. If a good permutation hasi,n,i+1 in order, then deleting n leavesa permutation of [nm — 1] with one bad location. The numberof bad permutations at i,i+ 1 that arise in this way is a,_2, since they are formed by treating i,i+1 asa unit and forbidding each unit from immediately following the preceding unit (with n missing andi,i+1 being a unit, there are n—2 units). Since there are n — 2 choicesfor the unit surrounding n, there are thus (n — 2)a,_2 good permutationsof [n] of this type. Now the induction hypothesis and derangement recurrence yield bn = (n 7 1)bp-1 + (n 7 2)bn-2 = (n ~ 1)Dy-1 + (n a 1)D,~2 + (n _ 2)Dn-2 + (n _ 2)Dn-3 = Dy + Dr-1

Is there a direct bijective proof? Note that D, + D,_1 counts the permutations of n with nofixed point except possibly for n in position n. 2.1.45. Letting D,, be the number ofpermutations of [n + k] having no fixed points in |n], we have Dy .~p = Dn-1,~4 + NDn-1,4-1 + (n + k — 1)Dnp-1 when k,n > 0, with D,, 9 being the ordinary derangement number D, and Do, = k!. The initial condition for k = 0 holds by definition. When n = 0, there is no restriction on the position of any element.

Chapter 2: Recurrence Relations

For k,n > 0, consider the usage of the element n+ k in such a permutation. There are D,_; , such permutations in which n+k is in a cycle by itself. There are nD,,_1,,-1 such permutations in which n + k is in a cy-

cle of length 2 with some element of[n]. In all other such permutations, deleting n+ k from its cycle yields a permutation of [n+ k —1] having no fixed point in [n], and each such permutation arises n + k — 1 times. 2.1.46. ean (") Disn-j =k! yee) Cyr )D,-;. We show that both sides count the set P of permutations of [n + k] with no fixed point in [n]. Let D,., =|P|. Let A =[n] and B= [n+k] —[n]. On the left side, we group P by the numberoffixed points. There are

(5 ) ways of choosing j fixed points in B and Dj4,_; ways to derange the remaining points. Thus D,,, = ean (")Disn-je The right side also counts P. Let m = min{n, k}. Each az € P swaps some A’ C A with some B’ C B, mapping A — A’ to itself and B — B’ to

itself. Let r = |A’| = |B’|; we have 0 < r < m. To form such a permutation, we choose A’ and B’ (temporarily leaving them in order), permute the resulting k elements of (B — B’) UA’ arbitrarily, and then permute (A — A’) U B’ without leaving any of A — A’ fixed. For fixed r, we can do

nanSY)QU)M

these steps in (*)(")k!D,-,,- ways. Our previous formula for D,-;,, yields

7=0

Here j counts the elements of B’ whose imageslie in A’ and have the same position there as the inverse images have in B’. To group P according to 7, we interchange the order of summation, apply (“)() =

)(‘-J) and apply the Vandermondeconvolution. j)\r-j

nanSooS(O)-eE(MEE

2.1.47. Instances of the Catalan numbers. In each case, showing ay = 1 and a, = an Qp-1An_- for n > 1 makes(a) the Catalan sequence. a) Ordered trees with n+ vertices. There is one tree with one vertex: a = 1. For n > 1, the root has at least one child. Let k be the number of vertices in the subtree rooted at the leftmost child. Deleting this subtree leaves an ordered tree with n — k + 1 vertices rooted at the original root. Choosing the two subtrees independently yields az_1a,_% ways to complete the full tree. Every ordered tree has some numberofvertices in the subtree at the leftmost child of the root, sosumming over k counts each ordered tree with n + 1 vertices exactly once: a, = an Ap—1An_k-

Section 2.1: Obtaining Recurrences

b) Noncrossing pairings of 2n points on a circle. With one way to pair no points, d@ = 1. For n => 1, consider pairings of x,,..., 2, (in order) on the circle. Since chords for pairs cannot cross, indices of paired vertices have opposite parity (leaving an even numberon eachside). Let x94-1 be the mate of x2,, where k € [n]. The other points form a noncrossing pairing on x1,...,Xas-2 and a noncrossing pairing on Xx9z,..., Xan.

Choosing them independently, there are az_,a,_; ways to complete the pairing. Summingoverthe possible mates of x2, counts each pairing ex-

actly once: an = 0), Uk-1An—kc) The numberof walls ofpennies on a base of n pennies. Thereis one way to put no penny on base of length 0, soay = 1. Forn > 1, ina wall of pennies, let k be the index of the first penny in the base row whoseright end is not covered. By this choice, the first row has k—1 pennies covering the first k pennies in the base row. Since no pennies are next to these, they serve as a base of length k — 1 for completing part of the wall. The rest of the wall sits on the last n — k pennies of the base, because the gap after the kth pennyis exposed. Hence there are a;_1a,_, ways to complete the wall. Summing over k counts each wall once: a, = an Ap—-1QAn_k.

2.1.48. Stack-sortable permutations of |n]. When the next input value x exists and is less than the top element of the stack or the stack is empty, x movesto the stack; otherwise, the top of the stack moves to the output. For any list, each element eventually moves to the stack and later to the output. The input permutation is sortable if the resulting output is 1 through n in order. a) The numbera, of sortable permutations of |n] satisfies the Catalan recurrence and hence is the Catalan number C,,. Note that ag = 1. For n > 1, we obtain the recurrence a, = )°;_, @k-1@n-z by interpreting k appropriately to group the sortable permutations into sets having the desired sizes. Proof 1. For any permutation, the algorithm empties the stack before moving n to it, then n sits on the bottom of the stack while the rest is processed, and finally n moves to the output. Letting k be the input position of element n, this implies that the input is sortable if and only if the part before n is a sortable permutation of [k —1] and the part after n

arises from a sortable permutation of [n — k] by adding k — 1 to each element. There are az_; choices for the first part and a,_; for the last part, chosen independently. Each sortable permutation has n in exactly one position and so occurs in one such group. Summing over sk thus counts each such sortable permutation of [n] once. Since there is one sortable

empty permutation, the counting sequence (a) thus satisfies the Catalan recurrence ay, = )\7_, @k-14n—% With ap = 1.

ZA,

Chapter 2: Recurrence Relations

Proof 2. For a sortable permutation, let 2k be the number of moves in the algorithm after which the stack first becomes empty again. The value x; sits on the bottom of the stack while some smaller elements are processed, and then it moves to the output. Each input value that has been used has moved twice. Since the input is sortable, the set of ele-

ments that have been output must be [k]. Furthermore, the last of these (the element x;) must be k, and the input in positions 2 through k must be

asortable permutation of |kK—1]. The portion of the input after x; must be a translation (by adding k) of a sortable permutation of [n — k]. Combining any two such sortable permutations produces a sortable permutation

of [n]. Summing over the mutually exclusive options for k, each sortable permutationof [n] is counted exactly once in the sum )\7_, Q4-1@n—rb) Input x1,...,Xn becomes sorted if and only if xz < x; < x; never occurs with i < j < k. We prove both implications by contrapositive. Necessity. Suppose that x, < x; < x; withi < j < k. Everything

less than x; that precedes x; must be output before x; reaches the stack (since the stack remains ordered). Thus x; reaches the output before the smaller number x; reaches the stack. Hence x; is output later than x;, and the outputis not in order. Sufficiency. If x1,..., Xn is not sortable, then its output has some least r such that r does not immediately follow r— 1. When r movesto output, r —1 is still in the input, since it is not in the output and the stack is in order. Also r—1 is not at the front of the input, since the rules would then put r—1 on the stack instead of popping r. Since all numbers

smaller than r — 1 are already in the output, the front of the input (s) is larger than r. Thus the input has...r...s....— 1... in that order, with s >r. These three numbersform a forbiddentriple. 2.1.49. The Catalan numberssatisfy the recurrence

Qn\

1%4_,

(2n-2k

c= ()-5 or n—k )

k=0

We compute C,, by subtracting from (7”) all the lattice paths from

(0, 0) to (n, n) that rise above the line y = x. Each such path rises above the line at somefirst point, moving from (k,k) to (k,k +1). We form

such a path by combining a ballot path from (0,0) to (k, k) with a path from (k, k) to (n,n). The latter part can be any lattice path from (k, k) to (n,n) as long as its first step is vertical. Since such paths have the same numberof vertical steps as horizontal steps, exactly half of them have thefirst step vertical. Hence the subtractive term for the paths the

first step above the diagonalafter (k, k) is $C,(?"-7*). (There are other less-efficient arguments.)

Section 2.1: Obtaining Recurrences

2.1.50. A partition of |[n] is noncrossing if there are noa,b,c,d witha < b <ec <dsuch that a andc are in one block and b and d are in another. Let A, be the set of noncrossing partitions of [n], with size apn. a) The numberof noncrossing partitions of {n] is C, (Catalan number). Thereis one such partition when n = 0. For n = 1, group A, by the smallest value in the block containing n; this value k ranges from 1 ton. Such a member P of A, is formed from a noncrossing partition of [k — 1] and the addition of k to the block containing n in a noncrossing partition of {k+1,...,n} (which is empty when k = n). The two partitions used can be formed in a;z_; and a,_, ways, respectively, and distinct such choices combine to form distinct members of A,. Each memberofA,, is counted in exactly one summand(one value of k)

and arises from partitions of [k—1] and |[n]—|k] in exactly one way. Thus An = an ap-1A,-, for n > 1. Since also ag = 1, we conclude a, = C,. b) Bijection to the set of ordered trees with n edges. Let B,, be the set ordered trees with n edges, with size b,. Note that b) = 1. Forn > 1, let r denote the root, and group B,, by the numberof edges in the subtree containing the leftmost edge from r and its descendants. If that subtree has k edges, rooted at v, then the full tree is formed by rooting anyordered tree with k — 1 edges at v and rooting any ordered tree with n —k edges at r, with the edge to uv placed at its left. Summing over k counts

all rooted trees with n edges, so b, = )°7_, bx-1bn-« for n > 1. Since the sequences satisfy the same recurrence andinitial conditions, a, = b, = C,. The recurrenceleads to an inductively defined bijection from A, to B,, because the piece corresponding to a given value of the index k has the samesize in both problems. For n = 0, the bijection maps the tree with no edges to the empyt

partition of [0], which has no blocks. Given bijections fm: Am — Bm for 0 < m < n, define f,: An — Bn as follows. For P € A,, let k be the highest element in the same block

as 1. Let P’ and P”be the noncrossing partitions of |k — 1] and [n] — [k] contained in P, where element k is deleted from the block containing 1. Let f,(P) be the ordered tree defined by adding a leftmost edge rv to the

root rof f,_;(P”) and letting v be the root of a copy of f,_1(P’). Note that Ffn(P) has n edges, so f,(P) € B,. Given any tree T in B, (for n > 1), we argue that T arises exactly once in this way, and hence /,, is a bijection. Deleting the leftmost edge incident to the root of J’ yields a rooted tree with k edges and a rooted tree with n — k edges, for some k. By the construction, T can arise as f,(P) only when the least element of the block containing n is precisely this value k. Now the noncrossing partitions P’ and P” use to form T from P are uniquely determined because f;_; and

Fn—-k are bijections.

Chapter 2: Recurrence Relations

c) The numberof noncrossing partitions of [n]| with l blocks equals the numberof ordered trees having n edges and | leaves. We again use induction on n. For n = 0, by convention a rooted tree with no edges has no leaves, and it correspondsto the only partition of [0], which has noblocks. Now suppose n > 0. For P € A, with / blocks, consider the image tree obtained in part (b). It combines the imagesof noncrossing partitions P’

of |k—1] and P”of |k—1]. If P” has 7 blocks, then inductively an ordered tree with 7 leaves is grown for it from the root r. In this case, P’ has l—j blocks, and inductively a tree with / — 7 leaves is added as a leftmost subtree of r. A bit of care is needed when k = 1, since the imageof the

partition of [0] has no blocks. In this case, thereis still a leaf for the first block; it is the leftmost child v placed under r, with v having no children. In total, P is mapped to a tree with / leaves.

2.1.51. Two problems solved by the same recurrence: Xn = ))j4441=n—1 Xi/XkXL with x9 = 1. Trivially in each problem, ap = bo = 1. a) a, counts the ways to split 3n points on a circle into n noncrossingtriangles. Let u1,..., U3, be the points in order. Point uz, isin a triple with points uv341 and U3j+34+2 forsome j and k with j,k > Oand j+k <n, since the points are grouped into triangles that do not cross. Let / = n—1—k-—/. Since the numbersof points between corners of the triangle containing Uz, are 37, 3k, and 3/, respectively, the number of ways to complete a grouping usingthis triangle is aja,a;. Summing over nonnegative j,k, l with sum n — 1 countsall the noncrossing groupings. c) c, counts the binary lists with 2n 1s and n Os in which every initial segment has at least twice as many 1s as Os. Such list is a 2-ballot list of length 3n. One way to describe the recurrencefor the C,, ordinary ballot lists is to sum C; C; overall nonnegative j, k with sum n—1, having found the 0 to pair with the initial 1 so that between them is a ballot list of length 27 and after the 0 is a ballot list of length 2k. Hereweproceed similarly. Given triple 110 and nonnegative j,k, l with sum n — 1, we form 2-ballot list of length 3n by inserting 2-ballot lists of lengths 37, 3k, and 3/ between the two 1s, between the 1 and the 0, and after the 0, respectively. To prove that this countsall the 2-ballot lists of length 3n, in sucha list x,,..., 3, we must identify the special triple to invert the construction. We give examples (not all of them!) for n = 3: 111100110: (7,k,l) =(0,1,1) 111011010: (7, k,l) = (2, 0, 0) 111010110: (j,k, l) =(1,0, 1) 111101100: (j,k, l) = (0, 2, 0) 111011100: (7,k,l) =(1,1,0) 110110110: (j,k, /) = (0, 0, 2) The special 0 is the first position s ending a prefix where the number of 1s is exactly twice the numberof Os (this is position 3n when / = 0).

Section 2.1: Obtaining Recurrences

The first special 1 begins the list. The position of the second special 1 is the largest r with r < s such that xo,...,x,_; is a 2-ballot list. Since the emptylist is a 2-ballot list, r exists and is at least 2. Stopping at an earlier completion of a 2-ballot list is not correct, since in lxy1z0 with x,y,z being ballot lists and y = 1y’, the list y’ does not have twice as many Is as Os and hence cannot be the second insertedlist. Wesimilarly cannot go farther thanr, because by definition whatis taken for the list of length 37 would not be a ballot list. 2.1.52. Let an n-walk bea walk of length n. Let w, count positive lattice n-walks in Z?, let a, count those ending on the horizontal axis, andlet

Cn = at (*)-

a) An = 2an-1 + Yp-5 Ak-2Gn—z for n = 1, with ap = 1. Group these

walks by the length (xk) up to the first return to the axis. When k = 1, there are two choicesfor thefirst step and a,_; waysto finish. When k > 1, the first step is up, the kth step is down, and the portion betweenis a positive lattice (k — 2)-walk shifted up one unit. There are az_2 such walks, and there are a,_; ways to finish after the first return to the axis. The value of k is unique for each walk, so summing over k yields a, =

Zan-1+ Yo-» Ak-2An—s for n > 1, with ap = 1. Qn = Chit, by induction on n. The basis is a9 = 1 = Cy. Since Co = C; = 1, the induction hypothesis yields n+1

= 2an-4S Ap-2An-k = 2C.“y Cy-1 Cnsi-k = =) C 1Cn4i1-k = Crs. k=2 k=2 k=1 b) w, = (°"*"), by recurrences. Proof 1 (many-term recurrence). wy, = 3Wn-1 + Sad Ap—-2Wn_-z for n> 1, with wo = 1. A positive lattice n-walk never revisits the axis if and only if it begins upward and then follow an upshift of a positive lattice (n — 1)-walk. Hence w,_; walks neverrevisit the axis. For the others, let k be the step of the first return to the axis. When k = 1, we have 2w,_1 walks. When k > 2, there are a;z_2 choices for the portion to thefirst

return, as in part (a). Each combines with any of the w,_,; ways to finish after step k. This derives the recurrence. Now weprove Ww, = (?7**) by induction on n. Note wo = 1 = (5). For

n > 1, part (a) yields w, = 3Wn-1 + )\p-9 Cr-1Wn_« for n > 1. The induc-

tion hypothesis and Cy = 1 yield wy, = 2(7”')+)7_, Cea (?""4""). By the Complementation and Committee-Chair Identities, 2(°""*) = 2(2"—") = n-1

(?"). Hence it suffices to prove (") + Yr, Cr("74") = (P""").

To prove this identity, we count lattice paths from (0, 0) to (n, n +1). Of these, ( “n) take their first step up. Group those that first step right

Chapter 2: Recurrence Relations

by their first return to the diagonal. Those that first return at (k, k) step right, then follow a ballot path of length 2k —2, then step up, then finish

with any lattice path from (k, k) to (n,n +1). Choosing the ballot path

and endinglattice path yields C,_1(7”.74*') such paths. Summingover k and adding the paths that first step up completes the proof. Proof2 (first-order recurrence). Every walk of length n is formed by extending a walk of length n — 1, and it arises from exactly one shorter walk in this way. Every walk of length n — 1 extends in four ways, except that if it ends on the axis it extends in only three ways. Thus wy, = 4Wn-1 — An_1, Valid for n > 1, with wo = 1. With a,_; = C,, the recurrence yields an inductive proof that w, =

(°"**). Basis: wo = 1 = (5). Induction step (for n > 1). We use the recurrence, the induction hypothesis and formula for a,_1, and the CommitteeChair Identity to compute

4 _4(2-1 1 (2n _4% 2n 1 (2n Mon SON ny = (> - aails)= a (3")- ail)

2 real) = 1 2n n+1\n

Cn) (rer) )

2n+1/2n n+1\n

2n+1 n+1

2n+1 n

c) The total numberofpositive lattice n-walks in three dimensions (not

going below the horizontal plane) is 7, (7)(*7")2""*. The steps in the last two coordinates combineto form a positive lattice walk in two dimensions, since the third coordinate remains nonnegative. The steps in the first coordinate can then be made arbitrarily. Grouping the walks by the numberof steps taken in the second or third coordinate, we choose the positions of those steps amongthe n steps, place one of the w; positive lattice k-walks into those positions, and place positive or negative steps arbitrarily for the first coordinate in the remaining positions. 2.1.53. Schroder and Delannoy numbers. a) Schroder numbers with positive even index are divisible by 3. Sy,

counts the paths from (0,0) to (n,n) that do not go above the diagonal and use steps in {(0, 1), (1, 0), (1, 1)}. We obtain a recurrence. The paths that start with adiagonalstep are completed by a Schroder path from (1,1) to (n,n); there are S,_; of these. All other paths start with a rightward step and makea first return to the diagonal at some

point (k, k), preceded by a vertical step from (k,k — 1). Between those steps is a Schroder path from (1, 0) to (k, k—1), chosen in S;_; ways. After (k, k), they follow a Schréder path from (k, k) to (n,n). Thus S, = Sn-1 + Vip=1 Sk-1Sn-r. Note that So = 1 and Sg = 6. To prove the claim by induction on n, write the recurrenceas S, = 3S,-1+ yo S,-1S,-%. For n > 2, the induc-

Section 2.1: Obtaining Recurrences

tion hypothesis implies that when n is even every term in the recurrence

is divisible by 3, since exactly one of {k —1,n—k} is even. b) an = 6an_1 —An-2 —2S,_-1, where a, is the nth central Delannoy num-

ber d;,,». A Delannoy npath is a word in {H, V, D} (horizontal, vertical, diagonal) from (0, 0) to (n,n). Consider the end of a Delannoy n-path. It

may end with one of {HV, VH, D} after following a Delannoy (n—1)-path; there are 3a,_; such paths. It can miss the point (n — 1,n — 1) by ending DV or DH; these paths correspondby deleting the last D to Delannoy

(n — 1)-paths that do not start with Delannoy (n — 2)-paths. Hence there are Qn_-1 — An_-2 of them. Finally, there are paths ending VV (and a symmetric argument for paths ending HH). On sucha path P, identify the last point of P (before

the end) where y — x is maximized. Since the path starts at (0,0), this point x is on or above the diagonal. The step after pis H. Form a new path P’ by changing this H to V and deleting the final VV. Each lattice point on P after x moves one step left and one step up, so the final point is now at (n—1,n-—1) instead of (n, n — 2). Furthermore, since x is at or above the diagonal, the path P’ rises above the diagonal. To invert

the map for any path P’ that rises above the diagonal, find thefirst point where y — x is maximized, and change the V preceding it to H. Hence the numberof Delannoy n-paths ending with VV is a,_,;—S,_1. By reflection, the same number end with HH. Summing the counts of the various possibilities yields a, = 3a,_) + (Qn—1 — Gn—2) + 2(Gn—1 — Sp-1). 2.1.54. S, = Con, where S,, is the number of Shapiro paths from (0, 0) to

(2n, 2n) (lattice paths avoiding the points (2i — 1, 2i — 1) on the diagonal). Proof1 (induction on n). Note that So = 1 = Co. For n > 0, consider the Shapiro paths that first return to the diagonal at (27, 2i), wherei > 0. There are 2C9;-1S,_; of these, since up to this point the path must bea Catalan path that doesn’t touch the diagonal or the reflection of such a path. Using the induction hypothesis, this is 2C2;-1 Con_9;. By rewriting the indices in one copy of the product, we can express this as Co;-1 Cana; + Cony Con-[a(n_d41]-. SuMMing over i and changing the direction of summation on the second term yields the usual Catalan recurrence, and the sum is C2,. Equivalently, we can show that both sequences satisfy the samerecurrence. Again the initial conditions Co = Sp agree. Grouping the even terms and odd terms of the recurrence for C2, separately and turning one of the sums aroundyields Co, = it 2Co;-1 Con_-2;. Viewing the oddindexed Catalan numbersas constants, this recurrencefor the even Catalan numbersis the sameas the recurrencefor {S,,} found above.

Chapter 2: Recurrence Relations

Proof 2 (bijection, by Warren Nichols). View Shapiro paths and ballot lists as binary lists. Balanced binary lists are half-0 and half-1. The parity (odd or even) of a balanced list of length 2n is the parity of n. Shapiro paths are the balanced lists with no initial odd balanced segment. A ballot list with no balanced initial subsegmentis strict. Deleting the first and last elements from a strict ballot list B yields a ballot list B*. The reflection X of a list X is obtained by interchanging 1 and 0. The null path is @. Let B and S denote the ballot lists and the Shapiro paths of length 2n. We define bijections y: S > B and ¢: B — S recursively. For the ba-

sis, W(@) = @ and ¢(@) = @. For the inductive step, split off the shortest balanced initial segment; it is anonemptystrict ballot list B or its reflection B. For each map, we have two cases. For w on S, the initial segment maybestrict ballot or reflected strict ballot; define y(BX) = By(X) and

(BX) = 1p(X)0B*. For ¢ on B, the initial segment may be even or odd;

define (BY) = B@(Y)if it is even and ¢(BY) = 0Y1¢(B*)if it is odd. Weestablish the bijections by induction. For the basis, ¢y(@) = @ = yo(@). The induction step has two cases for each composition. For elements of S, the initial balanced segment and also the remainder must be even. Depending on whether the initial segment is strict ballot or reflected strict ballot, we have ¢y~(BX) = ¢(By(X)) = Boy(X) = BX

or oY(BX) = o(1¥(X)0B*) = 0B'1¢((1y(X)0)*) = Boy(X) = BX. For elements of B with even or odd initial segment, we have ¥¢(BY) = Y(Bd(Y)) = Byd(Y) = BY if B is even or WA(BY) = YWOY1¢(B*) = 1y~¢(B*)OY = 1B*0Y = BYif B is odd. The resulting bijection can also be described explicitly. Each non-odd path breaks uniquely into a sequenceof strict ballot and reflected strict

ballot segments as P = W, B, W.B2--: W,B,W,+1, where W; and/or W,.+1 may be empty. The mapping of P to W,1W21---1W,W,.,0B70B*_, --- 0B; satisfies the recursive definition, and thus it is the map w. This explicit

bijection can also be verified directly. 2.1.55. The numberofDyck (2n)-paths that avoid {(4k,0): 1<k<n-1} is twice the numberofDyck (2n —1)-paths, where a Dyck n-pathis a path

from (0, 0) to (2n,0) using steps that move by (1,1) or (1, —1) without falling below the x-axis.

Turning steps by (1,1) into steps by (1,0) and steps by (1, —1) into steps by (0, 1) establishes a bijection from Dyck n-paths to ballot paths of length 2n. The numberof these paths is thus the Catalan numberC;,. Also, the Catalan numberssatisfy the recurrence C, = an C;C,-1-i-

Let A = {(4k,0): 1 <k <n-1}, let do, be the number of Dyck (2n)-paths that avoid A, and let dj, be the number of Dyck (2n)-paths with at least

Section 2.1: Obtaining Recurrences

one point in A. Note that Co, = don + dj.

A Dyck (2n)-path whosefirst point in A is (4k, 0) consists of a Dyck (2k)-path that avoids {(47,0): 1 < 7 < k — 1} followed by a Dyck (2n — 2k)-path. Thus, the number of Dyck (2n)-paths whose first point in A is

(4k, 0) is doxCon—pz, and in total di, =

S77} doz Con—2e-

With dz = 2 = 2C,, we proceed by induction. We have do, = 2Coz_1 for1 <k<n-1, and thus n—-1

2n—2

on = » 2C24-1 Con-2k = » Ci Con—1-i = Can — 2Con-1. k=1

i=l

Therefore do, = 2Con_-1, as desired. 2.1.56. When two teams play until some team wins n games, with Team A havingprobability p ofwinning any game, independently, the expected num-

ber ofgames played is n ye C,(pq)*, where C; is the kth Catalan number and q=1-p. Let a, be the expectation.

a)a,=n yo ("**)(pg* + p*q”). The probability that exactly n + k games are played with Team A reaching n wins on thefinal gameis p”q* times the numberoflists of n — 1 As and k Bs. Hence the probability

that n+ k gamesare played is ("*;~)(p"q* + p*q”). Since (n+ k)("*2") = n("t"), we have an =7n ye ("7*\(p"gk + p*q”). b) a, =n yo C,(pq)*. To obtain the desired result, it suffices to

show “#1 — 4a = —l_(*")\(pg)". First note

p’*'g* + p*q"*! = p"q*(1-—q) + p*¢"(1 —-p) — (p"g* 4 p*q”) _ (p"g**! 4 p**1q”).

We compute

An+1 _

(

nmt+tk+1)\,

n41 bk ntt

g +pq™)

k=0 _v

nt+k+1

n+k

Joorat + oa") n+k

n_k

nt+k+1

+ ( Japa" - ( f

1 n+1

2n+1

(") (pay.

bem

( k )+ (723) ler + p’q”)

=|8 =|8 IMs

n_,k+1

Joo" n+l

k+1_n

+ p**"q”)

n_l

lin

y (ia yJore +a

Jorg + p"**q")

Chapter 2: Recurrence Relations

2.1.57. The numbera, ofup-down permutationsof |n| (alternating ascents and descents starting with an ascent) equals the numberb, of equivalence classes of permutations of |n] under “flip” operations that can reverse the

entire list or can reverse thefirst k elements ifthe (k + 1)th elementis greater than all those before it. It suffices to show that the two sequencessatisfy the same recurrence A, = 5 a (7-7) An-1An-k, similar to the Catalan numbers. Note that ag = bp = 1. The up-down permutationsare also called alternating permutations. The value 2a, counts both the up-down permutations and the down-up permutationsof [n], since subtracting all elements from the value n+ 1 exchanges ascents and descents. Wesplit the set consisting of both types according to the position of the largest element n. If n is in position k, then there are kK—1 elements to be chosen to precede it, and the rest follow it. Since n is the largest element, the subsequent n — k elementsarearrangedin an up-downfashion(in a,_, ways) and the preceding elements, viewed from position k downto position 1, are also arranged in that fashion (in ag ways). We cannot control whether the step from position 1 to position 2 is an ascent or a descent Summing over k completes the count of all permutations of both types. Next consider the equivalence classes of permutations. For a word a, let a denote its reversal. As above, we group the permutations by the position of the largest element n. Let the sets of elements preceding and

following n be B and C. No flip can change the unorderedpair {B, C} (the pair can be exchangedby flipping the entire list). Thus all permutations equivalent to a permutation /ny have the form f’ny’ or y’nf’, where fi’ = Bandy’ = y. Conversely, any such permutation is equivalent to bny: the presence of n allows transforming the portion before a into anything in its equivalence class, and thus

Bny = B’ ny = yn’ = yn’ = y’nf’ = f'ny’ and

Bbny = Bny = ynB = ynB = y' np’. Thus the equivalenceclass of Bny is {B’ny’, yn’: B’ = B, y’ = y}-. To count the equivalence classes of permutations of [n], we choose

a partition of [n] — {n} into sets B and C of sizes k — 1 and n—k and populate the portions of the permutation before and after n with equivalence classes on those sets. Summing over k counts each equivalence class twice, since B and C can be switched. For n > 2, we thus obtain 26; = a (7-1 )On-1bne. The origin of the name for the numbersin this sequenceis that its exponential generating function is sec x + tan x (see Section 3.3).

Section 2.1: Obtaining Recurrences

2.1.58. For n €N, let T;(n) be the coefficient of (—1)*x”~* in the expan-

sion of [](x — i). a) A combinatorial proof that T,(n) = T,(n — 1) + (n — 1)Ty_1(n — 1). Note that 7',(n) is the sum of products of k membersof |n—1]. This counts the placements of k markers on a board having i positions in the ith row, with no two markers in the samerow: pick any k distinct rows, and place one markeron a position in each of those rows. The numberof placements without using row n—1 is T;,(n—1). The numberof placements using row n—-1 is (n—1)T;_;(n—1), by placing the last marker and then placing the other k — 1 on the smaller board.

b) T,(n) = ~~ iT;,_1(i) for k > 1. We use induction on k, with induction on n for fixed k. Note T;(n) = 0 for 0 <n < k and T)(n) = 1 for n> 0. For n> k, part (a) and the induction hypothesis yield

Ty(n) = Ty(n — 1) + (n— 1)Th-1 (2 — 1) = [ce _, UT; i(i)] +(n—-1)Ty-1(n-1) = vin =kiT,

i(Z).

c) T;(n) formulas: To(n) = 1, and T;(n) = a iTo(i) = i= (5).

Since i(5) = 3452(5) + 2(5), the Summation Identity yields

Teln) = DIT) = TPH i() = 3(2) + 20). d) T;. is a polynomial of degree 2k. We use induction on k. Since To(n) = 1, the claim holds for k = 0. For the induction step i7;_;(i) is a polynomial in i of degree 2k—1, and T;(n) is the sum of the valuesof that

polynomial at integers k through n — 1. Thus 7T;(n) — T;(n — 1) is a polynomial in n of degree 2k — 1. If p(n) — p(n —1) is a polynomialof degree d in n, then p(n) is a polynomial of degree d + 1. 2.1.59. The numbera, ofspanningtrees in the graph P,, © K, satisfies an = 30An—-1 — An_-2 for n= 38, with ag = ay = land ag =3. Let G, = Ki oPyp. a) Many-term recurrence. Let x1,...,Xn be the vertices of the path in order, and let v be their common neighbor. The trees not containing Ux, consist of aspanningtree of G,_; plus the edge x,,_1x,; there are a,_1 of these. For each tree containing vx,, let r be the least index such that the tree also contains the path x,,...,x,, with no edges from vu to these vertices (except the last). There is one such tree for each spanning tree of G,—1. This accountsfor all spanning trees, so dy = An_1 + yD 9 Gi.

b) Second-order recurrence. Proof 1 (From part (a)). The recurrence above is valid for n > 2. Thus when n > 3 wecan also write a,_1 = @,_9+ yee _g a. Subtracting the two equations yields ay — An_1 = An_1 — An—2 + An_1, OF An = 8apn_1 — An_2. This is not valid when n = 2.

Chapter 2: Recurrence Relations

Proof 2 (Direct argument). A spanning tree of G, contains a spanning tree of G,_; if and only if it contains exactly one of vx, and x,_1Xp. Thus there are 2a,_; trees of this form. The remaining trees contain both vx, and xy-1x, and therefore not vx,_;. Replacing {vxy, Xn-1xn} with UXn—-1 yields a spanning tree of G,_1, and this is reversible for spanning trees of G,_1 containing vx,_;. The spanning trees of G,_; not containing vx,_; consist of x,_2X,_1 plus a spanning tree of G,_», so there are An—2 of these. Thus the numberof spanning trees containing both edges incident to x, iS An_-1 — An_2. Proof 3 (System of recurrences). Let cn, dn, bn be the number of spanning trees of G, whose edges incident to x, are UXn, Xn-1Xn, or both, respectively. Our earlier arguments yield a, = bn, + ¢,n + dn, bn = bn—-1 + Cn-1, Cn = An-1, and dy = ayn_1. Substitutions yield the desired second-order recurrence via An + An-2 = Ant dn_-1 = dpn-1 +b, +e,+ dy = dn_-1 + bn_-1 + Cn-1 + 2Qn_1 = 8an_1.

c) a, = Fo, forn> 1. Since a; = 1 and a2 = 3, the claim holds for n =

1 and n = 2. Using part (b), the induction hypothesis, and the Fibonacci recurrence, for n > 3 we compute a, = 3dan_1 — An_2 = 3Fon-2 — Fan-4 =

2Fon-2 + Fon-3 = Fon-2 + Fon-1 = Fon. 2.1.60. All n-vertex 2-trees having exactly two simplicial vertices have the same numberof spanning trees. A 2-tree is generated from an edgebyiteratively adding one vertex having exactly two adjacent neighbors. Index the vertices as v;,...,U, in such an construction ordering; call it a 2-tree ordering. Various 2-trees having exactly two simplicial vertices. One has vertices v1,...,U, and edges{v;uv;: |i—j| < 2}. Anotheris obtained froma path by making one endpoint adjacentto all the other vertices. To count the spanning trees in such graphs, we describe their structure. An n-vertex 2-tree G has exactly two simplicial vertices if and only if G has a 2-tree ordering v1, ..., Un, such that each v; is adjacent to v;-1, for 2 < i<n. That is, v1,...,U, forma path in order. Since a vertex in a 2-tree with n > 3 is simplicial if and only if it has degree 2, the neighborhood in G of a simplical vertex v contains at most one simplicial vertex of G — v (if n > 3). Hence G has at least as many simplicial vertices as G — v. The only 2-tree with four vertices has exactly two simplicial vertices. If n > 5, then G—v has the same numberof simplicial vertices as G if and only if v is adjacent to some simplicial vertex of G — v. Hence in generating a larger 2-tree from the 4-vertex 2-tree by the reverse of a 2-simplicial ordering, the numberof simplicial vertices remains 2 if and only if each subsequent added vertex is adjacent to a current simplicial vertex.

Section 2.1: Obtaining Recurrences

Whenthere are exactly two simplicial vertices, this process can bereversed, because any simplicial vertex can be the next vertex deleted from the end in a 2-tree ordering. In particular, we can steadily avoid deleting one of the two original simplicial vertices. Since the numberof simplicial vertices cannot decrease below 2, each vertex we delete from the “other end” is adjacent to one simplicial vertex, thus forming the desired path. An n-vertex 2-tree having exactly two simplicial vertices has F2n_2 spanning trees. Let G, be sucha graph. Let v;,...,v, be a 2-tree ordering for Gy with v1,...,Un forming a path. The neighborsof v, among the earlier vertices are v,_; and another vertex. Corresponding statements hold for earlier indices, since deleting v, from G, yields a graph that can be treated as G,_;. Let t, be the numberof spanning trees in G,,, and let s,, be the numberof those spanning trees containing the edge vy,u,_1. Spanningtrees of G, contain one or two of the edges at v,. There are 2t,_1 trees containing one edgeat v,,. Note that the numberof spanning trees containing one of the edgesat v, is the same as the numberof spanning trees containing the other edge there. Trees that contain both edgesat uv, do not contain the edge e joining its neighbors, but replacing the edges at v, with e yields a spanning tree of G,-1. In fact, this yields a bijection between the trees in G,, containing both edges at v, and the tree in G,_; containing e. Since e is incident to Un—-1 in G,_1, the numberof spanning trees of G,_1 containing e is s,_1, regardless of which edge of G,,_1 at v,_1 ise. For n > 3, we conclude t, = 2t,-1 + S,-1. In addition, s, = t,_-1 + sn—1, since s, counts the trees extended by one particular edge at v,, and those containing both. The initial conditions are tg = sg = 1. Since we have made this argument for every G, in which v1,...,U, forms path, all such 2-trees have the same numberof spanningtrees. The verify that that numberis F’2,_-2, not as a basis that tg = F's and So = F,. To prove that t, = Fo,-2 and s, = Fo,-3, we use the induction hypothesis to compute tn, = 2Fen-4 + Fon-5 = Fon-4+ Fon-3 = Fon-2 and

Sn = Pon-4 t+ Pon—5 = Fon-z. 2.1.61. Spanning trees in the ladder graph G, consisting of two paths X1,--.,X, and y1,...,¥n plus edges x;y;. Let a, denote the number of spanning trees in G,. Note a; = 1, and now supposen > 1. An arbitrary spanning tree T must contain at least 2 of the three edges in the path P = Xn-1,Xn,¥n>Yn-1- There are 3a,_; trees that contain two of these edges. Trees containing all of P do not contain the edge e = x,_1yp-1, so such a tree can be shrunkto a tree in G,,_; by replacing P by e. This is a bijection between trees of G, containing P and trees of G,_; con-

Chapter 2: Recurrence Relations

taining e. Trees in G,_; containing e are counted by subtracting out the trees of G,_, that do not contain e, yielding a total of a,_; — a,_2. Thus An = 4ay,-1 — An_2, With ap = 1 and a» = 4. Comment: One can reach the same recurrence by introducing 6b, as the numberof spanning trees that contain the rightmost edge and c, as the number that do not. Then a, = b,+¢n, bn = bp_-1+2a,_-1, andc, = apn_} for n > 2, with a; = 6; = 1 andc, = 0. This can be reduced to a single recurrence for a, by substitution: eliminate c,, use the first equation for nandn-—1 to get by — bn_1 = An — 2An_1 + An_2, then eliminate b, — b,-4 with the second equation to obtain a, = 4an_-1 — An_2. 2.1.62. The effect of graph transformations on the number t of spanning trees. Let G be a graph with n vertices and m edges. If H is obtained from G by replacing every edge with an edge of multi-

plicity k, then t(H) = k”"1t(G). Proof1 (direct combinatorial argument). Each spanning tree T of G yields k”~+ distinct spanning trees of H by choosing anyone of the k

copies of each edge in T. Thus t(H) > k”"!1(G). Also, everytree arises in this way. A tree T in H uses at most one edge joining any two vertices. Since T is connected and acyclic, the edges in G with copies used in T

form a spanningtree of G that generates T. Hence t(H) < k”"!1(G). Proof 2 (induction on m using the recurrence for tT). If m = 0, then

t(G) = t(H) = 0, unless n = 1, in which case 1 = k® - 1. If m > 0, choose e € E(G). Obtain H’ from H by contracting all k copies of e. Obtain H”from H by deleting all k copies of e. The spanning trees of H can be grouped by whetherthey use a copy of e (they cannot use more than one

copy). There are k X t(H’) of these trees that use a copy of e and t(H”’) that do not. We can apply the induction hypothesis to H’ and H’”’, since each arises from a graph with fewer than m edges by having k copies of each edge: H’ from G:e and H” from G-— e. Thus

t(H) =kx1(H’)+ 1(H”) =k-k”-?*1(G-e) +k” !24(G -e) = k”[1(G-e)+7(G—e)] =k” 12(G). If H is obtained from G by replacing each e € E(G) with a path P(e) of

k edges, then t(H) = k™"*!7(G). Proof 1 (combinatorial argument). A spanning tree T of G yields

k™-"*1 spanning trees of H as follows. If e € E(T), include all of P(e). If e ¢ E(T), use all but one edge of P(e). Choosing one of the k edges of P(e) to omit for each e € E(G) — E(T) yields k”~"*! distinct trees (connected and acyclic) in H. Again we must show that all spanning trees have been generated. A tree J” in H omits at most one edge from each path P(e), else some vertex in P(e) would be separated from the remainderof H. Let

Section 2.1: Obtaining Recurrences

T be the spanning subgraph of G with E(T) = {e € E(G): P(e) C T’}. If T’ is connected and has no cycles, then the sameis true of 7’, and T’” is one of the trees generated from T as described above.

Proof 2 (induction on m). The basis step m = 0 is as in (a). For m > 0, select an edge e € E(G). The spanning trees of H use k or k — 1 edges

of P(e). These two types are counted by t(H’) and t(H”’), where H’is the graph obtained from H by contracting all edges in P(e), and H”is

the graph obtained from H by deleting P(e) (except for its end-vertices). Since these graphs arise from G- e and G — e (each with m — 1 edges) by replacing each edge with a path of length k, applying the induction hypothesis yields

t(H) = t(H’) + k-t(H”) = ko"Y-@D17(G-e) + kk"Y-™*1G — e)] =k"™*1(7(G-e)+1(G-—e)] =k™"*!7(G). 2.1.63. If a, is the number of dominotilings of a 4-by-n rectangle, then An = An-1 + 5Ayn_-2 + An-3 — An_-4 for n => 4, with initial conditions ap = 1, a; = 1, ag = 5, and ag = 11. Proof1 (system of recurrences). Let b, be the numberoftilings of a defective 4-by-n rectangle missing the top two (or the bottom two) squares in the last column, andlet c,, be the numberoftilings of a defective 4-by-n rectangle missing the top and bottom squares in the last column. Consider the waysto cover the nth columnof a 4-by-n rectangle when n > 2. With the last column covered by two vertical dominos, there are Qn—-1 completions. Using one vertical domino and two adjacent horizontal dominos(two cases), there are b,_; completions. With one vertical domino and two nonadjacent horizontal dominos, there are c,_; completions. Using four horizontal dominos, there are a,_2 completions. For b, and c, there are fewer cases: the two squaresin the last column maybe covered by two horizontal dominosor one vertical domino. For n > 2, we obtain An = An-1 + An-2 + 2bn-1 + Cp-1

On = bn-1 + Gn-1 Cn = Cn-2 + An-1,

with the initial conditions aj = a, = 6) = cy = 1 and cp = O. Expressions involving b and c can be eliminated using 6, — 6,1 = an_; and Cp — Cn_2 = Qn—1. Hence we write the recurrencefor a,_2 (valid when n > 4 and subtract it from the expression for ap. An — An-2 = An-1 — An-3 + An-2 — An-4 + 2(bn-1 _ bn-3) + Cn-1 — Cn-3.Using Cn—-1 ~ Cn—-3 = An-2 and bn-1 - bn-2 + bn-2 ~ bn-3 = An-2 + An-3

and collecting like terms, we obtain a, = Qn_1 + 5dn_-2 + An—-3 — An—4, AS

Chapter 2: Recurrence Relations

desired, valid for n > 4. The needed initial conditions az = 5 and a3 = 11 can be computed from the original system. Proof2 (break points, as in Application 2.1.3). Let h, be the number of dominotilings of a 4-by-n rectangle having no vertical break of length 4 between columnsof squares. We have hy = 1,1, = 1, andhg =4. Forn > 2, we have h, = 2 if n is odd and h, = 3 if n is even, as illustrated below. Grouping the tilings by the last vertical break before the end yields [n/2|

n—-1

|n/2|

an = » AmAn—m = An-1 + 4an-2 +2 3 Qn-1-2i + 3 » An-2im=0

i=l

i=2

To eliminate the summations, we write the corresponding expression

for An—2 (its validity requires n > 4) and subtract: |n/2|—1

|n/2|-1

An—-2 = An-3 + 4An-4 + 2 » An-3-21 + 3 i=1

An—2-2ii=2

Thus An — An-2 = (An-1 _ An-3) + (4an-2 _ Aan) + 2an-3 + 3an-4.

Simplifying yields a, = an_1+5an_-2+aAn-3—An_4 for n > 4, as desired. With ap = 1, the recurrencea,, = ane AmNn—m (valid for n > 1) generates the initial conditions as claimed.

2.1.64. If m > k, then >j=0 cj, k)/j! = (m+1,k+1)/m!, where c(n, k) is the number ofpermutations of |n| with k cycles. In every permutation of [m+ 1] with k + 1 cycles, element m+ 1 appears in somecycle. Let j be the numberof elements in other cycles. To form such a permutation, we choose those j elements, form a permutation on them with k cycles(in

c(j, k) ways), and permute the other m— j elementsto specify their order following m+ 1 on their cycle. Every permutation of [m+1] with k+1 cycles arises in this way for exactly one value of 7. Thus

cim+1,k+1)= i (eG, km — jf)! = m! VicU, A)/7!.

Section 2.1: Obtaining Recurrences

2.1.65. Gambler’s Ruin: Player A starts with $r, B with $s, and they flip a fair coin until one goes broke. a) The probability that A winsis —.. Let p(r, s) be the probability that

A eventually wins. Initial conditions are p(r, 0) = 1 and p(0, s) = 0. When r,s > 0, in order to win A must win the game that continues after the

first flip. Thus p(r, s) must satisfy p(r, s) = ¢p(r+1, s—1)+$p(r—-1, s+). Setting p(r, s) = —> solves all the equations. To see that this is the only

solution, let f(r) = p(r, s) over fixed r+s =n. We have f(0) = 0 and f(n) = 1. The equation simplifies to f(r) = $(f(r+1)—- f(r —1)). Thus f(r) is the average of f(r +1) and f(r —1), and f must belinear. b) The expected number f(r, s) of flips in the game is rs. Note that f(r, 0) = f(0,s) = 0, which agrees with the claimed formula. For r,s > 0, the expectation equals 1 for the current flip plus the expectation for the remainder of the gamein the state after this flip, weighted by the probability of reaching that state. That is,

f(r,s)=1+$f(rt+1,s—1)+$f(r-1,s+1). The claimed formula solves all these equations, since

rs=1+3(r+1\(s—1)+ $(r—-1)(s+ DV). A game withr+s dollars yields r +s—1 equations in r+s—1 unknowns, given by a tridiagonal matrix of coefficients, so the solution is unique. 2.1.66. The expected numberpx,ofsteps until the first time a random walk is k steps below the highest value it has reached is k(k +1). Write the walk as a string in U and D. Proof 1 (recurrences). The walk is one step below its highest-yet value for the first time whenthefirst D occurs. This occurs on step j with probability 2~/, so the expect time is 2. Thus p; = 2. Let gq; to be the expected numberof steps to reach k steps below theall-time high given a starting point k—1 steps below the all-time high. Note that gq; = p; = 2. To reach k steps below the all-time high, we mustfirst reach k — 1 steps below the all-time high. Hence p; = pz_1 + gy for k > 2. From a point k — 1 steps below the all-time high, after the next step with equal probability we are k or k — 2 steps below the all-time high. In the first case we have arrived, while in the second case we are k — 2 steps below the all-time high and must return to k — 1 steps below theall-time high. Thus the expected numberof additional steps in the second caseis Qr-1 + gx. Hence gq, = 1+ 5(Qk-1 + gz), Which simplifies to g, = 2+ qz_-1. With gq; = 2, we obtain g; = 2k. Thus pz = pz_-1 + 2k, and p,; = 2 yields

Pe = Do, 2i = k(k +1).

Proof 2 (transformation to Gambler’s Ruin). We prove that the answer is k(k+1) by expressing the problem in termsof the stopping time of

Chapter 2: Recurrence Relations

the classical Gambler’s Ruin problem in which one gamblerstarts with

$k dollars and the other with $(k+1), and each step transfers $1 from one gamblerto the other, each direction having equal probability. Interpret upward and downward movesas win andlosses by the gambler currently having less money, respectively. Since the total amount of moneyis odd, there can never be a tie, so this is well defined, and at every step each outcomehas probability 1/2. At each time, the gambler with less money has k — m dollars exactly when weare m steps below the currentall-time high. This is true at the start and is easily checked to be preserved by each move. The only interesting case is when we moveto a newall-time high. Before the move the moneyis split k + 1 to k. The gambler with less money wins: the path reaches a new high and the moneyis again split k + 1 to k, but the two gamblers interchangeroles.

In the classical problem starting with $a and $b, it is well known that the expected numberof steps until one gambleris ruined is ab; in this case k(k + 1). We have shownthatthis also is the expected number of steps until the path is first k steps below its all-time high. 2.1.67. The gambler and the devil play with n red balls and n + 1 blue balls. The gambler starts with one unit of money (infinitely divisible). At each round, the gambler bets some money (maybe 0), and the devil picks a remaining ball. When the ball is red, the gamblerloses the bet; when blue, the gambler gains that amount. The selected ball is discarded. The gambler wants to maximize his final amount, while the devil wants to minimizeit. If both play optimally, then the gambler’s final amountis 2.

We solve the more general problem of determining F(b,r), the final bankroll after optimal play when the gamestarts with b blue balls and r red balls. Clearly F(b, 0) = 2° and F(0,r) = 1, since then the gambler will bet the entire bankroll or nothing, respectively, on each round, and the dealer has no choice of color whenselecting the ball. Given b,r > 0, suppose that the gambler bets x. The dealer can choose a blue ball to increase the bankroll to (1 + x) or a red ball to decrease it to 1—x. Given subsequent optimalplay, the final bankrolls after

these choices are (1+x)F(b—1,r) and (1—x)F(b, r—1), respectively. Since the dealer chooses the ball to obtain the minimum andtheslopes have opposite sign, the gambler chooses x to make the alternatives equal. Thus

x= Feeae; , Which yields F(b,r)=

2F(b,r—1)F(6-1,r)

F(b,r-1)+F(6-1,r)

forb,r>1.

Weprove by induction on b +r that F(b,r) = 2°*"/ 7_, (°%”). Since

Section 2.1: Obtaining Recurrences

>-0 (5) = 2”, the claim holds when b = 0 orr = 0. When b,r > 1, 9

9. gotr—-1

gb+r

F(b,r)= FEL + FOr - » k=0 (C7) + ie (-**) - =O (77) ,

after shifting the index in the second sum andapplying Pascal’s Formula.

When 6 =r +1, we obtain F(r + 1,r) = 2?7*1/27" = 2. 2.1.68. If M is the n-by-n matrix whose first row and columnis all 1, and otherwise m;,; = Mi-1,; + Mi,j;-1 +xMj:-1,;-1, then det M = (1 + x)(), Let D, denote the desired value. Modify M by subtracting row i — 1 from row i for i from n— 1 down to 1, and then subtract column j — 1 from column j

for 7 from n—1 downto 1. Fori, 7 > 1, the entryin position (i, 7) becomes (m;,; — Mi-1,;) — (M,j;-1 — M-1,;-1). By the given recurrence, this equals

(1 + x)mj-1,;-1. The entries in row 0 and column 0 become 0, except for position (0,0), which remains 1. Expanding the determinant thusyields

D, = (1+x)""!D,_1. With D; = 1, the claim follows by induction. 2.1.69.

Ss S (*/)(ms n— 221) _ [(r+m)/2]![(n+m+ 1/2]! 4S

n— 2]

| n/2|!| m/2]!| n/2]!| m/2]!

when m and n are nonnegative integers. The assertion follows immediately from the fact that each side satis-

fies the sameinitial conditions a(n, 0) = a(0, n) = | n2/2 | +1 (by inspection) and recurrence

a(n, m)— a(n—1, m) — a(n, m—1) =

(7/2+mi2)° if both m and n are even 0

otherwise.

The fact that the right side satisfies the recurrence can be seen by

liberal use of the identities | (k — 1)/2] = | k/2| and | (k + 1)/2] =[k/2]. To prove it for the left side we combine the sums term by term and use

Pascal’s Formula to annihilate everything except the one term (i, j) = (n/2, m/2) that arises when both m and n are even. 2.1.70. Recurrence for beanbag testing. Bags dropped from floor b or higher break; lower survive. If f(t, k) is the largest b that can be confirmed by k available beanbags and t allowable tests, then f(t, k) = f(tt-1,k-1)+ f(t-1,k)+1 when k > 1, with f(t, 1) =t. A single beanbag can be used to test floor 1,...,¢in turn. The minimum floor b that causes breakage will be discovered if b < t. If the floors tested are not consecutive from floor 1, then the first time a floor j is

Chapter 2: Recurrence Relations

tested without having tested 7 — 1 the bag may break, and it cannot be determined whether 0b is j or j — 1. (Actually, the argumentfor there-

currenceis also valid when k = 1, with f(t, 0) = 0.) Suppose k > 1. Given the values when the sum of the argumentsis smaller, we claim f(t, k) = f(t-—1,k-—1)+ f(¢-—1,k)+1. Thefirst test

is from floor f(t-—1,k—1)+1; call this 7. If the bag breaks, then b < j. There remain k—1 bags and t—1 tests, which suffice to find 6 when 6 < j.

If they do not determine b (because the bags never break), then b = j. Otherwise, the bag does not break, and we know 6b > 7. There remain k bags and ¢t — 1 tests. The protocol for finding 6 in the range from 1 to

f(t -—1, k) can now be applied with 7 added to everytest. It will find b in the range from j + 1 to 7 + f(t—1,k), given that we know b > /.

This protocol shows f(t, k) > f(t-1,k-1)+ f(t-1,k)+1. It cannot confirm a larger value, because whenthefirst test succeeds the subsequent part of the protocol cannot be certain of confirming a value higher than j + f(t—1,k). Wealso must show that no other protocol can do better. If thefirst test is higher than 7, then the bag may break, and with k—1 bags and t— 1 tests we will not be able to confirm the threshold that may be anywhere between 1 and at least 7. If the first test is lower than j, then the bag may survive, and the subsequent k — 1 tests will not be able to confirm

all levels as high as 7 + f(t-—1, k).

2.2. ELEMENTARY SOLUTION METHODS 2.2.1. Let a, satisfy a, = 2a,_; + 3an_2 for n > 2. a) If ap and a, are odd, then a, is odd for all n > 0. Computing modulo 2, the recurrence reduces to a, = an_2 (mod2). Thus a, remains odd for all positive n. The generalsolution is an = 5 (ao +a ,)2"”+ 4 (2ao —a,)(—1)”. The characteristic equation is x? — 2x — 3 = 0, with roots 2 and —1. Hence the

general solution is a, = A2” + B(—1)” for constants A and B. Setting n=0Oand n= 1, these are determined by ag = A+B and a; = 2A—B, so

A = (ao + a1)/3 and B = (2a— a1)/4. 2.2.2. If(n— 3)a, = na,_; —n* —nforn > 4, with a3 = 10, then a, = (3) + 2(5) + ({) for n= 3. Let b, = (3) + 2(5) + (7); we seek a, = b,. Asa basis for induction, bs = (3) + 2(3) + (;) =1+6+3=10=as3. Forn> 4, the recurrence and induction hypothesis yield

Section 2.2: Elementary Solution Methods

2 (n — 3)dyn = Nan_-y —N* 2 —n=nb,_-1—-—n*—-—n

=f" 5" )+2n(" 5h) nf" 7") — nin 1)

=(n- 4 +2(n— 2(5) +(n- (7) - 2("5 ‘)

= (n—3)b, + 2(°) + 2(] - 2" ‘) = (n—3)bn Hence a, = b,. There is a simpler formula: a, = (3) + 2(3) + (7) =

("3") + ("3") = ("37). However a, = ("3") seemsnot so easy to verify by induction. 2.2.3. If an = an_s forn > 4, then a, The characteristic equation is x* —

1 = 0, with roots 1,-1,i,-i. Hence a, = A+ B(-1)’ + Ci” + D(-i)”. Evaluating at 0,1,2,3 yields

aj =A+B+C+D,

ay=A-B+i(C-D),

ag =A+B-(C+D),

azj=A-—B-i(C-D).

From this, A+ B= $(ao+ az),

C+D = $(ao— az),

A-B=34(a1 +43),

C— D= (a1 — as).

Finally,

A= F(a9 +a, +ag+a3),

C= F(ap + a1 —aq-4s),

B = +(ao — a1 + az — a3),

D = 4(ao — a1 — ag + a3).

2.2.4. If an = 8an_-1 — 2an-2 + 1 for n > 2, with ag = 2 and a, = 4, then a, = 3-2”-1-—nforn> 0. The characteristic equation is x? —3x+2 = 0, with roots 2 and 1. Because the exponential in the inhomogeneous term is a characteristic root, we use Cn as a particular solution: Cn = 3C(n —

1) — 2C(n — 2) +1 yields Cn = Cn—-3C+4C+1,s0 C = —1. Hence the general solution is a, = A2”+B-—n. Atn = 0andn = 1 we obtain 2=A+Band4=2A+B-1,soA=8and B= -1. 2.2.5. Savings at 5% interest, with 100 addedat the start of each year. Let a, be the amount in the account at the end of year n, so ap = 0. We are given a, = 1.05(a,_1 + 100) for n > 1, with ap = 0. Asa particular solution, we have a constant C, satisfying C = 1.05C + 105, so C = —2100.

The general solution is a, = A(1.05)” — 2100. At n = 0, we obtain 0 = A — 2100, so A = 2100. Thus a, = 2100(1.05” — 1).