|
#1 - 27-11-2011 10:07:04
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Total Désrodre
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
#2 - 27-11-2011 10:13:44
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
#3 - 27-11-2011 11:49:16
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
Total Désordr
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
Total Désorde
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
#5 - 27-11-2011 13:06:16
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
Tottal Désordre
Pour l'instant je ne me risquerai pas dans des calculs trop compliqués et je répondrai au moins 26. Je reviendrai...
Shadock
"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 : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Ttoal Désordre
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 : 3802
Total Déésordre
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 : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Total Désorrdre
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 : 176
total désotdre
Maintenant que j'ai grillé mes deux réponses mastermind 3, je viens ici faire un peu de maths.
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 : 1960
toral 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 : 3334
Total Désrodre
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
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
Ttal 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] )
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 : 1960
Total Désrodre
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 : 3802
Totla Désordre
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 : 3334
Toal Désordre
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
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 éDsordre
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
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 : 3334
Total Désordree
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
"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éqordre
Seulement moniteur, pour ma part
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 : 3334
toyal désordre
Moniteur de quoi?
"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
oTtal Désordre
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.
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 : 3334
total désordrz
La classe!
"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
totam désordre
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
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 : 3334
Total Désrodre
Oui mais bon "enseigner" en classe préparatoire n'est pas donné à tout le monde.
"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 Déssordre
Pas faux. Après y avoir été torturé moi-même, ça me fait du bien de me venger
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 : 3220
- Lieu: Luxembourg
Total Dséordre
shadock a écrit:Moniteur de quoi?
Moniteur de surf Il y a beaucoup de points communs entre les maths et le surf
Mots clés des moteurs de recherche
|
|