Propriétés des combinaisons — Les-mathematiques.net The most powerful custom community solution in the world

Propriétés des combinaisons

En me penchant sur l’énigme de la grenouille qui doit monter 20 marches, je suis tombé sur une propriété des combinaison qui m'échappe. La solution combinaisons sur ile des maths :
"Une grenouille se trouve devant un escalier de 20 marches. Sachant qu'elle peut gravir soit une, soit deux marches à la fois, et qu'elle ne peut redescendre, combien de solutions possibles y a-t il pour gravir l'escalier ?

Soit la grenouille décide de faire uniquement des bonds de 2 marches. Elle fera 10 bonds, c'est une première possibilité.

Soit, elle fait 9 bonds de 2 marches et deux bonds de 1 marche, ce qui fait 11 bonds. Dans ce cas, elle peut faire ses bonds de 1 marche quand elle veut. Pour savoir combien de possibilités compte ce cas, il faut savoir la répartition de deux bonds (de 1 marche) parmi 11 bonds.
C'est exactement le même problème que :
combien existe-il de possibilités de tirer 11 boules sachant que 2 sont rouges et 9 sont bleues. on a C(2,11) possibilités
donc si la grenouille fait 9 bonds de 2 marches et deux bonds de 1 marche, il y a C(2,11) possibilités.

Si elle fait 8 bonds de 2 marches et 4 bonds de 1 marche, ce qui fait 12 bonds, avec le même raisonnement, on sait qu'il y a C(4,12) possibilités.

Ainsi de suite, jusqu'au cas ou elle fait 20 bonds d'1 marche, ce qui fait cette fois C(20,20) possibilités.

En tout, il existe alors N possibilités :
N=C(0,10)+C(2,11)+C(4,12)+C(6,13)+C(8,14)+C(10,15)+C(12,16)+C(14,17)+C(16,1)+C(18,19)+C(20,20)
N=1+55+495+1716+3003+3003+1820+680+153+19+1
N=10946 possibilités"

La solution par Fibonacci est la plus élégante. Mais concernant les combinaisons, j'ai trouvé que l'on peut faire uniquement le cacul pour un nombre pair de bonds et le doubler. Pourquoi ? 5473×2=10946
1+495+3003+1820+153+1=5473
C'est vrai également pour un escalier de 12 ou 30 marches, à une unite près lorsque le total des combinaisons est impair.
Pour 12 marches :
Total des combinaisons : 233
Total pour un nombre pair de bonds
1+70+45+1=117
117×2=234
Pour 30 marches :
Total des combinaisons : 1346269
Total des combinaisons pour un nombre pair de bonds : 673135
673135×2=1346270 

Je suppose que ce doit être une propriété des sommes de combinaisons, mais je n'ai pas trouvé laquelle...

