Combinatoire (involutions)

Aide à la résolution d'exercices ou de problèmes de niveau Supérieur.

Modérateur: gdm_aidesco

Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Ne poster qu'un exercice (ou problème) par sujet et indiquer son niveau précis dans le titre du message.

Re: Combinatoire (involutions)

Messagepar paspythagore » Mercredi 09 Mars 2011, 22:27

Merci, cela veut dire que j'ai pris le problème à l'envers : il suffit de considérer $E\setminus \{x, f(x)\}$ et dire que par hypothèse, il y a un point fixe par une involution sur cet ensemble ?

Pour $k+1, n=2k+3$. Soit $x$ tel que $f(x)\neq x$. Considérons $E\setminus \{x, f(x)\}$. Son cardinal est $2k+1$ et par hypothèse, l'involution sur ce sous-ensemble possède un point fixe, donc l'involution sur $E$ aussi.

Pour vérifier que la restriction de $f$ à $E' = E \setminus \{x,f(x)\}$ est une application de $E'$ dans lui-même, je ne vois pas. Il existe une application de $E'$ dans lui même car il existe une existe une application qui associe un élément à chaque élément de $E'$ ?
paspythagore
Exa-utilisateur
 
Messages: 2287
Inscription: Mercredi 19 Novembre 2008, 15:35
Statut actuel: Post-bac

Publicité

Re: Combinatoire (involutions)

Messagepar balf » Jeudi 10 Mars 2011, 20:54

Il suffit de vérifier que si x' $\neq$ x, f(x), alors f(x') $\neq$ x, f(x). Ne pas oublier que, entre autres, une involution est bijective.

B.A.
balf
Zetta-utilisateur
 
Messages: 3847
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Combinatoire (involutions)

Messagepar paspythagore » Vendredi 11 Mars 2011, 09:31

Mais une involution est définie sur $E'$ par :
$f(x)= y \Longleftrightarrow x=y$ ou $y=f(x)$ et on a démontrer que cette relation est bijective, $y$ a un unique antécédent.

$f$ ne peut être qu'une application de $E'$ dans lui même ?
paspythagore
Exa-utilisateur
 
Messages: 2287
Inscription: Mercredi 19 Novembre 2008, 15:35
Statut actuel: Post-bac

Re: Combinatoire (involutions)

Messagepar balf » Vendredi 11 Mars 2011, 12:00

Là, vous mélangez l'involution (l'application f) et la relation d'équivalence associée. La restriction f' de f à E', a priori, est une application de E' dans E. Pour que ce puisse être une involution de E', il faut vérifier que f' arrive bien dans E'.

B.A.
balf
Zetta-utilisateur
 
Messages: 3847
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Combinatoire (involutions)

Messagepar paspythagore » Vendredi 18 Mars 2011, 22:37

Bonjour,
je ne suis pas à l'aise du tout :

Soit $x'\neq x, f(x)$ alors $f(x')=x'\neq x, f(x)$

ou $y'=f(x')\neq x'$, comme $f$ est bijective $f(y')=x'$ donc $f(x')\neq x, f(x)$

Donc $x' \neq x, f(x), \Rightarrow f(x') \neq x, f(x)$

La restriction de $f$ à $E\setminus \{x, f(x)\}$ est donc une application de :$E\setminus \{x, f(x)\}$ dans lui même et comme son cardinal est $2k+1$ et par hypothèse, l'involution sur ce sous-ensemble possède un point fixe, donc l'involution sur $E$ aussi.
paspythagore
Exa-utilisateur
 
Messages: 2287
Inscription: Mercredi 19 Novembre 2008, 15:35
Statut actuel: Post-bac

Re: Combinatoire (involutions)

Messagepar paspythagore » Samedi 19 Mars 2011, 09:44

Bonjour,

je reprends.

Supposons que $n = 2k + 1$ soit impair. En utilisant le résultat de la question 2,
montrer que toute involution d'un ensemble de cardinal impair admet un point fixe.
Que vaut $I_{2k+1}$?


Une involution sans point fixe est simplement une partition de $E$ en parties à deux éléments, où l'un est $x$, l'autre est $f(x)$ (et réciproquement). Si $n$ est impair, il y a donc un point fixe, on a alors $I_{2k+1}=0$

Récurrence

Si $k=0, n=1$ et $I_1=0$

