Dénombrement

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
digardel
Membre Naturel
Messages: 84
Enregistré le: 26 Aoû 2008, 17:36

dénombrement

par digardel » 29 Sep 2008, 11:31

Enoncé.
Compter le nombre de p-uplets d entiers naturels dont la somme est N.

Ma réponse
Il s agit de placer p-1 signe + dans la liste (1 1 1 1 ......1) (N nombres) on obtient un N+p-1 uplet (u1............u N+p-1) ou ui= 1 ou +
Ce N+p-1 uplet est mis en bijection avec le p uplet (a1.......ap) où ai est la taille du "paquet de 1".
Par exemple 0+3+4+1 est représenté par (+,1,1,1,+ ,1,1,1,1,+,1)
le résultat est donc C(n+p-1, p-1)
Je pense que c est juste mais l exercice est noté comme difficile est ma solution me parait bien simple et comme en dénombrement ,on peut étre persuadé qu une réponse est juste alors qu elle est totalement fausse,je préfère avoir une confirmation



digardel
Membre Naturel
Messages: 84
Enregistré le: 26 Aoû 2008, 17:36

par digardel » 29 Sep 2008, 17:40

suite de l exo
En déduire le nombre de façons dont on peut marquer p sommets d un polygone régulier a n sommets sans que 2 côtés consécutifs soient marqués.La je sèche

Mon idée de départ
Un marquage est un p uplet( x1………..xp) tel que x1>ou = 1
x2 >ou =x 1 +2
x3 >ou =x 2 +2
xp >ou =xp- 1 +2

Je pose a1 = x1-1 a2=x2-x1-2 ………….ap=xp-xp-1-2 et j obtiens une p liste d entiers dont la somme est x1+xp-2p+3 et ………. ?????????????
doit falloir introduire un autre terme a ma suite qui indique la place du n ieme sommet marqué mais je vois pas.Ceci dit çà a pas l air d interrésser bcp de monde

Maxmau
Membre Irrationnel
Messages: 1149
Enregistré le: 19 Mar 2008, 12:11

par Maxmau » 29 Sep 2008, 18:00

digardel a écrit:Enoncé.
Compter le nombre de p-uplets d entiers naturels dont la somme est N.

Ma réponse
Il s agit de placer p-1 signe + dans la liste (1 1 1 1 ......1) (N nombres) on obtient un N+p-1 uplet (u1............u N+p-1) ou ui= 1 ou +
Ce N+p-1 uplet est mis en bijection avec le p uplet (a1.......ap) où ai est la taille du "paquet de 1".
Par exemple 0+3+4+1 est représenté par (+,1,1,1,+ ,1,1,1,1,+,1)
le résultat est donc C(n+p-1, p-1)
Je pense que c est juste mais l exercice est noté comme difficile est ma solution me parait bien simple et comme en dénombrement ,on peut étre persuadé qu une réponse est juste alors qu elle est totalement fausse,je préfère avoir une confirmation


Bj
Voilà une autre solution qui confirme

Je note ;)(p,N) le nombre de p-uplets
;)(1,N) =1 et ;)(p,0)=1
La dernière coordonnée du p-uplet peut prendre les valeurs 0 ,1 , 2 , …………, N.
D’où :
;)(p,N) = ;)(p-1,N) + ;)(p-1,N-1) + ;)(p-1,N-2) + …….+ ;)(p-1,0) ( I )
On fait le tableau suivant
Ligne 1 : ;)(1,0) ;)(1,1) ;)(1,2) ……………. ;)(1,N)………..
Ligne 2 : ;)(2,0) ;)(2,1) ;)(2,2) ……………. ;)(2,N)………..
..etc..
;)(p,N) est à l’intersection de la ligne p et de la colonne N+1
D’après ( I ) chaque terme du tableau précédent est la somme du terme juste au-dessus et du terme juste à gauche.
Le tableau précédent n’est autre que le triangle Pascal ( modulo une rotation de pi/4)
Il est facile d’en déduire que ;)(p,N) = « N parmi p+N-1 » = « p-1 parmi p+N-1 »

digardel
Membre Naturel
Messages: 84
Enregistré le: 26 Aoû 2008, 17:36

par digardel » 29 Sep 2008, 18:27

