Title: Theory / Unimportant / Math / Combinatorics / Aigner / 1 Intro+9
Tags: fromImplication récupéré

Name: Enumerative combinatorics
Definition: The problem how to count the number of elements of a finite set given by some combinatorial conditions.
Page: 1
Chapter: Intro

Smaller0: \(|\bigcup_i S_i|\)
Greater0: \(\sum |S_i|\)
Page: 5
Chapter: 1
Variables: \(S_i\) sets
Smaller to greater: =
Name: Rule of sum

Definition: The set of sets containing \(k\) elements of \(X\)
Page: 5
Chapter: 1
Variables: \(X\) a set,
\(k\in\mathbb N\)
Notation: \(X\choose k\)

Definition: \(\frac{ n!}{k!(n-k)!}\) if \(k\le n\in\mathbb N\)
Page: 5, 12
Chapter: 1
Variables: \(k\in\mathbb Z\),
\(n\in\mathbb R\)
Notation: \(x\choose k\)
Definition2: \(\frac{x^{\underline k}}{k!}\) if \(k\ge 0\), \(0\) if \(k<0\)

Smaller0: \(\left|{X\choose n}\right|\)
Greater0: \({|X|}\choose n\)
Page: 5
Chapter: 1
Variables: \(X\) a set,
\(k\in\mathbb N\)
Smaller to greater: =

Smaller0: \(n\choose k\)
Greater0: \({n-1\choose k-1}+{n-1\choose k}\)
Page: 5
Chapter: 1
Variables: \(k\le n\in\mathbb N\)
Smaller to greater: =
Name: Pascal recurrence for binomial coefficients

Smaller0: \(|\Pi_i S_i|\)
Greater0: \(\Pi |S_i|\)
Page: 5
Chapter: 1
Variables: \(S_i\) sets
Smaller to greater: =
Name: Rule of product

Name: The coordinate sets
Definition: The \(S_i\)'s
Page: 5
Chapter: 1
Variables: \(S_i\) sets
Context: \(\Pi S_i\)

Definition: The set of tuples whose \(i\)-th element belong to \(S_i\)
Page: 5
Chapter: 1
Variables: \(S_i\) sets
Notation: \(\Pi S_i\)

Definition: A sequence of elements of \(A\)
Page: 6
Chapter: 1
Variables: \(A\) a set
Notation: A word over \(A\)

Question: The number of words of length \(r\)
Answer: is \(|A|^r\).
Page: 6
Chapter: 1
Variables: \(A\) a set,
\(r\in\mathbb N\)

Smaller0: there is a bijection between \(S\) and \(T\)
Greater0: \(|S|=|T|\)
Page: 6
Chapter: 1
Variables: \(S,T\) sets
Smaller to greater: iff
Name: Rule of bijection

Smaller0: \(f\) and \(g\) enumerates the same set
Greater0: \(f\) and \(g\) are equal
Page: 6
Chapter: 1
Variables: \(f(n),g(n)\) formulas

Name: An incidence system
Definition: A pair of set and a relation between them
Page: 6
Chapter: 1
Context: Combinatoric

Name: the \(a_i\) are incident
Page: 6
Chapter: 1
Variables: \(A_1,A_2\) sets \(I\subseteq A_1\times A_2\), an incidence system,
\(a_i\in A_i\)
Notation: \(a_1Ia_2\)

Definition: the numbers of elements incident to \(a_i\)
Page: 6
Chapter: 1
Variables: \(A_1,A_2\) sets \(I\subseteq A_1\times A_2\)
an incidence system
\(a_i\in A_i\)
Notation: \(d(a_i)\)
Assuming: if \(a_i\in \bigcap A_i\), it is clear by context which \(A_i\) is currently considered

Question: \(\sum_{a_1\in A_1}d(a_1)\)
Answer: =\(\sum_{a_2\in A_2}d(a_2)\)
Page: 6
Chapter: 1
Variables: \(A_1,A_2\) disjoint sets
\(I\subseteq A_1\times A_2\), an incidence system

