[PDF] [PDF] BIJECTIVE PROOF PROBLEMS

[PDF] Bijective Proof Examples

8 fév 2017 · strings of length 13 that contain exactly three 1s Proof Because h is injective and surjective, it is bijective Because there exists a bijection between the number of ways to buy 10 donuts from four flavors and the number of 0/1 strings of length 13 that contain exactly three 1s, those numbers must be equal

[PDF] BIJECTIVE PROOF PROBLEMS

18 août 2009 · A combinatorial proof of the problem is not known In all cases are Problems 27 , 28, 59, 107, 143, 118, 123 (injection of the type described),

[PDF] 2 Properties of Functions 21 Injections, Surjections - FSU Math

The examples illustrate functions that are injective, surjective, and bijective Here Prove that the function f : N → N be defined by f(n) = n 2 is injective Proof

Bijective Proofs: You say you want an involution? - Penn Math

5 mar 2009 · Definition A bijection is a one-to-one and onto mapping Example A B The philosophy of combinatorial proof Bijective proof Example n ∑

[PDF] Bijective matrix algebra - CORE

bijective proof that BA = I (See Theorem 44 and Theorem 47 in §6 ) First, we must give a rigor- ous definition of what we mean by a bijective proof of a matrix 

[PDF] Proofs with Functions

23 fév 2009 · A function that is both one-to-one and onto is called a bijection or a one-to- Let's prove this using our definition of one-to-one Proof: We need 

[PDF] Section 44 Functions

CS 130 – Discrete Structures 45 Example of Surjective Functions • To prove a function to be surjective: need to show that an arbitrary member of the codomain  

[PDF] Functions

1 mai 2020 · The same proof works with minor changes if f′(x) < 0 for all x Example Define f : R − {0} → R − {1} by f(x) = x + 1 x Prove that f is surjective

[PDF] Introduction Bijection and Cardinality

A function f from A to B is called onto, or surjective, if and For example, {a,b,c} = {d,e,f} a b Exercise: Prove that a bijection from A to B exists if and only if

[PDF] Final Exam Solution Guide - Stony Brook Mathematics

Justify your answer with a proof or a counter-example Yes, f is necessarily a bijection Since we are told it is an injection, it suffices to show that it is a surjection

[PDF] bijoux victoria catalogue 2020 belgique

[PDF] bikini toulouse programmation 2019

[PDF] bilan covid 19 france 9 avril 2020

[PDF] bilan financier association modele

[PDF] bilan financier cours et exercices+pdf

[PDF] bilan financier d'une entreprise exemple

[PDF] bilan financier modèle

[PDF] bilingual education act

[PDF] bilingual university in canada

[PDF] bilingual university located in canada's capital

[PDF] billet avion paris toulon air france

[PDF] billet d'avion air france promotion

[PDF] billet d'avion easyjet paris nice

[PDF] billet d'avion japon air france

[PDF] billet d'avion paris congo brazzaville

BIJECTIVE PROOF PROBLEMS

August 18, 2009

Richard P. Stanley

The statements in each problem are to be proved combinatorially, in most cases by exhibiting an explicit bijection between two sets. Try to givethe most elegant proof possible. Avoid induction, recurrences, generating func- tions, etc., if at all possible. The following notation is used throughout for certain sets of numbers:

Nnonnegative integers

Ppositive integers

Zintegers

Qrational numbers

Rreal numbers

Ccomplex numbers

[n] the set{1,2,...,n}whenn?N We will (subjectively) indicate the difficulty level of each problem as follows: [1] easy [2] moderately difficult [3] difficult [u] unsolved [?] The result of the problem is known, but I am uncertain whether a combinatorial proof is known. [?] A combinatorial proof of the problem is not known. In all cases, the result of the problem is known. Further gradations are indicated by + and -; e.g., [3-] is a little easier than [3]. In general, these difficulty ratings are based on the assumption that the solutions to the previous problems are known. For those wanting to plunge immediately into serious research, the most interesting open bijections (but most of which are likely to be quite difficult) are Problems 27, 28, 59, 107, 143, 118, 123 (injection of the typedescribed),

