proba : des boules et des paires

[inviteea028771]

pour le premier, je laisse tomber,
même d'essayer de passer de n à n+1 donne une combinatoire digne d'un camion de doliprane

Pourtant c'est simple, on fait des maths, il suffit donc de donner un nom à cette fonction

Notons la probabilité de faire k paires valides avec n boules suivant la procédure décrite plus haut.

Le nombre de façons de n'obtenir aucune paire valide est donc :


L'étude de la fonction est laissée en exercice au lecteur , j'ai bien une démonstration mais elle est trop longue pour tenir dans la marge
-----

[invite51d17075]

Pourtant c'est simple, on fait des maths, il suffit .....
L'étude de la fonction est laissée en exercice au lecteur , j'ai bien une démonstration mais elle est trop longue pour tenir dans la marge

un peu d'humour ça fait pas de mal !

[invite4492c379]

Hello,
j'ai passé un peu de temps sur ce problème ce week-end et je pense avoir un début de solution. Je reformule juste un peu l'énoncé ... L'urne contient 2n boules, on les retire successivement sans remise pour former un n-uple ordonné de n couples ordonnés. Un couple est valide si l'un des deux nombres est le successeur de l'autre. Quelle est la probabilité d'avoir un tirage avec au moins un couple valide ?

La démarche est simple : on commence par chercher tous les couplages parfaits du graphe complet K_2n dont les sommets sont étiquetés 1 à 2n. On obtient tous les ensembles de paires possibles. À chaque ensemble correspondent 2ⁿn! tirages possibles du problème original. Chercher le nombre de couplage parfait dans K2n privé des arêtes du chemin (1,2,3,4,...,2n) permet de trouver tous les ensemble de paires telles qu'aucune paire ne contenienne d'entiers consécutifs.
Je note par le nombre de couplages parfaits du graphe K_2n privé de des arêtes du chemin (1,...k), si k>1, du graphe K_2n si k=0,1. J'obtiens un relation simple :


Seuls les nous intéressent ici, le nombre de tirages ne comportant aucun couple valide.

Une recherche sur internet m'a permi de trouver une expression pour et une limite à
Plus le nombre de boules augmente, plus la probabilité d'avoir un tirage avec au moins un couple valide se rapprochera de .

Remarque: On obtient le même dénombrement dans la recherche du nombre de possibilités de placer n couples (civils) en ligne sans qu'un époux soit placé à côté de son épouse.

Si ça intéresse quelqu'un je peux formaliser ça un peu mieux et le poster.

[invite4492c379]

Précision :

[zyket]

Je me doutais bien que le problème que je m'étais posé était au dessus de mes possibilités.

En tout cas bravo et merci !!

[invite4492c379]

Hello,

cela ne signifie pas qu'il existe une démonstration plus courte tenant dans un marge

[invite51d17075]

salut photon
je ne comprend pas ça :
"Je note par le nombre de couplages parfaits du graphe K2n privé de des arêtes du chemin (1,...k),"
et donc pas la formule:

phi(n;k)=phi(n;k-1)-phi(n-1,k-2)

je crois que c'est la mot "arêtes" qui me trouble ! sorry

[inviteea028771]

Bien vu photon57

Je suis rassuré que la limite théorique de wn soit la même que celle trouvée par simulation

[invite4492c379]

Alors, une image vaut mieux que mille mots ...

Le graphe complet avec ses sommets étiquetés de 1 à 2n (avec ici n=4, K₈):
00-K2n.png et le même graphe privé des arêtes {{1,2},{2,3},{3,4},{4,5},{5,6}, {6,7},{7,8}} :ZZ-K2n.png

Sur le dessin suivant j'ai représenté en bleu un couplage parfait du dernier graphe K₈ \ (1,2,3,4,5,6,7,8)
ZZ-K2n-Coup.pngil s'agit du couplage {{1,8},{2,7},{3,5},{4,6}}. À partir de ce couplage on peut générer les tirages :
((1,8),(2,7),(3,5),(4,6)) x 4! permutations x 2⁴ (chaque couple pouvant apparaître croissant ou décroissant).

Ici le nombre de couplage parfait est égale à = le nombre de couplages parfaits pour le graphe K_8=2.4 privé des arêtes du chemin (1,..,8).

Pour le graphe suivant 0100-K2n.pngK8 privé des arêtes du chemin (1,2,3) je note son nombre de couplages parfaits .

[invite51d17075]

merci photon,
c'était le mot arète que j'avais du mal à interpreter
super demo , en tout cas