Skip to content.
Combinatoire 1
1
Les principes de base
2
Les récurrences
3
Les fonctions génératrices
4
Les problèmes de choisir des objets
5
Les problèmes d’occupation
6
Chapeaux, rencontres et tables rondes
7
La résolution des récurrences
Combinatoire 1
Combinatoire 1
Nicolas Bouffard
Table des matières
1
Les principes de base
1.1
Introduction et méthodes élémentaires
1.2
Multiplication: Le principe du produit
1.3
Addition: Le principe de la somme
1.4
Soustraction: Le principe d’inclusion-exclusion
1.5
Égalité: Le principe de la bijection
1.6
Division: Le principe d’équivalence
1.7
Existence: Le principe des nids de pigeons
1.8
Récurrence: Le principe d’induction
2
Les récurrences
2.1
Introduction
2.2
Problème de chaines binaires
2.3
Problème de chaînes ternaires
2.4
Problème de blocks
2.5
Problème de mots
2.6
Problème de triangulation
3
Les fonctions génératrices
3.1
Les fonctions génératrices ordinaires
3.2
Quelques exemples
3.3
Problème de pièces de monnaie
3.4
Les fonctions génératrices exponentielles
3.5
Le problème du Mississippi
3.6
Retour sur le problème des pièces de monnaie
4
Les problèmes de choisir des objets
4.1
Les 4 façons de choisir
4.2
Avec ordre / Avec remise
4.3
Avec ordre / Sans remise
4.4
Sans ordre / Sans remise
4.5
Sans ordre / Avec remise
4.6
Résumer des
4
\displaystyle 4
façons de choisir des objets
4.7
Quelques problèmes supplémentaires
4.8
Les probabilités
4.9
Le paradoxe des anniversaires
4.10
Le problème de la NHL
5
Les problèmes d’occupation
5.1
Introduction et les 8 cas triviaux
5.2
Application du principe du produit (4 cas)
5.3
Les compositions (4 cas)
5.4
Les nombres de Stirling de deuxième espèce et les nombres de Bell (4 cas)
5.5
Les partitions d’un entier (3 cas)
5.6
L’ordre dans les urnes et les nombres de Lah (6 cas)
5.7
Quelques problèmes supplémentaires
6
Chapeaux, rencontres et tables rondes
6.1
Le problème des chapeaux
6.2
Le problème des rencontres
6.3
Nombres de Stirling de première espèce
6.4
Le problème des ménages
6.5
Quelques identités sur les nombres de Stirling et de Lah
7
La résolution des récurrences
7.1
Introduction
7.2
Quelques outils
7.3
La méthode des fonctions génératrices
7.4
La méthode du polynôme caractéristique
7.5
La méthode de dérivation symbolique
7.6
La méthode des fonctions génératrices exponentielles
7.7
Applications des récurrences