125, 140, 148, 151, 195, 198, 215, 216, 217, 226, 235, and 247.

1

CONTENTS

1. Elementary Combinatorics 3

2. Permutations 10

3. Partitions 20

4. Trees 30

5. Catalan Numbers 38

6. Young Tableaux 50

7. Lattice Paths and Tilings 61

2

1. Elementary Combinatorics

1. [1] The number of subsets of ann-element set is 2n.

2. [1] Acompositionofnis a sequenceα= (α1,α2,...,αk) of positive

integers such that?αi=n. The number of compositions ofnis 2n-1.

3. [2] The total number of parts of all compositions ofnis equal to

(n+ 1)2n-2.

4. [2-] Forn≥2, the number of compositions ofnwith an even number

of even parts is equal to 2 n-2.

5. [2] Fix positive integersnandk. Find the number ofk-tuples (S1,S2,...,Sk)

of subsetsSiof{1,2,...,n}subject to each of the following conditions separately, i.e., the three parts are independent problems (all with the same general method of solution). (a)S1?S2? ··· ?Sk (b) TheSi"s are pairwise disjoint. (c)S1∩S2∩ ··· ∩Sk=∅

6. [1] IfSis ann-element set, then let?S

k?denote the set of allk-element subsets ofS. Let?n k?= #?S k?, the number ofk-subsets of ann-set. (Thus we aredefiningthe binomial coefficient?n k?combinatorially when n,k?N.) Then k!?n k? =n(n-1)···(n-k+ 1).

7. [1+] (x+y)n=?nk=0?

n k?xkyn-k. Herexandyare indeterminates and we define ?x k? =x(x-1)···(x-k+ 1) k!. Note.Both sides are polynomials inxandy. If two polynomials P(x,y) andQ(x,y) agree forx,y?Nthen they agree as polynomials.

Hence it suffices to assumex,y?N.

3

8. [1] Letm,n≥0. How many lattice paths are there from (0,0) to

(m,n), if each step in the path is either (1,0) or (0,1)? The figure below shows such a path from (0,0) to (5,4). (0,0)(5,4)

9. [1] Forn >0, 2?2n-1

n?=?2n n?.

10. [1+] Forn≥1,

n? k=0(-1)k?n k? = 0.

11. [1+] Forn≥0,

n? k=0? x k?? y n-k? =?x+y n? .(1)

12. [2-] Forn≥0,

n? k=0? x+k k? =?x+n+ 1 n?

13. [3] Forn≥0,

n? k=0? 2k k??

2(n-k)

n-k? = 4 n.

14. [3-] We have

m i=0? x+y+i i?? y a-i?? x b-i? =?x+a b?? y+b a? wherem= min(a,b). 4

15. [3-] Forn≥0,

n k=0? n k? 2 x k=n? j=0? n j?? 2n-j n? (x-1)j.

16. [3-] Fixn≥0. Then

i+j+k=n? i+j i?? j+k j?? k+i k? =n? r=0? 2r r?

Herei,j,k?N.

17. [?] Forn≥0,

2n? k=0(-1)k?2n k? 3 = (-1)n(3n)! n!3.

18. [3] Letf(n) denote the number of subsets ofZ/nZ(the integers modulo

n) whose elements sum to 0 (modn) (including the empty set∅). For instance,f(5) = 8, corresponding to∅,{0},{1,4},{0,1,4},{2,3}, {0,2,3},{1,2,3,4},{0,1,2,3,4}. Whennis odd,f(n) is equal to the number of "necklaces" (up to cyclic rotation) withnbeads, each bead colored white or black. For instance, whenn= 5 the necklaces are (writing 0 for white and 1 for black) 00000, 00001, 00011, 00101,

