Title: Theory / Unimportant / Math / Combinatorics / Analytic - Flajolet Sedgewick+14 / A Symbolic Methods
Tags: fromMath mathToDef hasSeenConjDef examplesSwitchExample1 récupéré duplicateToOtherBook partitionblock toBinaryRelation todo

Name: a partition of \(A\)
Definition: \(\bigcup A_i=\mathcal A\)
Page: 001
Chapter: 1
Variables: \(A\) a set.
Definition2: \(A_i\ne\emptyset\)
Conjdef: A set of subsets \(A_i\) of \(A\)
Definition3: \(A_i\cap A_j=\emptyset\) for every \(i\ne j\).
Extra: Analytic combinatoric I 4.2 P 62
Semigroup theory 1.4 p 20
Graph Reinhard Diestel. Ch 1. P 1
Aigner Combinatorics. 1.3. P 20

Name: The size of \(\alpha\).
Page: 16
Chapter: I
Section: 1
Variables: \(\mathcal A\) a class
\(\alpha\in\mathcal A\).
Notation: \(|\alpha|\)

Name: The set of elements of \(\mathcal A\) of size \(n\).
Page: 16
Chapter: I
Section: 1
Variables: \(\mathcal A\)
\(n\in\mathbb N\)
Notation: \(\mathcal A_n\)

Name: The cardinality of \(\mathcal A_n\).
Page: 16
Chapter: I
Section: 1
Variables: \(\mathcal A\)
\(n\in\mathbb N\)
Notation: \(A_n\)
Notation2: \(a_n\)

Name: The counting sequence of \(\mathcal A\)
Definition: The sequence \((A_i)_{i\in\mathbb N}\).
Page: 16
Chapter: I
Section: 1
Variables: \(\mathcal A\) and \(n\in\mathbb N\)
Index: 2
Kind: Def

Page: 17
Section: 1
Chapter: I
Nth element: \(\{1,\dots,n\}\) if \(i=n\), none otherwise
Notation: \(\mathcal I_i\)
Variables: \(i\in\mathbb N\)
Ogf: \(z^i\)
Nth value: \(1\) if \(n=i\), 0 otherwise
Index: 2
Kind: Ex
Asymptotically: 0

Page: 17
Section: 1
Chapter: I
Notation: \(\mathcal P\)
Name: The set of permutations
Ogf: \(\Pi_{m=1}^\infty Q[z^m]\)
Equation: \(\text{MSet}(\mathcal I)\)
Nth value: \(n!\)
Index: 2
Kind: Ex

Page: 018, 64
Section: 1, 4.3
Chapter: I
Nth element: A sequence of \(n\) beads, with two colours, where orientation matters, but not the permutation.
Name: Necklace
Ogf: \(\sum_{k\in\mathbb N}\frac{\phi_k}{k}\log\frac{1}{1-2z^k}\)
Nth value: \(\frac1n\sum_{k\mid n}\phi(k)2^{\frac nk}\), also \(D_n+1\) with \(\mathcal D\) the wheel class
Index: 1
Sequence name: circular words over a binary alphabet

Name: Unimodal permutations
Definition: A permutation with exactly one local maximum, that is \(\sigma_1\le\dots\le \sigma_{i-1}\ge\sigma_i\dots\ge\sigma_n\).
Page: 018
Chapter: I
Section: 1
Index: 2

Page: 018
Section: 1
Chapter: I
Notation: \(\mathcal B\cup \mathcal C\)
Name: Their union
Variables: \(\mathcal B,\mathcal C\) two combinatorial classes
Ogf: \(B(z)+C(z)\)
Index: (3)
Assuming: \((\mathcal B,\mathcal C)\) disjoint

Page: 18, 28
Section: 1
Chapter: I
Notation: \(\mathcal B\times \mathcal C\)
Name: Their cartesian product
Variables: \(\mathcal B,\mathcal C\) two disjoint combinatorial classes with OGF \(B(z)\) and \(C(z)\)
Ogf: \(B(z)C(z)\)
Index: (3)

Page: 19, 28
Definition: The existence of a bijection between two categories, which preservess size.
Chapter: I
Section: 1
Variables: \(\mathcal B,\mathcal C\) two disjoint combinatorial classes with OGF \(B(Z)\) and \(C(z)\)
Notation: \(\mathcal B\cong \mathcal C\)
Name: (Combinatorially) isomorphic combinatorial classes
Kind: Def
Index: 3
Definition2: Two combinatorial classes whose counting sequences are identical

