Inscription / Connexion Nouveau Sujet
Niveau autre
Partager :

PCSI - Devoir Maison

Posté par WEAZEDS (invité) 26-01-05 à 19:40

Bonsoir, je voulais demander votre aide pour ce devoir.
Ex3;
Soit un entier n1. On appelle permutation de l'ensemble En:={1,...,n}tout application bijective de En dans lui même.

(1) Combien y a-t-il de permutations de En?
Nous dirons qu'une permutation de En est concave s'il existe k {2,...,n-1} tel que
(i) < (i+1) si 1i<k
(i)>(i+1) si ki<n.

Nous dirons que k est la cime de f. Clairement f(k)=n.

(2) Combient y a-t-il de permutations concaves de E4?

(3) Soit k{2,...,n-1}. Montrer qu'il existe (\array{\ n-1 \\ k-1 }\) permutations concaves de En ayant k comme cime.

(4) En déduire le nombre de permutations concaves de En. Verifier que le résultat est cohérent avec le nombre trouvé en (1)!

__________
Merci

Posté par
franz
re : PCSI - Devoir Maison 27-01-05 à 00:01

1/
Card E_n=n!

2/
(4321)                   de sommet 1
(1432)(2431)(3421)  de sommet 2
(1243)(1342)(2341)  de sommet 3
(1234                    de sommet 4

soit 8 permutations concaves

3/
Comme tu l'as juducieusement remarqué l'image de k est  n.
Choisir un permutation concave de sommet k revient à choisir k-1 entiers parmi n-1 qui sont les images des k-1 entiers de 1 à k-1.
Pour qu'ils vérifient \sigma(i)<\sigma(i+1) ,\;\forall i \in [[1,k-1]], il faut les classer dans l'ordre croissant. Il n'y a qu'une possibilité.

De la même façon les images des entiers de k+1 à n sont les n-k entiers "laissés sur la touche" (car \sigma est un bijection). Il faut classer ces n-k entiers dans l'ordre décroissant à partir de k (1 possibilité)

Au final, il y a donc \(\array{n-1\\ \vspace{5}} \\k-1 \) permutations concaves distinctes.

4/
Card({\rm concaves}) = \Bigsum_{k=1}^n \(\array{n-1\\ \vspace{5} \\k-1} \)= \Bigsum_{j=0}^n\ (\array{n-1\\ \vspace{5} \\j} \)\,1^j\,1^{n-1-j} = 2^{n-1}

Posté par WEAZEDS (invité)re : PCSI - Devoir Maison 28-01-05 à 19:34

je te remercie pour les expliquations FRANZ.tchao.Pass un bon week-end.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1510 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !