Inscription / Connexion Nouveau Sujet
Permutations
Bon voilà un des problèmes du dm que j'ai à faire te j'y comprends vraiment rien déja que mes pergormances sur les deux autres exos ne sont pas brillantes si quelqu'un pourrait m'aider à rendre un devoir potable ça serait sympa.
On considère un entier n supérieur ou égal à 1.on note S(n) l'ensemble de toutes les permutations de [| 1;n |].On dit que i
[| 1;n |] est un point fixe de la permutation 
appartenant à S(n) si (i)=i.
On dit qu'une permutation est un dérangement quand elle n'a aucun point fixe.
1.Pour i [| 1;n |], on note Ai l'ensemble des permutations de S(n) ayant i pour point fixe.
Déterminer Card(Ai) puis Card(Ai1
Ai2...Aik) où 1
i1<i2<...<ikn.
2. on note D(n) l'ensemble des dérangements de [|1;n|].
a) Exprimer D(n) à l'aide des ensemble Ai.
b) En déduire que le nombre de dérangements de [|1;n|] noté d(n) vérifie : d(n)=n!
(k=0 à n) (-1)k/k!.
c)Ecrire un programme en Pascal calculant et affichant d(n)/n! pour n entré au clavier par l'utilisateur.
d) que représente d(n)/n!? Calculer si ele existe sa limite.
3.Pour 0pn, on note Fnp le nombre de permutations de [|1;n|] ayant exactement p points fixes.
ExprimerFnp à l'aide de d(n-p).En déduire son expression.
Bon je suis vraiment bloquée pour cette exo.
Au départ pour la question 1 je me sus dit que Card(Ai)=n mais après réflexion je me suis dit que c'était faux parce que sinon ça voudrait dire que que tous les éléments de [|1;n|] ont des points fixes.Bref je suis perdue.
Merci d'avance pour votre aide.
Bonjour,
1) les permutations laissant i fixe sont les permutations sur l'ensemble [1,n]
- {i} . Donc Card(Ai)=(n-1)!
On doit ensuite choisir k points parmi n qu'on laissera fixe. Les permutations laissants ces k points fixes sont les permutations des n - k restants. Donc Card(Ai1Ai2...Aik) = .(n-k)!
2 a) Vois-tu une relation très simple entre D(n) et les ensembles Ai ?
Pour satisfaire ma curiosité, où étudie-t-on encore le Pascal ?
Ah je ne voyais pas comme ça la question 1.en fait ce que je n'avais pas saisi c'est qu'on choisis les points fixes moi jpensais que c'était tous des points fixes.
Pour le 2. j'y avait déjà un peu réfléchi avant et j'ai dit que Dn = A1(barre)...An-1(barre)An(barre)=[A1
...An-1An](barre)
Je ne sais pas si vous allez comprendre avec les barres mais c'est le seul moyen que j'ai trouvé je ne sais pas comment les faire ici.
et pour répondre à votre question oui nous travaillons sur le Pascal et il arrive très souvent aux concours qu'on nous demande d'écrire un programme en pascal pour calculer qq chose pour mon plus grand malheur
.
Oui,
Dn =
Le nombre de dérangement est donc :
Dn = n! - card()
Pour calculer ce cardinal, une seule façon de faire : formule du crible.
ce sujet m'intéresse, merci pour ton aide Fradel. Cependant je ne comprends pas pourquoi tu dis qu'il faut "choisir k points parmi n qu'on laissera fixe", les points sont déjà choisis, je crois qu'il n'y a donc qu'à dénombrer les permutations de ces k points, soit (n-k)! ?
Sinon je ne comprends pas pourquoi on ne choisit pas le premier point fixe i, on aurait alors card(Ai)=(n-1)!.C(n,1)=(n-1)!.n= n! ?
Ensuite pour la formule du crible j'avais bien fait comme ça mais je ne comprends pas comment arriver au résultat attendu... j'ai toujours le "n!-" devant ma formule du crible ?
merci d'avance
En fait je viens de me rendre compte qu'on pouvait intégrer le premier n! à la somme en initialisant à 0, mais pour les questions du dessus je ne vois toujours pas.
Bonsoir clem 12
On doit ensuite choisir k points parmi n qu'on laissera fixe. Les permutations laissants ces k points fixes sont les permutations des n - k restants. Donc Card(Ai1
Ai2...Aik) = C'est une erreur d'écriture
: en effet,
Card(Ai1
Ai2...Aik) = (n-k)!
car les éléments i1, ... , ik sont fixés ; c'est la relation demandée dans l'énoncé. Il s'agit ici du nombre de permutations laissants fixes les points i1, ... , ik.
Mais on a :
Ai2...Aik) = Cette somme est le nombre de premutations laissant k points fixes. Cette relation est très utile pour la formule du crible.
ah là on est d'accord 
!
et dis moi, si on voulait calculer le nombre de possibilités pour qu'il y ait au moins un point fixe, on se ramène simplement à des surjections et on a n^n ?
euh! des surjections de quoi dans quoi ?
En fait, les permutations ayant au moins un point fixe, c'est des permutations qui ne sont pas des dérangements ; leur nombre est donc
n! - Dn = card()
en posant, comme ci-dessus, Dn le nombre d'éléments de D(n).
Annuler
connectez vous
algèbre en post-bac