Name: The incidence matrix of \(I\)
Definition: The \((0,1)\) matrix with \(m_{a_1a_2}\) being \(1\) if \(a_1Ia_2\), and 0 otherwise
Page: 6
Chapter: 1
Variables: \(A_1,A_2\) disjoint sets
\(I\subseteq A_1\times A_2\), an incidence system
Denoted by: \(M\)

Name: The \(n\) harmonic number
Definition: \(\sum_{i=1}^n\frac 1i\)
Page: 8
Chapter: 1
Variables: \(n\in\mathbb N\)
Notation: \(H_n\)

Page: 8
Section: 1
Nth element: The average numbers of dividors of numbers between 1 and \(n\)
Nth value: \(H_n\) or \(H_n-1\)
Asymptotically: \(\log n\)

Page: 10
Section: 2
Chapter: 1
Nth element: A permutation of \(k\) distinct elements of \(N\)
Variables: \(n\le k\in\mathbb N\)
Nth value: \(k^{\underline n}\)

Name: The failing factorial
Definition: \(\prod_{i=k-n+1}^ki\)
Page: 10
Chapter: 1
Section: 2
Variables: \(n\le k\in\mathbb N\)
Notation: \(k^{\underline n}\)
Definition2: \(n!{k\choose n}\)

Name: The rising factorial
Definition: \(\prod_{i=k}^{n+k-1}i\)
Page: 10
Chapter: 1
Section: 2
Variables: \(n\le k\in\mathbb N\)
Notation: \(k^{\overline n}\)

Smaller0: \(\frac{x^{\underline k}}{k!}\)
Greater0: \(\frac{(x-1)^{\underline k}}{(k-1)!}+\frac{(k-1)^{\underline k}}{k!}\)
Page: 11,12
Chapter: 1
Section: 2
Variables: \(x\in\mathbb R\)
\(k\in\mathbb Z\)
Index: 4
Smaller to greater: =
Hide middle: yes
Name: Pascal recurrence

Question: \({-1\choose n}\)
Answer: \(=(-1)^n\)
Page: 12
Chapter: 1
Section: 2
Variables: \(n\le k\in\mathbb N\)
Index: 4

Smaller0: \((-x^{\overline k})\)
Greater0: \({-1}^{k}(x^{\underline k})\)
Page: 12
Chapter: 1
Section: 2
Smaller to greater: =
Hide middle: i
Name: Reciprocity law

Question: \(\sum_{k=0} ^n{n\choose k}\)
Answer: equals \(2^n\)
Page: 13
Chapter: 1
Section: 2

Question: \(\sum_{i=0}^n{i\choose k}\)
Answer: equals \(n+1\choose k+1\)
Page: 13
Chapter: 1
Section: 2
Variables: \(k,n\in\mathbb N\)
Index: 8
Kind: eq

Question: \(\sum_{i=0}^n{m+i\choose i}\)
Answer: equals \(m+n+1\choose n\)
Page: 13
Chapter: 1
Section: 2
Variables: \(n,m\in\mathbb N\)

Smaller0: \((x+y)^n\)
Greater0: \(\sum_{k=0}^n{n\choose k}x^ky^{n-k}\)
Page: 14
Chapter: 1
Section: 2
Index: 12
Smaller to greater: =
Hide middle: yes

Smaller0: \((x+1)^n\)
Greater0: \(\sum_{k=0}^n{n\choose k}x^k\)
Page: 14
Chapter: 1
Section: 2
Smaller to greater: =
Hide middle: yes

Smaller0: \((x-1)^n\)
Greater0: \(\sum_{k=0}^n(-1)^k{n\choose k}x^k\)
Page: 14
Chapter: 1
Section: 2
Smaller to greater: =
Hide middle: yes

