Aspects algorithmiques de la combinatoire
Algorithmical aspects of combinatorics

R. Cori, D. Rossin

1 Permutations

Definition 1 A permutation of {1... n} is a bijection from {1... n} into itself.

There are several ways to represent a permutation. The first and most natural one is given below:

s = (

1	2	3	4	5	6
s(1)	s(2)	s(3)	s(4)	s(5)	s(6)

)

This representation is called the two-line representation. As the first line is always the identity one can forget its writing and the permutation is then given by its one-line representation:

s = (

s(1)

s(2)

s(3)

s(4)

s(5)

s(6)

)

The images of elements are written s(i) or s_i throughout the lesson.

Another notation for permutations, the cyclic notation, will be given further in this lesson.

In the first part, we are going to use statistics on permutations to give some complexity results on sorting algorithms.

1.1 Inversion table

Definition 2 (s_i,s_j) is an inversion in s if and only if s_i > s_j and i < j. We denote by Inv(s) the set of all inversions. Inv(s) = { (s_i,s_j), s_i > s_j and i < j}.

The number of inversions in s gives the number of elementary operations (transpositions) needed to transform s into the identity element.

Definition 3 The inversion table of a permutation is :
T_a[i] = |{j, (j,i) Î Inv(s)}|

Example: a = (3 7 5 2 4 8 6 1 9)

	1	2	3	4	5	6	7	8	9
T_a

Note that T_a[i] is the number of elements j greater than i but before i in a's one-line notation. Thus T_a[n] = 0 and 0 £ T_a[k] £ n-k.

Exercise 1

Prove that given a permutation s you can compute in O(n²) time its inversion table.
Prove that given a tabular T corresponding to a permutation s (unknown), one can retrieve s in O(n²) time.
Can you make faster ?

1.1.1 Enumeration and application to sorting algorithm analysis

Exercise 2 How many inversions could a permutation have ?

Let I_n,k be the number of permutations of length n having k inversions. Note that:

n(n-1)

k=0

I_n,k = n!

Note that I_n,k is also the number of arrays of size n such that 0 £ T[i] £ n-i and the sum of all elements equals k. By deleting the first entry of the array we obtain a new array of size n-1 respecting all conditions such that the sum of all elements equals k-T[0]. Thus

I_n,k =

k'=k-n+1

I_n-1,k'

Exercise 3 Fill the following array

N. inversions	0	1	2	3	4	5	6	7	8	9	10
n=1	1
n=2
n=3
n=4
n=5

Let I_n(x) the generating function of inversions:

I_n(x) = åI_n,k x^k

Note that I_n(x) = I_n-1(x)(1+x+...+x^n-1)
I_n(x) = 1(1+x)(1+x+x²)...(1+x+...+x^n-1)
I_n(x) = 1/n! å_k=0^n(n-1)/2 k I_n,k
I_n(x) = I'_n(1)/I_n(1) = ¶ ln(I_n(x))/¶ x(1)

Theorem 1 The average number of inversions in a permutation is n(n-1)/4.

Another (simpler) proof is easily derived from studying the miror permutation with the permutation.

1.1.2 Sorting by selection

In this algorithm you first find the smallest element and then you put it in the first place.

for (int i = 0; i < n ; i++)
  for (int j = i+1; j < n; j++)
    if (a[i] > a[j]) swap(a[i],a[j]);

When performing a swap operation, the number of inversions decrease by 1. So, the number of swaps equal the number if inversions.

1.1.3 Sorting by insertion

for (int i = 1; i < n; i++)
  for (int j = i; j !=0 && a[j]<a[j-1]; j--)
    swap(a[j],a[j-1]);

Exercise 4

The number of tests is :

1.2 Cycles and smallest element

Exercise 5 Let a be the following permutation : a = 372159648.