Name: Ordinary generating function of \(A\)
Definition: \(\sum_{n=0}^\infty A_nz^n\),
Page: 019
Chapter: I
Section: 1
Variables: \(\mathcal A\) a combinatorial classes
Notation: \(A(z)\)
Index: 4
Kind: Def
Definition2: \(\sum_{\alpha\in A}z^{|\alpha|}\)
Abbreviation: OGF

Name: The \(n\)-th coefficient
Definition: \(f_n\).
Page: 019
Chapter: I
Section: 1
Variables: \(f(z)=\sum_{n\ge 0}f_nz^n\),
\(n\in\mathbb N\)
Notation: \([z^n]f(z)\)

Name: An admissible \(m\)-ary construction
Definition: A counting sequences which only depends on the counting sequnces \((B^{(i)}_n)\).
Page: 019
Chapter: I
Section: 1
Variables: \(\Phi\) an \(m\)-ary construction that associates collection of classes \(\mathcal B^{(1)},\dots,\mathcal B^{(m)}\) a new class \(\mathcal A=\Phi(\mathcal B^{(1)},\dots,\mathcal B^{(m)})\)
Index: 5
Kind: Def

Name: An \(m\)-ary construction which satisfies the Hölder condition
Definition: An \(m\)-ary construction, \(\Phi(\mathcal B^{(1)},\dots,\mathcal B^{(m)})\), whose \(n\)-th classes depends of the \((B^{(i)}_k)\) with \(\theta(n)\le Kn+L\).
Page: 019
Chapter: I
Section: 1
Index: 3
Example: \(f(z)\mapsto{}f(z^2)\)

Name: An \(m\)-ary construction which satisfies the Lipschitz condition
Definition: An \(m\)-ary construction, \(\Phi(\mathcal B^{(1)},\dots,\mathcal B^{(m)})\), whose \(n\)-th classes depends of the \((B^{(i)}_k)\) with \(\theta(n)\le n+L\).
Page: 019
Chapter: I
Section: 1
Variables: \(\Phi\) an \(m\)-ary construction that associates collection of classes \(\mathcal B^{(1)},\dots,\mathcal B^{(m)}\) a new class \(\mathcal A=\Phi(\mathcal B^{(1)},\dots,\mathcal B^{(m)})\)
Index: 3
Example: \(f(z)\mapsto{}f(z^2)\)

Page: 24
Section: 2.1
Chapter: I
Nth element: \(\epsilon\) or \(1\) for the object of size 0.
Notation: \(\mathcal E\)
Name: The neutral class
Ogf: \(1\)
Nth value: 1 if \(n=0\), \(0\) othewise
Context: Combinatoric

Page: 24
Section: 2.1
Chapter: I
Notation: \(\mathcal Z\)
Name: The atomic class
Ogf: \(z\)
Nth value: 1 if \(n=1\), 0 otherwise

Page: 25, 27
Section: 2.1
Chapter: I
Notation: \(\text{Seq}(\mathcal B)\)
Name: Sequence construction
Variables: \(\mathcal B\) a combinatorial class.
Ogf: \(Q[B(z)]\)
Equation: \(\epsilon+\mathcal B+(\mathcal B\times \mathcal B)+\dots\)

Page: 25, 27, 34
Section: 2.1, 2.3
Chapter: I
Notation: \(\texttt{Cyc}(\mathcal B)\)
Name: Cycle construction
Variables: \(\mathcal B\) a combinatorial class.
Ogf: \(Log[B]\)
Equation: \((\texttt{Seq}(\mathcal B)\setminus\{\epsilon\})/\mathbf{S}\) with \(\mathbf S\) the equivalence relation defined by \((\beta_1,\dots,\beta_r)\mathbf{S}(\beta_{1+k},\dots,\beta_{r+k})\) for \(k\in\mathbb N\).

Page: 26, 29
Section: 2.1
Chapter: I
Nth element: A multisubset of \(\mathcal B\) whose elements's cardinal sum to \(n\)
Notation: \(\texttt{MSet}(\mathcal B)\)
Name: Multiset construction
Variables: \(\mathcal B\) a combinatorial class.
Ogf: \(\text{Exp}[B]\)
Equation: \(\Pi_{\beta\in\mathcal B}\text{Seq}(\{\beta\})\)
\((\texttt{Seq}(\mathcal B)\setminus\{\epsilon\})/\mathbf{R}\) with \(\mathbf R\) an arbitrary permutation

Page: 26, 28
Section: 2.1
Chapter: I
Nth element: The finite subsets of elements of \(B\) such that the sum of the size of those elements are \(n\)
Notation: \(\texttt{PSet}(\mathcal B)\)
Name: Powerset construction
Variables: \(\mathcal B\) a combinatorial class.
Ogf: -\(\Pi_{n\ge 1}\left(1+z^n\right)^{B_n}\),
-\(\Pi_{\beta\in\mathcal B}\left(1+z^{|\beta|}\right)\),
-\(\text{exp}\left(\sum_{k=1}^\infty\frac{(-1)^{k-1}B(z^k)}{k}\right)\)
Equation: \(\Pi_{\beta\in\mathcal B}\left(\{\epsilon\}+\{\beta\}\right)\)

Question: \(+, \times\) over combinatorial classes are
Answer: associative and distributive
Page: 26
Chapter: I
Section: 2.1

Page: 27
Section: 2.1
Chapter: I
Nth element: \(n\)
Notation: \(\mathcal I\)
Name: Natural numbers
Ogf: \(\frac{1}{1-z}\)
Equation: \(\text{Seq}(\mathcal Z)\setminus \{\epsilon\}\)
Nth value: \(1\)

Page: 42
Section: 3.1
Chapter: I
Nth element: Covering of \([1,n]\) by sequences of length between \(1\) and \(r\)
Notation: \(\mathcal C^{[1,r]}\)
Name: Interval covering by elements of size between 1 and \(r\)
Variables: \(r\in\mathbb N\)
Ogf: \(Q[I^{\{1,\dots,r\}}(z)]\) equals \(\frac{1}{1-\sum_{i=1}^r z^i}\) equals \(\frac{1-z}{1-2z+z^{r+1} }\)
Equation: \(\text{Seq}\left(\sum_{i=1}^r\mathcal Z^i\right)\)
Nth value: \(\sum_{j,k}(-1)^k{j\choose k}{n-rk-1\choose j-1}\)
Asymptotically: \(c_r\rho_r^{-n}\), with \(c_r\) and \(\rho_r\) some constant
Sequence name: Generalized Fibonacci numbers
Equation2: \(C(z)=1+(\sum_{i=1}^rz^i)C(z)\) The sum of the \(r\) preceding values (or 1, for the first \(r\) entries)

Page: 27, 42
Section: 2.1, 3.1
Chapter: I
Nth element: Covering of \([1,n]\) by sequences of length 1 or 2.
Notation: \(\mathcal C\), \(\mathcal C^{1,2}\)
Name: Interval covering
Ogf: \(Q[I^{1,2}(z)]=\frac1{1-z-z^2}\)
Equation: \(\text{Seq}\left(\mathcal Z+(\mathcal Z\times \mathcal Z)\right)\)
Nth value: \(\frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n\right]\)
Index: 5, 9
Kind: def
Asymptotically: \(\frac{1}{\sqrt5}\left(\frac{1+\sqrt5}2\right)^n\)
Sequence name: Fibonacci numbers
Equation2: \(C(z)=1+zC(z)+z^2C(z)\) The sum of the two preceding values (or 1, for the two first entries)

Name: Vallée's identity
Definition: \(M(z)=P(z)M(z^2)\)
Page: 30
Chapter: I
Section: 2.2
Variables: \(\mathcal C\) a combinatorial class
\(\mathcal M=\text{MSet}(\mathcal C)\),
\(\mathcal P=\text{PSet}(\mathcal C)\)

Page: 30
Section: 2.2
Chapter: I
Notation: \(\mathcal K_\Omega(\mathcal A)\)
Name: The restriction of \(\mathcal K\) where the number of elements satisfies \(\Omega\)
Variables: \(\mathcal A\) a combinatorial class,
\(\mathcal K\) representing Seq, Cyc, MSet, Pset and
\(\Omega\) a predicate over the integers.

Page: 30
Section: 2.2
Chapter: I
Nth element: The sequences of \(k\) elements of \(B\) whose size's sum is \(n\)
Notation: \(\text{Seq}_k(\mathcal B)\)
Variables: \(\mathcal B\) a combinatorial class
\(k\in\mathbb N\)
Ogf: \(\mathcal B^k\)

Page: 30
Section: 2.2
Chapter: I
Nth element: The sequences of at least \(k\) elements of \(B\) whose size's sum is \(n\)
Notation: \(\text{Seq}_{\ge k}(\mathcal B)\)
Variables: \(\mathcal B\) a combinatorial class,
\(k\in\mathbb N\)
Equation: \(\mathcal B^k\times \text{Seq}(\mathcal B)\)

Page: 30
Section: 2.2
Chapter: I
Nth element: The multisets of \(k\) elements of \(B\) whose size's sum is \(n\)
Notation: \(\text{MSet}_{k}(\mathcal B)\)
Variables: \(\mathcal B\) a combinatorial class,
\(k\in\mathbb N\)
Equation: \(\text{Seq}(\mathcal B)/\mathbf{R}\) with \(\mathbf R\) the equivalence relation under reordering

Name: Tree
Definition: Acyclic connected undirected graph
Page: 31
Chapter: I
Section: 2.3

Name: Rooted Tree
Definition: A tree and one of its vertex
Page: 31
Chapter: I
Section: 2.3

Name: A specification for \(\overrightarrow{\mathcal A}=(\mathcal A^{(1)},\dots,\mathcal A^{(r)})\)
Definition: A collection of \(r\) equations \(\mathcal A^{(i)}=\Phi_i(\mathcal A^{(1)},\dots,\mathcal A^{(r)})\), where each \(\Phi_i\) denotes a term built from the \(\mathcal A\) using disjoint union, produict, sequence, powerset, multiset, cycle, and neutral and atomic classes.
Page: 33
Chapter: I
Section: 2.3
Variables: \(r\in\mathbb N\)
\(\mathcal A^{(1)},\dots,\mathcal A^{(r)}\) \(r\) classes
Index: 7
Kind: Def

Name: Iterative specification
Definition: A specification such that \(\Phi_i\) only uses the constructors \(\mathcal A^{(1)},\dots, \mathcal A^{(i-1)}\).
Page: 33
Chapter: I
Section: 2.3
Variables: \(r\in\mathbb N\) and \(\mathcal A^{(1)},\dots,\mathcal A^{(r)}\) \(r\) classes with a specification \((\Phi_i)\).
Index: 7
Kind: Def
Name2: Non-recursive specification

Definition: \((\emptyset,\dots,\emptyset)\) if \(i=0\) and \(\Phi(\overrightarrow{\mathcal A}^{[i-1]})\) otherwise.
Page: 33
Chapter: I
Section: 2.3
Variables: \(r\in\mathbb N\) and \(\mathcal A^{(1)},\dots,\mathcal A^{(r)}\) be \(r\) classes with a specification \((\Phi_i)\). Let \(i\in \mathbb N\)
Notation: \(\overrightarrow{\mathcal A}^{[i]}\)
Index: 7
Kind: Def

Definition: The limit of the \(\overrightarrow{\mathcal A}^{[i]}\).
Page: 33
Chapter: I
Section: 2.3
Variables: \(r\in\mathbb N\)
\(\mathcal A^{(1)},\dots,\mathcal A^{(r)}\) be \(r\) classes with a specification \((\Phi_i)\)
\(i\in \mathbb N\)
Notation: \(\overrightarrow{\mathcal A}\)
Index: 7
Kind: Def

Name: A constructible combinatorial structures
Definition: A combinatorial structure which admits a (possibly recursive) specification in terms of sum, product, sequence, set, multiset and cycle construction.
Page: 33
Chapter: I
Section: 2.3
Variables: \(r\in\mathbb N\)
\(\mathcal A^{(1)},\dots,\mathcal A^{(r)}\) a class of combinatorial structures
Index: 8
Kind: Def
Definition2: \(\mathcal A\) is a component of a system of functional equations whose terms are built from \(1,z,+,\times,Q,Exp,\overline{Exp},Log\)
Name2: A specifiable combinatorial structures

Name: The quasi inverse of \(f\)
Definition: \(\frac{1}{1-f}\).
Page: 34
Chapter: I
Section: 2.3
Variables: \(f:\mathbb N\to\mathbb N\)
Notation: \(Q[f]\)
Definition2: \(\sum_{i\in\mathbb N}f^i\)

Name: Polya exponential of \(f\)
Definition: \(\exp\left(\sum_{k=1}^\infty\frac{f(z^k)}{k}\right)\).
Page: 34
Chapter: I
Section: 2.3
Variables: \(f:\mathbb N\to\mathbb N\)
Notation: \(Exp[f]\)
Definition2: \(\Pi_{n\ge 1}\left(1-z^n\right)^{-[z^n]f}=\Pi_{n\ge 1}Q[z^n]^{[z^n]f}\)

Name: The modified Polya exponential of \(f\)
Definition: \(\exp\left(\sum_{k=1}^\infty(-1)^{k-1}\frac{f(z^k)}{k}\right)\).
Page: 34
Chapter: I
Section: 2.3
Variables: \(f:\mathbb N\to\mathbb N\)
Notation: \(\overline{Exp}[f]\)
Extra: Correct: No factorial in the denominator

