Exo de TS: nombre de permutations convenables

[involutive]

Bonsoir tout le monde!

Je suis en terminale S et j'ai un exercice où j'ai beaucoup cherché, sans succès... Est-ce que quelqu'un pourrait me donner une piste pour le commencer? ça serait vraiment gentil...

Voilà l'énoncé:
"Soit n entier naturel non nul. On dit qu'une permutation (x₁, ..., x_2n) de l'ensemble des entiers compris entre 1 et 2n est convenable s'il existe au moins un i compris entre 1 et 2n - 1 tel que |x_i+1 - x_i| = n.
Démontrer qu'il y a strictement plus de permutations de l'ensemble des entiers compris entre 1 et 2n convenables que de permutations qui ne le sont pas.
Indication: On pourra introduire pour i entier compris entre 1 et 2n - 1 l'ensemble Ai des permutations (x₁, ..., x_2n) de l'ensemble des entiers compris entre 1 et 2n telles que |x_i+1 - x_i| = n."

Merci à tous de votre aide!
-----

[Tryss]

As tu calculé le cardinal de Ai ?

Ensuite on peut remarquer que l'ensemble des permutations convenables est égal à l'union des Ai (par contre attention, cette union n'est pas disjointe)

Puis, on peut regarder ici : http://fr.wikipedia.org/wiki/Princip...sion-exclusion

[PlaneteF]

Bonsoir,

Ce qui peut aussi t'aider c'est de voir ce qui se passe en prenant un cas concret, par exemple , ... et en explicitant , etc ...

Cordialement

[involutive]

Bonjour!
Merci à tous les deux pour vos réponses!

Oui je connais le cardinal de l'union des A_i avec la formule du crible, on l'a vue en cours, et j'ai aussi démontré cette inégalité:

Mais je ne vois pas comment le lien entre le deuxième membre de cette inégalité et la question...

J'ai essayé de prendre n=2, mais les valeurs des x_i sont arbitraires, donc je n'arrive pas tellement à me représenter A_i (autrement que sur un ensemble dessiné, comme pour la formule du crible).

[A voir en vidéo sur Futura]

[Tryss]

En fait le plus simple pour calculer le cardinal de Ai c'est :

- choisir un nombre a en position i
- le nombre en position i+1 est alors fixé (soit c'est a+n, soit a-n selon si a > n ou pas)
- choisir la position des 2n-2 autres nombres

Pour Ai inter Aj, c'est le même principe, ( il faut quand même traiter à part le cas j = i+1)

[involutive]

En fait le plus simple pour calculer le cardinal de Ai c'est :

- choisir un nombre a en position i
- le nombre en position i+1 est alors fixé (soit c'est a+n, soit a-n selon si a > n ou pas)
- choisir la position des 2n-2 autres nombres

Pour Ai inter Aj, c'est le même principe, ( il faut quand même traiter à part le cas j = i+1)

Mais si on a l'égalité dont j'ai parlé, je ne vois pas pourquoi il faut calculer le cadinal des A_i, et la somme des cardinaux des A_i inter A_j... pour moi il fallait peut-être faire le lien entre cette inégalité et l'énoncé (lien que je ne vois pas d'ailleurs...) parce que si on indentifiait A_i avec les données de l'énoncé, on n'aurait plus qu'à poser l'inégalité (déjà démontrée précédemment) et ça répondrait à la question... Mon problème c'est surtout que je ne vois pas le lien entre l'inégalité que j'avais mise en latex dans mon précédent message et l'énoncé de l'exercice...

Merci en tout cas de votre aide!

[Tryss]

Ai c'est l'ensemble des permutations convenables tel que |xi+1 - xi| = n

Toi tu veux le cardinal de l'ensemble de toutes les permutations convenables : il suffit de faire l'union des Ai pour toutes les avoir (et seulement celles ci)

[involutive]

Oui donc pour calculer le cardinal de l'ensemble des A_i convenables, on peut utiliser la formule du crible, puis pour calculer le cardinal de l'ensemble des permutations qui ne sont pas convenables, on peut faire:
2n! - card (U A_i)
car 2n! est le cardinal de l'ensemble des permutations de l'ensemble des entiers de 1 jusqu'à 2n.

Mais après pour prouver qu'il y a strictement plus de permutations convenables que de permutations pas convenables, il faudrait prouver que 2card (U A_i) - 2n! > 0 et je ne vois pas comment faire...

P.S.: dans ce message j'ai noté card (U A_i) le cardinal de l'union des A_i