Problème de Chaussettes

[ansset]

c'est ça, je pense:
formule valide uniquement si tous les cas existent dont (n-1,p-1) , (n-1,p+2)..
idiot, je suis.
-----

[Médiat]

Bonjour mike.p

En tentant de comprendre pourquoi la formule de la somme ( donc du nombre de tous le arrangements distincts quel que soit le nombre de paires contigues ) ne fonctionnait pas pour 2 et 3 non plus, je suis tombé sur une curieuse symétrie cyclique ( abcdabcd ).

 Cliquez pour afficher

C'est la bonne piste

[Médiat]

c'est ça, je pense:
formule valide uniquement si tous les cas existent dont (n-1,p-1) , (n-1,p+2)..
idiot, je suis.

 Cliquez pour afficher

C'est un bon début...

[ansset]

j'ai une idée de conjecture, mais il me faudrait le E(4,0) pour confirmer ou infirmer.
( pas de programmation possible chez moi )

[Médiat]

j'ai une idée de conjecture, mais il me faudrait le e(4,0) pour confirmer ou infirmer.
( pas de programmation possible chez moi )

 Cliquez pour afficher

e(4,0) = 96

[ansset]

@Mediat:
je sèche. ( même s'il n'a n'y a pas eu de pluie )
je ne retrouve pas les E(n,0) par le raisonnement, même si j'entrevois un truc avec les cycles ( symétries )
j'en viens aussi à douter de mon sigma(E(n;k)).
j'accepte avec miséricorde un indice substantiel ( evt par MP si Mike ne veut pas être tenté d'ouvrir un SPOLIER )
Cdt

ps : attend quand même 1H. au cas ou.......

[ansset]

bon, je jette les armes , le vase de Soisson, l'eau du bain ( sans le bébé ),.....
je trouve 108 pour E(4,0) sans pouvoir calculer les redondances probablement.

ps: depuis le début on considère implicitement que l'on tourne sur le cercle dans un seul sens, n'est ce pas. ( détail )

[mike.p]

je ne suis pas loin mais soit le calcul de E(n) est faux , soit le calcul de E(n,0), soit les 2

2 : 1, 0, 1, ( 1 , tot=2 et 2 )
3 : 5, 6, 3, 2, ( 2 , tot=16 et 16 )
4 : 96, 120, 63, 24, 6, ( 6 , tot=309 et 318 )
5 : 3435, 3930, 2163, 738, 180, 24, ( 24 , tot=10470 et 11352 )
6 : 185628, 201492, 110169, 37656, 8886, 1440, 120, ( 120 , tot=545391 et 623760 )
7 : 14124555, 14838714, 8009343, 2741250, 652056, 110688, 12600, 720, ( 720 , tot=40489926 et 48648960 )
8 : 1443435606, 1482561792, 790593903, 270359496, 64972974, 11391408, 1442232, 120960, 5040, ( 5040 , tot=4064883411 et 5108105520 )
9 : 191018519559, 192936991266, 101815345719, 34754613354, 8419312308, 1511507448, 202951800, 19784880, 1270080, 40320, ( 40320 , tot=530680336734 et 694702028160 )

je ne craque pas et ne demande pas d'indication supplémentaire

courage Anset ( pour tout )

[mike.p]

