Permutations, rotations et Cie

[Caribensila]

Bonjour à tous,

C'est ma 1ère intervention sur ce forum et j'espère poster dans la bonne rubrique. 1000 excuses si ce n'est pas le cas ( je suis plus habitué aux forum de prog ;).

Voici le problème qui me tarabuste :

Hypothèses :

Une table rectangulaire avec 18 convives, 8 de chaque côté et 1 à chaque bout.

Problème:

Combien y a t-il de plans de table différents possibles ?
En sachant que :
sont considérés comme différents 2 plans de table où au moins 1 convive a au moins 1 voisin direct différent ou 1 de ses 3 vis-à-vis différent,
ET
pour les convives placés en bout de table (les 2 présidents), sont considérés comme différents 2 plans de table où au moins 1 des deux présidents a au moins 1 des ses 4 voisins directs différent (les vis-à-vis n'étant pas considérés pour ce cas).


Je suis curieux de voir comment vous allez aborder ce problème...
Je crois savoir qu'il n'est pas de mise de demander un résultat ici, mais si une exception pouvait être faite et si je pouvais avoir une idée de l'ordre de grandeur, je vous en serais infiniment reconnaissant.
Et sinon, je vous serais quand même reconnaissant :)))

PS: Mon intention profonde est de savoir si une approche de ce problème par un algo génétique plutôt qu'une approche itérative est justifiée.
Voilà, j'espère avoir tout dit.

Merci à ceux qui me liront.
Cari

[fatal_error]

Bonjour,

je pense pas que je pourrai t'aider, mais j'ai du mal a saisir la différence entre
1 convive a au moins 1 voisin direct différent
et
1 de ses 3 vis-à-vis différent

Si un convive change de place, il aura forcément un vis a vis différent.
Si un convive a un vis a vis différent, c'est que il a changé de place ou en face ca a changé de place.

Donc dans ce sens j'ai envie de penser qu'on s'interesse pas aux vis a vis.


A partir de la avec de la combinatoire :
on pose un président : 18 choix possibles
on pose ses 4 coquinous : 4 arrangements sur 17 possibles (faut que yait un gars qui se bouge)
on pose le second président : 13 choix possibles
on pose ses 4 copains : 4 arrangements sur 12 possibles(ils peuvent se bouger aussi)
et on place le reste : 8!


Au final, je vois bien
plans de table différents.

ps:arrangement et pas combinaison car j'ai numéroté les chaises : a droite du président, c'est pas pareil qu'a gauche...

Bon, apres je suis pas une référence...le mieux, c'est ptet de tester avec une table a 6 et voir si les chiffres collent

[Caribensila]

«a droite du président, c'est pas pareil qu'a gauche...»
Bein si...
Imagine un plan où on ne bouge pas les deux présidents, et qu'on intervertisse seulement les convives des 2 côtés. Ils chandent de côté mais restent dans le même ordre... Cela, pour moi, ne constitue pas un nouveau plan de table.

En tout cas, merci beaucoup pour ta réponse...
Je retiens l'idée de la table de 6 pour tester ;)

[fatal_error]

J'ai tres envie de dire qu'il suffit de diviser le résultat par 4 car la table est "symétrique".
On pourrait pas diviser par 2 si par exemple, il y avait une chaise en plus qui serait inutilisée.
On divise par 4 car si on dit que on s'en tape des coté latéraux, j'imagine qu'on s'en tape aussi des coté en longueur.

exemple avec un président et 4 sous fifres(A,B,C,D):
Pour le président Z: le premier couple c'est le bord gauche, le second, le bord droit
(A,B),(C,D)
(A,B),(D,C)
(A,C),(B,D)
(A,C),(D,B)
(A,D),(B,C)
(A,D),(C,B)
On remarque que :
pour chaque position, on va avoir un UNIQUE double latéral: (A,B),(C,D) et (C,D),(A,B)

Si on s'occupe des doubles en longueurs, (si on a un président qui a changé sa place avec l'autre, etc), même raisonnement,pour une position donnée, il n'existe qu'un seul double. Et pour chaque position donnée, il existe un double

Donc au final, je diviserais bien tout par 4.

j'aurais bien testé avec une tite pile, mais des valises a faire ...

[Caribensila]

Ah, bein ouais...
Plus on réfléchit, plus ça semble un problème à la con (vous dites "à tiroirs" vous, les matheux, non?).
D'un autre côté, si c'était simple, je ne serais jamais venu vous emm...

«On pourrait pas diviser par 2 si par exemple, il y avait une chaise en plus qui serait inutilisée»
On postule que tout le monde vient quand j'invite, ok?! ;)

Sinon, bonnes vacances à toi (je dis ça à cause des valises... et en espérant que c'est pas pour un stage à la con à perpette).

Encore merci.
Cari

[fatal_error]

héhé, ca yest elles sont pliées.

Bon, cela dit, j'ai quand même pas le temps pour la pile, car je sais que si jmy met maintenant, jvais faire dla boulette.

vous dites "à tiroirs" vous, les matheux, non?

Je sais pas, chui en ecole d'info :we: (1e année)

et sinon, merci pour les vacances, le stage c'est pour la fin d'année(brrr on y pensera plus tard)

[Caribensila]

lol
...
Je me demande si, vu les tiroirs plein de bordel, on ne se fourvoierait pas en restant dans la combinatoire...

Mais bon! Pas grave. J'ai mon ordre de grandeur...

N'empêche, si qqun a une idée d'abordage, qu'il nous en fasse part !
Merci