Draw the digraph (directed graph) where each vertex represents a number of the permutation and there exists an arc between i and j if and only if j = a(i).
Write the cycles of this graph. This is called the cyclic notation of the permutation.
Let C_n,k be the number of permutations of size n with k cycles. Give the first values for n £ 5.
Show that C_n+1,k = n C_n,k + C_n,k-1.
Let C_n(x) = åC_n,k x^k. Prove that
C_n(x) = P_i=0^n-1 (x+i)
Prove that the average number of cycles in a permutation of size n is H_n = å_i=1ⁿ 1/i.

Definition 4 Let s be a permutation. s(i) is a partial minimum if s(i) is tricly less than all s(j), j < i.

The following algorithm gives the number of partial minima in a permutation.

min = a[0];
for (int i = 0; i < n ; i++)
  if (a[i] < min) min = a[i];

Exercise 6 Show that number of changes of partial minimal is equal to C_n,k.

We can give a bijective proof of this result using Foata transformation.

1.3 Descents and excedences

Definition 5 Let a be a permutation of size n.

a_i is a descent if a_i > a_i+1
a_i is an excedence (or weak excedence) if a_i ³ i
a_i is a strict excedence if a_i > i

Fill the following array:

	Nb descents	Nb excedences	Nb strict excedences
123
132
213
231
312
321

We denote by:

D_n,k the number of permutation of size n having k descents.
E_n,k the number of permutation of size n having k excedences.
F_n,k the number of permutation of size n having k strict excedences.

Note that for n=3 we have D_n,k = F_n,k = E_n,k+1.

Proposition 1 D_n,k = D_n,n-k-1.

Proof. Use a the mirror permutation.

Proposition 2 a^-1(i) = j Û a(j) = i, |E(a)|+|F(a^-1)| = n. Thus E_n,k = F_n,n-k

Proof.

Prove that if i £ a(i) then a^-1(a(i)) is not a strict excedent for a^-1.
Prove that if i > a(i) then a^-1(a(i)) is a strict excedent for a^-1.

Proposition 3 D_n,k = E_n,n-k

Proof. We only sketch the proof. Let a be a permutation with n-k excedents. We rewrite the permutation a in the cyclic notation, with the greatest element of each cycle in the first place and every maxima in increasing order like in Foata transformation. We obtain a permutation with k descents.

Exercise 7 Make an example of this transformation and prove the property above.

Exercise 8 With the three last propositions, prove the claim result D_n,k = F_n,k = E_n,k+1

Proposition 4 D_n,k = (k+1) D_n-1,k + (n-k) D_n-1,k-1

Proof. Choose where you insert the greatest element.

Exercise 9 Let D_n(x) = åD_n,k x^k. Prove that D_n(x) = (1+(n-1)x)D_n-1(x) + (x-x²)D'_n-1(x).

2 Permutation pattern

2.1 Greatest increasing subsequence

Definition 1 The longest increasing subsequence of a permutation s is the largest value p such that there exist i₁,...,i_p and a_i₁ < a_i₂ < ... < a_{i_p} with i₁ < i₂ < ... < i_p.

Exercise 1 Let s = ( 7, 9, 12, 2, 11, 3, 8, 5, 6, 1, 4, 10 ). Give the longest increasing subsequence.

Proof. Build iteratively all the longest increasing subsequences.

¬ 9 ¬

ì
í
î

¬ 3 ¬

ì
í
î

5 ¬ 6 ¬ 10

This leads to the following dynamic programming algorithm where you fill in two different arrays:

BEST[i] = j if the longest increasing subsequence of size i ends by j and j is the smallest value possible.
PRED[k] = precessor of k in the largest increasing subsequence ending with k.

Exercise 2 Give the algorithm for computing the longest increasing subsequence.

2.2 Permutation pattern

Definition 2 Let s and p be two permutations of size n and p respectively with p £ n. We say that p is a pattern of s whenever there exists i₁ < i₂ < ... < i_p such that s_{i_k} < s_{i_l} whenever p_k < p_l for all 1 £ k ¹ l £ p.

For example, we say that 132 occurs in 123 64 5. But we say that 543216 avoids 132. .

2.3 One-stack sortable permutations

A stack is an ordered set, with two operations, pop and push such that:

pop returns the last element inserted and deletes it from the set.
push add an element to the set.

Let S be a stack. A permutation s₁s₂...s_n is said to be one-stack sortable if it can be transformed to identity by the following algorithm.

i ¬ 1, S is the empty stack
Either:
- push the element s_i in the stack and increment i by one.
- or pop an element from the stack and write it out.
Return to step 2.

The output is the list of elements popped from the stack.

Exercise 3

Give the one-stack sortable permutations of size 1, 2, 3 and 4.
Find a characterization for these permutations and prove it..

Definition 3 A plane tree of size n is a tree with n edges embedded in the plane and rooted on an edge.

Exercise 4

How many tree are there of size 1, 2 and 3.

Exercise 5 Let T be the following tree:

Number the edges through a postfix depth first traversal of the tree
Read the tree through a prefix depth first traversal of the tree
Notice that the resulting permutation avoids 231. Prove it.

Definition 4 A unary-binary tree is a plane rooted tree where each vertex has arity 1 or 2 (i.e. degree 2 or 3). Vertices of arity 1 have either a right or a left son. A binary tree is a plane rooted tree where each vertex has arity 2.

Exercise 6

How many unary-binary trees are there of size 1, 2, 3 and 4 ?
Notice that a vertex of a plane tree is either the leftmost child of another node or the brother of a node. Deduce a correspondance between unary-binary trees and plane trees.
How many binary trees are there with 2, 3 and 4 leaves ?
Find a correspondance between those objects

2.4 Dyck paths

Definition 5 A Dyck path of length n is a path in the plane starting at (0,0), ending at (n,n) and made of n horizontal and n vertical steps that never goes under the line y=x. A Dyck path of length n is a path in the plane starting at (0,0), ending at (2n,0) made of n (1,1) steps and n (1,-1) steps which never goes below the x axis.

Exercise 7 Considering a left-right depth first traversal of a plane tree, show that Dyck paths of length n are in one-to-one correspondence with plane trees of size n.

2.5 Enumeration

We want to enumerate the number of plane trees with n edges or the number of Dyck path of size n or the number of unary-binary trees with n-1 edges or the number of binary trees with n+1 leaves.

2.5.1 Enumeration of binary trees

A binary tree is either a leaf or an ordered set of two binary trees. Thus :

B(x) = x + B²(x)

2.5.2 Enumeration of Dyck paths

A Dyck path is either an empty one or an ordered set of two Dyck paths. Thus:

D(x) = x D²(x) + 1

2.5.3 Direct proof on Dyck path

Note that a Dyck path is a word which contains n letters a and n letters b. Get a Dyck path and add a dwon step at the end. These paths are in bijection with Dyck paths. Then consider all words with n letters a and n+1 letters b. Notice that only one rotation of this word corresponds to such a path.

2.6 Enumeration of pattern-avoiding permutations

The first question which arises in this definition is given a pattern p, how many permutations of size n avoids p ?

Stanley and Wilf conjectured (Bona 1997, Arratia 1999), that for every permutation pattern s, there is a constant c(s)<¥ such that for all n, F(n,s)£[c(s)]ⁿ.

A related conjecture stated that for every s, the limit lim₍n®¥)[F(n,s)]^(1/n) exists and is finite.

Arratia (1999) showed that these two conjectures are equivalent. The conjecture was proved by Marcus and Tardos (2004). In fact Marcus and Tardos prove The Füredi-Hajnal conjecture on matrix containment.

See article from Marcus and Tardos for the proof.

3 Trees

Given n numbered vertices, how many trees can you draw ?

Exercise 1

Try n=2,3,4
Guess a formula

3.1 Cayley formula and Prüfer code

Definition 1 A tree si a set of n-1 pairs of vertices (i,j) such that the graph obtained is acyclic.

Theorem 1 The number of trees (with n vertices) equals n^n-2.

Note that n^n-2 is also the number of words of length n-2 on the alphabet 1,2...,n.

3.1.1 Prüfer code

The prüfer code of a tree is given by the following algorithm:

Let l the leave with the greatest label.
Write the label of the neighbor of l.
Delete l from the tree.
If the number of remaining vertices is greater than 2 goto 1.

Remark 1 The leaves of the original tree are the numbers which does not appear in the code.

Exercise 2 Prove it

Exercise 3 Given the Prüfer code of a tree a₁,a₂,...,a_n-2 give an algorithm to find the associated tree

Another proof of the enumeration of trees can be given via the matrix tree theorem.

Theorem 2 [Matrix Tree] Let G=(V,E) be a graph. The number of spanning trees of this graph is given by the determinant of any of (n-1)×(n-1) submatrices of the following matrix :

æ
ç
ç
ç
è

d₁	-E(1,2)	...	-E(1,n)
-E(2,1)	d₂	...	-E(2,n)
...	...	...	...
-E(n,1)	-E(n,2)	...	-d_n

ö
÷
÷
÷
ø

3.1.2 Trees with prescribed degree (proof from Wikipedia)

Another proof of the Cayley formula comes from the following Lemma:

Lemma 1 The number of trees on vertices 1,...,n with degree d₁,d₂,...,d_n, (åd_i = 2n-2) is:

(n-2)!

(d₁-1)!(d₂-1)!...(d_n-1)!

Proof. We prove this formula by induction on the number of vertices. For n=1 and n=2 the proposition holds trivially. So assume the proposition holds for n-1. Since åd_i = 2n-2 there exists k such that d_k = 1. Suppose that d_n = 1 without loss of generality. For i = 1, 2, ..., n-1 let B_i be the set of trees on the vertex set {v₁, v₂, ... v_n-1 } such that:

d(v_j) =

ì
í
î

d_j,	if j ¹ i
d_j-1,	if j=i

Trees in B_i correspond to trees in A with the edge v_i,v_n, and if d_i = 1, then B_i = f.

Since v_n must have been connected to some node in every tree in A, we have that

|A| =

n-1

i=1

|B_i|

Further, for a given i we can apply either the inductive assumption (if d_i > 1) or our previous note (if d_i = 1, then B_i = f) to find |B_i|:

|B_i| =

ì
ï
í
ï
î

if d_i=1

(n-3)!

(d₁-1)!···(d_i-2)!···(d_n-1-1)!

otherwise

for i=1,2,...,n-1

Observing that

(n-3)!

(d₁-1)!···(d_i-2)!···(d_n-1-1)!

(n-3)!(d_i-1)

(d₁-1)!···(d_n-1-1)!

it becomes clear that, in either case, |B_i| = (n-3)!(d_i-1)/(d₁-1)!···(d_n-1-1)!.

So we have

|A|

n-1

i=1

|B_i|

(1)

n-1

i=1

(n-3)!(d_i-1)

(d₁-1)!···(d_n-1-1)!

(2)

(n-3)!

(d₁-1)!···(d_n-1-1)!

n-1

i=1

(d_i-1)

(3)

And since d_n = 1 and å_i=1ⁿd_i = 2n-2, we have:

|A| =

(n-3)!

(d₁-1)!···(d_n-1)!

(n-2) =

(n-2)!

(d₁-1)!···(d_n-1)!

which proves the lemma.

We have shown that given a particular list of positive integers d₁, d₂, ..., d_n such that the sum of these integers is 2n- 2, we can find the number of trees with labeled vertices of these degrees. Since every tree on n vertices has n - 1 edges, the sum of the degrees of the vertices in an n-vertex tree is always 2n- 2. To count the total number of trees on n vertices, then, we simply sum over possible degree lists. Thus, we have:

|T_n| =

d₁+d₂+···+d_n = 2n-2

(n-2)!

(d₁-1)!···(d_n-1)!

If we reindex with k_i = d_i - 1 for i=1,2,...,n, we have:

|T_n| =

k₁+k₂+···+k_n = n-2

(n-2)!

k₁!··· k_n!

Finally, we can apply the multinomial theorem to find:

| T_n | = n^{n - 2}

as expected.

3.1.3 Cycles and transpositions

Let a be a cycle : a=(1 3 7 5 8 2 4 6). a can be written as a product of transpositions:

a = (1 3)(3 7)(7 5)(5 8)(8 2)(2 4)(4 6)

Note the you can always write a cycle as a product of n-1 transpositions.

Theorem 3 The number of ways to write a cycle of length n as a product of n-1 transpositions is n^n-2.

For example: (1 3 2) = (1 2)(2 3) = (1 3)(1 2) = (2 3)(1 3)

Lemma 2 The product t₁t₂...t_n-1 is a cycle if and only if the graph G=(V,E) where V=1,2,...,n and there is an edge between i and j if and only if (i j) is a transposition that appears in the product.

Proof. Note first that a graph made of n vertices and n-1 edges is either a tree (if it is conected) or it has several connected components.

Then, note that if s is a permutation that has k ³ 2 cycles then s t is a permutation with k-1 cycles if t=(i j) and i and j are in different cycles.

As there is n^n-2 different trees, and for each tree there are (n-1)! different ways of making the product we have a surjection from trees to cycles. But each cycle is obtained the same number of times by symmetry so that for each cycle there is n^n-2 ways of writing it as a product of transpositions.

3.2 Parking function

Definition 2 A serie a₁,...,a_n is a Parking serie if the following algorithm give a position to all cars 1,...,n.

For i from 1 to n do
i takes the first empty position k such that k ³ a_i

For example 111,123,132,231,213,312,321,112,121,211,113,131,311,122,212,221 are all Parking series of size 3.

Theorem 4 The number of Parking functions is (n+1)^n-1.

Another equivalent definition is :

Definition 3 a₁,...,a_n is a Parking serie if and only if there exists a permutation a=a₁,a₂,...,a_n such that " i, a_i £ a_i.

Exercise 4 Is the serie 6 3 1 2 2 7 6 6 a Parking serie ?

The following java algorithm determine if a serie is a Parking serie/

[H] nthe number of cars u an array where u[i] is the choice of car i place an empty array of size n Returns true if all cars have found an empty place and false otherwise

i=1 n j ¬ u[i] j £ n && place[j] != 0 j ¬ j+1 j == n+1 false place[j] ¬ i true

To prove the enumeration formula consider a Parking with n+1 places and a serie of n integers between 1 and n+1.

4 Chromatic polynomial

Let f be a function such that f_G(z) counts the number of ways to color G with exactly z colors.

Exercise 1 Show that f_G(z) is a polynomial by considering the coloring of G, G-e and G/e.

Definition 1 The chromatic polynomial of a graph G is a polynomial p_G(z) which counts the number of ways to color G with exactly z colors.

If e is an edge of a graph G then G-e represents the graph G where the edge e has been deleted and G/e represents the graph where G has been contracted.

Exercise 2 Show that p_G(z) is a polynomial by considering the coloring of G, G-e and G/e.

Prove that :

p(x)=å_{FÌ E}(-1)^Fx^V-r(F) where the sum is over all subsets F of E, and r(F) denotes the rank of F in G, i.e. the number of elements of any maximal cycle-free subset of F. Compute the chromatic polynomial of T_n a tree with n vertices, K_n and C_n, .

The chromatic polynomial of a disconnected graph is the product of the chromatic polynomials of its connected components. The chromatic polynomial of a graph of order n has degree n, with leading coefficient 1 and constant term 0. Furthermore, the coefficients alternate signs, and the coefficient of the (n-1)st term is -m, where m is the number of edges.

5 Tutte polynomial

5.1 Definitions

The Tutte polynomial T_G of the graph G=(V,E) could be defined by the two following recursive formula:

T_G =

ì
í
î

x T_G/e	If e is an isthmus
y T_G-e	If e is a loop
T_G-e + T_G/e	Otherwise

T_G =

F Ì E

(x-1)^r<E>-r<F>(y-1)^n<F>

where r<E> = |G|-k(E) et n<E> = |E|-|G|+k(G) = |E|-r<E> (edges-vertices+connected components). r is called the rank and n the nullity.

Note that the second definition yields a polynomial but the first one could give many polynomials. First, we can prove that the first definition is correct i.e. that every sequence of edge contraction/deletion yields to the same polynomial.

