Problème de Chaussettes

[mike.p]

merci

je vérifierai que ce n'est pas ( 2n-1)! / ( 2 ^(n-1) ) au titre de la circularité de la propriété Madame , Monsieur , le bit de la 1re couleur ayant déjà été imposé par la détermination arbitraire du début du cercle. Bon, c'est laborieux. Mais j'ai bon espoir pour E(n,p) ...
-----

[ansset]

ansset : je suis parti de 0 pour ce problème, ne vous en faites pas une montagne
!

ce n'est pas exactement le mot.
disons que vu le temps que j'espère consacrer à y réfléchir, je cherche des pistes plutôt qu'une/des récurrences "brutales" sur p
par exemple
E(n+1,p) en fct de E(n,p) , ce genre de chose qui pourrait amener des idées.
Cdt

[ansset]

il me semble que
E(n+1,p)=E(n,p)(2n-p)(2n-p-1)
(2n-p) pour la première chaussette ajoutée ( toutes les places sauf entre les paires construites )
(2n-p-1) pour sa jumelle ( qui ne doit pas tomber dans le même "trou initial" ) ( la gauche ou la droite n'important pas ici )
comme on connait
E(p,p)=(p-1)!
je pense qu'on les déduit tous , non ?

[ansset]

E(n+1,p)=E(n,p)(2n-p)(2n-p-1)/2
car sinon on crée 2 configurations identiques.

[Médiat]

C'est une bonne piste, mais vous n'avez pas pris en comptes toutes les possibilités (comme pour mike.p, si vous voulez des indices n'hésitez pas à me solliciter)

[mike.p]

(2n-p) pour la première chaussette ajoutée ( toutes les places sauf entre les paires construites )
(2n-p-1) pour sa jumelle ( qui ne doit pas tomber dans le même "trou initial" ) ( la gauche ou la droite n'important pas ici )

attention, quand tu en ajoutes une à un endroit, il devient possible de placer de part et d'autre du point d'insertion 2 de la même couleur. Je suis passé par le même écueil ( en retirant une paire plutôt que l'ajouter et après avoir défini l'arrangement non circulaire )

[ansset]

je sais que j'ai un petit soucis, car j'ai testé sur n petit.
je continue quand même tout à l'heure dans la voie E(n+1,p)
donc à p constant, ce qui (me) semble plus simple.
Cdt

[ansset]

dans la pratique mon calcul donnait
E(n+1,p)=E(n,p)(2n-p)(2n-p-1)/2
test sur E(3,0)
E(3,0)=E(2,0)4*3/2=1*6=6
sauf qu'à la main je n'ai que 4 solutions ( redondance qcq part )
( même si pas doué avec les truc à la mano, et même fâché en général avec les chiffres )

[ansset]

anway, E(n+1,p) n'est pas simple multiple de E(n,p)
ex: E(2,1)=0 , alors que pour n>2 E(n,1) diff de 0
il doit y avoir un truc sur la circularité mal pris en compte.

[Médiat]

E(3,0)=E(2,0)4*3/2=1*6=6
sauf qu'à la main je n'ai que 4 solutions ( redondance qcq part )

J'en trouve

 Cliquez pour afficher

5

[mike.p]

pour l'instant, j'en suis , à peut être un coef près à :
E(n,p) = ( 2n-p ) E(n-1,p-1) + p x E(n-1,p)

on ajoute une paire pour passer de l'indice n-1 à n et du nombre de paires constituées de p-1 à p.
décomposons le en
- une insertion dans tous les arrangements précédents n'importe où sauf dans une paire déjà constituée : donc ( 2n-p ) E(n-1,p-1)
- et une insertion dans tous les arrangements écartés précédemment qui produisaient une paire de trop, avec le milieu de chaque paire comme point d'insertion possible, soit p x E(n-1,p)

Pour la suite, je verrai demain matin après une vérif de ci-dessus

[Médiat]

Bonjour mike.p,

 Cliquez pour afficher

p x E(n-1,p) : OK
( 2n-p ) E(n-1,p-1) : KO (je ne suis pas d'accord sur le nombre d'intervalles possibles...)

[mike.p]

Bonjour !

j'ai peur de trouver la solution en ouvrant le masque.

[ansset]

je complète ( en plus j'ai fait une erreur de calcul avec mon 6 )
et c'est bien 5 et pas 4 pour E(3,1) : faute de frappe
ajoutons une paire soit donc E(n,p)
cas de figures:
pE(n-1,p) : on recrée une paire en en cassant une. ( p constant )
(2n-p)E(n-1,p-1) : on recrée une paire dans un intervalle.
(1/2)(2n-p)(2n-p-1)E(n-1,p) : on place les deux chaussettes séparément ( C(2n-p;2)), sans toucher aux paires existantes
p(2n-p)E(n-1,p+1) : on détruit une paire sans en recréer une autre.

[Médiat]

j'ai peur de trouver la solution en ouvrant le masque.

Juste un commentaire sur vos réponses

[Médiat]

Bonjour ansset

 Cliquez pour afficher

pE(n-1,p) : on recrée une paire en en cassant une. ( p constant ) : OK
(2n-p)E(n-1,p-1) : on recrée une paire dans un intervalle. :KO (nombre d'intervalles)
(1/2)(2n-p)(2n-p-1)E(n-1,p) : on place les deux chaussettes séparément ( C(2n-p;2)), sans toucher aux paires existantes : KO (nombre d'intervalles)
p(2n-p)E(n-1,p+1) : on détruit une paire sans en recréer une autre. KO (nombre d'intervalles)

Recompter les intervalles devrait être facile, mais vous avez omis quelques cas ...

[ansset]

merci,
retour à ma "signature"

[mike.p]

Juste un commentaire sur vos réponses

merci de la précision !

[ansset]

j'ai certes oublié le fait de casser 2 paires
(1/2)p(p-1)E(n-1,p+2)
pour le nb d'intervalles ( 2n-p) , qcq chose doit m'aveugler...... pour l'instant

[mike.p]

Juste un commentaire sur vos réponses

en effet, c'est le (n,p) d'avant pas celui d'après !

Il y a enfin l'autre récurrence , E(n,0) en fonction de E(n-1,0), qui est hors du domaine d'appli de la 1re. Excellente occasion de voir ce que pourrait vouloir dire E(n,-1) ( je m'égare à peine un petit peu ... )

A tout à l'heure

[Médiat]

@ansset

 Cliquez pour afficher

j'ai certes oublié le fait de casser 2 paires : OK
(1/2)p(p-1)E(n-1,p+2) : KO, mais vous devriez corriger facilement

[Médiat]

Il y a enfin l'autre récurrence , E(n,0) en fonction de E(n-1,0), qui est hors du domaine d'appli de la 1re.

Effectivement ...

Bon courage

[ansset]

je complète ( en plus j'ai fait une erreur de calcul avec mon 6 )
et c'est bien 5 et pas 4 pour E(3,1) : faute de frappe
ajoutons une paire soit donc E(n,p)
cas de figures:
pE(n-1,p) : on recrée une paire en en cassant une. ( p constant )
(2n-p)E(n-1,p-1) : on recrée une paire dans un intervalle.
(1/2)(2n-p)(2n-p-1)E(n-1,p) : on place les deux chaussettes séparément ( C(2n-p;2)), sans toucher aux paires existantes
p(2n-p)E(n-1,p+1) : on détruit une paire sans en recréer une autre.

ok, même erreur que mike, je crois.
nb d'intervalles à des rangs diff.

pE(n-1,p) : on recrée une paire en en cassant une. ( p constant )
(2n-p-1)E(n-1,p-1) on recrée une paire dans un intervalle.
(1/2)(2n-p-2)(2n-p-3)E(n-1,p) : on place les deux chaussettes séparément ( C(2(n-1)-p;2)), sans toucher aux paires existantes
(p+1)(2n-p-3)E(n-1,p+1) : on détruit une paire sans en recréer une autre
(1/2)(p+2)(p+1))E(n-1,p+2) : on détruit deux paires.

[Médiat]

@ansset

 Cliquez pour afficher

OK : pE(n-1,p) : on recrée une paire en en cassant une. ( p constant )
OK : (2n-p-1)E(n-1,p-1) on recrée une paire dans un intervalle.
OK : (1/2)(2n-p-2)(2n-p-3)E(n-1,p) : on place les deux chaussettes séparément ( C(2(n-1)-p;2)), sans toucher aux paires existantes
OK : (p+1)(2n-p-3)E(n-1,p+1) : on détruit une paire sans en recréer une autre
OK : (1/2)(p+2)(p+1))E(n-1,p+2) : on détruit deux paires.

Vous avez résolu la partie la plus facile

[ansset]

je vous hais
Cdt

je suppose que la suite est la résolution complète !?

[Médiat]

je vous hais

Merci, c'était le but

je suppose que la suite est la résolution complète !?

A part pour quelques cas particuliers (E(n ,n), ou E(n)) je ne connais pas de formule fermée, si c'est à cela que vous faites allusion, la réponse est non, l'étape suivante c'est de compléter votre réponse (je n'ose pas en dire plus).

[ansset]

OK,
à tout à l'heure peut être.

[ansset]

A part pour quelques cas particuliers (E(n ,n), ou E(n)) je ne connais pas de formule fermée, si c'est à cela que vous faites allusion, la réponse est non, l'étape suivante c'est de compléter votre réponse (je n'ose pas en dire plus).

sachant que l'on cherché à exprimer E(n,p) en fct des E(n-1,p') p' : {p-1,p,p+1,p+2}
je me demande si on ne peut pas poursuivre en cherchant à exprimer
E(n,p) en fct de E(n',p)
je vais aller dans ce sens, pour voir ..........cher bourreau

[Médiat]

E(n,p) en fct de E(n',p)

Ce n'est pas ce que j'avais en tête (et je ne crois pas à cette piste (n' n'est pas bornée))

[ansset]

effectivement, j'allais écrire ds ce sens avant de sortir.