NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 18/05/2018

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

 

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 à 2n – 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 (21) et une fois 2 marches (12)  };

*      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

*      PartitionsIndex

Voir

*      Escalier roulant

*      Fibonacci et partitions

*      Jeux et énigmesIndex

*      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