mais ce n'est pas une proposition, ça correspond surement à peu de corrections mais la table qui résulte d'une itération est fausse ... ( j'en ai déjà une moins fausse )

[Médiat]

bon, je jette les armes , le vase de Soisson, l'eau du bain ( sans le bébé ),.....
je trouve 108 pour E(4,0) sans pouvoir calculer les redondances probablement.

 Cliquez pour afficher

Apportez une attention particulière aux configurations périodiques ...

ps: depuis le début on considère implicitement que l'on tourne sur le cercle dans un seul sens, n'est ce pas. ( détail )

Oui, c'est bien cela

[Médiat]

@mike.p :

 Cliquez pour afficher

4 : 96, 120, 63, 24, 6, : OK

les suivants sont faux , mais votre calcule du total est correct

[mike.p]

@mike.p :

 Cliquez pour afficher

4 : 96, 120, 63, 24, 6, : OK

les suivants sont faux , mais votre calcule du total est correct

mais comment le total peut il être correct alors qu'il n'est pas juste sur cette ligne ?
ne serait ce pas plutot

 Cliquez pour afficher

96, 126, 66, 24, 6, ( 6 , tot=318 et 318 )

Je n'ai trouvé d'exclusion possible que dans le cas où p=0 ou bien lorsque le total est calculé par dénombrement direct.

ou alors si c'est celle que vous avez relevée qui est juste : total qui suit "tot=" est la somme des valeurs trouvées, le total calculé est la valeur suivante. Le calcul du total avec mes invisibles du début est très similaire finalement...

Pas grave, c'était globalement faux.


allez, encore un peu et j'y serai ... Il y a des valeurs particulières qui permettent de décortiquer le calcul

[Médiat]

mike.p

 Cliquez pour afficher

96, 126, 66, 24, 6, : KO
96, 120, 63, 24, 6 KO (désolé, j'avais lu trop vite)
tot = 318 : OK

[mike.p]

mike.p

 Cliquez pour afficher

96, 126, 66, 24, 6, : KO
96, 120, 63, 24, 6 KO (désolé, j'avais lu trop vite)
tot = 318 : OK

merci ! les totaux sont un bon point de vérif

[ansset]

EP !
j'ai trouvé E(4,0) et les redondances avec les circularités.
me reste à mettre l'ensemble au propre.

[mike.p]

Bonjour,

encore moins de temps en semaine que le we ...

soyez gentil d'utiliser le spoiler si vous avez la solution merci

[ansset]

d'accord Mike.
je trouve

 Cliquez pour afficher

On cherche E(n+1,0) et on connait E(n,0),E(n,1),E(n,2)

Depuis E(n,0)
c'est là que les cycles interviennent et j'entend par cycle une double itération telle que
ABAB, ABCABC ( il en a 2 pour n=3 ), ABCDABCD (6 ),.....
E(n,0) contient (n-1)! solutions de ce type ( combinatoire )
et donc ( E(n,0)-(n-1)!) solutions autres
en rajoutant une paire
chaque cycle engendre n² solution au rang n+1
chaque "non-cycle" : 2n(2n-1)/2 solutions
E1(n+1,0)=n²(n-1)!+(2n(2n-1)/2)(E(n,0)-(n-1)!)

Depuis E(n,1) : on casse la paire et on place "l'orpheline" ailleurs.
E2(n+1,0)=(2n-1)E(n,1)

Depuis E(n,2) : on s'insère dans les deux paires
E3(n+1,0)=E(n,2)

au total :
E(n+1,0)=E1+E2+E3=
n²(n-1)!+(2n(2n-1)/2)(E(n,0)-(n-1)!) +
(2n-1)E(n,1) +
E(n,2)

ainsi
si E(2,p) : 1,0,1
E(3,0)=2²1!+(4*3/2)(1-1)+3*0+1=4+0+0+1=5

E(4,0)=3²(2)!+(6*5/2)(E(3,0)-2)+5E(3,1)+E(3,2)
E(4,0)=18+45+30+3=96

je ne me suis pas attaqué à la détermination de E(n) ( sigma )
Cdt

[Médiat]

Bonjour ansset,



Néanmoins (), pourriez-vous poster Les valeurs que vous trouvez pour E(n, p), pour 0 <= n <= 5, afin que je puisse confirmer définitivement (avec un tableur c'est très facile de les calculer) ...

[ansset]

je vais le faire.
ps : je ne veux pas risquer une rupture ( FS donne des boutons à ma chérie en ce moment et j'ai été prié d'intervenir très peu dorénavant ! ), alors je le fais en "lousdé" ...... chuuuuuttttt !

[ansset]

sous toute réserve ( mon tableur a fumé la moquette ...)
donc calcul à la main...

1: 0,1
2: 1,0,1
3: 5,6,3,2
4: 96,126,66,24,6
5: 3724,3540,2400,624,180,24

à refaire après avoir reinstaller OpenOffice..

[ansset]

en général, quand je calcule à la main, c'est la cata !
je reviendrais après avoir résolu mon pb de tableur.

[Médiat]

Bonsoir ansset

 Cliquez pour afficher

4: 96,126,66,24,6 Désolé : KO (calcul ou formule ?)

[ansset]

oui, oui, à vrai dire j'ai repris une formulation plus haut en ne vérifiant que le 126
de fait pour 4 et 5

 Cliquez pour afficher

4 : 96,126,72,24,6
mais total = 324 ( et pas 318 ) ????
à moins que mon calcul en 0 ne soit pas bon.
je suis dans l'expectative.
avec ces résultats j'ai
5 : 3570,4476,2502,840,270,24 total =11682.
je cherche mon erreur.

[ansset]

donc, en en restant sur 4.
soit le sigma n'est pas celui prévu.
soit ma modélisation en 0 mérite un ajustement ( premier terme probablement )
soit j'ai un bug dans mon tableur.

[Médiat]

Bonjour ansset

 Cliquez pour afficher

soit le sigma n'est pas celui prévu. : le total doit bien être 318
soit ma modélisation en 0 mérite un ajustement ( premier terme probablement ) vos valeurs E(n, 0) sont correctes, y compris pour n=4
soit j'ai un bug dans mon tableur. : Cela ne vient sans doute pas de là

soit ...

[mike.p]

Bonjour,

je n'y suis pas arrivé mais espère ne pas voir la solution pour pouvoir jouer encore un peu ...

Voici où j'en suis

 Cliquez pour afficher

2 : 1, 0, 1, ( tot=2 et 2 )
3 : 5, 6, 3, 2, ( tot=16 et 16 )
4 : 96, 120, 72, 24, 6, ( tot=318 et 318 )
5 : 4194, 4320, 2460, 840, 180, 24, ( tot=12018 et 11352 )
6 : 305850, 243540, 131400, 44400, 9900, 1440, 120, ( tot=736650 et 623760 )
7 : 33123330, 20068920, 10112940, 3376800, 768600, 120960, 12600, 720, ( tot=67584870 et 48648960 )

formule du total :
E(n) = (2n-1) ! / 2^(u-1) + (u-1)! /2 -- ( 1 )
déjà je ne comprends pas que ce ne soit pas
(2n-1) ! / 2^(u-1) - (u-1)! /2 puisque je voyais ce terme comme une exclusion
qui contrairement à la première , ne fonctionne pas pour 2 , 3 , 4. Il n'y a plus de concordance à partir de 5.

E(n,0) = (2n-2-1)*(2n-2-3)*( E(n-1,0) - (n-2)! ) +
( 2(n-1)+ (n-1)*(n-2) + (n-1)! ) * (n-2)/2 + // terme pour l'exclusion pour symétrie demi cyclique
(2n-3)* E(n-1,1) +
E(n-1,2) ;

si p >= 1 , il n'y a pas de reprise des précédents sans paire
E(n,p) = ( 2n-p-1 ) * E(n-1,p-1) +
(p+ (2n-2-p) * (2n-3-p) /2 ) * E(n-1,p) +
(p+1) * ( 2n-2-p-1 )* E(n-1,p+1) +
(p+2) * (p+1) * E(n-1,p+2)/2 ) ;

si p=1 , retirer l'exclusion pour symétrie demi cyclique : "(n-1) * (n-2) !" , soit "( n-1 ) !"

Bon, ce n'est pas une proposition, le montage se montre branlant en ( 1 ) . Il y a surement une erreur de fond répétée.
Mais je la trouverai !

Bonne journée à tous

[Médiat]

Bonjour mike.p

 Cliquez pour afficher

OK : 2 : 1, 0, 1, ( tot=2 et 2 )
OK : 3 : 5, 6, 3, 2, ( tot=16 et 16 )
OK : 4 : 96, 120, 72, 24, 6, ( tot=318 et 318 )
KO : 5 : 4194, 4320, 2460, 840, 180, 24, ( tot=12018 et 11352 )
KO : formule du total : E(n) = (2n-1) ! / 2^(u-1) + (u-1)! /2 -- ( 1 )
Votre formule ne fonctionne pas dès n = 2

E(n,0) =
KO (2n-2-1)*(2n-2-3)*( E(n-1,0) - (n-2)! ) +
KO ( 2(n-1)+ (n-1)*(n-2) + (n-1)! ) * (n-2)/2 + // terme pour l'exclusion pour symétrie demi cyclique
OK : (2n-3)* E(n-1,1) +
OK : E(n-1,2) ;
Ce que vous appelez "symétrie demi cyclique" je l'appelle "périodique"

OK : si p >= 1 , il n'y a pas de reprise des précédents sans paire

E(n,p) =
OK : ( 2n-p-1 ) * E(n-1,p-1) +
OK : (p+ (2n-2-p) * (2n-3-p) /2 ) * E(n-1,p) +
OK : (p+1) * ( 2n-2-p-1 )* E(n-1,p+1) +
OK : (p+2) * (p+1) * E(n-1,p+2)/2 ) ;

[mike.p]

Bonjour Mediat

j'avais mal converti la somme, il manquait des parenthèses.

 Cliquez pour afficher

E(n) = (2n-1) ! / 2^(u-1) + (u-1)! /2 -- ( 1 )

E(n) = ( (2n-1) ! / 2^(u-1) + (u-1)! ) /2

Bon, je ne dois pas assez prendre au sérieux la symétrie périodique.
Ce soir, ( si je ne voyage pas ) je chercherai plus de récurrence ; là, n'en voyant pas, je calcule les exclusions en partant de n-2.

Je construirai aussi un tableau par Monte-Carlo, ce par quoi j'aurai du commencer ...

merci pour cette bonne prise de tête

[Médiat]

@mike.p

 Cliquez pour afficher

E(n) = ( (2n-1) ! / 2^(u-1) + (u-1)! ) /2

C'est ok, sous cette forme, il me paraît naturel de les configuration soit ajoutées avant de diviser par 2

merci pour cette bonne prise de tête

Quand on se pose une question idiote, il n'y a pas de raison de ne pas en faire profiter les autres

[ansset]

@Médiat:

 Cliquez pour afficher

c'est mon 126 au lieu de 120 !
mais j'ai pourtant appliqué la même formule pour E(n,p) avec p non nul
la seule diff du E(n,1) est qu'il est le seul à faire intervenir le dernier terme ((p+1)(p+2)/2)E(n-1,n+2)
( terme nul pour n=3).
je ne vois pas la boulette, pourtant je suis sur d'être tout proche.

Cdt