En maths on appelle ça des dérangements

http://fr.wikipedia.org/wiki/Principe_d … -exclusion

Vasimolo

Je ne me rappel pas avoir vu ça, je trouve une relation de récurrence mais pas de formule générale :

WolframAlpha me dit que c'est !n (j'ai d'abord pris ça pour une erreur je ne connaissais pas la sous-factoriel)

Pour trouver la récurrence j'ai posé aussi [latex]v_n[/latex] le nombre de classement d'un ensemble ordonné à n élément avec exactement 1 élément à sa place,
[TeX]v_{n+1}=(n+1)u_n[/TeX]
En effet les classements où seul le n ème élément est à sa place (il y en a [latex]u_n[/latex]) sont isomorphes à l'ensemble des classement où le i ème élément est à sa place (l'isomorphisme transforme le i ème en le dernier et décale tout les élément après i d'un élément "vers la gauche", il suffit ensuite de changer la relation d'ordre pour retrouver la propriété que seul le dernier élément est à sa place)

cela donne [latex]u_{n+1} = nu_n+v_n[/latex] (On part des classement pour n élément et on remplace un élément (n possibilités) par le dernier, on ajoute les [latex]v_n[/latex] classement où le n ème élément prend la place de l'élément qui était à sa place)

et enfin [latex]u_{n+1}=n(u_n+u_{n-1})[/latex] avec [latex]u_1=0 ; u_2=1[/latex]

donc [latex]u_{26}=148362637348470135821287825[/latex]

Merci pour ce problème instructif

Mathieu

Problème interressant.

La réponse est le 26ème nombre de la série de nombres suivante:

1 - 0
2 - 1
3 - 2
4 - 9
5 - 44
6 - 265
7 - 1854
8 - 14833
9 - 133496
10 - 1334961
11 - 14684570
12 - 176214841
13 - 2290792932
14 - 32071101049
15 - 481066515734
16 - 7697064251745
17 - 130850092279664
18 - 2355301661033953
19 - 44750731559645106
20 - 895014631192902121
21 - 18795307255050944540
22 - 413496759611120779881
23 - 9510425471055777937262
24 - 228250211305338670494289
25 - 5706255282633466762357224
26 - 148362637348470135821287825
27 - 4005791208408693667174771274
28 - 112162153835443422680893595673
29 - 3252702461227859257745914274516
30 - 97581073836835777732377428235481
31 - 3025013288941909109703700275299910
32 - 96800425246141091510518408809597121
33 - 3194414033122656019847107490716704992
34 - 108610077126170304674801654684367969729
35 - 3801352699415960663618057913952878940514
36 - 136848697178974583890250084902303641858505
37 - 5063401795622059603939253141385234748764684
38 - 192409268233638264949691619372638920453057993
39 - 7503961461111892333037973155532917897669261726
40 - 300158458444475693321518926221316715906770469041
41 - 12306496796223503426182275975073985352177589230680
42 - 516872865441387143899655590953107384791458747688561
43 - 22225533213979647187685190410983617546032726150608122
44 - 977923461415104476258148378083279172025439950626757369
45 - 44006555763679701431616677013747562741144797778204081604
46 - 2024301565129266265854367142632387886092660697797387753785
47 - 95142173561075514495155255703722230646355052796477224427894
48 - 4566824330931624695767452273778667071025042534230906772538913
49 - 223774392215649610092605161415154686480227084177314431854406736
50 - 11188719610782480504630258070757734324011354208865721592720336801

qui n'est autre que la série A000166 sur OEIS.
Sauf que sur OEIS, la série ne va que jusqu'a 21 lettres.

Edit: Apparently OEIS a une liste plus longue de la série qui va jusqu'a 200, ici, si j'avais su....

Effectivement, si on regarde les proportions on trouve:
1 - 0 -> 0%
2 - 1 -> 50%
3 - 2 -> 33.333333333%
4 - 9 -> 37.500000000%
5 - 44 -> 36.666666667%
6 - 265 -> 36.805555556%
7 - 1854 -> 36.785714286%
8 - 14833 -> 36.788194444%
9 - 133496 -> 36.787918871%
10 - 1334961 -> 36.787946429%
11 - 14684570 -> 36.787943923%
12 - 176214841 -> 36.787944132%
13 - 2290792932 -> 36.787944116%
14 - 32071101049 -> 36.787944117%
Au dela, ca se maintient a 36.787944117% qui est 1/e
au devrais-je dire... La proportion tend vers 1/e.

La formule est [latex]\sum_{k=0}^{26} (-1)^{(26-k)}(26-k)! C_{26}^k[/latex]
Explications:
On a 26! permutations.
On enlève pour chaque lettre les 25! permutations qui garde cette lettre fixe
Du coup, on ajoute celles qu'on a retiré 2 fois: pour chaque paire de lettre les 24! permutations qui garde cette paire fixe
Du coup on a ajouté 2 fois celles qu'on avait retiré, on enlève pour chaque triplette de lettres les 23! permutations qui gardent ces lettres fixes, etc...

On peut d'ailleurs remplacer 26 par n'importe quel nombre N
Euler a donné une formule sympathique pour calculer f(N) par récurrence:
F(N) = N*f(N-1) + (-1)^N
F(2) = 1
F(3) = 2
F(4) = 9
F(5) = 44
F(6) = 265
F(7) = 1854
F(8) = 14833
F(9) = 133496
F(10) = 1334961
F(11) = 14684570
F(12) = 176214841
F(13) = 2290792932
F(14) = 32071101049
F(15) = 481066515734
F(16) = 7697064251745
F(17) = 130850092279664
F(18) = 2355301661033953
F(19) = 44750731559645106
F(20) = 895014631192902121
F(21) = 18795307255050944540
F(22) = 413496759611120779881
F(23) = 9510425471055777937262
F(24) = 228250211305338670494289
F(25) = 5706255282633466762357224
F(26) = 148362637348470135821287825

J'aime bien la réponse de Scarta, qui a le bénéfice de la clarté. (À part le [latex](-1)^{26-k}[/latex] qui est un peu débile, vu que la parité de [latex]26-k[/latex] est celle de [latex]k[/latex] )

Merci pour votre participation.
Perso, j'ai fait exactement comme Mathieu Verlan, en créant 2 suites adjacentes. Il est à remarquer que la convergence vers la proportion 1/e est rapide car pour 12 caractères, les 9 premiers chiffres décimaux de 1/e sont bons.

Tu serais tenté de dire zéro alors que tu peux créer à la main des arrangements dans ce genre : BCDA par exemple.

24 arrangements possibles, OK. 6 possibilités avec chaque lettre à sa place, OK. Mais tu en comptes certaines plusieurs fois. Exemple trivial : l'arrangement ABCD appartient aux arrangements qui conservent A à sa place, à ceux qui conservent B à sa place, à ceux qui conservent C à sa place ET à ceux qui conservent D à sa place. Tu viens donc de le compter quatre fois.

De la même façon, ABDC, ADCB, ACBD, DBCA, CBAD et BACD sont comptés deux fois chacun. Ca fait 9 de trop dans ton compte... Et tu en déduis qu'il reste 9 arrangements qui ne laissent aucune lettre à sa place.



EDIT : je vois que les autres n'ont pas une âme de pédagogue

Seulement moniteur, pour ma part

Moniteur = thésard qui donne un certain nombre de TD ou TP par an, contre une prime sur sa bourse de thèse

En maths niveau première année de prépa.

En toute modestie, euh... Ouais, c'est la méga-classe

Mais je ne suis même pas un vrai prof, donc, euh... Pas tant que ça

Pas faux. Après y avoir été torturé moi-même, ça me fait du bien de me venger