Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 17-04-2018 11:40:57

wade
Membre
Inscription : 09-03-2018
Messages : 11

denombrement

Bonjour,pouvez vous m aider a resoudre cet exercice suivanr:
De combien de facons peut on descendre un escalier de 6 marches,sachant que l on peut descendre une,deux ou trois marches a la fois.

Hors ligne

#2 17-04-2018 12:41:57

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 033

Re : denombrement

Bonjour

  Je ne sais pas si c'est la meilleure façon mais je ferai par recurrence  : je compterais d'abord le nombre de façons de descendre un escalier à 1 marche, puis un escalier à deux marches, puis à 3 marches, etc...

F

Hors ligne

#3 18-04-2018 18:50:32

wade
Membre
Inscription : 09-03-2018
Messages : 11

Re : denombrement

Bonjour,en fait j ai essaye de faire par récurrence mais c' est un peu complique pour moi

Dernière modification par wade (18-04-2018 18:51:24)

Hors ligne

#4 18-04-2018 22:32:42

D_john
Invité

Re : denombrement

Bonsoir,

S'il y avait autant de marches qu'à la tour Eiffel, ça vaudrait la peine de chercher une méthode mais ici,
le plus simple pour répondre à cette question me semble l'arborescence :
L'arbre a 21 branches alors c'est pas la mort !
Courage...

#5 19-04-2018 15:30:42

eldou
Membre
Inscription : 27-03-2018
Messages : 18

Re : denombrement

Bonjour,

Si il faut combiner, dans ce cas, si je ne me trompe pas, ce serait :

[tex] _6C_1 +  _6C_2 +  _6C_3 [/tex] ?

Hors ligne

#6 19-04-2018 17:17:16

D_john
Invité

Re : denombrement

Salut eldou,

Je sais bien que parfois, on descend les maches 4 à 4 mais même en comptant ces possibilités (j'obtiens 29) je n'arrive pas au nombre que tu proposes (41). Je pense que wade ne reviendra pas alors je peux donner la bonne réponse : 24 possibilités.
A+

#7 19-04-2018 17:53:17

eldou
Membre
Inscription : 27-03-2018
Messages : 18

Re : denombrement

Bonjour D_john,

Merci pour la correction.
J'ai été trop vite, c'est un tort.

D'ailleurs, ça n' a pas de sens ce que j'ai proposé (combinaisons de marches).

Hors ligne

#8 19-04-2018 22:06:59

eldou
Membre
Inscription : 27-03-2018
Messages : 18

Re : denombrement

A vrai dire, j'apprends ...

En "googlant"; cet exercice de marche est lié à la suite de Fibonacci ?

Hors ligne

#9 19-04-2018 23:04:22

D_john
Invité

Re : denombrement

J’ai l’impression que les arbres ça ne te branche pas... c'est pourtant très simple.
Il s’agit de représenter graphiquement toutes les possibilités de descendre ces 6 marches par un arbre (à l’envers !).
On part de la marche n°6 (sur la première ligne).
Il y a 3 possibilités de descendre (sur la deuxième ligne) :
- soit 1 marche et on se retrouve sur la marche n°5 ;
- soit 2 marches et on se retrouve sur la marche n°4 ;
- soit 3 marches et on se retrouve sur la marche n°3 ;
On part de la marche n°5. Il y a 3 possibilités de descendre :
- soit 1 marche et on se retrouve sur la marche n°4 ;
- soit 2 marches et on se retrouve sur la marche n°3 ;
- soit 3 marches et on se retrouve sur la marche n°2 ;
etc. (et merci le copier coller !).
Quand on arrive à 0, la branche est terminée.
Quand toutes les branches sont à 0, il reste à les compter.
A toi de jouer... je te laisse terminer l’arbre.

                    6
                /        |       \
              5        4          3
               / | \     / | \      /    | \
             4     3  2  3 2  1   2  1  0 (fin)
           / | \
         3  2  1

#10 20-04-2018 07:51:55

Ostap Bender
Membre
Inscription : 23-12-2015
Messages : 242

Re : denombrement

Un programme python de débutant pour résoudre le problème et valider la solution 24.


def S(n):
      if n<1:
           return 0
      elif n==1:
           return 1
      elif n==2:
           return 2
      elif n==3:
           return 4
      else:
           return S(n-1)+S(n-2)+S(n-3)

print (S(6))
 

Ostap Bender

Hors ligne

#11 20-04-2018 09:47:00

eldou
Membre
Inscription : 27-03-2018
Messages : 18

Re : denombrement

Bonjour D_john,

En effet, je ne suis pas branché :-)

C'est à dire que le livre avec lequel j'apprends (Mathématiques de base, série Schaum) ne reprend pas le dénombrement par arbre. (Uniquement une brève théorie, avec théorèmes et exemples, ainsi que des exercices à résoudre).

Disons que j'étais en train de m'exercer avec les quelques exercices proposés sur ce lien, et que je suis tombé sur ce poste intitulé "dénombrement" (sous discussions des forums).

Dernière modification par eldou (20-04-2018 10:26:33)

Hors ligne

#12 22-04-2018 08:49:33

eldou
Membre
Inscription : 27-03-2018
Messages : 18

Re : denombrement

Ostap Bender a écrit :

Un programme python de débutant pour résoudre le problème et valider la solution 24.


def S(n):
      if n<1:
           return 0
      elif n==1:
           return 1
      elif n==2:
           return 2
      elif n==3:
           return 4
      else:
           return S(n-1)+S(n-2)+S(n-3)