An other proof is to repark that both definitions are equivalent so that the first is a definition !!!

6 Evaluations of the Tutte polynomial for a connected graph

6.1 Evaluation in (1,1)

Give an interpretation of T_G(1,1).

6.2 T_G(2,1)

Give an interpretation of T_G(2,1).

6.3 T_G(1,2)

Give an interpretation of T_G(1,2).

6.4 T_G(2,2)

Give an interpretation of T_G(2,2).

6.5 Towards a new Definition of Tutte polynomial

T_G(x,y) =

i,j

t_ijxⁱy^j

where t_ij is the number of spanning forests of G with internal activity i and external activity j.

The proof is by induction on the number of edges of G=(V,E). The formula is true for G=(V,). Suppose now that the formula is true till m-1 edges and take a graph G with n vertices and m edges e₁,...,e_m.

Let G'=G-e_m and G'' = G/e_m. By induction T_G' = å_ijt'_ij xⁱ y^j et T_G'' = å_ijt''_ij xⁱ y^j

We now separate different cases depending on the nature of e_m.

If e_m is an isthmus (or bridge), then e_m belongs to any spanning forest of G. Moreover, e_m is internal active in every forest. So F is a (i,j) spanning forest if and only if F-e_m is a (i-1,j) spanning forest of G-e_m. Indeed e_m does not modify the activity of any other edges.

Hence:

å

i,j
t_ijxⁱy^j =

å

i,j
t'_i-1,jxⁱy^j = x

å

i,j
t'_i-1,jx^i-1y^j = xT_{G-e_m}(x,y) = T_G(x,y)
If e_m is a loop, then e_m belongs to no spanning forest. A subgraph F is a spanning foret if and only if it is a spanning forest of G-e_m. Moreover, e_m is external active in any spanning forest. F is a (i,j) spanning forest iff it is a (i,j-1) spanning forest of G-e_m.
Otherwise notice that we can separate the spanning forests of G into two parts: those which contain e_m and the others. The first ones are in bijection with spanning forests of G-e_m and the others with G/e_m.

This new definition allow to prove that the number of spanning trees whose internal activity and external activity is given do not depend on the numbering of the edges.

6.6 Hardness of computation

Computing T_G(a,b) for a graph G is P-hard everywhere except for (1,1), (-1,-1), (0,-1), (-1,0), (i,-i), (-i,i), (j,j²), (j²,j) where the evaluation is polynomial.

7 Words

7.1 Exhaustive generation

The goal is to give an algorithm to compute all words of size n on an alphabet with m letters.

The first and naive algorithm consists in counting from 0000000 to (m-1)(m-1)(m-1)... by adding 1 at each step.

The algorithm becomes: [H] n the size of words m the size of the alphabet, here m=2 Compute all words of size n

