Problème de Chaussettes

[ansset]

si je comprend, on cherche un peu tout ce qu'on pourrait dire de cette "thématique", sans chercher à la résoudre.
à part le trivial E(n,n), on a fait
E(n,p) en fct des E(n-1,p')
quoi d'autre ?
je manque d'idées......
-----

[mike.p]

J'en trouve

 Cliquez pour afficher

5

Je cherchais des valeurs numériques et ai ouvert ce spoiler.

pour E(3,0) j'en obtiens 7 :

b+bc+c
b+c+bc
b+cb+c
b+cbc+
bc+b+c
bc+bc+
bcb+c+

1 : 0, 1, ( - )
2 : 1, 0, 1, ( 1 )
3 : 7, 8, 3, 2, ( 2 )
4 : 148, 160, 82, 24, 6, ( 6 )
5 : 5346, 5760, 2910, 900, 180, 24, ( 24 )
6 : 295320, 315840, 159120, 49440, 10320, 1440, 120, ( 120 )
7 : 23124480, 24561600, 12349680, 3864000, 827400, 124320, 12600, 720, ( 720 )
8 : 2435978160, 2572093440, 1291555440, 406647360, 88830000, 13991040, 1582560, 120960, 109619022240, ( 5040 )
9 : 332190336240, 349001049600, 175088284560, 55423962720, 12297761280, 2002916160, 3069574855200, 7015638450240, 18894851020080, 40003430080320, ( 40320 )

entre parenthèses : (n-1) !

J'ai utilisé ceci après avoir initialisé à la main jusqu'à n = 2

E(n,0) = (n-1) (2n-3) E(n-1,0) + (2n-3) E(n-1,1) + E(n-1,2) ;
// prendre le jeu précédent mais aussi ce qui en contenait 1 ou 2 qui sont cassables

et de la même façon :

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

// ici le jeu précédent plus une paire, ceux avec déjà une paire de trop plus rien, ceux en ayant 2 de trop dont on casse une et ceux avec 2 de trop, on en casse 2. On ne peut pas en casser plus de 2 ni en créer plus d'une.

Ca diverge en 8 , donc c'est faux au moins à partir de 7 !
Mais bon, faut trouver un bug certain qui se révèle tard, ça restreint le champ de recherche.
Je m'y mets après un thé

[Médiat]

@mike.p

 Cliquez pour afficher

b+bc+c
b+c+bc = bcb+c+
b+cb+c
b+cbc+ = bc+b+c
bc+bc+

[ansset]

inutile : à reformuler proprement.

[ansset]

voilà,
peut on chercher à "déconstruire" E(n,n) jusqu'à E(n,0) ?

[mike.p]

@mike.p

 Cliquez pour afficher

b+bc+c
b+c+bc = bcb+c+
b+cb+c
b+cbc+ = bc+b+c
bc+bc+

bien vu

[Médiat]

@mike.p

 Cliquez pour afficher

E(n,0) =
(n-1) (2n-3) E(n-1,0) : KO
+ (2n-3) E(n-1,1) : OK
+ E(n-1,2) : OK

OK avec :

 Cliquez pour afficher

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

Il vous reste une "subtilité" à mettre au jour, bon courage et amusez-vous bien (comme je me suis amusé en me posant bêtement cette question )

[ansset]

Il vous reste une "subtilité" à mettre au jour, bon courage et amusez-vous bien (comme je me suis amusé en me posant bêtement cette question )

comme tu reprends ma formulation dans le second spoiler ( que j'ai ouvert ).
je prend donc la remarque suivante : la recherche de la "subtilité" comme piste.
en fait je l'interprète comme ça.
Cdt

[Médiat]

voilà,
peut on chercher à "déconstruire" E(n,n) jusqu'à E(n,0) ?

Qu'appelez-vous déconstruire ?

De mon côté j'ai juste écrit les relations de récurrence qui permettent de calculer E(n, p) (sauf pour E(n) où une formule directe peut être calculée (bien utile pour les contrôles))

[ansset]

mess croisés.
"déconstruire" était de partir d'une situation E(n,n) pour en tirer
E(n,n-1), E(n,n-2),.....
mais votre réponse à mike laisse entendre qu'après l'équation de E(n,p) en fct des E(n-1,p'), on est en recherche d'une "subtilité'.
voir mon post précédent.

[Médiat]

comme tu reprends ma formulation dans le second spoiler ( que j'ai ouvert ).
je prend donc la remarque suivante : la recherche de la "subtilité" comme piste.
en fait je l'interprète comme ça.

EDIT je viens de voir votre dernier post, c'est la bonne direction (celle que j'ai prise en tout cas) ...

[ansset]

laquelle,
la subtilité ou l'approche dégressive que j'ai mentionné ?
désolé d'être incertain sur l'interprétation.
Cdt

[Médiat]

La recherche de la ou des subtilités qui restent ...

[ansset]

d'accord , merci.

[mike.p]

@mike.p

 Cliquez pour afficher

E(n,0) =
(n-1) (2n-3) E(n-1,0) : KO
+ (2n-3) E(n-1,1) : OK
+ E(n-1,2) : OK

OK avec :

 Cliquez pour afficher

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

Il vous reste une "subtilité" à mettre au jour, bon courage et amusez-vous bien (comme je me suis amusé en me posant bêtement cette question )

(n-1) (2n-3) E(n-1,0) : KO
mais plutôt
(n-1) (2n-4) E(n-1,0)

pour l'autre, il manquait un diviseur 2 :
(p+1) (2n-3-p ) E(n-1,p+1) +
par
(p+1) (2n-3-p )/2 E(n-1,p+1) +

mais ça ne colle toujours pas avec le calcul de la somme ou même E(n,n) à partir de n=7. Normalement, si A007060 est juste on devrait avoir un facteur 2^(n-1) avec les E(n,0) ... rien de tel et pas le temps de prendre une autre voie.

1 : 0, 1, ( 1 )
2 : 1, 0, 1, ( 1 )
3 : 5, 8, 3, 2, ( 2 )
4 : 103, 148, 82, 24, 6, ( 6 )
5 : 3590, 5136, 2826, 900, 180, 24, ( 24 )
6 : 192650, 273848, 150984, 48768, 10320, 1440, 120, ( 120 )
7 : 14722312, 20813272, 11487232, 3756432, 821352, 124320, 12600, 720, ( 720 )
8 : 1518733976, 2137323720, 1180594680, 389817120, 87350400, 13930560, 1582560, 120960, 68343033960, ( 5040 )
9 : 203338655792, 285082160336, 157582131120, 52435637040, 11972069760, 1981532160, 1913846518080, 4373975200320, 11610589821840, 28426582437680, ( 40320 )

en enlevant le 4e terme de la récurrence, 8 devient juste. Bon, c'est par là qu'il faut revoir.

Dimanche approchant un peu vite, je reprends dans un petit moment ; il y a peut être un bug informatique dans mon script avec le cache à E(m,q) ...

[mike.p]

oui, il y avait un bug dans mon cache, là j'obtiens


1 : 0, 1, ( 1 )
2 : 1, 0, 1, ( 1 )
3 : 5, 8, 3, 2, ( 2 )
4 : 103, 148, 82, 24, 6, ( 6 )
5 : 3590, 5136, 2826, 900, 180, 24, ( 24 )
6 : 192650, 273848, 150984, 48768, 10320, 1440, 120, ( 120 )
7 : 14722312, 20813272, 11487232, 3756432, 821352, 124320, 12600, 720, ( 720 )
8 : 1518733976, 2137323720, 1180594680, 389817120, 87350400, 13930560, 1582560, 120960, 5040, ( 5040 )
9 : 203338655792, 285082160336, 157582131120, 52435637040, 11972069760, 1981532160, 241708320, 21349440, 1270080, 40320, ( 40320 )
10 : 34284745290880, 47916286877248, 26502852807712, 8874614126400, 2056306398000, 349927483200, 44842386240, 4327223040, 305424000, 14515200, 362880, ( 362880 )

E(n,n) calculé par la récurrence donne bien maintenant (n-1) !
Ca ne garantit pas que c'est juste mais je peux passer à d'autres vérifs maintenant ...

( si c'est bon, comment publier le petit html qui contient le javascript ? on peut le copier sur un disque dur et l'appeler avec le navigateur )

[mike.p]

oui, il y avait un bug dans mon cache, là j'obtiens

j'ai mis à jour la mauvaise version ...

1 : 0, 1, ( 1 )
2 : 1, 0, 1, ( 1 )
3 : 5, 6, 3, 2, ( 2 )
4 : 93, 114, 63, 24, 6, ( 6 )
5 : 3093, 3702, 2085, 738, 180, 24, ( 24 )
6 : 159123, 186798, 104697, 36792, 8886, 1440, 120, ( 120 )
7 : 11706855, 13527510, 7525545, 2638434, 642480, 110688, 12600, 720, ( 720 )
8 : 1166758995, 1330791102, 734983731, 257292192, 63183774, 11280528, 1442232, 120960, 5040, ( 5040 )
9 : 151373857701, 170793649542, 93711653901, 32759655642, 8099510676, 1480844088, 201591000, 19784880, 1270080, 40320, ( 40320 )
10 : 24795039205059, 27721124855214, 15122003134137, 5279024011560, 1311999646710, 243975967248, 34562805264, 3698009280, 286580880, 14515200, 362880, ( 362880 )
11 : 5004930432293823, 5551967387647134, 3013098968215341, 1050404142388506, 262098905239320, 49358646760608, 7188515306208, 812488491936, 70015937760, 4386087360, 179625600, 3628800, ( 3628800 )
12 : 1220689109213446100, 1344986780095481600, 726615428527443700, 252961447196128450, 63312777044873816, 12039460480582128, 1789466015596464, 210093747655680, 19383574479840, 1372789848960, 70890223680, 2395008000, 39916800, ( 39916800 )

désolé

[Médiat]

Bonsoir,

4 : 93, 114, 63, 24, 6, ( 6 ) : KO, donc les suivants aussi ...

Attention, A007060 correspond à un disposition linéaire ...

[ansset]

le mot "subtilité" me trotte dans la tête sans vouloir me causer.
il reste muet avec un petit sourire
il y en aurait il un autre ( un(e) cousin(e) ) qui permettrait de mieux le percevoir sans offenser sa pudeur ?
Cdt

[Médiat]

Bien sûr je mets sous spoiler :

 Cliquez pour afficher

Le cas p = 0 est très spécial, pas uniquement parce que (p-1) ne veut rien dire ...

[ansset]

me doutais un peu, parmi d'autres idées.
merci.
rv demain.
bonne soirée.

[mike.p]

Bonsoir,

4 : 93, 114, 63, 24, 6, ( 6 ) : KO, donc les suivants aussi ...

Attention, A007060 correspond à un disposition linéaire ...

en effet, ils ne passent pas la vérif de la somme ... Nous laissez vous jusqu'à demain matin ?

a propos de A007060 : ils ne sont pas très clairs : "the number of (directed) Hamiltonian paths of the n-cocktail party graph" qui est normalement circulaire de ce que j'en sais ; c'est vrai qu'hamiltonian aurait du me mettre la puce à l'oreille ...

bonne soirée

[Médiat]

Nous laissez vous jusqu'à demain matin ?

Tout le temps que vous voulez

[ansset]

nouvelles du front.
mince je tourne encore en rond pour une conjecture sur E(n,0)
d'autant que je ne retrouve pas 5 pour E(3,0) avec l'équation trouvée.
( mal recopié ds mon coin, bug, ou médocs actuels après mon hospi en urgence ... ???)

[Médiat]

Bonjour,

Vous êtes sorti ?

[ansset]

Bonjour,

Vous êtes sorti ?

sorti ???
non, pas de cette énigme amusante.
HS : ( mais hospi récente pendant 2 sem , et traitement lourd à la maison depuis 10 j )

[ansset]

une réponse à mon post précédent sur E(3,0) ? ( par application de la formule )
c'est ridicule, je sais, un épais brouillard là ce matin..... désolé.

[Médiat]

HS : ( mais hospi récente pendant 2 sem , et traitement lourd à la maison depuis 10 j )

C'est bien sur ce point que je posais la question.

Je vous confirme que

 Cliquez pour afficher

E(3, 0) = 5

[mike.p]

Bonjour,

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

prenons tous les cas possibles pour n = 2
aabb
abab

Dans le problème des cocktails, Monsieur et Madame sont différenciés, comme si nous savions distinguer des chaussettes droites des gauches
aabb donne :
aAbB
aABb
AabB
AaBb
( soit 2 bits pour distinguer les dames des couples )

alors que abab donne
abAB
--- ABab -- écarté car circulaire du précédent
AbaB
--- aBAb -- idem
( soit 1 bit seulement )

diviser les 6 ( et donc non les 8 attendues ) variantes à couples différenciés par n bits ( ici 2² ) ne pouvait qu'être faux

Idem aux ordres supérieurs.
Il n'y a que 2 de chaque couleur, un motif ne peut être reproduit plus d'une fois. Quid de la parité de n ? à voir ...

En tous les cas, ça invalide des vérifications faciles par la somme d'une ligne de n ou par la liste connue des C(n,0) , celle dont les couples sont différenciés.

Prendre un autre chemin ? Ce dimanche de répit en laissera peut être le temps ...

[ansset]

@Mediat:
oui, bien sur, mais ce n'est pas ce qui me gène.
mais le fait est que l'application de la formule ne s'applique donc pas
car on obtient 7 si on néglige le terme en E(2,-1),
ce que donc on ne peut pas faire, semble t il.
ou alors, il faut à tout prix que je me recouche.