00111, 01011, 01111, 11111. (This is easy ifnis prime.)

19. [2-] How manym×nmatrices of 0"s and 1"s are there, such that every

row and column contains an odd number of 1"s?

20. (a) [1-] Fixk,n≥1. The number of sequencesa1···ansuch that

(b) [2+] If in additiona1?=an, then the numbergk(n) of such se- quences is g k(n) = (k-1)n+ (k-1)(-1)n.(2)

Note.It"s easy to prove bijectively that

g k(n-1) +gk(n) =k(k-1)n-1, from which (2) is easily deduced. I"m not sure, however, whether anyone has given adirectbijective proof of (2). 5

21. [2-] Ifpis prime anda?P, thenap-ais divisible byp. (A combinato-

rial proof would consist of exhibiting a setSwithap-aelements and a partition ofSinto pairwise disjoint subsets, each withpelements.)

22. (a) [2] Letpbe a prime. Then?2p

p?-2 is divisible byp2. (b) (?) In fact ifp >3, then?2p p?-2 is divisible byp3.

23. [2-] Ifpis prime, then (p-1)! + 1 is divisible byp.

24. [1] AmultisetMis, informally, a set with repeated elements, such as

{1,1,1,2,4,4,4,5,5}, abbreviated{13,2,43,52}. The number of ap- pearances ofiinMis called themultiplicityofi, denotedνM(i) or justν(i). The definition of asubmultisetNofMshould be clear, submultisets doesMhave?

25. [2] Thesizeorcardinalityof a multisetM, denoted #Mor|M|, is its

number of elements, counting repetitions. For instance, if

M={1,1,1,2,4,4,4,5,5}

then #M= 9. A multisetMisona setSif every element ofMis an element ofS. Let??n k??denote the number ofk-element multisets on ann-set, i.e., the number of ways of choosing, without regard to order, kelements from ann-element set if repetitions are allowed. Then n k?? =?n+k-1 k?

26. [2-] Fixk,n≥0. Find the number of solutions in nonnegative integers

to x

1+x2+···+xk=n.

27. [*] Letn≥2 andt≥0. Letf(n,t) be the number of sequences withn

theithxand thejthxin the sequence. (Thus the total number of terms in each sequence isn+ 2t?n

2?.) Then

f(n,t) =(n+tn(n-1))! n!t!n(2t)!(n 2)n j=1((j-1)t)!2(jt)!(1 + (n+j-2)t)!. 6 Note.This problem a combinatorial formulation of a special case of the evaluation of a definite integral known as theSelberg integral. A combinatorial proof would be very interesting.

28. [*] Abinary de Bruijn sequenceof degreenis a binary sequencea1a2···a2n

