Forum de mathématiques - Bibm@th.net

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Dénombrement : ensembles sans paires d'entiers consécutifs, par Alicia

Re-bonjour,

  Bon, j'ai merdé quelque part, la conversation initiale n'est plus accessible, je la reprend.
Alicia nous demandait :

Au loto on tire 6 numéros dans [|1...49|]. Combien de tirages ne contiennent aucune paire d'entiers consécutifs?

A la demande de Freddy, Chalec nous précisait un peu 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 lui ai alors répondu :

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

Puis Alicia proposait une réponse avec notamment

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

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

Freddy lui faisait remarquer que c'était impossible, puisque c'est plus que le nombre total de grilles du loto.

Revan intervenait alors (décidément, il y a du monde intéressé par cet exo!)

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?

Je reprends donc le fil de mes explications.

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 [tex]F_n^p[/tex], 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.

Chalec

Membre

Inscription : 14-12-2009

Messages : 2

Re : Dénombrement : ensembles sans paires d'entiers consécutifs, par Alicia

Merci beaucoup pour votre aide, cela m'a été très utile!
Bonne continuation

alicia_010

Membre

Inscription : 13-12-2009

Messages : 7

Re : Dénombrement : ensembles sans paires d'entiers consécutifs, par Alicia

Merci beaucoup également! Vous aviez tout à fait raison pour Kpn...
C'est vraiment gentil de votre part.