print (S(6))
 

Ostap Bender

Je me suis trituré la tête, mais pas en vain. Pour la compréhension, le programme d'Ostap Bender se déroule de cette façon ?

1) La variable n=6 parcourt la fonction : n'étant pas inférieure à 1, ni égale à 1, 2 ou 3, elle s'appelle de nouveau avec n-1, donc n=5.
2) L'histoire se répète pour n =5 et n = 4
3) Arrivée à n=3 : la fonction retourne 4, et revient à la précédente n=4
4) S'étant arrêtée à n-1, elle continue en n-2, soit n=4-2, et retourne 2. Elle continue en n-3, soit n=4-3, et retourne 1.
5) Et ainsi de suite .. J'ai schématisé le déroulement ci-dessous (en jaune, les valeurs retournées

Dénombrement

Dernière modification par eldou (22-04-2018 09:58:24)

Hors ligne

#13 23-04-2018 14:10:31

Ostap Bender
Membre
Inscription : 23-12-2015
Messages : 242

Re : denombrement

Bonjour Elidou.

Le programme dit simplement que situ es sur la marche [tex]n\geq 4[/tex], tu n'as que trois possibilités qui s'excluent les unes les autres.
Tu descends d'une marche et il te reste S(n-1) possibilités.
Tu descends de deux marches et il te reste S(n-2) possibilités.
Tu descends de troismarches et il te reste S(n-3) possibilités.

Tu additionnes le tout, ça te donne S(n) possibilités.

Si tu développes en série entière [tex]S(x) = \dfrac 1{1-x-x^2-x^3} - 1[/tex] au voisinage de zéro, tu verras apparaître tes coefficients. Vois-tu pourquoi ?
Tu peux ensuite décomposer ta fraction en éléments simples pour avoir une expression fermée pour ces nombres. Moi je n'en ai pas le courage, rien de résoudre l'équation du troisième degré...

Ostap Bender

Hors ligne

#14 23-04-2018 16:51:55

eldou
Membre
Inscription : 27-03-2018
Messages : 18

Re : denombrement

Salut Ostap Blender,

Honnêtement, je ne suis pas si loin en math. Quésako, série entière ? Donc, non, je ne vois pas. Désolé et merci, en même temps. J'ai simplement compris le déroulement récursif du programme, c'est déjà cela de pris. Grâce aux exercices proposés sur geeksforgeeks.

Dans mon bouquin, en reprenant l'index, je lis séries entières, page 172  ;-). Je ne suis qu'à la fin du chapitre des probabilités, page 137.
Donc, j'y approche...

Pour mon apprentissage, je n'ai pas de contraintes de temps (contrairement à un étudiant), je fais cela récréativement. C'est ce qui rend plus agréable.

Hors ligne

#15 24-04-2018 14:09:36

Ostap Bender
Membre
Inscription : 23-12-2015
Messages : 242

Re : denombrement

Bonjour Eldou.

Une autre approche est de considérer que la suite [tex]S(n)[/tex] vérifie une récurrence lnéaire
[tex]S(n)-S(n-1)-S(n-2)-S(n-3)=0[/tex].
Soit [tex]a[/tex] la racine réelle de l'équation [tex]x^3-x^2-x-1=0 [/tex], [tex]b[/tex] etb[tex]\overline b[/tex] les racines irréelles de cette équation,
Les solutions (réelles) de cette récurrence linéaire sont les suites [tex](u_n)[/tex] définies par
[tex]u_n=Aa^n+Bb^n+\overline B (\overline b)^n[/tex] où [tex]A[/tex] et [tex]B[/tex] sont déterminées par les conditions initiales
[tex]\left\lbrace \begin{array}{rcccccl}
Aa&+&Bb&+&\overline B \overline b&=&1\\
Aa^2&+&Bb^2&+&\overline B (\overline b)^2&=&2\\
Aa^3&+&Bb^3&+&\overline B (\overline b)^3&=&4
\end{array}\right.
[/tex]

Ostap Bender

Hors ligne

#16 25-04-2018 15:10:09

wade
Membre
Inscription : 09-03-2018
Messages : 11

Re : denombrement

mercie !

Hors ligne

#17 20-06-2018 09:17:33

Black Jack
Membre
Inscription : 15-12-2017
Messages : 470

Re : denombrement

Salut,

Avec d'aussi petits nombres, même sans maîtriser le sujet, on peut arriver à tout lister.
Ce n'est pas une "bonne" méthode, mais cela doit permettre de vérifier si on ne s'est pas planté en réfléchissant par les méthodes probablement attendues (combinaisons et autres)

1 1 1 1 1 1 --> 1 possibilité.
1 1 1 1 2 --> 5 possibilités. (qui sont : 11112, 11121, 11211,12111,21111)
1 1 2 2 --> 6 possibilités. (qui sont : 1122,1212,1221,2211,2121,2112)
2 2 2 --> 1 possibilités.
1 2 3 --> 6 possibilités. (qui sont : ...)
3 3 --> 1 possibilités.
1 1 1 3 --> 4 possibilités. (qui sont : ...)

Total = 1 + 5 + 6 + 1 + 6 + 1 + 4 = 24 possibilités.

Hors ligne

#18 20-06-2018 15:09:12

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : denombrement

Salut,

non, non, c'est très bien comme ça, c'est astucieux et  je ne pense pas qu'on cherche à faire faire des calculs plus sioux.
Je pense qu'on cherche plutôt à tester le bon sens propre au bon matheux !


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

Pied de page des forums