(soai= 0 or 1) such that all 2n"circular factors"aiai+1...ai+n-1(tak- ing subscripts modulo 2 n) of lengthnare distinct. An example of such a sequence forn= 3 is 00010111. The number of binary de Bruijn sequences of degreenis 22n-1. Note.Note that 22n-1=⎷22n. Hence ifBndenotes the set of all binary de Bruijn sequences of degreenand{0,1}2ndenotes the set of all binary sequences of length 2 n, then we want a bijection?:Bn×Bn→ {0,1}2n. Note.Binary de Bruijn sequences were defined and counted (nonbi- jectively) by Nicolaas Govert de Bruijn in 1946. It was then discovered in 1975 that this problem had been posed A. de Rivi`ere and solved by

C. Flye Sainte-Marie in 1894.

29. [3] Letαandβbe two finite sequences of 1"s and 2"s. Defineα < βif

αcan be obtained fromβby a sequence of operations of the following types: changing a 2 to a 1, or deleting the last letter if it is a 1. Define α?βifαcan be obtained fromβby a sequence of operations of the following types: changing a 2 to a 1 if all letters preceding this 2 are also 2"s, or deleting the first 1 (if it occurs). Givenβandk≥1, letAk(β) be the number of sequences∅< β1< β2<···< βk= β. LetBk(β) be the number of sequences∅ ?β1?β2? ··· ? k=β. For instance,A3(22) = 7, corresponding to (β1,β2) = (2,21), (11,21), (1,21), (11,12), (1,12), (1,11), (1,2). SimilarlyB3(22) = 7, corresponding to (β1,β2) = (2,21), (11,21), (1,21), (2,12), (1,12), (1,11), (1,2). In general,Ak(β) =Bk(β) for allkandβ.

30. [1] TheFibonacci numbersFnare defined byF1=F2= 1 andFn+1=

F n+Fn-1forn≥2. The numberf(n) of compositions ofnwith parts

1 and 2 isFn+1. (There is at this point no set whose cardinality is

known to beFn+1, so you should simply verify thatf(n) satisfies the Fibonacci recurrence and has the right initial values.)

31. [2-] The number of compositions ofnwith all parts>1 isFn-1.

32. [2-] The number of compositions ofnwith odd parts isFn.

7

33. [1+] How many subsetsSof [n] don"t contain two consecutive integers?

34. [2-] How many binary sequences (i.e., sequences of 0"s and 1"s) (ε1,...,εn)

satisfy

35. [2] Show that

?a

1a2···ak=F2n,

where the sum is over all compositionsa1+a2+···+ak=n.

36. [3-] Show that

?(2a1-1-1)···(2ak-1-1) =F2n-2, where the sum is over all compositionsa1+a2+···+ak=n.

37. [2] Show that

?2{#i:ai=1}=F2n+1, where the sum is over all compositionsa1+a2+···+ak=n.

38. [2+] The number of sequences (δ1,δ2,...,δn) of 0"s, 1"s, and 2"s such

that 0 is never immediately followed by a 1 is equal toF2n+2.

39. [2?] Show thatF2n-Fn-1Fn+1= (-1)n-1.

40. [2-] Show thatF1+F2+···+Fn=Fn+2-1.

41. [2] Continuing Exercise 5, fix positive integersnandk. Find the num-

ber ofk-tuples (S1,S2,...,Sk) of subsetsSiof{1,2,...,n}satisfying S

1?S2?S3?S4?S5? ···.

(The symbols?and?alternate.) 8

Bonus Chess Problem

(related to Problem 27)

R. Stanley

2004

Serieshelpmate in 14: how many solutions?

In a Serieshelpmate inn, Black makesnconsecutive moves. White then makes one move, checkmating Black. Black may not check White (except possibly on his last move, if White then moves out of check) and may not move into check. White and Black arecooperatingto achieve the goal of checkmate. Note.For discussion of many of the chess problems given here, see 9

2. Permutations

42. [1] In how many ways cannsquare envelopes of different sizes be ar-

ranged by inclusion? For instance, with six envelopesA,B,C,D,E,F (listed in decreasing order of size), one way of arranging them would beF?C?B,E?B,D?A, whereI?Jmeans that envelopeIis contained in envelopeJ.

43. [2+] Letf(n) be the number of sequencesa1,...,anof positive integers

such that for eachk >1,konly occurs ifk-1 occurs before the last occurrence ofk. Thenf(n) =n!. (Forn= 3 the sequences are 111,

112, 121, 122, 212, 123.)

44. [2-] Letw=a1a2···anbe a permutation of 1,2,...,n, denotedw?

S n. We can also regardwas the bijectionw: [n]→[n] defined by w(i) =ai. We say thatiis afixed pointofwifw(i) =i(orai=i).

The total number of fixed points of allw?Snisn!.

45. [2] Aninversionofwis a pair (i,j) for whichi < jandai> aj. Let

inv(w) denote the number of inversions ofw. Then w?Snq inv(w)= (1 +q)(1 +q+q2)···(1 +q+···+qn-1).

46. [1] For anyw?Sn, inv(w) = inv(w-1).

47. [2-] How many permutationsw=a1a2···an?Snhave the property

(whetheriis to the left or right ofi+1) are all less thani? An example of such a permutation is 976412358.

48. [2-] How many permutationsa1a2···an?Snsatisfy the following

n= 3 there are the four permutations 123, 213, 231, 321.

49. [2] Aderangementis a permutation with no fixed points. LetD(n)

denote the number of derangments of [n] (i.e., the number ofw?Sn with no fixed points). (SetD(0) = 1.) Then

D(n) =n!?

1-1

1!+12!- ···+ (-1)n1n!?

.(3) 10 Note.A rather complicated recursive bijection follows from a gen- eral technique for converting Inclusion-Exclusion arguments to bijective proofs. What is wanted, however, is a "direct" proof of the identity

D(n) +n!

1!+n!3!+···=n! +n!2!+n!4!+···.

In other words, the number of ways to choose a permutationw?Sn and then choose an odd number of fixed points ofw, or instead to choose a derangement inSn, is equal to the number of ways to choose w?Snand then choose an even number of fixed points ofw.

50. [1] Show that

D(n) = (n-1)(D(n-1) +D(n-2)), n≥1.

51. [3] Show that

D(n) =nD(n-1) + (-1)n.

(Trivial from (3), but surprisingly tricky to do bijectively.)

52. [2] Letm1,...,mn?Nand?imi=n. The number ofw?Snwhose

disjoint cycle decomposition contains exactlymicycles of lengthiis equal ton!

1m1m1!2m2m2!···nmnmn!.

Note that, contrary to certain authors, we are including cycles oflength one (fixed points).

53. [1+] Afixed point free involutioninS2nis a permutationw?S2n

satisfyingw2= 1 andw(i)?=ifor alli?[2n]. The number of fixed point free involutions inS2nis (2n-1)!! := 1·3·5···(2n-1). Note.This problem is a special case of Problem 52. For the present problem, however, give a factor-by-factor explanation of the product

1·3·5···(2n-1).

54. [3] IfX?P, then write-X={-n:n?X}. Letg(n) be the

number of ways to choose a subsetXof [n], and then choose fixed

point free involutionsπonX?(-X) and ¯πon¯X?(-¯X), where¯X={i?[n] :i /?X}. Theng(n) = 2nn!.

11

55. [2-] Letn≥2. The number of permutationsw?Snwith an even

number of even cycles (in the disjoint cycle decomposition ofw) is n!/2.

56. [2] Letc(n,k) denote the number ofw?Snwithkcycles (in the

disjoint cycle decomposition ofw). Then n k=1c(n,k)xk=x(x+ 1)(x+ 2)···(x+n-1). Try to givetwobijective proofs, viz., first lettingx?Pand showing that both sides are equal as integers, and second by showing thatthe coefficients ofxkon both sides are equal.

57. [2] Letwbe a random permutation of 1,2,...,n(chosen from the

probability that in the disjoint cycle decomposition ofw, the length of the cycle containing 1 isk? In other words, what is the probability thatkis the least positive integer for whichwk(1) = 1? Note.Letpnkbe the desired probability. Thenpnk=fnk/n!, where f nkis the number ofw?Snfor which the length of the cycle containing

1 isk. Hence one needs to determine the numberfnkby a bijective

argument.

58. (a) [2] Letwbe a random permutation of 1,2,...,n(chosen from the

uniform distribution),n≥2. The probability that 1 and 2 are in the same cycle ofwis 1/2. (λ1,λ2,...,λ?), whereλ1≥λ2≥ ··· ≥λ?>0 and?λi=k. Choose a random permutationw?Sn. LetPλbe the probability that 1,2,...,λ1are in the same cycleC1ofw, andλ1+1,...,λ1+quotesdbs_dbs21.pdfusesText_27