Name: Kronecker symbol
Definition: \(1\) if \(i=j\), 0 otherwise
Page: 14
Chapter: 1
Section: 2
Notation: \(\delta_{i,j}\)

Smaller0: \({x+y\choose n}\)
Greater0: \(\sum_{k=0}^n{x\choose k}{y\choose n-k}\)
Page: 14
Chapter: 1
Section: 2
Index: 15
Smaller to greater: =
Name: Vandermonde identity
Hide sides: yes

Smaller0: \((x+y)^{\overline n}\)
Greater0: \(\sum_{k=0}^n{n\choose k}x^{\overline k}y^{\overline{n-k}}\)
Page: 15
Chapter: 1
Section: 2
Index: 16
Smaller to greater: =
Hide middle: yes

Smaller0: \((x+y)^{\overline n}\)
Greater0: \(\sum_{k=0}^n{n\choose k}x^{\overline k}y^{\overline{n-k}}\)
Page: 15
Chapter: 1
Section: 2
Variables: \(n\in\mathbb N\),
\(x,y\in\mathbb R\)
Index: 16
Smaller to greater: =
Hide sides: yes

Smaller0: \((x+y)^{\underline n}\)
Greater0: \(\sum_{k=0}^n{n\choose k}x^{\underline k}y^{\underline{n-k}}\)
Page: 15
Chapter: 1
Section: 2
Variables: \(n\in\mathbb N\),
\(x,y\in\mathbb R\)
Index: 16
Smaller to greater: =
Hide sides: yes

Name: A multiset
Definition: A function from a set to natural numbers
Page: 15
Chapter: 1
Section: 2
Index: 16
Intuition: A set, with non-distinct element
French: multiensemble

Name: The size of \(M\)
Definition: The number of elements of \(M\), counting multiple times elements present multiple times
Page: 15
Chapter: 1
Section: 2
Variables: \(M\) a multiset
Index: 16

Name: The multiplicity of \(o\) in \(M\)
Definition: The number of times \(o\) belongs to \(M\)
Page: 15
Chapter: 1
Section: 2
Variables: \(M\) a multiset,
\(o\) an element
Index: 16

Page: 15
Section: 2
Chapter: 1
Nth element: The number of \(n\)-multiset with \(k\) elements
Name: Multisets
Variables: \(X\) a \(k\)-set
Nth value: \({n+k-1}\choose {n}\), \(\frac{k^{\overline n}}{n!}\)
Index: 18

Smaller0: \((\sum_{i=1}^m x_i)^n\)
Greater0: \(\sum_{(k_1,\dots, k_m)}{n\choose k_1\dots k_m}\prod_{i=1}^mx^{k_i}_i\)
Page: 15
Chapter: 1
Section: 2
Variables: \(X\) a \(k\)-set
Smaller to greater: =
Hide middle: ye
Name: Multinomial theorem

Name: Multinomial coefficient
Definition: \(\frac{n!}{\prod k_i!}\)
Page: 15
Chapter: 1
Section: 2
Variables: \(X\) a \(k\)-set
Notation: \({n\choose k_1\dots k_m}\)
Assuming: \(\sum k_i=n\)

Name: The \(m\times n\)-lattice of integral points in \(\mathbb Z^2\)
Definition: \([m-1]\times[n-1]\)
Page: 16
Chapter: 1
Section: 2

Name: A \((0,1)\)-step
Definition: An horizontal step
Page: 17
Chapter: 1
Section: 2
Variables: \(m,n\in\mathbb N\)
Context: Lattice

Name: A \((1,0)\)-step
Definition: A vertical step
Page: 17
Chapter: 1
Section: 2
Variables: \(m,n\in\mathbb N\)
Context: Lattice

Name: A lattice path
Definition: A succession of step from \((0,0)\) to \((m,n)\)
Page: 17
Chapter: 1
Section: 2
Variables: \(m,n\in\mathbb N\)