ok super comme solution .J arrivais pas à voir le triangle de pascal.Merci mais bon j étais sur de mon résultat car j avais testé sur 7 ou 8 cas et j avais tj le bon résultat.Si t as une idée pour la suite de l exo je suis preneur

Albizzia
Messages: 8
Enregistré le: 29 Sep 2008, 18:27

par Albizzia » 29 Sep 2008, 18:37

Pour revenir à la première méthode, je ne comprend pas le résultat.
J'aurais dis la chose suivante:

J'ai donc une liste 1 1 1 1 ... 1, avec N fois 1.
Je veux placer p-1 signes + dans cette liste: j'ai N-1 emplacements pour les +.
Il y a donc ( p-1 parmi N-1) façons de placer les (p-1) + dans la liste.
Soit (p-1 parmi N-1) p-uplets dont la somme vaut N.

Quelqu'un peut-il m'expliquer mon erreur?

digardel
Membre Naturel
Messages: 84
Enregistré le: 26 Aoû 2008, 17:36

par digardel » 29 Sep 2008, 22:51

la somme estcomposée des 1 etdes signes +. . Si tu choisis p-1 éléménts (que tu décudes d appeler + )dans un ensemble de n-1 élements ,le nombre d éléments restants est n-p

Maxmau
Membre Irrationnel
Messages: 1149
Enregistré le: 19 Mar 2008, 12:11

par Maxmau » 30 Sep 2008, 10:57

digardel a écrit:suite de l exo
En déduire le nombre de façons dont on peut marquer p sommets d un polygone régulier a n sommets sans que 2 côtés consécutifs soient marqués.La je sèche

Mon idée de départ
Un marquage est un p uplet( x1………..xp) tel que x1>ou = 1
x2 >ou =x 1 +2
x3 >ou =x 2 +2
xp >ou =xp- 1 +2

Je pose a1 = x1-1 a2=x2-x1-2 ………….ap=xp-xp-1-2 et j obtiens une p liste d entiers dont la somme est x1+xp-2p+3 et ………. ?????????????
doit falloir introduire un autre terme a ma suite qui indique la place du n ieme sommet marqué mais je vois pas.Ceci dit çà a pas l air d interrésser bcp de monde


Bj

En partant d’un sommet et en adoptant le sens trigonométrique, un marquage n’est-il pas une suite d’entiers a1 , a2 , ….., ap tous supérieurs ou égaux à 2 et dont la somme est égale à n ?

digardel
Membre Naturel
Messages: 84
Enregistré le: 26 Aoû 2008, 17:36

par digardel » 30 Sep 2008, 12:43

ok pour la somme d entiers tous supérieurs ou égaux à 2
C est d ailleurs ce que j ai fait.
Mais le premier peut valloir 1
et qd tu a s additionné tous les espaces qu il y a entre chaque sommet tu n as pas fait le tour complet.
En écrivant la réponse je crois que j ai trouvé la solution......Il faut rajouter un p+1 eme nombre qui donne la distance entre le dernier point et n
merci,en fait j aurais du faire un dessin

Maxmau
Membre Irrationnel
Messages: 1149
Enregistré le: 19 Mar 2008, 12:11

par Maxmau » 30 Sep 2008, 13:48

digardel a écrit:ok pour la somme d entiers tous supérieurs ou égaux à 2
C est d ailleurs ce que j ai fait.
Mais le premier peut valloir 1
et qd tu a s additionné tous les espaces qu il y a entre chaque sommet tu n as pas fait le tour complet.
En écrivant la réponse je crois que j ai trouvé la solution......Il faut rajouter un p+1 eme nombre qui donne la distance entre le dernier point et n
merci,en fait j aurais du faire un dessin



Re

Je ne comprends pas bien
Pour moi, a1 est le nombre de côtés « franchis » pour aller du premier sommet au second, a2 le nombre de côtés « franchis » pour aller du second sommet au troisième……………..et finalement ap le nombre de côtés « franchis » pour aller du dernier sommet au premier
Ainsi je fais bien le tour complet

Ou alors je n’ai pas compris le Pb

digardel
Membre Naturel
Messages: 84
Enregistré le: 26 Aoû 2008, 17:36

par digardel » 30 Sep 2008, 15:03

ok comme çà il y a bien une somme de p nombre supérieurs ou egaux à 2 mais il faut préciser le choix du premier sommet ......Sinon on obtiendrait p-1 parmi n-p-1 ce qui est faux ....

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 21 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite