Forum de mathématiques - Bibm@th.net

alicia_010

Membre

Inscription : 13-12-2009

Messages : 7

Problème: Dénombrement

Bonjour! Je suis à la dernière question :D de mon exercice et on me demande:
Au loto on tire 6 numéros dans [|1...49|]. Combien de tirages ne contiennent aucune paire d'entiers consécutifs?
Merci d'avance pour votre aide! :)

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Problème: Dénombrement

Salut,

pourrais tu nous donner le sujet complet, il est possible que cette dernière question soit liée aux précédentes ?

A moins que les questions soient toutes indépendantes les unes des autres.

Merci.

Dernière modification par freddy (14-12-2009 19:40:52)

Chalec

Membre

Inscription : 14-12-2009

Messages : 2

Re : Problème: Dénombrement

bonsoir!
Je pense que je fais exactement le même exercice, voila l'énoncé:
  [tex]Soit\;n\in \mathbb{N}\,et\,n\geq 1,\,on\,note\,{F}^{p}_{n}\;l'ensemble\,des\,parties\,de\,\left[|1...n|\right]\,de\,cardinal\,p[/tex] ne contenant aucune paire d'entiers consécutifs. On note [tex]{K}^{p}_{n}\;le\,cardinal\,de\,{F}^{p}_{n}[/tex]

On nous demande ensuite de déterminer K quand p>n, p=n et p=0

Puis on pose  [tex]{a}_{1},{a}_{2}...{a}_{p}[/tex] des entiers écrits dans l'ordre croissant et tels que  [tex]\left\{{a}_{1};...;{a}_{p}\right.\in \,{F}^{p}_{n}\;pour\,k\,\in \,\left[\left|1...p\right|\right]\,on\,pose\,{b}_{k}=\,{a}_{k}+1-k.\;Montrer\,que\,1\leq {b}_{1}<{b}_{2}<...<{b}_{p}\leq n+1-p[/tex]

la troisième question consiste à construire une bijection de  [tex]{F}^{p}_{n}\;dans\;{G}^{p}_{n},\;G\;\acute etan t\;le\;sous-ensemble\;de\;{\left[\left|1...n+1-p\right|\right]}^{p}\;constitu\acute e\;des\,p-uplets\;\left({b}_{1},...,{b}_{p}\right)\;tels\;que\;{b}_{1}<{b}_2<...<{b}_{p}}[/tex]

Il faut ensuite determiner K avant d'arriver a la question d'alicia.

Je bloque moi même a la deuxième question, je ne vois pas comment on peut le montrer, ensuite, je ne comprend pas la puissance que l'on peut observer a la question 3.
Pourriez vous m'aider?
Je vous remercie d'avance

Dernière modification par Chalec (14-12-2009 19:47:23)

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Re : Problème: Dénombrement

Bonsoir,

  Bon, je me colle à la deuxième question alors.
On a [tex]b_{k+1}-b_k\geq a_{k+1}-a_k-1[/tex]
Or, [tex]a_k[/tex] et [tex]a_{k+1}[/tex] ne sont pas des entiers consécutifs.
On a donc [tex]a_{k+1}-a_k\geq 2[/tex] ce qui prouve que [tex]b_{k+1}-b_k\geq 1[/tex]
De plus, on a [tex]b_1=a_1\geq 1[/tex] et [tex]b_{p}=a_p+1-p\leq n+1-p[/tex]

Pour la troisième question, la bijection est donnée par l'énoncé dans la deuxième question. Reste à vérifier que c'est une bijection.

Reste ensuite à calculer le cardinal de [tex]G_n^p[/tex]....

Pour Alicia, si tu as fais tout le reste, ce que tu cherches, c'est [tex]K_{49}^6[/tex]...

Fred.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Problème: Dénombrement

Salut,

ensuite, j'irais jeter un oeil ici : http://www.bibmath.net/dico/index.php3? … ement.html

et là : http://www.bibmath.net/dico/index.php3? … aison.html

