Question à propos du Rubik's Cube 3x3x3
- sakd0
- Passe sa journée ici. Et dort ici, aussi
- Messages : 811
- Enregistré le : sam. juil. 22, 2006 1:05 pm
- Localisation : Reims
bon alors deadalnix tu dis que mon raisonnement est faux mais c'était pas du tout MON raisonnement, j'essayer de faire comprendre que le 1er résultat de g-kid était faux : 8!-7!
mintenant je peux vous donner la réponse, qui s'appuie sur des choses concrètes (troll qu'est ce que tu nous racontes !! expliques un peu :/ )
la réponse pour 8 est 14833, sans compter la multiplication par le nombre d'orientation possible etc.
Cela vient du fait qu'il faut résoudre la relation de récurrence :
P(n) = (n-1) * [ P(n-1)+P(n-2) ]
avec P(n)=nombre de combinaison de n éléments où aucun élément n'est à sa place.
Et la solution est : P(n)=somme de k=0 à k=n de [ (-1)^k ] / k!
Je vais scanner la démonstration qui explique pourquoi une telle relation de récurrence et comment la résoudre (par 2 méthodes par contre ... niveau math spé oblige pour la deuxième démonstration )
mintenant je peux vous donner la réponse, qui s'appuie sur des choses concrètes (troll qu'est ce que tu nous racontes !! expliques un peu :/ )
la réponse pour 8 est 14833, sans compter la multiplication par le nombre d'orientation possible etc.
Cela vient du fait qu'il faut résoudre la relation de récurrence :
P(n) = (n-1) * [ P(n-1)+P(n-2) ]
avec P(n)=nombre de combinaison de n éléments où aucun élément n'est à sa place.
Et la solution est : P(n)=somme de k=0 à k=n de [ (-1)^k ] / k!
Je vais scanner la démonstration qui explique pourquoi une telle relation de récurrence et comment la résoudre (par 2 méthodes par contre ... niveau math spé oblige pour la deuxième démonstration )
- sakd0
- Passe sa journée ici. Et dort ici, aussi
- Messages : 811
- Enregistré le : sam. juil. 22, 2006 1:05 pm
- Localisation : Reims
Je donne déjà la 1ère démonstration puisqu'il n'y a que de l'écriture. Il y a pas besoin de plus de connaissance que ça en math ou quoi, il y a juste besoin de temps pour bien comprendre.
Donc on cherche le nombre de configuration où aucun élément n'est à sa place. On numérote les éléments de 1 à n, et 1 doit aller à la place 1, 2 à la place 2, etc
-Si on commence par placer un élément en 1, on a n-1 choix puisqu'il ne faut pas placer 1 en 1. On place l'élément k à la place n°1.
Maintenant il faut faire la différence entre 2 cas :
(1) -On place l'élément 1 à la place n°k
(2) -On ne place pas l'élément 1 à la place n°k
Pour (1) : on a donc permuter 1 et k, et le problème revient maintenant à chercher le nombre de configuration à n-2 éléments avec n-2 places où aucun élément ne doit être à sa place.
Pour (2) : situation : on a placé l'élément k (en n°1), on a placé un élément différent de 1 en k.
Maintenant il faut placer n-2 éléments de tel sorte que aucun ne soit à sa place, mais il y a un élément particulier : 1. En effet, sa place est déjà prise puisque k est à la place n°1.
Donc le problème revient à placer n-2 éléments sachant qu'il y en a un qui n'a pas de place ! Ce problème est différent de celui où il faut placer des éléments sachant que TOUS ont une place puisque maintenant un élément n'a pas de place interdite.
Regardons un exemple du problème pour 3 éléments : 1,2,3 et disons que 1 n'a pas de place, et dont qu'il peut aller n'importe où :
il y a 3 combinaisons où aucun élément n'est à sa place :
1 3 2
2 3 1
3 1 2
Alors que si on considère que 1 à une place, la place n°1, alors le nombre de configurations est 2 : 2 3 1 et 3 1 2.
On a bien un nombre différent de place suivant que tous les éléments ont une place interdite où qu'un des éléments n'a pas de place interdite.
Donc on note P(n) le nombre de configuration de n éléments où aucun n'est à sa place, sachant que chaque élément a une place.
Et on note Q(n) le nombre de configuration de n éléments où aucun n'est à sa place, sachant que n-1 éléments ont une place, et qu'un élément n'a aucune place.
( Remarque : il y a toujours n places, puisqu'il y a toujours n éléments à placer, cela veut dire qu'il y a en fait une place "libre" où tout le monde peut aller. )
Pour résumer P(n) = (1) + (2) = (n-1)*P(n-2) + (n-1)*(n-2)*Q(n-2)
On cherche maintenant une autre relation du même type sur Q(n).
Le problème : il y a n éléments et n places. Il a n-1 éléments qui ont une place interdite, 1 élément qui n'a aucune place interdite, et il y a donc une place qui peut accepter n'importe qui.
Soit A l'élément qui n'a pas de place interdite. Soit B le n° de la place où tout le monde peut aller.
Il y a encore 2 cas à distinguer :
(1) Si on place l'élément A à la place B, alors le problème revient à P(n-1).
(2) Si on ne place pas l'élément A à la place B (il y a n-1 choix différents), alors il y a toujours l'élément A qui n'a pas de place interdite et qui doit être placer quand même, donc le problème revient à Q(n-1).
D'où : Q(n) = (1) + (2) = P(n-1) + (n-1)*Q(n-1)
Finalement on a le système :
P(n) = (n-1)*P(n-2) + (n-1)*(n-2)*Q(n-2)
Q(n) = P(n-1) + (n-1)Q(n-1)
en simplifiant :
P(n) = (n-1)*Q(n-1)
Q(n) = (n-1)*Q(n-1) + Q(n-2)*(n-2) = P(n) + P(n-1)
puis finalement :
P(n) = (n-1)*P(n-1) + (n-1)*P(n-2)
Maintenant commence la démonstration : (juste du jeu d'écriture)
P(n) - n*P(n-1) = -P(n-1) + (n-1)*P(n-2) = - [ P(n-1) - (n-1)*P(n-2) ]
On pose A(n)= P(n) - n*P(n-1)
On a donc A(n) = -A(n-1)
On a A(2) = P(2) - 2*P(1), avec P(2)=1 et P(1)=0 cela donne A(2)=1
Donc par récurrence : A(n)=(-1)^n
Donc : A(n) = P(n) - n*P(n-1) = (-1)^n
On divise par n!
P(n)/n! = P(n-1)/(n-1)! + (-1)^n
On pose B(n) = P(n)/n!
On a donc : B(n) = B(n-1) + (-1)^n
Par récurrence : B(n) = Somme de k=0 à k=n de (-1)^k
Et puisque P(n) = n!*B(n) on a le résultat :
P(n) = n! * [ Somme de k=0 à k=n de (-1)^k ]
En espérant avoir été clair et concis
Donc on cherche le nombre de configuration où aucun élément n'est à sa place. On numérote les éléments de 1 à n, et 1 doit aller à la place 1, 2 à la place 2, etc
-Si on commence par placer un élément en 1, on a n-1 choix puisqu'il ne faut pas placer 1 en 1. On place l'élément k à la place n°1.
Maintenant il faut faire la différence entre 2 cas :
(1) -On place l'élément 1 à la place n°k
(2) -On ne place pas l'élément 1 à la place n°k
Pour (1) : on a donc permuter 1 et k, et le problème revient maintenant à chercher le nombre de configuration à n-2 éléments avec n-2 places où aucun élément ne doit être à sa place.
Pour (2) : situation : on a placé l'élément k (en n°1), on a placé un élément différent de 1 en k.
Maintenant il faut placer n-2 éléments de tel sorte que aucun ne soit à sa place, mais il y a un élément particulier : 1. En effet, sa place est déjà prise puisque k est à la place n°1.
Donc le problème revient à placer n-2 éléments sachant qu'il y en a un qui n'a pas de place ! Ce problème est différent de celui où il faut placer des éléments sachant que TOUS ont une place puisque maintenant un élément n'a pas de place interdite.
Regardons un exemple du problème pour 3 éléments : 1,2,3 et disons que 1 n'a pas de place, et dont qu'il peut aller n'importe où :
il y a 3 combinaisons où aucun élément n'est à sa place :
1 3 2
2 3 1
3 1 2
Alors que si on considère que 1 à une place, la place n°1, alors le nombre de configurations est 2 : 2 3 1 et 3 1 2.
On a bien un nombre différent de place suivant que tous les éléments ont une place interdite où qu'un des éléments n'a pas de place interdite.
Donc on note P(n) le nombre de configuration de n éléments où aucun n'est à sa place, sachant que chaque élément a une place.
Et on note Q(n) le nombre de configuration de n éléments où aucun n'est à sa place, sachant que n-1 éléments ont une place, et qu'un élément n'a aucune place.
( Remarque : il y a toujours n places, puisqu'il y a toujours n éléments à placer, cela veut dire qu'il y a en fait une place "libre" où tout le monde peut aller. )
Pour résumer P(n) = (1) + (2) = (n-1)*P(n-2) + (n-1)*(n-2)*Q(n-2)
On cherche maintenant une autre relation du même type sur Q(n).
Le problème : il y a n éléments et n places. Il a n-1 éléments qui ont une place interdite, 1 élément qui n'a aucune place interdite, et il y a donc une place qui peut accepter n'importe qui.
Soit A l'élément qui n'a pas de place interdite. Soit B le n° de la place où tout le monde peut aller.
Il y a encore 2 cas à distinguer :
(1) Si on place l'élément A à la place B, alors le problème revient à P(n-1).
(2) Si on ne place pas l'élément A à la place B (il y a n-1 choix différents), alors il y a toujours l'élément A qui n'a pas de place interdite et qui doit être placer quand même, donc le problème revient à Q(n-1).
D'où : Q(n) = (1) + (2) = P(n-1) + (n-1)*Q(n-1)
Finalement on a le système :
P(n) = (n-1)*P(n-2) + (n-1)*(n-2)*Q(n-2)
Q(n) = P(n-1) + (n-1)Q(n-1)
en simplifiant :
P(n) = (n-1)*Q(n-1)
Q(n) = (n-1)*Q(n-1) + Q(n-2)*(n-2) = P(n) + P(n-1)
puis finalement :
P(n) = (n-1)*P(n-1) + (n-1)*P(n-2)
Maintenant commence la démonstration : (juste du jeu d'écriture)
P(n) - n*P(n-1) = -P(n-1) + (n-1)*P(n-2) = - [ P(n-1) - (n-1)*P(n-2) ]
On pose A(n)= P(n) - n*P(n-1)
On a donc A(n) = -A(n-1)
On a A(2) = P(2) - 2*P(1), avec P(2)=1 et P(1)=0 cela donne A(2)=1
Donc par récurrence : A(n)=(-1)^n
Donc : A(n) = P(n) - n*P(n-1) = (-1)^n
On divise par n!
P(n)/n! = P(n-1)/(n-1)! + (-1)^n
On pose B(n) = P(n)/n!
On a donc : B(n) = B(n-1) + (-1)^n
Par récurrence : B(n) = Somme de k=0 à k=n de (-1)^k
Et puisque P(n) = n!*B(n) on a le résultat :
P(n) = n! * [ Somme de k=0 à k=n de (-1)^k ]
En espérant avoir été clair et concis
Modifié en dernier par sakd0 le sam. mars 24, 2007 11:18 am, modifié 3 fois.
- sakd0
- Passe sa journée ici. Et dort ici, aussi
- Messages : 811
- Enregistré le : sam. juil. 22, 2006 1:05 pm
- Localisation : Reims
Voilà la 2ème démonstration. Belle démonstration avec une matrice lol.
Par un MP* du Lycée Masséna (et avec un tout petit peu d'aide de ma part lol pour le tout début il avait oublier le 1 dans 1+[...] )
La 1ère égalité s'établit naturellement il suffit d'y réfléchir 2 minutes (peut-être 3 pour les moins habitués :p ).
On fixe n-k éléments parmi n, il y a donc n-k éléments à leur place, et on multiple par le P(k), c'est à dire qu'on multiplie par le nb de combinaison de k éléments où aucun n'est à sa place.
Et le nombre de combinaison possible de groupe de k éléments parmi n éléments est égale au nombre de combi de groupe de n-k éléments parmi n éléments. : [n-k parmi n]=[k parmi n]
Par un MP* du Lycée Masséna (et avec un tout petit peu d'aide de ma part lol pour le tout début il avait oublier le 1 dans 1+[...] )
La 1ère égalité s'établit naturellement il suffit d'y réfléchir 2 minutes (peut-être 3 pour les moins habitués :p ).
On fixe n-k éléments parmi n, il y a donc n-k éléments à leur place, et on multiple par le P(k), c'est à dire qu'on multiplie par le nb de combinaison de k éléments où aucun n'est à sa place.
Et le nombre de combinaison possible de groupe de k éléments parmi n éléments est égale au nombre de combi de groupe de n-k éléments parmi n éléments. : [n-k parmi n]=[k parmi n]
- g-kid
- Dr G-kid
- Messages : 2783
- Enregistré le : mer. mars 29, 2006 8:58 pm
- Localisation : île de la Réunion
- Contact :
Ca se rapproche du zéro.
Tu pourrais me montrer comment on obtient 14833 pour 8 mal placés en remplaçant les données des formules, en exemple pour m'entraîner.
"Je donne déjà la 1ère démonstration puisqu'il n'y a que de l'écriture. Il y a pas besoin de plus de connaissance que ça en math ou quoi, il y a juste besoin de temps pour bien comprendre.
Donc on cherche le nombre de configuration où aucun élément n'est à sa place. On numérote les éléments de 1 à 8, et 1 doit aller à la place 1, 2 à la place 2, etc
-Si on commence par placer un élément en 1, on a 8-1 choix puisqu'il ne faut pas placer 1 en 1. On place l'élément k à la place n°1. [...] "
Tu pourrais me montrer comment on obtient 14833 pour 8 mal placés en remplaçant les données des formules, en exemple pour m'entraîner.
"Je donne déjà la 1ère démonstration puisqu'il n'y a que de l'écriture. Il y a pas besoin de plus de connaissance que ça en math ou quoi, il y a juste besoin de temps pour bien comprendre.
Donc on cherche le nombre de configuration où aucun élément n'est à sa place. On numérote les éléments de 1 à 8, et 1 doit aller à la place 1, 2 à la place 2, etc
-Si on commence par placer un élément en 1, on a 8-1 choix puisqu'il ne faut pas placer 1 en 1. On place l'élément k à la place n°1. [...] "
- sakd0
- Passe sa journée ici. Et dort ici, aussi
- Messages : 811
- Enregistré le : sam. juil. 22, 2006 1:05 pm
- Localisation : Reims
bah oui voilà n=8 et dans la formule ça donne donc :
P(8) = 8! * [ [(-1)^0]/0! + [(-1)^1]/1! + [(-1)^2]/2! + [(-1)^3]/3! + [(-1)^4]/4! + [(-1)^5]/5! + [(-1)^6]/6! + [(-1)^7]/7! + [(-1)^8]/8 ] = 14833
tu met soit 2,3,4,5,6,7,8 à la place n°1
ensuite si tu a choisi 3 par exemple
- si tu met 1 a la place n°3, alors il faut placer les 6 élément restants 2,4,5,6,7,8 avec les 6 places restantes (chacun à une place interdite) donc le probleme revient à celui pour 6 éléments où chacun a une place interdite : j'ai appelé P(6) le nombre de combinaisons possibles de ce problème.
- par contre si tu ne met pas 1 à la place n°3 et que tu met soi 2,4,5,6,7,8
alors il te reste 6 places, 6 éléments à placer, sachant que 1 n'aura pas de place interdite.
Par exemple si tu met 2 a la place n°3
il te reste à placer 1,4,5,6,7,8, sur les places : 2,4,5,6,7,8.
Tu retrouves le probleme de 6 éléments et 6 places sachant qu'un élément n'a aucune place interdite : il s'agit de l'élément 1. Et il y a une place qui peut accepter n'importe qui : la place n°2.
J'ai appelé Q(6) le nombre de combinaisons possibles de ce problème
P(8) = 8! * [ [(-1)^0]/0! + [(-1)^1]/1! + [(-1)^2]/2! + [(-1)^3]/3! + [(-1)^4]/4! + [(-1)^5]/5! + [(-1)^6]/6! + [(-1)^7]/7! + [(-1)^8]/8 ] = 14833
tu met soit 2,3,4,5,6,7,8 à la place n°1
ensuite si tu a choisi 3 par exemple
- si tu met 1 a la place n°3, alors il faut placer les 6 élément restants 2,4,5,6,7,8 avec les 6 places restantes (chacun à une place interdite) donc le probleme revient à celui pour 6 éléments où chacun a une place interdite : j'ai appelé P(6) le nombre de combinaisons possibles de ce problème.
- par contre si tu ne met pas 1 à la place n°3 et que tu met soi 2,4,5,6,7,8
alors il te reste 6 places, 6 éléments à placer, sachant que 1 n'aura pas de place interdite.
Par exemple si tu met 2 a la place n°3
il te reste à placer 1,4,5,6,7,8, sur les places : 2,4,5,6,7,8.
Tu retrouves le probleme de 6 éléments et 6 places sachant qu'un élément n'a aucune place interdite : il s'agit de l'élément 1. Et il y a une place qui peut accepter n'importe qui : la place n°2.
J'ai appelé Q(6) le nombre de combinaisons possibles de ce problème
- sakd0
- Passe sa journée ici. Et dort ici, aussi
- Messages : 811
- Enregistré le : sam. juil. 22, 2006 1:05 pm
- Localisation : Reims
soit P(n) est le nombre de configurations de n éléments où aucun élément n'est à sa place alors P(n)/n! = exp(-1) = .3678794412, c'est à dire que P(n) représente plus du tiers du nombre de configuration possible.
En bref, la proportion de combinaison où aucun élément n'est à sa place par rapport au nombre totale de combinaison est une constante !
En bref, la proportion de combinaison où aucun élément n'est à sa place par rapport au nombre totale de combinaison est une constante !