Title: Theory / Unimportant / Math / Combinatorics / Aigner / 2 Generating functions+8=
Tags: fromAlgorithm hasNotNewEffectReturnsMeaning récupéré

Page: 93
Section: 1
Chapter: 3
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)

Definition: \(1\) if \(P\) is true, \(0\) if \(P\) is false
Page: 93
Chapter: 3
Section: 1
Variables: \(P\) a property
Notation: \([P]\)

Name: The reflected polynomial of \(c\)
Definition: \(\sum_{i=0}^dc_iz^{d-i}\)
Page: 94
Chapter: 3
Section: 1
Variables: \(c(z)=\sum_{i=0}^d c_iz^i\in\mathbb C[z]\)
Notation: \(c^R\)
Definition2: \(z^dc(\frac 1z)\)
Definition3: \(\prod_{\alpha:\text{ a root}}(1-\alpha z)\)

Definition: \(\frac{1-\sqrt 5}{2}\)
Page: 95
Chapter: 3
Section: 1
Context: Combinatorics
Notation: \(\hat\tau\)
Definition2: \(-\tau^{-1}\)
Definition3: \(1-\tau\)

Smaller0: the OGF of \((a_{n})_{n\in\mathbb N}\) is of the form \(\frac{p(z)}{c(z)}\) with \(p(z)\) of degree less than \(d\)
Greater0: the OGF of \((a_{n})_{n\in\mathbb N}\) is of the form \(\sum_{i=1}^k\frac{g_i(z)}{(1-\alpha_iz)^{d_i}}\) with \(g_i(z)\) of degree less than \(d_i\)
Page: 95
Chapter: 3
Section: 1
Variables: \(c_0=1,c_1,\dots,c_d\ne 0\in\mathbb Z\)
\(d\ge 1\)
\(c(z)=1+\sum_{i=1}^dc_iz^i=\prod_{j=1}^k(1-\alpha_jz)^{d_j}\) with \(\alpha_j\) the roots of \(c^R(z)\)
\(\mathbb F\) a field
\((a_{n})_{n\in\mathbb N}\in\mathbb F\) a sequence
Kind: Theo
Smaller to greater: iff
Assuming: \(\mathbb F\)'s characteristic is 0
Construction: The set of sequences satisfying one of those condition has dimension \(d\). It then suffices to take sequence from one of those set and show it belongs to another one.
Smallest: \(\sum_{i=0}^dc_ia_{c+d-i}=0\)
Greatest: \(a_n=\sum_{i=1}^kp_i(n)\alpha_i^n\) for each \(n\in\mathbb N\), with \(p_i(n)\) a polynomial of degree less than \(d_i\)

Page: 95
Implementation: Find the roots \(\alpha_i\) of \(c^R(z)\), with multiplicity \(d_i\).
Write \(a_n=\sum_{i=1}^kp_i(n)\alpha_i^n\) for each \(n\in\mathbb N\), with \(p_i(n)\) a polynomial of degree less than \(d_i\)
Solve for \(0\le n\le d\)
Section: 1
Chapter: 3
Effect: Finding a closed form for the sequence \((a_n)_{n}\) such that \(\sum_{i=0}^d c_ia_{n-i}=0\) for all \(n>d\)
Variables: \(c_0=1,c_1,\dots,c_d\ne 0\in\mathbb Z\)
\(d\ge 1\)
Kind: Theo