Name: The Polya logarithm of \(f\)
Definition: \(\sum_{k=1}^\infty\frac{\phi(k)}{k}\log Q[f(z^k)]\).
Page: 34
Chapter: I
Section: 2.3
Variables: \(f:\mathbb N\to\mathbb N\)
Notation: \(Log[f]\)

Smaller0: \(n!\)
Greater0: \(\left(\frac{n}{e}\right)^n\sqrt{2\pi n}\left(1+O\left(\frac 1n\right)\right)\)
Page: 37
Chapter: I
Section: 2.3
Smaller to greater: \(\sim\)
Hide middle: yes
Name: Stirling formula

Name: A partition of \(n\)
Definition: A sequence \((x_1,\dots,x_k)\) with \(n=\sum_{i=1}^k x_i\) and \(1\le x_k\le\dots\le x_1\).
Page: 39
Chapter: I
Section: 3.1
Variables: \(n\in\mathbb N\)
Index: 9
Kind: Def

Page: 31
Section: 2.3
Chapter: 1
Notation: \(\mathcal G\)
Name: The class of planar tree

Name: The permutation sending \(i\) to \(\sigma_i\)
Page: 17
Chapter: I
Section: 1
Variables: \(n\in\mathbb N\), \(\{\sigma_1,\dots,\sigma_n\}=\{1,\dots,n\}\)
Notation: \((\sigma_1,\dots,\sigma_n)\)
Index: 2
Kind: Ex

Page: 44
Section: 3
Chapter: I
Nth element: Interval covering of \(n\) by elements of size belonging to \(T\)
Notation: \(\mathcal C^{\mathcal T}\)
Variables: \(\mathcal T\subseteq \mathcal I\)
Ogf: \(\mathcal Q[T(z)]\)
Equation: \(SEQ(SEQ_{\mathcal T}(\mathcal Z))\)

Page: 42
Section: 3
Chapter: I
Nth element: A non-decreasing sequence of positive natural whose sum is \(n\)
Notation: \(\mathcal P\)
Name: Partitions
Ogf: \(\Pi_{n\in\mathbb N}Q[z^n]\)
Equation: \(MSET(\mathcal I)\)
Asymptotically: \(\frac{\exp\left(\pi\sqrt{\frac{2n}{3}}\right)}{4n\sqrt{3}}\)

Page: 42
Section: 3
Chapter: I
Notation: \(\mathcal P^{\mathcal T}\)
Name: Partitions whose summands are restricted to \(\mathcal T\)
Variables: \(\mathcal T\subseteq \mathcal I\)
Ogf: \(\Pi_{n\in\mathcal T}Q[z^n]\)
Equation: \(MSET(SEQ_{\mathcal T}(\mathcal Z))\)

Definition: \(\left\lfloor r+\frac 12\right\rfloor\)
Page: 43
Chapter: I
Section: 3
Variables: \(r\in\mathbb R\)
Notation: \(\left\lceil r\right\rfloor\)

Name: The Durfee square of \(P\)
Definition: The greatest \(h\) such that \(h\) elements of \(P\) are at least \(h\).
Page: 45
Chapter: I
Section: 3
Variables: \(P\) a partition
Index: 6
Kind: Ex
Extra: h index ?
Intuition: Greatest square as in

Name: A stack polyomino
Definition: The diagram of a composition such that, for some \(j,l\), one has \(1\le x_1\le \dots\le x_j\ge x_{j+1}\dots\ge x_l\ge 1\).
Page: 45
Chapter: I
Section: 3
Index: 6
Kind: Ex

Page: 47
Section: 3
Chapter: I
Nth element: A class of equivalence of composition of \(n\) up to circular shift. I.e. for \(n=32\)
Notation: \(\mathcal D\)
Name: The class of wheel
Ogf: \(\sum_{k=1}^\infty\frac{\phi(k)}{k}\log\left(1-\frac{z^k}{1-z^k}\right)^{-1}\)
Equation: \(Cyc(\mathcal I)\)
Nth value: \(-1+\frac{1}n\sum_{k\mid n}\phi(k)2^{\frac nk}\)
Index: , (47)
Asymptotically: \(\frac {2^n} n\)

Name: An alphabet
Typ: A finite set
Page: 49
Section: 4
Chapter: I

Name: A letter
Definition: An element of an alphabet.
Page: 49
Chapter: I
Section: 4

Name: A word
Definition: A finite sequence of letters.
Page: 49
Chapter: I
Section: 4

Name: A language
Definition: A set of words.
Page: 49
Chapter: I
Section: 4

Page: 16, 31, 58, 50
Section: , 1, 2.3, 4.2, 4
Chapter: I
Nth element: A sequence of \(n\) letters of \(A\)
Notation: \(\mathcal W\)
Variables: \(m\in\mathbb N\)
\(A\) an alphabet with \(m\) letters
Ogf: \(Q[mz]\)
Equation: \(\text{Seq}(m\mathcal Z)\)
Nth value: \(m^n\)
Index: 1, 4
Kind: Ex, Prop

Name: A regular specification
Definition: An iterative specification that only involves atoms, sums, cartesian products and sequences constructions.
Page: 51
Chapter: I
Section: 4.1
Variables: \(A\) an alphabet

Name: A specification-regular language
Definition: there exists a class \(M\) described by a regular specification such that \(\mathcal {L}\cong\mathcal M\).
Page: 51
Chapter: I
Section: 4.1
Variables: \(A\) an alphabet
Context: Combinatorics
Definition2: it can be described unambiguously by a regular expression
Conjdef: A language \(\mathcal L\) such that, equivalently
Definition3: whose OGF is a rational function
Abbreviation: A S-regular language

Name: A finite automaton
Definition: Set of states \(Q\)
Page: 56
Chapter: I
Section: 4.1
Variables: \(A\) an alphabet
Definition2: Initial state \(q_0\)
Conjdef: A directed multigraph with
Definition3: Set of final states \(\overline Q\)
Definition4: Edges are labelled by letters of the alphabet A.

Name: A deterministic finite automaton
Definition: A finite automaton such that, for each state \(q\) and letter \(a\) there is at most one edge strarting from \(q\) labelled by \(a\)
Page: 56
Chapter: I
Section: 4.1
Variables: \(A\) an alphabet
Extra: No initial state is assumed

Name: A transition
Definition: An edge of the automaton
Page: 56
Chapter: I
Section: 4.1
Variables: \(A\) an alphabet
\(F\) a finite automaton

Name: An automaton-regular language
Definition: A set of words accepted by a determenistic finite automaton
Page: 57
Chapter: I
Section: 4.1
Variables: \(A\) an alphabet
Index: 12
Kind: Def
Abbreviation: An A-regular language

Name: An \(A\)-regular combinatorics class
Definition: A class \(\mathcal M\) of words such that \(\mathcal M\cong \mathcal L\) for \(\mathcal L\) some \(A\)-regular language
Page: 57
Chapter: I
Section: 4.1
Index: 12
Kind: Def

Name: Iverson's bracket notation
Definition: 1 if \(P\) holds, 0 otherwise
Page: 58
Chapter: I
Section: 4.1
Variables: \(P\) a predicate
Notation: [$]\llbracket{}P
\rrbracket[/$]
Index: 11
Kind: Footnote

Question: The generating function of \(L\) is (using matrix notation):
Answer: [$](1,\dots,0)\left(\text{card}\{\alpha\in\mathcal A\mid \text{$(q_i,q_j)$ is labelled by $\alpha$} \}\right)_{i,j\in Q}(\llbracket{}q_0\in\overline Q \rrbracket, \dots,\llbracket{}q_s\in\overline Q \rrbracket)^t[/$]
Page: 57
Chapter: I
Section: 4.1
Variables: \(G\) a deterministic automaton,
\(\mathcal A\) an alphabet with \(s\) states
\(\mathcal L\) the language accepted by \(G\)
Index: 3
Kind: Prop

Name: The equation associated to \(G\)
Definition: For \(0\le i<s\), [$]\mathcal L_i=\sum_{(q_i,\alpha,q_j)\in G}\alpha \mathcal L_j+\llbracket{}q_i\in \overline Q
\rrbracket\epsilon[/$].
Page: 58
Chapter: I
Section: 4.1
Variables: \(G\) a deterministic automaton with \(s\) states,
\(\mathcal A\) an alphabet
Index: 3
Kind: Prop

Name: The autocorrelation of \(\mathfrak p\)
Definition: The \(k\)-tuple whose \(i\)-th element is [$]\llbracket{}p_{i+1}p_{i+2}\dots p_k=p_1\dots p_{k-i}\rrbracket[/$].
Page: 58
Chapter: I
Section: 4.2
Variables: \(\mathcal A\) an alphabet,
\(\mathfrak p\) a word of length \(k\)
Index: 3
Kind: Prop

