dénombrement bizarre
Salut à tous. S v p je suis bloqué sur cet exo :
De combien de façons n paires de chaussettes peuvent être suspendue sur un fil à linge de façon que les chaussettes adjacentes proviennent de paires de chaussettes différentes si les paires de chaussettes sont indistinguables et chaque paire est différente.
S v p j'attends votre réponse.
annulé........................ ..............
Salut,
prenons le cas de deux paires par exemple (a,a) et (b,b), cela va donner 2 cas possibles en respectant les conditions de l’énoncé :
a-b-a-b
b-a-b-a
c'est ce que j'ai compris de votre énoncé si c'est correct, veuillez me dire svp.
Bonjour,
en raisonnant de manière récursive, appelons An le nombre d'arrangements de n pairs de chaussettes, n supérieur à deux, vérifiant la condition précédente.
Voyons maintenant comment on peut ajouter une nouvelle pair à un arrangement de n pair. Voyons sur un exemple avec 4 pairs de chaussettes :
...|...|...|...|...|...|...|.. .|...
Chaque barre représente une chaussette de l'arrangement, les trois petits petits représentent les endroits libres où je peux rajouter une chaussette d'une cinquième pair ( il y a 9 emplacement libres).
Pour ajouter la première chaussette, je choisis un espace libre ou la mettre, mettons le quatrième espace libre, nous obtenons :
...|...|...| ... / ... |...|...|...|...|...
Si maintenant je veux ajouter la dernière chaussette de ma cinquième pair, je dois la mettre à la place d'un des pointillé qui n'est pas en gras, sinon j'aurais deux chaussettes de la même pair qui seront côte à côte. On constate alors que pour faire cela, j'ai du au final choisir deux emplacements libres distincts parmi ceux de la configuration de départ avec 4 pairs de chaussettes. Or on a exactementfaçon de faire ce choix ou le truc entre parenthèse est le coef binomial 2 parmis 9.
On a donc
Et de manière générale :
De ça tu peux en déduire le nombre de configurations possible ^^
Bonjour,
Je pense que c'est un peu plus compliqué.
Si j'ai bien compris votre formule, on devrait avoir
Je suis en train de rédiger, pour l'instant, je trouve : 0, 2, 30, 864, 39 480
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Je pourrais donner des explications à la demande, mais voilà les résultats :
Soit
et la formule de récurrence :
et pour
Formules, qui une fois injectées dans un tableur me donne pour A(0, n) :
0, 2, 30, 864, 39480, 2631600, 241133760, 29083420800, 4467125013120, 851371260364800.
ce qui est conforme à la suite A114938 de l'OEIS.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
ce raisonnement ne marche pas, parce que la configuration à n paires n'a pas besoin de vérifier la condition, l'ajout d'une chaussette de la (n+1)ième paire peut séparer deux chaussettes de la même paire qui étaient auparavant contiguës.Envoyé par thepasboss
Pour le cas de trois paires, j'ai trouvé
ab-ac-bc
ab-ca-bc
ab-ca-cb
ab-cb-ac
ab-cb-ca
_____________
ac-ab-cb
ac-ba-bc
ac-ba-cb
ac-bc-ba
ac-bc-ab
_____________
ba-bc-ac
ba-ca-bc
ba-ca-cb
ba-cb-ac
ba-cb-ca
_____________
bc-ab-ac
bc-ab-ca
bc-ab-ca
bc-ac-bc
bc-ca-ba
_____________
ca-ba-bc
ca-ba-cb
ca-bc-ab
ca-bc-ba
ca-cb-ab
_____________
cb-ab-ac
cb-ab-ca
cb-ac-ab
cb-ac-ba
cb-ca-ba
Mais j'ai pas bien compris votre formule Médiat si vous pouvez nous fournir quelques explications svp
effectivement.
la correction prenant en compte ce que je n'avais pas remarqué a été fait par médiat.
Pour mettre en place ce genre de récurrence, il faut construire une solution à partir d'autres en faisant attention à trois points absolument nécessaires
1) liste exhaustive de cas.
2) ne prendre en compte que des cas disjoints.
3) que chaque cas soit calculable à l'aide des données précédentes
Pour calculer A(p, n + 1), on part d'une situation avec n paires, on ajoute une paire, et pour avoir p paires liées, il faut impérativent en avoir déjà au moins p - 1 et au plus p + 2.
Il est facile de voir que cette liste est exhaustive, mais est-elle disjointe ?
Je note a, b, c, d des chaussettes déjà placées et x les nouvelles :
p - 1 paires liées : aa bb cc dd --> aa xx bb cc dd (1 paire liée de plus)
p paires liées : aa bb cc dd --> a xx a bb cc dd (même nombre)
p paires liées : aa bb cc dd --> aa x bb x cc dd (même nombre)
p + 1 paires liées : aa bb cc dd --> aa bxb cc x dd (1 paire liée de moins)
p + 2 paires liées : aa bb cc dd --> axa bb cxc dd (2 paires liées de moins)
Je vous laisse vous convaincre que ces cas sont disjoints.
Les calculs de chacun des cas ci-dessus sont très simples.
Je suis parti des données pour n = 1, on aurait pu partir de n = 0 (A(0, 0) = 1, a(n, 0) = 0) et je pense (je viens de vérifier : c'est bon) que si on définit A(-1, n) = 0, la récurrence doit marcher avec une seule formule et non deux (avec aussi la convention que
Dernière modification par Médiat ; 29/02/2012 à 21h04.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
D’après l’OEIS on a la formule suivante:ce qui est conforme à la suite A114938 de l'OEIS.
une explication sur comment on arrive à cette formule est donnée dans le livre Enumerative Combinatorics de Richard P. Stanley au chapitre 2, exemple 2.2.3 consultable avec google books (lien: http://books.google.be/books?id=EvJg...page&q&f=false)
maintenant il ne me reste plus qu’à comprendre
