Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 27-11-2011 10:07:04

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

rotal désordre

Bonjour à tous.
Certains ont peut être vu ça pendant leurs études supérieures, si oui ça sera rapide pour eux. Pour les autres, le plaisir de la découverte est là accessible.

Combien de classements différents des 26 lettres de l'alphabet existent quand aucune lettre n'est à sa place ?

Bon amusement



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 27-11-2011 10:13:44

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Total Déésordre

En maths on appelle ça des dérangements

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

Vasimolo

 #3 - 27-11-2011 11:49:16

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 679

Total Désorde

Le nombre de classements  est de
       148362637348470135821287825
A comparer avec
26!=403291461126605635584000000
Il se calcule aisément au moyen d'une récurrence forte.

 #4 - 27-11-2011 12:40:33

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

Toatl Désordre

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 lol 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 smile

Mathieu

 #5 - 27-11-2011 13:06:16

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3313

Total Désoordre

Pour l'instant je ne me risquerai pas dans des calculs trop compliqués et je répondrai au moins 26. Je reviendrai...

Shadock smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #6 - 27-11-2011 13:07:37

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

Total Déosrdre

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


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #7 - 27-11-2011 15:37:39

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Total Déssordre

Beaucoup de bonnes réponses. Curieusement personne n'a pensé (mais la question n'était pas posée) à donner la proportion par rapport au nombre total de combis différentes.
Shadock, il faut revoir, en effet, ce min peut être, comment dire... amélioré.

 #8 - 27-11-2011 19:50:30

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

Total Déssordre

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.


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #9 - 29-11-2011 18:30:06

esereth
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 175

yotal désordre

Maintenant que j'ai grillé mes deux réponses mastermind 3, je viens ici faire un peu de maths.yikes

Je n'avais jamais eu l'occasion de traiter le problème des dérangements avec de tels nombres
Je m'étais contenté du classique problème des chapeaux  où n vaut 5 ou 6.

pour26: 148362637348470135821287825

La formule que j'ai utilisée :

d(n)=n*d(n-1)+(-1)^n avec d(1)=0 pour amorcer la récurrence.

 #10 - 29-11-2011 18:35:13

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

tital désordre

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

 #11 - 29-11-2011 22:44:55

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3313

total désordrr

Prenons un cas simple 4 lettres dans l'alphabet: ABCD
La lettre A est à sa place pour ABCD, ABDC, ACBD, ACDB, ADBC et ADCB
La lettre B est à sa place pour ABCD, ABDC, CBAD, CBDA, DBAC et DBCA
Etc, il y a donc (n-1)! permutation ou les lettres sont à leurs places. (On pourrait procéder par récurrence en partant de n lettres pour le démontrer.)

Le nombre de permutation est n! le désordre est donc "total" dans n!-(n-1)!
Avec n=26 on a 26!-25!=387780251083274649600000000

Je ne suis pas totalement sur de moi mais je pense avoir déjà une bien meilleure approche du problème lol

Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #12 - 30-11-2011 15:59:05

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Totla Désordre

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] big_smile)


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #13 - 30-11-2011 16:17:48

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Total Dsordre

Tu noteras cependant la phrase suivante en dessous de la formule:
"On peut d'ailleurs remplacer 26 par n'importe quel nombre N"
La formule générale est N-k, d'où le 26-k

 #14 - 30-11-2011 18:03:24

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Total Désrodre

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.

 #15 - 30-11-2011 18:50:39

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3313

Total Dséordre

Sioupli je ne vois ce qui fait tache dans mon "raisonnement" ?

Avec 4 lettres, je ne vois pas comment vous trouvé 9 moi je serai presque tenté de dire 0 puisque il y a 6 possibilités avec chaque lettre à ça place donc avec 4 lettres il y a 4!=24 arrangements possibles moins tout ceux où une lettre est à ça place soit 6*4=24 et 24-24=0 hmmyikes

Aïïïïïïe Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #16 - 01-12-2011 13:38:14

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

total déqordre

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 roll


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #17 - 01-12-2011 15:16:19

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3313

Total Dsordre

A oui en effet, merci beaucoup. Et quand on est prof (si je ne me trompe pas) je pense qu'il vaut mieux être pédagogue.

Shadock smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #18 - 01-12-2011 16:59:59

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Total Désorddre

Seulement moniteur, pour ma part big_smile


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #19 - 01-12-2011 18:11:06

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3313

Ttal Désordre

Moniteur de quoi? yikes


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #20 - 02-12-2011 16:17:58

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

total désorsre

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

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


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #21 - 02-12-2011 22:03:29

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3313

Total Déssordre

La classe! smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #22 - 02-12-2011 22:15:48

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Total Désorre

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

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


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #23 - 02-12-2011 22:28:23

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3313

Total Désorrdre

Oui mais bon "enseigner" en classe préparatoire n'est pas donné à tout le monde. big_smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #24 - 02-12-2011 22:33:58

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Total Dsordre

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


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #25 - 03-12-2011 08:43:25

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2706
Lieu: Luxembourg

Total Dséordre

shadock a écrit:

Moniteur de quoi? yikes

Moniteur de surf big_smile Il y a beaucoup de points communs entre les maths et le surf lol

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 78 pommes et que vous en prenez 43, combien en avez-vous ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete