dénombrement bizarre

[invite15285302]

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

[invite06b993d0]

annulé........................ ..............

[invite91724928]

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.

[thepasboss]

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 exactement faç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 ^^

[A voir en vidéo sur Futura]

[Médiat]

Bonjour,

Je pense que c'est un peu plus compliqué.

Si j'ai bien compris votre formule, on devrait avoir , or (facile) donc devrait être égal à 20, or .

Je suis en train de rédiger, pour l'instant, je trouve : 0, 2, 30, 864, 39 480

[Médiat]

Je pourrais donner des explications à la demande, mais voilà les résultats :
Soit = Nombre d'accrochages de paires de chaussettes avec paires réunies.
, et
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.

[invite06b993d0]

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.

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.

[invite91724928]

Pour le cas de trois paires, j'ai trouvé ce qui est identique avec les résultats de Médiat, et pour bien mettre en évidence ces cas, voici toutes les possibilités :
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

[thepasboss]

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.

effectivement.

la correction prenant en compte ce que je n'avais pas remarqué a été fait par médiat.

[Médiat]

Mais j'ai pas bien compris votre formule Médiat si vous pouvez nous fournir quelques explications svp

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

[zoonel]

ce qui est conforme à la suite A114938 de l'OEIS.

D’après l’OEIS on a la formule suivante:


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