Problème niveau collège...

[Ben314]

Salut,
Ca fait 10 minutes que je cherche à résoudre un problème posé en "collège" et j'y arrive pas

Parmi les n! permutations des nombres {1..n}, combien y en a t'il qui ne contiennent pas deux nombres successifs cote à cote c'est à dire pas de (...,k,k+1,...) ni de (...,k+1,k,...) ?

Bon, d'accord, dans le problème initial, il y avait la petite info suplémentaire n=4 mais on est pas obligé de s'en servir :doh:

[benekire2]

Salut,
Ca fait 10 minutes que je cherche à résoudre un problème posé en "collège" et j'y arrive pas

Parmi les n! permutations des nombres {1..n}, combien y en a t'il qui ne contiennent pas deux nombres successifs cote à cote c'est à dire pas de (...,k,k+1,...) ni de (...,k+1,k,...) ?

Bon, d'accord, dans le problème initial, il y avait la petite info suplémentaire n=4 mais on est pas obligé de s'en servir :doh:

c'est peut être parce que il y avait marqué n=4 que c'était niveau collège ...

[Nightmare]

Salut ben !

T'as demandé à un logiciel de calcul de nous conjecturer le nombre de telles permutations pour les premiers n? Déjà pour n=2,3,4 il n'y en a aucune, n=5 j'en trouve 6. Je ne vois pas, pour le moment, de formule générale et encore moins de méthode pour y arriver :lol3:

[Ben314]

1) T'as demandé à un logiciel de calcul de nous conjecturer le nombre de telles permutations pour les premiers n?
2) Déjà pour n=2,3,4 il n'y en a aucune,
3) n=5 j'en trouve 6.
4) Je ne vois pas, pour le moment, de formule générale et encore moins de méthode pour y arriver :lol3:

1) => pas encore...
2) Pour n=4 il me semble que 2413 et évidement 3142 fonctionnent
3) pas fait et, si je le fait c'est avec le 1) car pour moi les entiers, c'est "1,2,3,4,beaucoup" et "beaucoup=Ordinateur" :zen: )
4) Moi non plus et moi non plus (en fait dans les "énigmes", quand je précise pas au début que j'ai la soluce, et ben souvent ça veut dire que... je sais pas faire :doh: )

Le truc bizare, c'est que, si on note Pi l'évènement "a_{i+1}=a_i+1 ou a_i-1" et en supposant les Pi indépendants (ce qui est faux, mais à quel point ?) alors le calcul est simple et le résultat assez joli...

[beagle]

serait pas plus facile de compter l'inverse?,
tous les cas qui font foirer,
on commence avec 1,
avec 1-2, combien de positions, et combien de combi avec les autres nombres
puis on passe à 2
les 2-3 puisque les 2-1 sont déjà faits, en enlevant les déjà comptés 1-2-3,3-2-1
puis les 3,...
récurrence?

me rend pas bien compte de la difficulté du boulot que je donne aux autres moi.Si c'est crevant laissez tomber.En général si c'est trop long et fastidieux je demande à ma femme de le faire,
mais bon pour les maths,...

[Ben314]

Bon, voila les premières valeurs :
0 1
1 1
2 0
3 0
4 2
5 14
6 90
7 646
8 5242
9 47622
10 479306
11 5296790
12 63779034
13 831283558
14 11661506218
15 175203184374
16 2806878055610
17 47767457130566
18 860568917787402
19 16362838542699862
20 327460573946510746

Bon, (évidement), j'ai un peu triché : en fait j'ai calculé les 12 premières puis je les aient "donné à manger" à google qui m'a recraché les... 500 premières... (si vous voulez la soluce, vous pouvez faire pareil... :zen: )
En fait, en lisant tout, il y a une formule (récurente) pas super compliqué (mais ils expliquent pas d'où elle vient)

Donc... On peut continuer à chercher...

[Nightmare]

C'est bien ce que j'avais trouvé pour n=9 :lol2:

[Nightmare]

Euh, t'as calculé les 12 premières à la main? :s

[Ben314]

S'il y en a qui veulent "la soluce" (blanchie):
1 ère indication
C'EST UNE RECCURENCE SUR LES 4 TERMES PRECEDENTS


Solution :
SI n = 0 OU 1 ALORS a(n) = 1; SI n = 2 OU 3 ALORS a(n) = 0;
SINON a(n) = (n+1)*a(n-1) - (n-2)*a(n-2) - (n-5)*a(n-3) + (n-3)*a(n-4).

Mais je ne sais pas d'où ça sort...

[Ben314]

Euh, t'as calculé les 12 premières à la main? :s

Tu parle, Déjà rien que 6x7 j'ai du mal... (par contre 2^16 "par coeur"...)
Ce genre de truc, je ressort mon bon vieux turbo-pascal de son tiroir...