Réponses

  • Modifié (October 2023)
    La somme des diagonales ascentantes dans le tableau-triangle de Pascal donne les nombres de Fibonacci. Il me semble qu'on en a déjà parlé, et peut-être plusieurs fois.
  • Modifié (October 2023)
    Les nombres de Fibonacci sont définis par $F_0=0$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$ pour $n \ge 2$.
    Ne pas oublier que $\displaystyle \binom{m}{p}=0$ si $m \in \mathbb N$, $p \in \mathbb N$, $m<p$, et non, ce n'est pas une convention.
    La somme des diagonales ascendantes dans le tableau-triangle de Pascal donne les nombres de Fibonacci : $\displaystyle \sum_{k=0}^{n}\binom{n-k}{k}=F_{n+1}$, ou si l'on préfère sommer seulement les termes non nuls : $\displaystyle \sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\binom{n-k}{k}=F_{n+1}$.
     Cette égalité est très facile à prouver par récurrence, surtout dans sa première forme ci-dessus.
    Elle conforte la double attaque de ce problème combinatoire.
  • Modifié (October 2023)
    J'ai posé ce problème au temps jadis dans Le Petit Archimède n° 81-83, janvier-mars 1982, p. 57, sous l'habillage suivant :
    PB 142 - De combien de manières différentes (en tenant compte de l'ordre) peut-on vider un tonneau de 100 litres au moyen d'une bouteille
    de 1 I. et d'une bouteille de 2 l. (magnum) ? http://www.lepetitarchimede.fr/pa/PA81-82-83.pdf
    J'ai publié une solution dans le n° 86-87, octobre 1982, p. 44 : http://www.lepetitarchimede.fr/pa/PA86-87.pdf
  • Modifié (October 2023)
    Merci beaucoup pour ces propriétés remarquables concernant les combinaisons. Mais pour la grenouille la somme est de la forme sigma [k de 0 à n/2] de C(2k,n/2+k) si on raisonne sur le nombre de bonds de un saut sur le total des bonds, et sur la formule que vous évoquez si on raisonne sur le nombre de bonds de 2 sauts sur le total des bonds. On retrouve les mêmes valeurs dans l'ordre inverse puisque C(k,n)=C(n-k,n).
    Si on fait la somme des possibilites pour  un nombre de sauts pairs, la formule devient sigma [k de 0 à n/2] de C(2k,n-2k) , et je constate que c'est la moitié de la somme des possibilités des sauts pairs et impairs sur plusieurs cas particuliers...

    (Je ne sais pas generer les symboles mathematiques). 
    On doit pouvoir éclairer facilement ma question que je renouvelle ci-après pour n valant respectivement 20,12 et 30 
    La solution par Fibonacci est la plus élégante. Mais concernant les combinaisons, j'ai trouvé que l'on peut faire uniquement le cacul pour un nombre pair de bonds et le doubler. Pourquoi ? 5473×2=10946
    1+495+3003+1820+153+1=5473
    C'est vrai également pour un escalier de 12 ou 30 marches, à une unite près lorsque le total des combinaisons est impair.
    Pour 12 marches :
    Total des combinaisons : 233
    Total pour un nombre pair de bonds
    1+70+45+1=117
    117×2=234
    Pour 30 marches :
    Total des combinaisons : 1346269
    Total des combinaisons pour un nombre pair de bonds : 673135
    673135×2=1346270 
    Je suppose que ce doit être une propriété des sommes de combinaisons, mais je n'ai pas trouvé laquelle...

    [Leonardo Fibonacci (1170-1250) prend toujours une majuscule. AD]
  • Modifié (October 2023)
    Frydman Charles Je ne comprends pas bien ces raisonnements.
    Soit $x_n$ le nombre de façons pour la grenouille de monter $n$ marches, c'est-à-dire le nombre de suites d'entiers égaux à $1$ ou $2$, de somme $n$.
    Pour $n=1$, on a : $1=1$ et c'est tout, d'où : $x_1=1$,
    Pour $n=2$, on a : $2=1+1=2$, d'où : d'où : $x_2=2$,
    Pour $n=3$, on a : $3=1+1+1=1+2=2+1$,  d'où : $x_3=3$,
    Donc $x_n=n$, non je blague ;)
    Pour $n=4$, on a : $ 4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2$,  d'où : $x_4=5$,
    Pour $n \ge 3$, les sommes commençant par $1$ sont au nombre de $x_{n-1}$ et les sommes commençant par $2$ sont au nombre de $x_{n-2}$. 
    D'où : $x_{n}=x_{n-1}+x_{n-2}$.
    C'est la même récurrence que celle qui régit la suite de Fibonacci définie par $F_0=0$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$ pour $n \ge 2$.
    Comme $x_1=F_2$ et que $x_2=F_3$, on a : $x_n=F_{n+1}$ pour tout $n \in \mathbb N^*$, et là je ne blague plus ;) .
    Sur la suite de Fibonacci, on peut consulter : https://oeis.org/A000045
    La formule de Binet donne : $F_{n}=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n})$ d'où $F_n \simeq \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{n}$ quand $n$ est un peu grand, pour ainsi dire.
    Par exemple : $x_{30}=F_{31}\simeq \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{31}\simeq1,3463\times 10^{6}$.
    Je joins un tableau des valeurs de $x_n$, que je n'ai pas su mettre en personne sur le forum.
    J'aborderai tantôt l'autre approche de ce problème. Mais les deux me semblent bien expliquées dans Le Petit Archimède vers lequel j'ai donné un lien.
    Bonne après-midi.
    Fr. Ch.
  • Modifié (October 2023)
    Tout a fait d'accord pour la suite de Fibonacci. En prenant le problème avec les combinaisons, on trouve le même résultat, mais c'est plus compliqué ! Pour résumer ma question, pourquoi si on fait le total des possibilités si le nombre de sauts est pair, on trouve la moitié du total des possibilités ? (à  une unité près si le total est impair,  sur plusieurs cas particuliers).
  • Modifié (October 2023)
    J'ai expliqué ceci dans Le Petit Archimède au temps jadis, et  j'ai donné le lien vers cette explication dans un précédent message, mais peut-être était-elle un peu trop succincte. 
    On doit déterminer le nombre $x_n$ des suites de $1$ et $2$ de somme $n$. Soit $k$ le nombre de termes égaux à $2$, d'où  $0 \le k \le \left\lfloor \frac{n}{2}\right\rfloor$. Si $j$ est le nombre de termes égaux à $1$, on a : $2k+j=n$, d'où $j=n-2k$,  et le nombre de termes de la somme est : $k+j=n-k$. 
    Le nombre de suites de $1$ et de $2$ de $n-k$ termes, avec $k$ fois $2$ et $n-2k$ fois $1$ est $\displaystyle \binom{n-k}{k}$. 
    Le nombre total de ces suites est donc : $\displaystyle x_n=\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\binom{n-k}{k}$.
    En relation avec mon précédent message, nous avons ici une démonstration combinatoire de l'égalité : $\displaystyle \sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\binom{n-k}{k}=F_{n+1}$.
    J'ai indiqué plus haut que cette égalité se démontre aussi sans mal par récurrence, indépendamment de toute interprétation combinatoire, surtout si on l'écrit : $\displaystyle \sum_{k=0}^{n }\binom{n-k}{k}=F_{n+1}$. Il y a bien longtemps que le $0$ a été inventé, alors autant s'en servir  ;).
    Bonne soirée.
    Fr. Ch.
  • Merci
    Bonne soirée 
    Ch. Fr.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!