Page: 17
Section: 2
Chapter: 1
Nth element: The set of lattices paths in \(m\times n\) integral lattice
Notation: \(L(m,n)\)
Variables: \(m,n\in\mathbb N\)
Nth value: \({m+n\choose m}\)

Name: The family of all partitions of \(S\)
Page: 20
Chapter: 1
Section: 3
Variables: \(S\) a set
Notation: \(\prod(N)\)

Definition: The union of the \(A_i\), assuming that the \(A_i\) are pairwise disjoint
Page: 20
Chapter: 1
Section: 3
Notation: \(\dot\bigcup A_i\)

Name: A \(k\)-partition of \(N\)
Definition: A partition of \(N\) into \(k\) blocks
Page: 20
Chapter: 1
Section: 3
Variables: \(N\) a set
\(k\in\mathbb N\)

Page: 20
Section: 3
Chapter: 1
Nth element: \(k\)-partitions of \(\{1,\dots,n\}\)
Variables: \(n,k\in\mathbb N\)
Sequence name: Stirling number of the second kind
Sequence notation: \(S_{n,k}\) or \(\genfrac\{\}{0pt}{}{n}{k}\)

Page: 20
Section: 3
Chapter: 1
Nth element: partitions of \(\{1,\dots,n\}\)
Variables: \(n,k\in\mathbb N\)
Equation: \(\sum_{k=0}^nS_{n,k}\)
Sequence name: Bell number
Sequence notation: \(\text{Bell}(n)\)

Page: 20
Section: 3
Chapter: 1
Nth element: A map from \(N\) to \(R\)
Notation: \(Map(N,R)\)
Variables: \(N,R\) sets
Nth value: \(|R|^{|N|}\)

Page: 20
Section: 3
Chapter: 1
Nth element: An injective map from \(N\) to \(R\)
Notation: \(\mathrm{Inj}(N,R)\)
Variables: \(N,R\) sets
Nth value: \(|R|^{\underline{|N|}}\)

Page: 20
Section: 3
Chapter: 1
Nth element: An surjective map from \(N\) to \(R\)
Notation: \(\mathrm{Surj}(N,R)\)
Variables: \(N,R\) sets
Nth value: \(|R|!S_{|N|,|R|}\)

Question: \(\sum_{k=0}^nS_{n,k}x^{\underline k}\)
Answer: equals \(x^n\)
Page: 21
Chapter: 1
Section: 3
Variables: \(n\in\mathbb N\)

Name: A polynomial sequence
Definition: A sequence of polynomials over a field of characteristic 0 such that the degree of the \(n\)-th element is \(n\)
Page: 21
Chapter: 1
Section: 3
Typ: A basis of the set of polynomial
Denoted by: \(p_0(x),p_1(x),\dots\)

Name: The connected coefficient between the sequences \((p_n(x))\) and \((q_n(x))\)
Definition: The numbers \(a_{n,k}\) such that \(p_n(x)=\sum_{k=0}^na_{n,k}q_k(x)\)
Page: 21
Chapter: 1
Section: 3
Variables: \((p_n(x))\) and \((q_n(x))\) two polynomial sequences
Example: \((S_{n,k})\)
Typ: Infinite lower triangle matrix
Applied to: \((x^n)\) and \(x^{\underline n}\)

Smaller0: \(j=1\)
Greater0: 1
Page: 22
Section: 3
Variables: \(i,j\in\mathbb N\)
Prefix Greater: \(S_{i,j}\) equals
Smaller1: \(i=j\)
Connect Smaller0: or

Smaller0: \(j=2\)
Greater0: \(2^{i-1}-1\)
Page: 22
Chapter: 1
Section: 3
Variables: \(i,j\in\mathbb N\)
Prefix Greater: \(S_{i,j}\) equals

Smaller0: \(j=i-1\)
Greater0: \(n\choose 2\)
Page: 22
Chapter: 1
Section: 3
Variables: \(i,j\in\mathbb N\)
Prefix Greater: \(S_{i,j}\) equals