Name: The autocorrelation polynomial of \(\mathfrak p\)
Definition: [$]\sum_{j=0}^{k-1}\llbracket{}p_{i+1}p_{i+2}\dots p_k=p_1\dots p_{k-i}
\rrbracket z^i[/$].
Page: 58
Chapter: I
Section: 4.2
Variables: \(\mathcal A\) an alphabet,
\(\mathfrak p\) a word of length \(k\)
Notation: \(c(z)\)
Index: 3
Kind: Prop

Page: 61
Section: 4.2
Chapter: I
Name: Words not containing the pattern \(\mathfrak p\) as a factor
Variables: \(\mathcal A\) an alphabet of cardinality \(m\),
Let \(\mathfrak p\) a word of length \(k\)
Ogf: \(\frac{c(z)}{z^k+(1-mz)c(z)}\)
Index: 4
Kind: Prop
Extra: j'ai perdu un truc
\(c(z)\) the autocorrelation polynomial of \(\mathfrak p\)

Page: 61
Section: 4.2
Chapter: I
Nth element: A word of length \(n\)-the having no prefix in \(\mathcal L\)
Name: The prefix language of \(\mathcal L\)
Variables: \(\mathcal A\) an alphabet of cardinality \(m\),
Let \(\mathcal L\) a language
Equation: \(\widehat L(z)\)
Index: 33

Name: The prefix language of \(\mathcal L\)
Definition: The language of words which have no strict prefix belonging to \(\mathcal L\).
Page: 61
Chapter: I
Section: 4.2
Variables: \(\mathcal A\) an alphabet of cardinality \(m\),
\(\mathcal L\) a language
Index: 33

