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)

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, 2
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