The Art of Bijective Combinatorics Part I
An introduction to enumerative, algebraic and bijective combinatorics
The Institute of Mathematical Sciences, Chennai, India (January-March 2016)
List of bijections
Trees
bijection binary trees — complete binary trees, Ch2a 26 video
bijection binary trees — (forests of) planar trees, Ch2a 36 video
bijection binary trees — 2-colored Motzkin paths, Ch2a 90 video
bijection (complete) binary trees — Dyck paths, Ch2a 65 video and (with violin) 70 video
bijection (complete) binary trees — triangulations Ch2b 31 video
bijection planar trees — Dyck paths, Ch2a 92 video
bijection planar trees — Lukasiewicz paths, Ch2a 98 video
Paths
bijection Dyck paths — (complete) binary trees , Ch2a 65 video and 72 video
bijection Dyck paths — planar trees, Ch2a 92 video
bijection Dyck paths — 2-colored Motzkin paths, Ch2a 55 video
bijection 2-colored Motzkin paths — binary trees Ch2a 90 video
bijection Dyck paths — semi-pyramids of dimers, Ch2c 71 (with violin) video
bijection Lukasiewicz paths — Dyck paths , Ch2a 60 video
bijection Lukasiewicz paths — planar trees, Ch2a 98 video
Staircase polygons
bijection staircase polygons — 2-colored Motzkin paths, Ch2a 105 video
bijection staircase polygons — Dyck paths, Ch2a 110 video
bijection staircase polygons — basis of TL_n , Ch2b-complements-TLn, 23 video
bijection staircase polygons — (321)- avoiding permutations, Ch2b-complements-TLn, 34 (no video)
Non-crossing partitions
bijection non-crossing partitions — Dyck paths, Ch2b 8 video
bijection non-crossing partitions — Catalan permutations , Ch2b 53 video
Planar maps
bijection planar maps — planar quartic maps, Ch2d 18 video
bijection rooted planar maps — rooted planar quartic maps, Ch2d 20 video
reverse bijection, Ch2d 22 video more explanations in this video
bijection rooted planar quartic maps — well balanced blossoming trees,
(Schaeffer bijection) Ch2d 25-44 video
bijection triangulations — (complete) binary trees, Ch2b 23 (with violin) video
Temperley-Lieb algebra TL_n
bijection basis of TL_n — some heaps of dimers, Ch2b-complements-TL_n, 18 video
bijection basis of TL_n — Dyck paths, Ch2b-complements-TL_n, 19 video
bijection basis of TL_n — staircase polygons, Ch2b-complements-TL_n, 23 video
bijection basis of TL_n — (321)- avoiding permutations, Ch2b-complements-TL_n, 31 video
Permutations
bijection permutations (cycles notation) — permutations (word), Ch4a 7-8 video and 20 video
bijection permutations — assemblées of increasing arborescences, Ch4a 96 video
bijection permutations — increasing binary trees, Ch4a 75-76 video
bijection permutations — inversion table, Ch4a 29-30 video
reverse bijection 33-44 video
bijection permutations — inversion table (with the Maj index), Ch4a 52-72 video
bijection permutations — pair of Young tableaux same shape (Robinson-Schensted, RS)
RS with Schensted insertions, Ch4c 24-46 video
RS with light and shadows, Ch4c 53-73 video
RS with growth diagrams Ch4d 4-26 video
RSK matrices — pairs of semi-standard Young tableaux, Ch4d 63 video
bijection involutions (no fixed points) — oscillating tableaux, Ch4d 52-55 video
bijection involutions (no fixed points) — Hermite histories, Ch4b 68-77 video
bijection Catalan permutations — non-crossing partitions, Ch2b 53 video
bijection (321)- avoiding permutations — basis of the TL_n, Ch2b-complements-TLn, 31 video
Histories
bijection Hermite histories — chord diagrams, Ch4b 68-77 video
bijection Laguerre histories — permutations (with binary trees), Ch4b 11-22 video
(with words), Ch4b 23-33 video
reciprocal bijection Ch4b 34-40 video
Rook placements
bijection rook placements — oscillating tableaux, Ch4d 52 video
bijection rook placements — Hermite histories, Ch4d 53 video
bijection rook placements — involutions with 2-colored fixed points, Ch4d 56 video
bijection staircase rook placements — Partitions, Ch4d 58 video
Non-intersecting configurations of paths
bijection plane partitions — non-intersecting configurations of paths, Ch5a 97-105 video
bijection aztec tilings — non-intersecting configurations of Schröder paths, Ch5b 94 video
bijection semi-standard Young tableaux — non-intersecting configurations of paths,
Ch5a 69-70 (by rows) video
Ch5b 19-22 (by rows) video (by columns) video
Bijective proof of identities
visual proof of Pythagorus theorem, Ch1a 84 video
bijective proof of an identity with q-series, Ch1a 113 video
bijective proof for the number of aztec tilings, Ch5b 94-113 video
bijective proof for the number of Baxter permutations,
Ch4b 108-122, video (bijection Baxter permutations triple of paths with Laguerre histories)
and Ch5a 45-48 video (triple of paths as binomial determinant)
and Ch5a 81-86 video (with the formula contents / hook length)
bijective proofs for the formula giving the Catalan number:
the philosophy of bijective proofs for various Catalan formulae, Ch1a 127 video
bijective proof of the multiplicative recursion for Catalan numbers, Ch2b 60 video
bijective proof related to the cyclic lemma, Ch2c 11 video
bijective proof with binary trees, Ch2c 22 video , with Dyck paths, Ch2d 80 video
bijective proof with the reflexion principle, 44 video
bijective proof of Lagrange inversion formula, Ch2c 28-39 video
bijective proof of Mehler identity, Ch3b 27-34 video
bijective proof of Touchard identity, Ch2b 73 video