(true) { print(f) j = n-1 (f[j]==1) f[j] = 0 j-- (j == -1) Exit f[j] = 1

Proposition 1 The number of comparisons is 2ⁿ⁺¹-1.

7.2 Gray Code

We want to compute every word but changing only one bit between two words.

Exercise 1

Find an ordering of words of size n verifying the above property. Try for n=1,2,3.
Write the form of the serie.
Write the example for n=4.
Guess an algorithm to compute all words using this Gray code.

7.3 Factors of a word

We want to find a word such that all words of size n are factors of this word. For example 00110 for n=2 and 0001011100 for n=3 are such words. This words are called De Bruijn words. Their length is 2ⁿ+n-1.

8 Lyondon words

Definition 1 A word is a Lyndon word iff " f = f'f'', f'¹ e we have f < f'' for the lexicographic order.

For example 010 is not a Lyndon word because 0 < 010.

Exercise 1 Give all Lyndon words of size 1,2,3,4. Prove that every word (except 0) begins with 0 and ends with 1.

Proposition 1 Every word which is not a power of another word has a unique conjugate which is a Lyndon word.

8.1 Enumeration

Theorem 1 Let L_m(d) the number of Lyndon words of size d on alphabet {0,1,...,m-1}.

d|n

dL_m(d)=mⁿ

Theorem 2 The Möbius function is a number theoretic function defined by µ(n)={

0 if n has one or more repeated prime factors;

1 if n==1;

(-1)^k if n is a product of k distinct primes,

.

The moebius inversion formula is the transform inverting the sequence g(n)=sum₍d|n)f(d) into f(n)=å_(d|n)µ(d)g(n/d)

where the sums are over all possible integers d that divide n and µ(d) is the Möbius function.

Theorem 3

L_m(n)=1/n

d|n

µ(d) m^n/d

8.2 Fundamental Theorem

Theorem 4 Every word f can be written in a unique way as f = l₁l₂...l_k such that l_i is a Lyndon word and l_i ³ l_i+1

Proof. Existence by induction by taking the largest suffix that is a Lyndon word. Unicity : If l₁...l_k = l'₁...l'_k' suppose that l'_k = u l_k.

Theorem 5 For all n, the word obtained by taking all Lyondon words of size d|n followed by its n-1 first letters is a De Bruijn word. The Lyondon words are taken in lexicographic order.

Example, for n=4 the word 0,0001,0011,01,0111,1,000 has length 19 and each factor of length 4 is distinct.

Index

Cayley
- tree, 3.1
chromatic polynomial, 1
conjecture
- Stanley-Wilf, 2.6
Dyck path, 2.4
function
- parking, 3.2
inversion, 2
- generating function, 1.1.1
- table, 3
minimum
- partial, 4
Prufer
- code, 3.1.1
parking
- function, 3.2
path
- Dyck, 2.4
pattern, 2.2
permutation, 1
- descent, 5
- excedence, 5
- increasing subsequence, 2.1
- inversion, 2
- inversion table, 3
- one-stack sortable, 2.3
- pattern, 2.2
  - avoidance, 2.2
  - involvment, 2.2
- product of transpositions, 3.1.3
- representation
  - cyclic, 2
  - one-line, 1
  - two-line, 1

polynomial
- chromatic, 1
Stanley-Wilf, 2.6
sorting
- insertion, 1.1.3
- selection, 1.1.2
table
- inversion, 3
  - computation, 1
tree, 3
- binary, 4
- Cayley, 3.1
- Prufer code, 3.1.1
- plane, 3
- unary-binary, 4

This document was translated from L^AT_EX by H^EV^EA.

Aspects algorithmiques de la combinatoire Algorithmical aspects of combinatorics

R. Cori, D. Rossin

Table of Contents

1 Permutations

1.1 Inversion table

1.1.1 Enumeration and application to sorting algorithm analysis

1.1.2 Sorting by selection

1.1.3 Sorting by insertion

1.2 Cycles and smallest element

1.3 Descents and excedences

2 Permutation pattern

2.1 Greatest increasing subsequence

2.2 Permutation pattern

2.3 One-stack sortable permutations

2.4 Dyck paths

2.5 Enumeration

2.5.1 Enumeration of binary trees

2.5.2 Enumeration of Dyck paths

2.5.3 Direct proof on Dyck path

2.6 Enumeration of pattern-avoiding permutations

3 Trees

3.1 Cayley formula and Prüfer code

3.1.1 Prüfer code

3.1.2 Trees with prescribed degree (proof from Wikipedia)

3.1.3 Cycles and transpositions

3.2 Parking function

4 Chromatic polynomial

5 Tutte polynomial

5.1 Definitions

6 Evaluations of the Tutte polynomial for a connected graph

6.1 Evaluation in (1,1)

6.2 TG(2,1)

6.3 TG(1,2)

6.4 TG(2,2)

6.5 Towards a new Definition of Tutte polynomial

6.6 Hardness of computation

7 Words

7.1 Exhaustive generation

7.2 Gray Code

7.3 Factors of a word

8 Lyondon words

8.1 Enumeration

8.2 Fundamental Theorem

Index

Aspects algorithmiques de la combinatoire
Algorithmical aspects of combinatorics

6.2 T_G(2,1)

6.3 T_G(1,2)

6.4 T_G(2,2)