après avoir vérifié que les deux ensembles étaient équipotents (http://www.bibmath.net/dico/index.php3? … otent.html)

Bon courage.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Problème: Dénombrement

Je bloque moi même a la deuxième question, je ne vois pas comment on peut le montrer, ensuite, je ne comprend pas la puissance que l'on peut observer a la question 3.
Pourriez vous m'aider?
Je vous remercie d'avance

Salut,

la réponse est dans la question, si je puis dire, ou plutôt dans la définition de G(n,p) car on choisit p fois chaque élément dans l'ensemble des nombre entiers [1, 2, ...,  n+1-p].

Si on note cet ensemble E(n,p), tu es bien d'accord que l'application qui
à chaque {a(1), ., a(k), .., a(p)} de F(n,p)  associe {b(1, .. b(k), ...  b(p)} de E(n,p)xE(n,p) ... E(n,p)  a bien pour ensemble image le produit cartésien de E(n,p) p fois, d'où la notation qui t'intrigue
(cf. http://www.bibmath.net/dico/index.php3? … cart.html)

Dernière modification par freddy (15-12-2009 17:51:52)

alicia_010

Membre

Inscription : 13-12-2009

Messages : 7

Re : Problème: Dénombrement

Bonjour à tous!
Merci pour vos réponses...Je pense ne pas avoir donné assez d'indications, toutes mes excuses. En effet voici l'énoncé:

"Soit n appartenant à N* et p appartenant à N. On note Fpn(p en exposant et n en indice) l'ensemble des parties de [|1...n|] de cardinal p ne contenant aucune paire d'entiers consecutifs. On note Kpn (p en exposant et n en indice) le cardinal de Fpn (p en exposant et n en indice)."

"Combien vaut Kpn (p en exposant et n en indice) si p>n? Combien vaut Knn (n en exposant et n en indice)?
Combien vaut K0n (p en exposant et n en indice)?"

donc j'ai répondu Kpn=0 (impossible)
                  Knn=0
                  K0n=1 ( ensemble vide)

Puis on pose a1 (1 en indice), a2;...;ap des entiers écrits dans l'ordre croissant et tels que {a1;...;ap} appartenant à Fpn (p en exposant et n en indice). Pour k appartenant à [|1..p|] on pose bk (k en indice)=ak ( k en indice) + 1 -k. Montrer que:

1 inf ou égal à b1( 1 en indice)<b2<....<bp inf ou égal à n+1-p.

La troisième question consiste à construire une bijection de
Fpn (p en exposant et n en indice) dans Gpn, G étant un sous ensemble de [|1...n+1-p|]à la puissance p constitué des p-uplets (b1 (1 en indice),...,bp) tels que b1<b2<...<bp.

J'ai trouvé f(x)=x+1-k pour tout k appartenant à [|1...n|]

La quatrième consiste à déterminer Kpn ( p en exposant  et n en indice).

Donc j'ai trouvé Kpn=(n+1-p)^p

Et je trouve pour K =(49+1-6)^6=7256313856

Finalement, j'ai trouvé la réponse à la question posée mais je suis pas vraiment sûr. Ce serait donc gentil de votre part de me donner votre avis :). Mais merci encore pour votre aide...

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Problème: Dénombrement

Salut,

non, du tout. Le nombre total de grilles est égal à 13 983 816.

Tu ne peux donc pas trouver plus de 7 milliards de solutions.

Revan

Invité

Re : Problème: Dénombrement

Bonsoir, Je suis sur le meme exo (bizare, bizare...)

J'ai trouvé Kpn= p parmi (n+1-p) avec l'application numérique sa donne:

K6 49 = 44! / (6!x38!)
         = 7 059 052

En revanche je n'arrive pas a construire une bijection de Fpn vers Gpn.... Et je n'ai pas d'idée
Aurais tu une piste?

Merci d'avance

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Re : Problème: Dénombrement

Bonjour,

  Je reviens un peu dans le débat....
Si vous relisez mon message un peu plus haut, j'ai déjà écrit que la bijection est donnée par l'énoncé.
A un p-uplet [tex](a_1,\dots,a_p)[/tex] de $F_n^p$, où les [tex]a_i[/tex] sont écrits en ordre croissant, on associe
le p-uplet [tex](b_1,\dots,b_p)[/tex] avec [tex]b_k=a_k+1-k[/tex]. La question précédente nous dit qu'on arrive bien dans [tex]G_n^p[/tex], reste à voir qu'il s'agit d'une bijection...

Le cardinal de [tex}G_n^p[/tex] est donc le nombre de partie à p éléments dans un ensemble à n+1-p éléments, c'est bien
[tex]\binom{n+1-p}{p}[/tex]

Fred.