Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 32

[ Maths ] Dénombrement



  1. #1
    ZimbAbwé

    [ Maths ] Dénombrement


    ------

    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é.

    -----

  2. Publicité
  3. #2
    jobherzt

    Re : [ Maths ] Dénombrement

    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 !

  4. #3
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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...

  5. #4
    jobherzt

    Re : [ Maths ] Dénombrement

    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..

  6. #5
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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 ?

  7. A voir en vidéo sur Futura
  8. #6
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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 ?

  9. Publicité
  10. #7
    jobherzt

    Re : [ Maths ] Dénombrement

    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).

  11. #8
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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" ?

  12. #9
    Médiat

    Re : [ Maths ] Dénombrement

    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 )
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  13. #10
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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)

  14. #11
    ericcc

    Re : [ Maths ] Dénombrement

    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...

  15. #12
    Médiat

    Re : [ Maths ] Dénombrement

    Citation Envoyé par ZimbAbwé Voir le message
    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 .
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  16. Publicité
  17. #13
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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

  18. #14
    Médiat

    Re : [ Maths ] Dénombrement

    Citation Envoyé par ZimbAbwé Voir le message
    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 ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  19. #15
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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 ?

  20. #16
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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 ?

  21. #17
    Médiat

    Re : [ Maths ] Dénombrement

    Citation Envoyé par ZimbAbwé Voir le message
    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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  22. #18
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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 ?

  23. Publicité
  24. #19
    Médiat

    Re : [ Maths ] Dénombrement

    Citation Envoyé par ZimbAbwé Voir le message
    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  25. #20
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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²

  26. #21
    Médiat

    Re : [ Maths ] Dénombrement

    Citation Envoyé par ZimbAbwé Voir le message
    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) ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  27. #22
    ericcc

    Re : [ Maths ] Dénombrement

    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

  28. #23
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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 ?
    Dernière modification par ZimbAbwé ; 17/10/2008 à 12h30.

  29. #24
    Médiat

    Re : [ Maths ] Dénombrement

    Citation Envoyé par ZimbAbwé Voir le message
    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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  30. Publicité
  31. #25
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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 ?

  32. #26
    Médiat

    Re : [ Maths ] Dénombrement

    Citation Envoyé par ZimbAbwé Voir le message
    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]n, 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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  33. #27
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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

  34. #28
    Médiat

    Re : [ Maths ] Dénombrement

    Citation Envoyé par ZimbAbwé Voir le message
    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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  35. #29
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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

  36. #30
    ZimbAbwé

    Re : [ Maths ] Dénombrement

    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 ?

Sur le même thème :

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Dénombrement ....
    Par mimicaro dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 07/05/2008, 20h08
  2. Le dénombrement
    Par ferrarinero dans le forum Mathématiques du supérieur
    Réponses: 12
    Dernier message: 09/03/2008, 22h30
  3. Dénombrement
    Par maseru dans le forum Mathématiques du supérieur
    Réponses: 23
    Dernier message: 02/03/2008, 15h44
  4. dénombrement
    Par Astro boy dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 16/05/2006, 16h07
  5. dénombrement
    Par yonyon dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 11/05/2006, 20h15