Supposons que pour $k\neq 0$ le nombre d'involutions possibles dans l'ensemble $E$ soit $I_{2k+1}=0$, ce qui veut dire que toute involution d'un ensemble de cardinal $2k+1$ possède un point fixe.

Pour $k+1, n=2k+3$. Choisissons un couple $\{x, f(x)\}$ avec $x\neq f(x)$ et considérons :$E\setminus \{x, f(x)\}$.

Soit $x'\neq x, f(x)$ alors $f(x')=x'\neq x, f(x)$ avec $x', f(x')\in E\setminus \{x, f(x)\}$.

ou $y'=f(x')\neq x'$, comme $f$ est bijective $f(y')=x'$ donc $f(x')\neq x, f(x)$

Donc $x' \neq x, f(x), \Rightarrow f(x') \neq x, f(x)$

La restriction de $f$ à $E\setminus \{x, f(x)\}$ est donc une application de :$E\setminus \{x, f(x)\}$ dans lui même et comme son cardinal est $2k+1$ et par hypothèse, l'involution sur ce sous-ensemble possède un point fixe, donc l'involution sur $E$ aussi.


Questions suivantes :
Supposons $n=2k$ soit pair.Trouver une involution de $[1,2k]$ qui soit sans point fixe. En déduire $I_{2k}\geq 1$.

