[ Maths ] Dénombrement

[inviteb64a2f8e]

Bonjour à tous,

Voilà j'ai trouvé un exercice (sans son corrigé malheureusement) sur les dénombrements et je ne comprends pas la première partie.

Voilà l'énoncé :

On monte un escalier en franchissant à chaque pas, soit une marche, soit deux marches.

1) Soit n un entier naturel, n>=4. On note p(n) le nombre de façons d'enchainer les pas de une marche et les pas de deux marches pour gravir un escalier de n marches.

(a) Déterminer une relation entre p(n-1) , p(n) et p(n+1)
(b) En déduire p(n) en fonction de n

2) On appelle k le nombre de pas de deux marches que l'on peut faire pour gravir un escalier de n marches/

(a) Quelles sont les valeurs possibles pour k ?
(b) Calculer en fonction de k le nombre total de pas nécessaires
(c) Justifier que la somme de k=0 à E(n/2) de n parmi (n-k) est égal à p(n) (désolé pour l'écriture j'ai DL Latex mais je sais pas comment ça fonctionne)

Voilà en fait je ne comprends pas du tout la 1ère partie. Je trouve la 2ème partie beaucoup plus logique et c'est comme cela que j'aurais fait je pense (je ne suis pas pour autant sûr de savoir répondre aux questions^^)

Je viens de commencer le dénombrement donc je m'y perds avec les combinaisons, permutations, p-listes, etc... mais ça doit être facile pour vous car il parait que c'est un exercice "type"

Je vous serais reconnaissant de m'aider un petit peu ^^

Merci !

ZimbAbwé.
-----

[invitebe0cd90e]

La premiere partie n'est pas si compliquée : l'idée c'est que comme tu progresse au maximum par 2 marches, il va forcement y avoir une relation de recurrence : en effet, gravir n+1 marche peut se decomposer en:
- gravir une marche, puis n
- gravir n marche, puis une
- gravir n-1 marche puis 2
- gravir 2 marches puis une

Tu est forcement dans une de ces configurations ! Donc si tu connais le nombre de moyen de gravir n-1 et n marches, tu peux calculer le nombre de moyen pour n+1 !

[inviteb64a2f8e]

Ah uè ok je vois. Mais ça veut dire qu'il faut que je calcule le nombre de façons de gravir n-1 marches et n marches afin d'avoir la façon de gravir n+1 marches ?

Donc ça m'avance pas énormément, c'est pour ça que je ne comprends pas cette méthode. La difficulté est de calculer p(n), c'est-à-dire le nombre de façons de gravir n marches donc s'il me le faut pour calculer p(n+1) ce n'est pas très intéressant, si ?

Je fais sûrement un erreur de logique...

[invitebe0cd90e]

Euh, non, au contraire ca t'avance bien ! n'oublie pas que n est un nombre quelconque, ce qu'on vient de prouver c'est que pour calculer p(n+1) il suffit de savoir le calculer pour des valeurs plus petites, c'est ce qu'on appelle une relation de recurrence ! on ne te demande pas de calculer quoi que ce soit directement !

L'idee c'est que si tu connais mettons p(1) et p(2) (qui sont faciles a calculer), alors tu connais p(2). Puisque tu connais p(2), tu connais p(3), etc..

[A voir en vidéo sur Futura]

[inviteb64a2f8e]

Ah uè ok donc je calcule des petites valeurs (par exemple p(3) et p(4) car n>=4) et donc je vais trouver une relation que je généralise ensuite c'est ça ?

[inviteb64a2f8e]

En calculant p(n) pour des petites valeurs de n je trouve la conjecture :
p(n) = p(n+1) - p(n-1)

Est-ce qu'il faut que je démontre cette hypothèse par récurrence alors ou est-ce que cela suffit (ça m'étonnerait quand même ^^) ?

Et comment je déduis une expression de p(n) en fonction de n à partir de cette relation ?

[invitebe0cd90e]

Non, tu n'a as compris. Le relation entre p(n+1), p(n) et p(n-1) tu ne dois pas la trouver en calculant de petites valeurs ! tu la trouves a partir de ce que je dit dans mon premier message, ensuite tu utilises cette relation pour trouver une formule "directe" pour p(n).

[inviteb64a2f8e]

D'accord.

Mais alors si j'utilise ce que tu as dit dans ton premier message, j'ai :

p(n+1) = 1 + p(n)
ou p(n+1) = p(n) +1
ou p(n+1) = p(n-1) + 2
ou p(n+1) = 2 + p(n-1)

Ai-je le droit d'additionner toutes ces équations les unes avec les autres car il s'agit de "ou" ?

[Médiat]

Salut jobherzt,

Je ne suis pas d'accord avec ton analyse :
Pour gravir n+1 marches, soit on finit avec un pas de 1 marche (et on était sur la marche n), soit on finit par un pas de 2 marches (et on était sur la marche n-1), ces deux cas étant complets et exclusifs, le nombre de façon d'atteindre la marche n+1 est donc :
p(n+1) = ... (salut ZimbAbwé, tu ne croyais pas que j'allais donner la solution quand même )

[inviteb64a2f8e]

Nan évidemment je ne veux pas qu'on me donne la réponse toute cuite ça ne serait pas drôle

Je voudrais juste une petite piste...

Je dois décomposer p(n+1) en : p(n) + 1 ou p(n-1) + 2 (comme le propose Mediat)

ou en les 4 cas que propose jobherzt ?

Et alors comment faire pour trouver une relation de p(n+1) ? Car je ne peux pas additionner en faisant :
p(n+1) = 1 + p(n) + 2 + p(n-1)

[inviteaf1870ed]

p(n) est le nombre de façons d'enchainer les pas.
Pour arriver à la n-eme marche
-Soit on était à la marche n-1 : combien de façons avait on d'y arriver ?
-Soit on était à la marche n-2 : combien de façons avait on d'y arriver ?
On additionne ces deux nombre et on a le résultat.

Dans ton dernier calcul tu mélanges p(n) qui est un nombre de façons, et 1 ou 2 qui est un nombre de marches...

[Médiat]

Je dois décomposer p(n+1) en : p(n) + 1 ou p(n-1) + 2 (comme le propose Mediat)

Argghh je n'ai jamais proposé cette horreur .

[inviteb64a2f8e]

Oui désolé d'avoir utilisé cette écriture je voulais résumer la proposition de Médiat mais j'ai mélangé les torchons et les serviettes ^^

Ok donc d'après le raisonnement de ericcc on a la relation p(n+1) = p(n) + p(n-1)
Il suffit donc alors de calculer le nombre de façons d'arriver à la (n-1)ième marche et le nombre de façons d'arriver à la nième marche et de les additionner.

Mais je ne comprends pas en quoi il est plus facile de calculer p(n) et p(n-1) pour avoir p(n+1) et donc comment trouver une expression de p(n) en fonction de n

[Médiat]

la relation p(n+1) = p(n) + p(n-1)

C'est une relation de récurrence bien connue (suite de Fibonacci) dont on connait l'expression de p(n) en fonction de n, mais ce n'est pas évident à démontrer quand on ne la connait pas. Est-ce qu'il y avait d'autres parties dans cet exercice, ou faisait-il suite à un autre exercice sur la suite de Fibonacci ?

[inviteb64a2f8e]

Ah ui la suite de Fibonacci me dit quelque chose je pense qu'on en a parlé dans le cours.
Et non, cet exercice ne fait suite à aucun exercice et cette question (relation entre p(n), p(n-1) et p(n+1) puis trouver expression de p(n) en fonction de n) est la première.
La suite de Fibonacci est la seule façon de trouver une expression de p(n) en fonction de n ?

[inviteb64a2f8e]

Si j'essaie d'exprimer p(n) en fonction de n avec la suite de Fibonacci, je peux détermine r1 et r2 (solution de l'équation caractéristique r² = r + 1) mais après je bloque pour déterminer les nombres A et B tels que :

p(n) = A * r1^n + B * r2^n

En effet, dans mon exercice n>=4 donc j'ai un système avec des r1^4 et r2^5
Ca devient alors beaucoup plus difficile de résoudre le système non ?

[Médiat]

Si j'essaie d'exprimer p(n) en fonction de n avec la suite de Fibonacci, je peux détermine r1 et r2 (solution de l'équation caractéristique r² = r + 1) mais après je bloque pour déterminer les nombres A et B tels que :

p(n) = A * r1^n + B * r2^n

En effet, dans mon exercice n>=4 donc j'ai un système avec des r1^4 et r2^5
Ca devient alors beaucoup plus difficile de résoudre le système non ?

A et B sont des constantes.

[inviteb64a2f8e]

Mais on trouve r1 = (1+5^0.5) / 2 (désolé je sais pas comment écrire les racines^^) et r2 = (1-5^0.5) / 2
Mais on va donc avoir des nombres décimaux, ce qui n'est pas possible puisque p(n) doit appartenir à l'ensemble des entiers naturels non ?

[Médiat]

Mais on trouve r1 = (1+5^0.5) / 2 (désolé je sais pas comment écrire les racines^^) et r2 = (1-5^0.5) / 2
Mais on va donc avoir des nombres décimaux, ce qui n'est pas possible puisque p(n) doit appartenir à l'ensemble des entiers naturels non ?

Donc, dans ton calcul des constantes, les radicaux doivent disparaître

[inviteb64a2f8e]

Donc il faut que je résoude le système:

p(4) = A * (1+5^0.5) / 2)^4 + B * (1-5^0.5) / 2)^4
p(5) = A * (1+5^0.5) / 2)^5 + B * (1-5^0.5) / 2)^5

Avec p(4) et p(5) que j'ai calculé et pour lesquels je trouve p(4) = 5 et p(5) = 8

Et donc pour cela je dois faire disparaître les radicaux ? Je ne peux pas utiliser l'identité remarquable (a+b)(a-b) = a² - b²

[Médiat]

Donc il faut que je résoude le système:

p(4) = A * (1+5^0.5) / 2)^4 + B * (1-5^0.5) / 2)^4
p(5) = A * (1+5^0.5) / 2)^5 + B * (1-5^0.5) / 2)^5

Puisque A et B sont des constantes, pourquoi ne pas faire le calcul avec p(1) et p(2) ?

[inviteaf1870ed]

Une manière simple de voir les choses :
si on prend p(0)=1 (un peu tiré par les cheveux, mais on peut dire qu'il n'y a qu'une seule façon de ne pas monter un escalier-même si Cécile Sorel affirme le contraire pour la descente ) et p(1)=1, on trouve exactement la suite de Fibonacci

[inviteb64a2f8e]

J'ai pris p(4) et p(5) parce que dans l'énoncé il est précisé soit n >= 4.

Mais si je prends p(0) = 1 et p(1) = 1, je vais quand même me retrouver avec des racines de 5 dans mon expression de A et de B et donc de p(n) alors que p(n) doit être naturel, non ?

[Médiat]

Mais si je prends p(0) = 1 et p(1) = 1, je vais quand même me retrouver avec des racines de 5 dans mon expression de A et de B et donc de p(n) alors que p(n) doit être naturel, non ?

Ce "donc" n'est pas justifié, et faux ici.

[inviteb64a2f8e]

En résolvant le système, je trouve au final :

p(n) = [(1+rac5)/(2rac5)] * [(1+rac5)/2]^n + [(rac5-1)/(2rac5)] * [(1-rac5)/2]^n

(En posant rac5 = 5^0.5)

Il y a bien des racines de 5 dans mon expression de p(n) non ? A moins que j'ai manqué une simplification ?

[Médiat]

En résolvant le système, je trouve au final :

p(n) = [(1+rac5)/(2rac5)] * [(1+rac5)/2]^n + [(rac5-1)/(2rac5)] * [(1-rac5)/2]^n

(En posant rac5 = 5^0.5)

Il y a bien des racines de 5 dans mon expression de p(n) non ? A moins que j'ai manqué une simplification ?

Je n'ai pas vérifié les calculs, mais en développant les [machins]ⁿ, il me semble bien que les rac(5) disparaissent (ce qui est bon signe pour tes calculs). Tu peux vérifier en calculant quelques exemples.

[inviteb64a2f8e]

En prenant n = 4 , je trouve p(n) dépendant de rac5 :S

Les racines de 5 ne semblent pas se simplifier quand je les mets à la puissance 4 par exemple. J'espère que c'est une erreur de calcul

[Médiat]

En prenant n = 4 , je trouve p(n) dépendant de rac5 :S

Les racines de 5 ne semblent pas se simplifier quand je les mets à la puissance 4 par exemple. J'espère que c'est une erreur de calcul

Avec ta formule je trouve p(4) = 5 ce qui ne contient pas de rac(5) et qui est juste en plus.

[inviteb64a2f8e]

En prenant n = 4 , je trouve p(n) dépendant de rac5 :S

Les racines de 5 ne semblent pas se simplifier quand je les mets à la puissance 4 par exemple. J'espère que c'est une erreur de calcul

[inviteb64a2f8e]

Tu trouves p(4) = 5 avec ma formule ?

C'est une bonne nouvelle, ça signifie que c'est moi qui ait fait une erreur de calcul. Mais [(1+rac5)/2]^4 et [(1-rac5)/2]^4 donnent bien (7+3rac5)/2 et (7-3rac5)/2 non ? Les racines de 5 se simplifient après en multipliant par A et B ?