CoursE X.V. IMSc 2016
Course IMSc Chennai, India
January-March 2016
An introduction to enumerative, algebraic and
bijective combinatorics
Index
admissible orientation (of a planar graph), Ch5b 148
algebra of formal power series Ch1a 33
algebraic grammar, Ch1d 70
algebraic language, Ch1d 71
algebraic power series, Ch1b 27
(alpha)-distribution (in the Catalan garden), Ch2c 13, Ch2c 47, Ch2c 55-57
alternative tableaux, Ch4d-complements 6
alternating permutations, Ch3b 65
ambiguous grammar, Ch1d 74
André, Désiré, Ch3b 65
André permutation, Ch4a 102
ansatz (cellular), Ch4d 50, Ch4d-complements 18
Appell polynomial, Ch3b 40
Arbogast triangle, Ch2c 17-19
arborescence (species), Ch3a 15, 44-45, 55
(enriched increasing), Ch3b-complements 23
(1-2 increasing), Ch4a 97
arctic circle theorem, Ch5b 130
area parameter (q-Catalan), Ch2d 59-62
Askey tableau (of orthogonal polynomials), Ch3b-complements 45
assemblée (of structures for species), Ch3a 28
(of permutations), Ch3b 5
(of increasing arborescences), Ch4a 95
associahedron, Ch4d-complements 44, Ch5b 116
automaton, Ch1d 77
average cost (of an insertion in a random binary search tree), Ch4a 116
average height (in a random increasing binary tree), Ch4a 120
average Strahler number (of a random binary tree) Ch2b-complements-Strahler, 2
aztec tilings, Ch5b 87
balanced blossoming trees, Ch2d 38
ballot paths, Ch2a 47
ballot problem, Ch2c 15, 51
basis of the Temperley-Lieb algebra, Ch2b-complements-TL_n, 18-22
Baxter permutations, Ch4b 107, Ch5a 43
Bell numbers, Ch3a 13, 54
(beta)-distribution (in the Catalan garden), Ch2c 49, Ch2c 58-61
Bernoulli numbers, Ch3b 75
bifurcation ratio (in rivers network), Ch2b-complements-Strahler, 24
bijection basis of the Temperley-Lieb algebra — staircase polygons,
Ch2b-complements-TL_n, 23-28
bijection basis of the Temperley-Lieb algebra — (321)- avoiding permutations,
Ch2b-complements-TL_n, 23-28
bijection binary trees — complete binary trees, Ch2a 26
bijection binary trees — (forests of) planar trees, Ch2a 36
bijection binary trees — 2-colored Motzkin paths, Ch2a 90
bijection (complete) binary trees — Dyck paths, Ch2a 65 (video with violin), 72
bijection Catalan permutations — non-crossing partitions, Ch2b 53
bijection Dyck paths — 2-colored Motzkin paths, Ch2a 55
bijection Dyck paths — Lukasiewicz paths, Ch2a 60
bijection Dyck paths — semi-pyramids of dimers, Ch2c 71 (video with violin)
bijection Hermite histories — chord diagrams, Ch4b 68-77
bijection Laguerre histories — permutations (with binary trees), Ch4b 11-22
(with words), Ch4b 23-33, reciprocal bijection Ch4b 34-40
bijection non-crossing partitions — Dyck paths, Ch2b 8
bijection staircase polygons — 2-colored Motzkin paths, Ch2a 105
bijection staircase polygons — Dyck paths, Ch2a 110
bijection permutations (cycles notation) — permutations (word), Ch4a 7-8, 20
bijection permutations — assemblées of increasing arborescences, Ch4a 96
bijection permutations — increasing binary trees, Ch4a 75-76
bijection permutations — inversion table, Ch4a 29-30, 33-44
bijection permutations — inversion table (with the maj index), Ch4a 52-72
bijection permutations — pair of Young tableaux same shape (Robinson-Schensted)
with Schensted insertions, Ch4c 24-46
with light and shadows, Ch4c 53-73
with growth diagrams Ch4d 4-26
(extension to matrices) matrices — pairs of semi-standard Young tableaux (RSK), Ch4d 63
bijection planar maps — planar quartic maps, Ch2d 18
bijection planar trees — Dyck paths, Ch2a 92
bijection planar trees — Lukasiewicz paths, Ch2a 98
bijection plane partitions — non-intersecting configuration of paths,
bijection rooted planar maps — rooted planar quartic maps, Ch2d 20
bijection rooted planar quartic maps — well balanced blossoming trees,
(Schaeffer bijection) Ch2d 26-44
bijection aztec tilings — non-intersecting configurations of Schröder paths, Ch5b 94
bijection triangulations — (complete) binary trees, Ch2b 23 (video with violin), 31
bijection semi-standard Young tableaux — non-intersecting configurations of paths,
bijective proof (of an identity) Ch1a 113
bijective proof for the number of aztec tilings, Ch5b 94-113
bijective proof for the number of Baxter permutations, Ch4b 108-122, 45-48, 81-86
bijective proof of the multiplicative recursion for Catalan numbers, Ch2a 30, Ch2b 60
bijective proof for the formula giving the Catalan number Ch1a 127, 132, Ch2c 22
bijective proof of Lagrange inversion formula, Ch2c 28-39
bijective proof of Mehler identity, Ch3b 27-34
bijective proof of Touchard identity, Ch2b 73
binary search tree, Ch4a 103
analysis of the insertion in —, Ch4a 115
binary tree, Ch2a 11
binary tree (complete), Ch1a 3, Ch2a 10
binohedron, Ch4d-complements 56
binomial determinant, Ch5a 29
binomial power series Ch1a 42
binomial type polynomial, Ch3b 36
bilateral Dyck path, Ch1b 42
blossoming trees, Ch1d 37
bounce parameter (q-Catalan), Ch2d 65-67
Boolean lattice, Ch4d-complements 22
Bousquet-Mélou, Mireille, Ch1d 86
Bruhat order (weak), Ch4d-complements 24
canopy (of binary tree), Ch2d 97-98, 92
Cartier-Foata commutation monoids Ch1b 36
Catalan numbers Ch1a 7, Ch1b 38
q-analogue of Catalan numbers, Ch2d 57-63
Catalan factorisation, Ch2d 76-77
Catalan permutations, Ch2b 41
Catalan triangle, Ch2c 16
Catalan word, Ch2d 78
catalytic variables, Ch1d 85
Cayley tree (species), Ch3a 15, 44-45
cellular ansatz, Ch4d 50, Ch4d-complements 18
Charlier polynomials, Ch3b-complements 44
Chomsky-Schützenberger theorem, Ch1d 75
chords diagram, Ch2b 35
circuit, Ch1b 83
cofactor, Ch1b 90
combinatorial object (class of) Ch1a 56
complete symmetric functions, see homogeneous symmetric functions
concatenation (of two words) Ch1a 44
conjugate words, Ch2c 4
labelled —, Ch2c 4
contents (Young tableaux), Ch5a 54-64, 76
context-free grammar, see algebraic grammar
context-free language, see algebraic language
control theory, Ch3b-complements 13
convex polyomino, Ch1d 61—64
Cori-Vauquelin (planar maps), Ch2d 31
covering relation (poset), Ch4d 12
crossing (of a chord diagram), Ch4b 86
crossing condition (for the LGV Lemma), Ch5a 8
cycle, Ch1b 84
cycle (species), Ch3a 12, 50
cyclic lemma, Ch2c 5
decreasing sequence (in a permutation), Ch4c 101
« déployé" of a permutation, Ch4a 76
depth-first search (in a planar tree), Ch2a 35
derangements, Ch3a 12, 25
derivative (of formal power series) Ch1a 41
derivative (species), Ch3a 49
derivative (L-species), Ch3b 57
derivative (weighted species), Ch3b 13
derivation tree, Ch1d 74
descent (of a permutation), Ch4a 16
De Sainte-Catherine, Ch5b 156-162
determinant, Ch1b 89
D-finite power series, Ch1b 77
differential equations (with forcing terms), Ch3b-complements 3, 13
directed animal, Ch1d 42
random, Ch1d 47—48
on a circular strip Ch1d 51
directed path, Ch1c 21
Dixon elliptic functions, Ch3b-complements 38
double descent (of a permutation), Ch4a 79
double rise (of a permutation), Ch4a 79
double vertex (of a binary tree), Ch2a 14
DLA (Diffusion Limited Aggregation), Ch2b-complements-Strahler, 28
D-partitions Ch1a 74
dual (of a Young tableau), Ch4c-complement 19-52, 45
duality (for paths and non-intersecting configurations of paths), Ch5b 31, 32
Duffing equation, Ch3b-complements 20
Dyck language, Ch1d 72
Dyck lattice, Ch4d-complements 38-40
Dyck paths (definition) Ch1a 134, Ch2a 46
(bounded) Ch1c 23
elementary circuit, Ch1b 84
elementary symmetric functions, Ch5b 15
empty species, Ch3a 18
endofunction (species), Ch3a 13, 36
Erdös-Szekeres theorem, Ch4c 105
excedance (of a permutation), Ch4a 18
exponential generating functions Ch1a 34
exponential (of formal power series) Ch1a 42
Euler letter to Goldbach (introducing Catalan numbers), Ch1a 15, Ch2b 17-20
Euler formula for convex polyhedron, Ch2b 21
Euler-Descartes defects formula for polyhedron, Ch2b 21-22
Euler pentagonal theorem, Ch1c 77, Ch1d 4—13
Eulerian polynomials, Ch4a 17, 19
exponential polynomial, Ch3b 39
external vertex Ch1a 6
factor (left, right) of a word Ch1a 45
factorisation (of a word) Ch1a 45
Favard theorem, Ch4b 44
Fermat matrix (of binomial coefficients), Ch5b 38
inverse matrix, 39-41
Ferrers diagram, Ch1a 64
Fibonacci generating function Ch1a 23
Fibonacci polynomials, Ch1c 30, 35, 44, Ch1d 15
Flajolet, Philippe, Ch3b-complements 38, Ch2b-complements-Strahler 2
Fliess expansion, Ch3b-complements 4
Foata, Dominique, Ch4a 17, 102
Fomin, Sergey, Ch4d 3, 27, Ch4d 45
forest of planar trees, Ch2a 33
free monoid, Ch1a 44
forbidden pattern (for permutations), Ch2b 54
formal power series Ch1a 32
Françon, Jean, Ch1b 64, Ch2b 116
Frobenius identity, Ch4a 17
galactogram (in radiology), Ch2b-complements-Strahler, 30
(gamma)-distribution (in the Catalan garden), Ch2c 62-64
generating function (of a class of combinatorial objects) Ch1a 57
generating function (of a species), Ch3a 9
generating functions (of weigthed species), Ch3b 8
Genocchi numbers, Ch3b 75
Gessel path, 84
growth diagrams, Ch4d 3
Hankel determinant, Ch5b 55
— of Catalan numbers, Ch5b 153-154
Hasse diagram, Ch1d 14, Ch4d 12
heap of dimers, Ch1b 21
generating function, Ch1d 15
connected, Ch1d 87
height, left-, right- (of a vertex in a binary tree), Ch2a 15
Hermite polynomials, Ch1c 62, Ch3b 15-19, Ch3b-complements 42
moments of —, Ch4b 69-71
q-analogue I, Ch4b 79-86, q-analogue II, Ch4b 100
Hermite histories, Ch4b 68-77, Ch4d 54
q-analogue I, Ch4b 79-86, q-analogue II, Ch4b 100
Hipparcus number, Ch5b 121-124
histories (differential equations), Ch3b-complements 17
holonomic power series, see D-finite or P-recursive
homogeneous symmetric functions, Ch5b 14
hook length formula (for increasing binary trees), Ch4a 90
(for Young tableaux), Ch4c 8, Ch5a 54-64, 76
Hydrogeology, Ch1b 49, Ch2b-complements-Strahler, 24
increasing binary trees, Ch3b 44, Ch4a 74
infinite product (of formal power series) Ch1a 38
integral (of an L-species), Ch3b 62
iterated integral, Ch3b-complements 5, 34
increasing sequence (in a permutation), Ch4c 98
internal vertex Ch1a 6
inorder (in a binary tree), 21
inverse (of formal power series) Ch1a 41
inversions number (of a permutation), Ch4a 26
inversion table (of a permutation), Ch4a 26
involution (species), Ch3a 11, 33
involution with no fixed points (species), Ch3a 11, 33
irreducible representation (of the symmetric group), Ch4c 86
Ising model, Ch5b 150-151
isolated point (of a matching) Ch1c 58
Jacobi elliptic functions, Ch3b 79, Ch3b-complements 36
Jacobi-Trudi identities (for Schur functions), Ch5b 12
(for skew Schur functions) 26, 28
Jacobi permutations, Ch4a 98
Jeu de taquin, Ch4c-complement 2-8
Kastelyn formula, Ch5b 66-67, 126-129
Kastelyn theorem, Ch5b 145
kernel methodology, Ch1d 85
Knuth, Don, Ch1b 36, Ch2b 116, Ch4c 51, Ch4c-complement 55
Knuth transpositions, Ch4c-complement 55
Kreweras path, Ch1d 84
Kreweras determinants, Ch5b 49
lacet, see circuit
Lagrange inversion formula, Ch1d 22—23, 32, Ch2c 27-39
Laguerre configuration, Ch3b 23
Laguerre histories, Ch4b 4-10
weighted —, Ch4b 54
restricted —, Ch4b 60
q-analogues I, Ch4b 91-94, Ch4d-complements 14-16
q-analogue II, Ch4b 96
Laguerre polynomials, Ch1c 63, Ch3b 20-25
moments of —, Ch4b 48-53, 59, 66
q-analogue I, Ch4b 91-94, 98, Ch4d-complements 14-16
q-analogue II, Ch4b 96
Lah numbers, Ch3b 6
langage (in a free monoid) Ch1a 45
Lascoux, Alain, Ch4c-complement 60, Ch4d-complements 53, Ch5a 37
lattice, Ch4d-complements 20
leaf Ch1a 6
length (of a word) Ch1a 44
Leroux, Pierre, Ch3b-complements 13
LGV Lemma, Ch5a 3, 23
linear species, Ch3b 41
Loday, Jean-Louis, Ch4d-complements 46-48
logarithm (of formal power series) Ch1a 42
logarithmic height (of a Dyck path), Ch1c 68, Ch2b 103
logarithmic lemma (for heaps of dimers), Ch1b 26
Lucas polynomials, Ch1c 50
Laplace, Ch3b-complements 37
Lukasiewicz path, Ch2a 51
Lukasiewicz word, Ch2a 52
MacMahon, Percy, Ch4a 51
MacMahon formula for plane partitions in a box, Ch5a 96, 106-110
Macmahon-Narayana determinant Ch5b 42
Mahonian distribution, Ch4a 51
Maj index (q-Catalan number), Ch2d 57
Maj index (permutations), Ch4a 51, 52-72
Markov chain, Ch2d 91
matching (of the segment graph) Ch1c 30
matching polynomial (of a graph) Ch1c 57
Mehler identity (for Hermite polynomials), Ch3b 27
Meixner I, II polynomials, Ch3b-complements 44
minimum elements (left-to-right), Ch4a 9
moments (of orthogonal polynomials), Ch3b-complements 41, Ch4b 47
Motzkin path, Ch1d 46, Ch2a 48
(prefix of) Ch1d 45
2-colored —, Ch2a 50
Narayana numbers, Ch2c 51, Ch5a 44, 83
nesting (of a chord diagram), Ch4b 84
neutral element (in a free monoid) Ch1a 44
Nim game (on the Rothe diagram of a permutation), Ch4c 79
non-commutative formal power series Ch1a 46
non-crossing partitions, Ch2a 118, 122, Ch2b 7
ordered trees, see planar trees
operations of combinatorial objects Ch1a 47, 55
operations on species, Ch3a 22
operations on L-species, Ch3b 55
operations on weighted species, Ch3b 9
operators U and D (combinatorial representation), Ch4d 45
oscillating tableaux, Ch4d 51
2-colored — Ch4d 56
orthogonal polynomials (formal), Ch3b-complements 40
orthogonal Sheffer polynomials, Ch3b-complements 44
outstanding elements (permutations), Ch4a 15
partitions (of integers) Ch1a 64
partitions (species), Ch3a 13, 36
PASEP, Ch4d-complements 2
Pascal triangle, Ch1b 60
Path, Ch1b 81
generating function N/D, Ch1b 86
bijective proof for N/D, Ch1c 9
in a quadrant, Ch1d 83
path length (of a binary tree), Ch1d 86
pattern (31-2) in a permutation, Ch4b 40
peak (of a permutation), Ch4a 79
peak (of a Dyck path),
pebbles problem on a binary tree, Ch2b-complements-Strahler, 7-23
perfect matching, Ch1c 58
and tilings, Ch5b 79
permutahedron, Ch4d-complements 53-54
permutations, Ch1b 85, Ch4a 3
(graphical representation), Ch4a 5
permutations sortable by one stack, see Catalan permutations
permutations tableaux, Ch4d-complements 11
permutations, (312)-avoiding — , Ch2b 55
Pfaffian (definition), Ch5b 146
Pfaffians methodology, Ch5b 148
Pingala, Ch1b 62, Ch1c 41
plactic monoid, Ch4c-complement 60
planar maps, Ch1d 26, Ch2d 10
planar trees, Ch2a 32
plane partitions, Ch5a 92
pointed combinatorial object, Ch1b 17
pointed species, Ch3a 43
pointed weighted species, Ch3b 12
Polya q-analogue, Ch1d 63
Polya urn model, Ch3b-complements 37
polyomino, Ch1d 55
convex Ch1d 61—64
random convex Ch1d 66—68
poset (species), Ch3a 14, Ch4d 12
postorder (in a binary tree), Ch2a 23
P-recursive power series, Ch1b 77
preorder (in a binary tree), Ch2a 17
preorder (in a planar tree), Ch2a 35
primitive word, Ch2c 4
principal branch, left-, right- (of a binary tree), Ch2a 16
product (of combinatorial objects) Ch1a 60
product (of species), Ch3a 24
product (of weighted species), Ch3b 10
pyramids (of dimers) Ch1b 26
Pythagoras theorem (visual proof) Ch1a 65
q-analogues (introduction), Ch2d 54-56, Ch4a 25
q-analogues of Catalan numbers, Ch2d 57-63
(q,t)-Catalan, Ch2d 65-74
quantum gravity, Ch1d 40
quartic planar maps, Ch2d 18
Ramanujan Ch1a 77
ramification matrix (of a binary tree), Ch2b-complements-Strahler, 26
random directed animal, Ch1d 47-48
random binary tree, Ch2b-complements-Strahler, 42, 44
random binary search tree, Ch2b-complements-Strahler, 40, 44
random convex polyominoes, Ch1d 66—68
rational language, Ch1d 77
rational power series, Ch1b 77, 80, Ch1d 17
reflection principle (the), Ch2c 41-47, 49-53
registers (minimum number for computing an arithmetical expression),
Ch2b-complements-Strahler, 4-6
representation theory of groups, Ch4c 82
rise (of a permutation), Ch4a 16
Rogers-Ramanujan identities Ch1a 79
rook placements, Ch4d 53, 56, 59
Rothe diagram, Ch4a 28
RSK, (Robinson-Schensted-Knuth) introduction Ch4c 17, Ch4d 63
with Schensted insertion, Ch4c 23
geometric version with light and shadow, Ch4c 52
Schaeffer bijection (for planar maps), Ch1d 34, Ch2d 25-44
Schensted (bumping process), Ch4c 23
Schröder numbers, Ch5b 114
Schur functions, Ch4c-complement 68, Ch5b 16
skew —, Ch5b 23
Schützenberger, Marcel-Paul, Ch3b 78, Ch4a 17, 102, Ch4c-complement 2, 9, 60
Schützenberger methodology, Ch1d 31, 70
secant numbers, Ch3b 56, 71, Ch4a 22, 97
self-avoiding path, Ch1b 83
separation of variables (differential equation), Ch3b-complements 24-28
sequence (of combinatorial objects) Ch1a 63
semi-pyramids of dimers, Ch1b 38, Ch2c 66-69
Sheffer polynomials, Ch3b 36
shuffle product, Ch3b-complements 7
simple vertex, right, left (of a binary tree), Ch2a 14
singleton (species), Ch3a 18
species, Ch3a 4
skeleton (of a permutation), Ch4c 65, 77
skew Schur functions, Ch5b 23
stack polyomino, Ch1c 43
staircase polygon, Ch2a 104
stair decomposition if a heap of dimers, Ch2b-complements-TL_n, 15
stationnary probabilities, Ch1d 93
for the TASEP, Ch2d 96, 99
for the PASEP, Ch4d-complements 10
Stirling numbers 1st kind, Ch3b 38, Ch4a 11
Stirling numbers 2nd kind, Ch3b 39
Strahler number (of a binary tree), Ch1b 47, Ch1c 64, Ch2b 106-118
Ch2b-complements-Strahler, 2-50
sub-excedante function, Ch4a 24
substitution (in formal power series) Ch1a 40
substitution (for combinatorial objects), Ch1b 45
substitution (of species), Ch1d 28
substitution (of weighted species), Ch3b 11
subtree, left, right (of a binary tree), Ch2a 13
subword Ch1a 45
sum (of combinatorial objects) Ch1a 59
sum (of species), Ch1d 23
sum (of weigthed species), Ch3b 9
summable family of formal power series Ch1a 35
symmetric functions, Ch5b 13
elementary —, Ch5b 15
homogeneous (complete) — Ch5b 14
symmetric group, Ch4a 6
symmetric order (in a binary tree), see inorder
synthetic images of trees and landscapes, Ch2b-complements-Strahler, 33-50
Tamari lattice, Ch4d-complements 26
tangent numbers, Ch3b 65, 71, Ch4a 22, 97, Ch5a 90
TASEP, Ch2d 90-103, Ch5b 42
Tchebychef polynomials 2nd kind, Ch1c 44
Tchebychef polynomials 1st kind, Ch1c 51
Temperley-Lieg algebra, Ch2b-complements-TL_n, 2-34
tilings, Ch5b 63
aztec, Ch5b 87
on a rectangle, Ch5b 65-68, 125-129
on a triangular lattice, Ch5b 69
Touchard identity, Ch2a 59, Ch2b 73
trace monoids Ch1b 36
transition matrix methodology, Ch1b 86
transport (of structures), Ch3a 6
triangulation of a convex polygon Ch1a 14, Ch2b 14
trough (of a permutation), see valley
Tutte, Ch1d 28
uniform species, Ch3a 17
up-down sequence (of a permutation), Ch4a 21, 92, Ch5a 89
valley (or a permutation), Ch4a 79
Vandermonde determinant, Ch5a 66-67
vertébré, Ch3a 46
vertically convex polyomino, Ch1d 59
viscous fingering, Ch2b-complements-Strahler, 29
Walks, see paths
weight (of a heap of dimers) Ch1b 24
weighted species, Ch3b 3
— L-species, Ch3b 69
well balanced blossoming trees, Ch2d 42
x-factorisation (of a permutation), Ch4a 77
x-decomposition (of a permutation), Ch4b 36
Young lattice, Ch4d 15
Young tableaux, Ch4c 3
semi-strandad —, Ch5a 68
zeros (of matching polynomial of graphs), Ch1c 60
(of Fibonacci polynomials) Ch1d 1
(of Lucas polynomials) Ch1d 20
last update: 6 April 2016
return to:
