Recherche formule générale pour un arrangement particulier

[roy37]

Bonjour,

Je cherche à calculer le nombre de solution correspondant aux critères suivants :

Ranger les nombres de 1 à N de manière à ce que pour tout nombre k de la suite, le nombre immédiatement précédent et le nombre immédiatement suivant ne soit pas égal à k-1 ou k+1.

Pour N=4 par exemple, on cherche à trouver le nombre d'arrangements qui respectent la règle imposée.
Les seules solutions sont : {2,4,1,3} et {3,1,4,2}. La réponse est donc 2 pour N=4.

J'ai pu trouver pour N=5 qu'on en avait 14, j'ai même le résultat pour N=6 mais la tâche étant un peu fastidieuse je n'ai pas vérifier mon résultat, je ne vais donc pas le donner. Je sais qu'n petit programme informatique me permettrait de trouver la solution rapidement mais ce n'est pas le but que je recherche.


Existe-il une formule me permettant de faire ce calcul pour n'importe quelle valeur de N ? J'ai quelques pistes mais je ne parvient toujours pas à trouver une formule.

J'espère avoir l'aide de quelqu'un ici,
merci d'avance pour ceux qui s'y pencheront.
-----

[Médiat]

Bonjour,

j'ai même le résultat pour N=6 mais la tâche étant un peu fastidieuse

90 ?

[roy37]

Non je trouve 108, mais il est possible que je me sois trompé, bien que la différence soit assez importante entre les 2 résultats.

[roy37]

J'ai essayé en prenant le problème à l'envers. C'est à dire que j'ai d'abord calculer le nombre d'arrangements possibles pour les N nombres. Puis je chercher à soustraire toutes les possibilités qui ne répondent pas au critère de sélection.
Par exemple je peux avoir le nombre de fois où apparaît la suite {1,2}, ça me permet d'obtenir le nombre de solutions qui ne doivent pas être comptabilisées à cause de cette suite. Je peux refaire la même manip' pour toutes les suites de 2 nombres mais le total ne représente rien. Si je prends {1,2} et {2,3} par exemple, toutes les solutions qui auront la suite 1,2,3 seront comptabilisées 2 fois avec cette méthode.

[A voir en vidéo sur Futura]

[mike.p]

Bonjour,

est ce un exercice scolaire ou bien un moment de détente ? dans ce dernier cas, il vaut mieux utiliser le forum ludique avec ses solutions directes sous spoiler.

propositions de solutions sous spoiler ? ça nous changerait les idées ...

[roy37]

Non ce n'est pas pour un exercice scolaire. On peut éventuellement appeler ça un moment de détente oui.

[ansset]

pour N=6 , j'en trouve 92

 Cliquez pour afficher

12 si le premier est 1 ou 6 ( par symétrie )
16 si le premier est 2 ou 5
18 si le premier est 3 ou 4
mais fait un peu "à la main" ce matin donc une boulette ( de +1 ) n'est pas impossible.
j'aimerai savoir comment Mediat a trouvé son 90 ( analytique, programme, autre.. )
la solution est peut être de chercher une récurrence sur N

[Médiat]

Bonjour ansset,

Avez-vous pensé à soustraire les cas symétriques (ne pas multiplier systématiquement par 2 ) ?

[ansset]

ps , pour 5, j'en trouve 18.

[ansset]

Bonjour ansset,

Avez-vous pensé à soustraire les cas symétriques (ne pas multiplier systématiquement par 2 ) ?

je place les nombres dans un ordre donné,( systématique ) donc à priori aucune n'est symétrique.
et il n'y a que 2 d'écart entre 90 et 92,
j'ai peut être fait par contre une faute d'attention qcq part.

[ansset]

un début de récurrence:

 Cliquez pour afficher

pour passer de N=4 à N=5
les deux solutions de N=4 entraînent 2*(6-1) sol = 10 solutions ( 5 positions pour le nouveau nombre 5 )
auquel s'ajoute:
parmi les 4! arrangements, les arrangements commençant un nombre fixe qui ne contiennent [B}qu'un seul couple isolé et "cassable"[/B]
( les autres cas éliminés comportent soit des doubles couple distincts, soit des sous arrangements contenant ( n-1;n;n+1).
ces arrangements particuliers non comptabilisés au rang 4, trouve une solution au rang 5 en cassant le couple.
d'où pour 5
10 sol +
2*4=8 sol
total 18, même chiffre que je retrouve "à la main" , avec donc une autre approche.

[Médiat]

Je vous confirme qu'il y en a 14 pour n = 5 (sans doute comptez-vous deux fois les arrangements qui commencent par 3, c'est ce que je voulais dire en parlant de symétriques, mais dans le cas 6 il n'y en a pas )

[minushabens]

Ranger les nombres de 1 à N de manière à ce que pour tout nombre k de la suite, le nombre immédiatement précédent et le nombre immédiatement suivant ne soit pas égal à k-1 ou k+1.

il suffit de considérer par exemple k+1. Le problème serait plus joli si on ajoutait la contrainte que 1 et N ne doivent pas être contigus, de même que le premier et le dernier nombres de la suite.

[roy37]

Je vous fourni le document que j'ai fait pour trouver la solution pour 5 et pour 6.
A partir des solutions pour 5 j'ai déterminer que toutes les solutions où on rencontre 2 "anomalies" ne peuvent pas donner de solution pour 6. Quand je parle d'une "anomalie" je veux dire deux nombres qui se suivent (exemple : 1,2,4,3,5 on a 1,2 et 4,3 comme anomalies, rajouter un 6 ne peux en combler qu'une).

J'ai pu cerner tous les cas possibles pour arriver à un résultat de 108 pour 6, après revérification je ne vois pas d'erreurs, encore moins avec 5, je ne trouve pas ces 18 solutions.

[ansset]

oui , exact pour le 14, bien vu l'erreur.

[Médiat]

ansset, Je confirme N=6 : 90 cas

 Cliquez pour afficher

votre erreur vient du cas "16 si le premier est 2 ou 5", en fait c'est 15.

[roy37]

il suffit de considérer par exemple k+1. Le problème serait plus joli si on ajoutait la contrainte que 1 et N ne doivent pas être contigus, de même que le premier et le dernier nombres de la suite.

Si j'ai bien compris la contrainte que tu souhaiterais rajouter, le problème devient beaucoup plus simple puisque maintenant tout nombre de la suite ne peut pas être différencier d'un autre. Donc ensuite il suffit de calculer le nombre de solutions commençant par l'un de ces nombres puis de multiplier par N. Ça pourrait être intéressant aussi mais je vais rester sur le problème initial.

[ansset]

mais pas une erreur de symétrie, un cas "mauvais" non oublié.
je confirme aussi pour le 6 ( tj le même type d'erreur , un cas de trop non éliminé )

[roy37]

A priori je trouve plutôt ça moi :

14 pour 1 et 6
18 pour 2 et 5
22 pour 3 et 4

Un total de 108 du coup.

[ansset]

recurrence suite / mess précédent:

 Cliquez pour afficher

on a bien 2*5 solutions +4 ( et non 2*4) , là c'est une erreur de redondance ( symétrie )
reste à étendre , en commençant par le passage de 5 à 6 pour voir

[Médiat]

A priori je trouve plutôt ça moi :

14 pour 1 et 6
18 pour 2 et 5
22 pour 3 et 4

Un total de 108 du coup.

Je trouve respectivement : 12, 15 et 18 soit 90

[roy37]

2*(9*4 + 18*1) = 108

9 solutions issues de N=5 donnent chacune 4 solutions pour N=6, soit 36 solutions.
18 solutions issues de N=5 donnent chacune 1 solution pour N=6, soit 18 solutions.

Comme tout ces solutions sont des solutions commençant par 1, 2 ou 3 on peut faire une symétrie et donc multiplier le tout par deux.

[roy37]

Je vais lister les solutions que j'ai commençant par 1 :
1,3,6,4,2,5
1,3,5,2,4 (on peut placer le 6 à 4 endroits donc 4 solutions à partir de cette suite)
1,4,2,6,3,5
1,4,2,5,3 (on peut placer le 6 à 4 endroits donc 4 solutions à partir de cette suite)
1,4,6,3,5,2
1,5,2,4,6,3
1,5,3,6,2,4
1,5,3,6,4,2

Je ne trouve rien d'autre pour ma part, quelle serait la 15ème solution que tu trouves ? (étrange un nombre impair en plus)

[Médiat]

Je vais lister les solutions que j'ai commençant par 1 :
1,3,6,4,2,5
1,3,5,2,4 (on peut placer le 6 à 4 endroits donc 4 solutions à partir de cette suite)
1,4,2,6,3,5
1,4,2,5,3 (on peut placer le 6 à 4 endroits donc 4 solutions à partir de cette suite)
1,4,6,3,5,2
1,5,2,4,6,3
1,5,3,6,2,4
1,5,3,6,4,2

Commençant par 1 je n'en ai que 12 (message #21), dans vos 2 cas multiples vous annoncez 4 solutions, il n'y en a que 3

[roy37]

Autant pour moi je me suis trompé de personne.

Par contre j'en compte bien 4 :
6,1,3,5,2,4
1,6,3,5,2,4
1,3,5,2,6,4
1,3,5,2,4,6

[Médiat]

6,1,3,5,2,4 ne commence pas par 1.

[roy37]

Ah oui en effet. Est-ce que la solution est par contre bien prise en compte dans la symétrie ? A première vue je pense que oui.

[Médiat]

Oui, puisque le symétrique est 1,6,4,2,5,3 qui est obtenu à partir de 1,4,2,5,3

[ansset]

Je trouve respectivement : 12, 15 et 18 soit 90

j'ai un doute d'un seul coup :
par exemple
pour un début par 2:
246153 est sol
et pour un début par 3:
351642 est sol
Or quand on multiplie par 2 à la fin , c'est pour traiter les cas 4,5,6
mais on oublie les symétries éventuelles sur les petits nombres, non?
en enlevant celle ci, je retrouve 90,
mais je n'ai pas vérifié qu'il n'y en avait pas d'autres.
Et du coup, "démarrer par" mérite d'être précisé et doit sous entendre sans symétrie plus tard quand on multipliera par 2...

sinon, re-correction de ma recurrence de 4 à 5:

 Cliquez pour afficher

2 solutions pour N=4 , mais pas 5 solutions à partir de celles ci, car le 5 ne doit pas être collé au 4
uniquement 3 solutions.
donc par ajout du 5 sur solutions existantes au rang 4 : 6*2 =8 solutions.
ensuite il y a bien 8 cas de doublons uniques "cassables" ( j'ai dit une erreur tout à l'heure ) sur les arrangements non valable au rang 4.
donc 6+8= 14

[ansset]

suite de la récurrence:

 Cliquez pour afficher

pour N=5, on a 14 sol
ce qui donne déjà 14(6-2)=56 solutions "naturelles", auxquelles il faut ajouter les nouvelles combinaisons
dans la répartition des 5! arrangement ( en tout cas pour les débuts 1;2;3)
on trouve:
pour (1;.. ) outre les 2 solutions, 7doublons isolés.
pour (2;.. ) les 3 solutions et 9 doublons mais dont seuls 6 sont non récurrents par symétrie avec ceux d'avant.
pour (3;.. ) 4 solutions mais 2 sont récurrentes et 8 doublons dont 4 sont récurrents.
restes qu'on retrouve:
3+2+2 solutions indépendantes soit 14 au total.
et pour les doublons : 7+6+4=17 doublons " cassables"
ce qui induit 34 solutions de plus au rang 6
total 56+34=90 solutions au rang 6.

reste à trouver la logique pour déduire les doublons isolés....
c'est pas gagné.