$\left \{ \begin{array}{cc} f(x)=x+1 &\text{ si }x\text {est impair } \\f(x)=x-1 &\text{ si }x\text {est pair } \end{array} \right.$
Donc il existe au moins une involution si $n=2k$ est pair.

Montrer que pour tout $^k\geq 1$, on a $\I_{2(k+1)}=(2k+1)I_{2k}$.

Si $n=2(k+1)=2k+2$, on a $2$ éléments distincts de plus,
Soit ils sont en relation l'un avec l'autre et on a $I_{2k}$ involutions,
soit il y a $2k$ relations possibles en les arrangeant avec les $2k$ éléments restants.
Donc : $I_{2(k+1)}=(2k+1)I_{2k}$

En déduire que pour tout $k\geq 1$, on a :
$I_{2k}=\dfrac{(2k)!}{2^k(k!)}$


Par récurrence :
Initialisation : si $k=1, I_2=\dfrac{2!}{2!(1!)}=1$, la proposition est vraie.
Hypothèse : supposons la relation vraie pour $2k$ : $I_{2(k+1)=(2k+1)I_{2k}$
Récurrence : pour $n=2(k+1)$, on a $I_{2(k+1)}=(2k+1)I_{2k}$

$=(2k+1)\dfrac{(2k)!}{2^k(k!)}$

$=\dfrac{(2k+1)!}{2^k(k!)}$

En multipliant numérateur et dénominateur par $2k+2=2(k+1)$, on obtient :

$I_{2(k+1)}=\dfrac{(2k+2)!}{2^{k+1}(k+1)!}$

Ce qui est vrai par hypothèse, donc : pour tout $k\geq 1$, on a :
$I_{2k}=\dfrac{(2k)!}{2^k(k!)}$
Dernière édition par paspythagore le Samedi 19 Mars 2011, 21:02, édité 1 fois.
paspythagore
Exa-utilisateur
 
Messages: 2287
Inscription: Mercredi 19 Novembre 2008, 15:35
Statut actuel: Post-bac

Re: Combinatoire (involutions)

Messagepar balf » Samedi 19 Mars 2011, 20:48

Bonsoir,
Soit
$x'\neq x, f(x)$, alors $f(x')=x'\neq x, f(x)$" avec $x', f(x')\in E\setminus \{x, f(x)\}$.

Évitez l'usage de "avec", qui ne veut rien dire ici. 'Donc' va très bien. Et surtout, il faut dire : alors, soit f(x')=x'... Il ne résulte pas du fait que x' $\neq$ x,f(x) que f(x')=x' ;ce n'est qu'une des possibilités.
ou $y'=f(x')\neq x'$, comme $f$ est bijective ...

C'est "soit" plutôt que "ou" (il s'agit d'une alternative), et la suite résulte du fait que f est une involution, pas qu'elle est bijective.

Question suivante : vous oubliez de dire pourquoi elle est sans point fixe (c'est clair, encore faut-il le dire).

Relation de récurrence : vous n'avez pas énuméré toutes les possibilités : si les éléments supplémentaires ne s'échangent pas entre eux, ils s'échangent avec des éléments des 2k initiaux, mais pas n'importe comment (ils ne peuvent s'échanger avec le même élément). Il faut compter le nombre d'injections d'un ensemble à 2 éléments dans un ensemble à 2k éléments.

Quant à la récurrence proprement dite, vous avez oublié les $ ... $, et elle est pratiquement incompréhensible.

B.A.
balf
Zetta-utilisateur
 
Messages: 3847
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Combinatoire (involutions)

Messagepar paspythagore » Samedi 19 Mars 2011, 23:08

Bonsoir,

je ne comprends pas :

Question suivante : vous oubliez de dire pourquoi elle est sans point fixe (c'est clair, encore faut-il le dire).


si les éléments supplémentaires ne s'échangent pas entre eux, il faut compter le nombre d'injections d'un ensemble à 2 éléments dans un ensemble à 2k éléments.




Si $n=2(k+1)=2k+2$, on a $2$ éléments distincts de plus,
Soit ils sont en relation l'un avec l'autre et on a $I_{2k}$ involutions,
soit, ils ne sont pas en relation et on a $\dfrac{(2k)!}{(2k-2)!}=(2k)(2k-1)$ involutions.
paspythagore
Exa-utilisateur
 
Messages: 2287
Inscription: Mercredi 19 Novembre 2008, 15:35
Statut actuel: Post-bac

Re: Combinatoire (involutions)

Messagepar balf » Dimanche 20 Mars 2011, 01:25

Ce que vous ne comprenez pas : vous cherchez bien les involutions sans point fixe ?

Je suis d'accord sur les $I_2k$ involutions (ça mérite d'être détaillé). Mais je ne comprends pas la fin (si les éléments supplémentaires ne sont pas en relation). Ce que vous calculez, c'est la nombre d'injections d'un ensemble à 2 éléments dans un ensemble à 2k éléments.

B.A.
balf
Zetta-utilisateur
 
Messages: 3847
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Combinatoire (involutions)

Messagepar paspythagore » Dimanche 20 Mars 2011, 15:16

Montrer que pour tout $k\geq 1$, on a $\I_{2(k+1)}=(2k+1)I_{2k}$.

Si $n=2(k+1)=2k+2$, on a $2$ éléments distincts de plus $(x, y)$,
Soit ils sont toujours en relation l'un avec l'autre ($f(x)=y$) quelle que soit l'involution $f$ choisie pour les $2k$ éléments restants : on a donc $I_{2k}$ involutions,
soit, ils ne sont pas en relation. Pour le premier élément il peut être en relation avec les $2k$ autres et il reste $I_{2k}$ solutions pour les $2k$ éléments restants.

Il y a en tout : $I_{2k}+2kI_{2k}= (2k+1)I_{2k}$ involutions possibles pour $2(k+1)$ éléments.
paspythagore
Exa-utilisateur
 
Messages: 2287
Inscription: Mercredi 19 Novembre 2008, 15:35
Statut actuel: Post-bac

Re: Combinatoire (involutions)

Messagepar balf » Dimanche 20 Mars 2011, 18:24

C'est que, justement, si l'un des 2k éléments est associé à l'un des deux nouveaux éléments, ce qui reste, c'est 2k-1 éléments, parmi lesquels il faut choisir l'image du second des nouveaux éléments, ce qui fait qu'il en reste ...

B.A.
balf
Zetta-utilisateur
 
Messages: 3847
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Combinatoire (involutions)

Messagepar paspythagore » Dimanche 20 Mars 2011, 23:23

C'est que, justement, si l'un des 2k éléments est associé à l'un des deux nouveaux éléments, ce qui reste, c'est 2k-1 éléments, parmi lesquels il faut choisir l'image du second des nouveaux éléments, ce qui fait qu'il en reste ...


$2k$
paspythagore
Exa-utilisateur
 
Messages: 2287
Inscription: Mercredi 19 Novembre 2008, 15:35
Statut actuel: Post-bac

Re: Combinatoire (involutions)

Messagepar balf » Lundi 21 Mars 2011, 11:04

Non : 2k-2.

B.A.
balf
Zetta-utilisateur
 
Messages: 3847
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Combinatoire (involutions)

Messagepar paspythagore » Lundi 21 Mars 2011, 21:32

Bonsoir.

Il reste $2k-2$ éléments une fois qu'on a associé les deux nouveaux éléments. Combien cela fait il d'involution sans point fixe ?
Si $x$ et $y$ sont les deux nouveaux éléments et qu'on les associe avec $x'$ et $y'$, cela fait une manière de les associer, sachant que $x$ peut être associé de $2k$ façons différentes et $y$ de $2k-1$ façons. Cela fait $2k\cdot (2k-1)$ façons et il reste $2k-2$ éléments. Mais alors comment arriver à $2k\cdot I_{2k}$ ?
Pourquoi ne peut on partir de l'ensemble à $2k$ éléments des éléments qui nous restent une fois associé le premier élément nouveau pour dire que l'on $2k$ façons d'associer le premier élément nouveau et qu'il y a $I_{2k}$ façons d'arranger les $2k$ éléments restants ?
paspythagore
Exa-utilisateur
 
Messages: 2287
Inscription: Mercredi 19 Novembre 2008, 15:35
Statut actuel: Post-bac

Re: Combinatoire (involutions)

Messagepar paspythagore » Samedi 26 Mars 2011, 14:57

Je ne comprends pas.

Montrer que pour tout $k\geq 1$, on a $\I_{2(k+1)}=(2k+1)I_{2k}$.

Si $n=2(k+1)=2k+2$, on a $2$ éléments distincts de plus $(x, y)$,
Soit ils sont toujours en relation l'un avec l'autre ($f(x)=y$) quelle que soit l'involution $f$ choisie pour les $2k$ éléments restants : on a donc $I_{2k}$ involutions,
soit, ils ne sont pas en relation. Si $x$ et $y$ sont les deux nouveaux éléments et on les associe avec $x'$ et $y'$, cela fait une manière de les associer, sachant que $x$ peut être associé de $2k$ façons différentes et qu'il reste $2k-1$ éléments plus $y'$, c'est à dire $2k$ éléments. Le sous-ensemble $[1,2(k+1)]\setminus \{x, x'\}$ a $2k$ éléments, il y $I_{2k}$ involutions sans point fixe sur l"ensemble $[1,2(k+1)]\setminus \{x, x'\}$

Il y a en tout : $I_{2k}+2kI_{2k}= (2k+1)I_{2k}$ involutions possibles pour $2(k+1)$ éléments.
paspythagore
Exa-utilisateur
 
Messages: 2287
Inscription: Mercredi 19 Novembre 2008, 15:35
Statut actuel: Post-bac

Re: Combinatoire (involutions)

Messagepar balf » Samedi 26 Mars 2011, 16:39

Eh bien voilà ! C'est parfait.

B.A.
balf
Zetta-utilisateur
 
Messages: 3847
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Combinatoire (involutions)

Messagepar paspythagore » Samedi 26 Mars 2011, 18:01

Merci.

En déduire que pour tout $k\geq 1$, on a :
$I_{2k}=\dfrac{(2k)!}{2^k(k!)}$

Par récurrence :
Initialisation : si $k=1, I_2=\dfrac{2!}{2!(1!)}=1$, la proposition est vraie.

Hypothèse : supposons la relation vraie pour $2k$ : $I_{2k}=\dfrac{(2k)!}{2^k(k!)}$

Récurrence : pour $n=2(k+1)$, on a $I_{2(k+1)}=(2k+1)I_{2k}$

$=(2k+1)\dfrac{(2k)!}{2^k(k!)}$

$=\dfrac{(2k+1)!}{2^k(k!)}$

En multipliant numérateur et dénominateur par $2k+2=2(k+1)$, on obtient :

$I_{2(k+1)}=\dfrac{(2k+2)!}{2^{k+1}(k+1)!}=\dfrac{(2(k+1))!}{2^{k+1}(k+1)!}$

La propriété $I_{2k}=\dfrac{(2k)!}{2^k(k!)}$ est donc vraie pour $k\geq 1$.
paspythagore
Exa-utilisateur
 
Messages: 2287
Inscription: Mercredi 19 Novembre 2008, 15:35
Statut actuel: Post-bac

Re: Combinatoire (involutions)

Messagepar balf » Samedi 26 Mars 2011, 18:52

C'est bon.

B.A;
balf
Zetta-utilisateur
 
Messages: 3847
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Combinatoire (involutions)

Messagepar paspythagore » Samedi 26 Mars 2011, 20:44

Merci balf.

Si vous avez un peu de temps pour regarder mes deux autres messages, je vous en remercie d'avance.
paspythagore
Exa-utilisateur
 
Messages: 2287
Inscription: Mercredi 19 Novembre 2008, 15:35
Statut actuel: Post-bac

Précédente

Retourner vers Exercices et problèmes : Supérieur

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 7 invités