Partition, escalier à 2 marches

NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 06/03/2019 Orientation générale DicoMot Math Atlas Références M'écrire Barre de recherche DicoCulture Index alphabétique Brèves de Maths
	Jeux et énigmes
Débutants Général	Combinatoire				Glossaire Général
INDEX Partitions Jeux Combinatoire	Escalier 2	Escalier 3	Timbres	Abeille
	Parties de jeu	Tournois	Lapins	Croix
	Tableaux	Loto traditionnel avec cartons
		Sommaire de cette page >>> Problème de l'escalier >>> Quatre marches >>> Escalier à marches >>> Compositions des nombres de 1 à 5 >>> Compositions des nombres de 6 à 10 >>> Formule de récurrence >>> Bilan

ESCALIER qui mène à FIBONACCI

Décomposition d'un entier sous contraintes

(1/2)

Qui l'eut cru? Lorsque vous montez les marches d'un escalier en progressant d'une ou deux marches à la fois, vous expérimentez la suite des nombres de Fibonacci sans le savoir.

Voici l'énigme classique à résoudre:

Un escalier compte 5 marches. Je monte les marches par une ou par deux. Combien de possibilités?

Moyen imagé de compter les façons de décomposer un nombre en sommes de termes avec la contrainte de n'utiliser que des nombres allant de 1 à k, comme 5 = 1 + 2 + 2.

Petit point de situation

Cette page et la suivante traite de la décomposition partielle des nombres: partitions avec permutation avec les nombres de 1 à k seulement.

S'agissant des partitions (vraies, sans permutation), on rappelle la propriété importante des partitions partielles: la quantité de partitions avec k sommants est égale à celle des partitions avec le nombre k.

Ce n'est pas le cas avec les compositions. Mais, deux propriétés sont à noter:

la quantité totale des compositions de l'entier n est égale à 2^{n – 1}, et

la quantité partielle des compositions avec les nombres jusqu'à k est égale à un nombre k-bonacci (objet de ces pages).

Voir Partitions – Orientation – Petit narratif avec liens sur ces pages

Problème de l'escalier

Voici le décompte pour 1, 2 ou 3 marches:

1 marche: 1 seule possibilité;

2 marches: 2 possibilités

{deux fois 1 marche (2₁) et une fois 2 marches (1₂) };

3 marches: 3 possibilités;

4 marches : 4 possibilités? Ce serait trop simple …

ESCALIER à 4 marches

Avec quatre marches, on compte 5 possibilités.

Vous aurez compris, avec la notation employée, qu'il s'agit en fait de compter toutes les partitions du nombre 4 en utilisant que des 1 et des 2.

4 = 1 + 1 + 1+ 1 (marche une à une)

4 = 2 + 1 + 1 (deux marches puis une à une)

4 = 1 + 2 + 1 (etc.)

4 = 1 + 1 + 2

4 = 2 + 2

Il y en a effectivement 5. Il s'agit de toutes les partitions, permutations comprises que l'on appelle plutôt compositions

Récapitulatif:

Marches	1	2	3	4	5	6
Possibilités	1	2	3	5	8?	13?
Suppléments		1	1	2	3	5

Suppléments = quantité de possibilités en plus pour une marche de plus.

Compositions de n (n de 1 à 5)

Nous avons vu que le problème de l'escalier revient à un problème de partition d'un nombre.

Étudions les partitions du nombre n dans les conditions suivantes:

avec les nombres 1 et 2 exclusivement,

selon toutes les permutations, mais

en ignorant les permutations du même nombre: Ex: 2 + 2 et 2 + 2 comptent pour une seule combinaison.

Le tableau montre les différentes partitions (en fait compositions) pour n de 1 à 5.

Explications:

n = 3 => 1+2 représente les deux possibilités 1+2 et 2+1, soit deux possibilités

n = 4 => 1+1+2 illustre le cas de 1+1+2, 1+2+1 et 2+1+1, soit trois possibilités.

n = 5 => 1+2+2 compte pour trois cas selon la place du 1: 1+2+2, 2+1+2, et 2+2+1.

Compositions de n (n de 6 à 10)

Poursuivons cette analyse pour de telles partitions (en fait, compositions) des nombres de 6 à 10.

Explications:

n = 6 => 1+1+1+1+2 conduit a 5 possibilités suivant la position du 2.

n= 6 => 1+1+2+2 est représentatif des six possibilités suivantes:

1 + 1 + 2 + 2

1 + 2 + 1 + 2

1 + 2 + 2 + 1

2 + 1 + 1 + 2

2 + 1 + 2 + 1

2 + 2 + 1 + 1

En fait, ce sont les toutes les combinaisons de deux objets (ici le nombre 2) parmi quatre objets:

En vert, la simplification que l'on effectue immédiatement avec un peu d'habitude.

On peut voir les choses aussi avec les permutations: permuter quatre objets: 4!. Mais les deux 1 donnent des permutations identiques: 2! C'est la même chose pour les 2 qui donnent 2! permutations à éliminer. Soit le bilan: 4!/ (2! x 2!) = 1 x 2 x 3 x 4 / 4 = 6.

n = 7 => 1+1+1+2+2 Combinaisons de 2 parmi 5:

ou permutations: 5! / (3! x 2!) = 10.

n = 9 => 1+1+1+2+2+2, un dernier exemple de calcul:

ou permutations: 6! / (3! x 3!) = 4 x 5 x 6 / 6 = 20.

Formule de récurrence

Ce tableau présente les compositions des nombres de 1 à 6: partitions avec autorisation des permutations.

On se limite aux additions avec les nombres 1 et 2 exclusivement.

Voyez la construction:

1. Recopiez la composition précédente et ajoutez 1;

2. Recopiez la composition d'avant et ajoutez 2.

Pour le nombre 6:

On retrouve toutes les compositions du 5 en ajoutant 1. Facile!

Ensuite, pami toutes ces nouvelles combinaisons, il est possible de remplacer les deux 1 finaux par un seul 2. Or, c'est la même quantité que pour le 4 à laquelle on a ajouté 1 pour faire le 5, puis 1 pour faire le 6.

Soit la formule générale: D(n + 1) = D(n) + D(n–1)

C'est typiquement la formule de récurrence de la construction des nombres de Fibonacci.

Bilan

Le problème de la montée des n marches d'un escalier est équivalent à celui de la composition (partition avec permutations) du nombre n.

Avec la montée de 1 ou 2 marches à la fois – ou la composition avec des 1 et 2 exclusivement – la quantité de possibilités est égale au nombre de rang n+1 de la suite de Fibonacci.

n	1	2	3	4	5	6	7	8	9	10
Possibilités	1	2	3	5	8	13	21	34	55	89
Fibonacci	1	1	2	3	5	8	13	21	34	55

Que se passe-t-il si je pouvais monter aussi trois marches? >>>

Donnez-moi les conclusions, tout de suite >>>

Retour	Partitions – Quantité
Suite	Escalier avec trois marches Études de cas sous contrainte avec 67 Partitions – Fonctions génératrices Chemin le plus court Trajets d'un point à un autre Voyageur de commerce Partitions – Index
Voir	Escalier roulant Fibonacci et partitions Jeux et énigmes – Index Méandres Papier plié Parcours du taxi en ville Partage – Énigmes classiques
DicoNombre	Nombre 14 Nombre 89
Cette page	http://villemin.gerard.free.fr/aJeux1/Combin/Escalier.htm