Smaller0: the first time a word of \(L\) is encountered in an infinite word
Greater0: \(\frac12\widehat L'(\frac 12)\)
Page: 61
Chapter: I
Section: 4.2
Variables: \(\mathcal A\) a binary alphabet,
\(\mathcal L\) a language
Index: 33
Smaller to greater: equals
Hide middle: yes

Name: Borges's Theorem
Definition: Any finite set of pattern occurs in a random text of length \(n\) with probability tending to 1 exponentially fast as \(n\to\infty\)
Page: 61
https://en.wikipedia.org/wiki/Infinite_monkey_theorem
Chapter: I
Section: 4.2
Variables: \(\mathcal A\) a binary alphabet of cardinality \(m\),
\(\mathcal L\) a language
Index: 35
Name2: Infinite monkey theorem

Name: A code
Definition: any word of \(\mathcal W\) decomposes in at most one manner into factors that belongs to \(\mathcal F\)
Page: 62
Chapter: I
Section: 4.2
Variables: \(\mathcal A\) a alphabet,
Index: 36
Definition2: \(S_{\mathcal F}(z)=Q[F(z)]\)
Example: \(\{a,ab,bb\}\)
Conjdef: A finite set \(\mathcal F\subseteq SEQ(\mathcal A)\) such that, equivalently

Name: Not a code
Page: 62
Chapter: I
Section: 4.2
Variables: \(\mathcal A\) a alphabet,
Index: 35
Example: \(\{a,aa,b\}\)

Definition: The set of words admitting a decomposition into elements of \(\mathcal F\).
Page: 62
Chapter: I
Section: 4.2
Variables: \(\mathcal A\) a alphabet,
\(\mathcal F\subseteq SEQ(\mathcal A)\)
Notation: \(\mathcal{S_F}\)
Index: 35

Question: Difference between Polya operator and modified Polya exponential ?
Answer: The modified Polya exponential contains a \((-1)^{k-1}\)
Page: 34
Chapter: I
Section: 2.3
Answer2: its symbol is overlined.

Name: A (combinatorial) class
Definition: A finite or denumerable set on which a size function is defined, such that:
-the size of an element is a non-negative integer,
-the number of elements of any size is finite.
Page: 16
Chapter: I
Section: 1

Page: 17, 32, 38, 35,
Section: 1, 2.3
Chapter: I
Nth element: A decomposition of an \(n\)-gone in triangle
Name: Triangulations
Ogf: \(\frac{1-\sqrt{1-4z} }{2z}\)
Nth value: \(\frac{(2n)!}{(n+1)!n!} =\frac{1}{n+1}{2n\choose n}\)
Kind: Ex
Asymptotically: \(\frac{4^n}{\sqrt{\pi n^3} }\)
Sequence name: The Catalan sequence
Equation2: \(\mathcal G=\text{Seq}(\mathcal G)\)
Nth element2: A rooted plane tree with \(n\) elements: a root with a finite sequence of descendant, being also rooted plane tree.
Notation2: \(\mathcal G\)
Name2: Rooted plane tree

Page: 39, 40
Section: 3.1
Chapter: 1
Nth element: A sequence \((x_1,\dots,x_k)\) with \(n=\sum_{i=1}^k x_i\) and \(1\le x_k,\dots, x_1\).
Notation: \(\mathcal C\)
Name: Compositions (combinatorics)
Equation: \(C(z)=Q[I(z)]\)
Nth value: \(2^{n-1}\)
Index: 9, (36)
Kind: Def,

Page: 44
Section: 3
Chapter: 1
Nth element: A sequence \((x_1,\dots,x_k)\) with \(n=\sum_{i=1}^k x_i\) and \(1\le x_k,\dots, x_1\).
Notation: \(\mathcal C^{(k)}\)
Name: Compositions with \(k\)-parts
Variables: \(k\in\mathbb N\)
Equation: \(I(z)^k\)
Nth value: \({n-1\choose k-1}\)
Index: 6
Kind: Ex

Page: 48
Section: 3
Chapter: I
Nth element: A sequence \(0<x_1<\dots<x_k\) with \(\sum x_i=n\)
Notation: \(\mathcal Q\)
Name: Partitions into distinct summands
Ogf: \(\prod_{n\ge 1}(1+z^n)\)
Equation: \(PSET(\mathcal I)\)
Index: (49)
Asymptotically: \(\frac{3^{3/4}}{12n^{3/4}}\exp\left(\pi\sqrt{\frac n3}\right)\)

Question: The OGF of \(SEQ(\mathcal F)\) is
Answer: rational
Page: 59
Chapter: I
Section: 4.2
Variables: \(\mathcal A\) a alphabet,
\(\mathcal F\subseteq SEQ(\mathcal A)\)
Index: 2
Kind: Ex

Name: The golden ratio
Definition: \(\frac{1+\sqrt5}2\)
Page: 42
Chapter: I
Section: 3.1
Context: Analytic combinatorics, I 3.1. P 42
Combinatorics Aigner, generating function. Ch 3.1 p 95
Notation: \(\phi\)
Name2: The golden section
Notation2: \(\tau\)

Page: 62, 63
Section: 4.3
Chapter: I
Nth element: A set partition of \(\{1,\dots,n\}\) into \(r\) blocks
Notation: \(\mathcal S^{(r)}_n\)
Ogf: \(\frac{z^r}{\prod_{i=1}^r(1-iz)}\)
Sequence name: Stirling numbers of the second kind, or better, as the Stirling partition numbers
Equation2: \(\prod_{i=1}^r b_i\text{Seq}(\sum_{z=1}^i b_j)\)
Sequence notation: \(\genfrac\{\}{0pt}{}nr\)
Nth element2: a word of lenth \(n\) over \(\{b_1,\dots,b_r\}\), where the first occurrence of \(b_i\) exists and is before the first occurrence of \(b_{j}\) for \(j>i\)

Name: The block leader of \(B\)
Definition: The least element of \(B\)
Page: 62
Chapter: I
Section: 4.3
Variables: \(n\in\mathbb N\)
\(P\) a set partition of \(\{1,\dots,n\}\) (i.e. an element of \(\mathcal S_n\))
\(B\) a block of \(P\)
Context: Integral partition

Name: The index of \(B\)
Definition: The rank of the leader of \(B\) in the set of block leader.
Page: 62
Chapter: I
Section: 4.3
Variables: \(n\in\mathbb N\)
\(P\) a set partition of \(\{1,\dots,n\}\) (i.e. an element of \(\mathcal S_n\))
\(B\) a block of \(P\)
Context: Partition

Page: 64
Section: 4.3
Chapter: I
Nth element: A finite language whose sum of word's length is \(n\)
Name: Finite languages
Variables: \(B=\{b_1,\dots,b_n\}\) an alphabet

Page: 64
Section: 4.3
Chapter: I
Nth element: A finite binary language whose sum of word's length is \(n\)
Name: Finite binary languages
Ogf: \(\exp\left(\sum_{k\ge1}\frac{(-1)^{k-1}}k\frac{2z^k}{1-2z^k}\right)\)
Equation: [$]\textsc{PSet}(\textsc{Seq}_{\ge1}(\mathcal A))[/$]

Name: A block of the partition
Definition: Some \(A_i\)
Page: 20
Chapter: 1
Section: 3
Variables: \(N\) a set
\(\{A_i\}\) a partition of \(N\)
Context: Partition
Extra: Flajolet, symbolic method, ch 1.4.3. P62
Aigner Combinatoric intro, Ch 1.3 P 20