Nombre d'involutions
Bonsoir,
Pour tout ensemble $E$ fini, de cardinal $n \geq 1$, on note $u_n$ le nombre d'involutions de $E$, c'est-à-dire d'applications $f$ de $E$ dans $E$ telles que $f \circ f=Id_E$
Pour $n=1$, il y en a une seule car $f = Id_E$ mais je bloque pour $n=2$ et $n=3$.
Pour tout ensemble $E$ fini, de cardinal $n \geq 1$, on note $u_n$ le nombre d'involutions de $E$, c'est-à-dire d'applications $f$ de $E$ dans $E$ telles que $f \circ f=Id_E$
Pour $n=1$, il y en a une seule car $f = Id_E$ mais je bloque pour $n=2$ et $n=3$.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Mais dans un manuel de 2nd, très certainement !
Seigneur, je prie pour que tu ne parviennes jamais au lycée !
Les deux sont involutives. $f_1 \circ f_1 (a)=f_1 (b)=a$
Réponse : il y en a $2$ pour $n=2$.
Dans le cas général je ne comprends rien même au corrigé qui fixe $a$ dans $E$ et qui considère $f(a)=a$ ou $f(a)=b \ne a$ je ne comprends pas ça sert à quoi de faire ça.
À établir une formule de récurrence, je pense.
On a le choix de ce que fait f. Mais pas le choix de ce que fait fof. Donc, si tu pars d'une valeur a,
- soit f(a)=a, et c'est gagné puisque f(f(a))=f(a)=a.
- soit f(a)=c, et nécessairement, on définit f(c)=a pour que fof=Id. On ne définit pas 1 image pour 1 antécédent, mais 2 images pour 2 antécédents.
Tu comprends donc que ton ensemble E va s'organiser en 2 groupes. Le groupe des singletons que f renvoie sur eux-mêmes, et le groupe des couples d'éléments que f envoie l'un sur l'autre.Donc, combien de possibilités ?
Je trouve la formule suivante :
$\displaystyle q(n)=\sum_{k=0}^{E(\frac n 2)}\frac 1 {2^kk!}A_n^{2k}$
Où q est la quantité d'involutions (pour l'ensemble E avec n éléments)
k, le nombre de couples
E(x), la partie entière
$q(1)=\frac 1 {2^00!}A_1^{0}=1$
$q(2)=\frac 1 {2^00!}A_2^{0}+\frac 1 {2^11!}A_2^{2}=1+1=2$
$q(3)=\frac 1 {2^00!}A_3^{0}+\frac 1 {2^11!}A_3^{2}=1+3=4$
etc
PS: je ne connaissais pas la bonne réponse a priori.
Qu'est-ce que tu ne comprends pas dedans ?
Je ne comprends pas pourquoi si $f(a)=a$ il y a $u_{n+1}$ involution $f$ de ce type.
Je ne comprends pas pourquoi on fait des restrictions pour dénombrer le nombre d'involution dans les deux cas.
Deuxième question : je ne te comprends pas. Qu'appelles-tu "faire des restrictions" ???
Si, en revanche, il est en couple, il faut lui trouver un partenaire.
On peut toujours trouver une formule par récurrence ou une formule générale. Le fait de restreindre permet de trouver la formule par récurrence.
Je ne comprends pas mieux qu'avec le corrigé.
@Gabuzomeu
$u_{n+1}$ est le nombre d'involutions dans un ensemble fini de cardinal $n+1$.
$E \backslash \{a\}$ possède $n+1$ éléments.
La dernière question c'est ce que je n'ai pas compris. Comment on trouve $u_{n+1}$ pour le premier cas ?
Comment on compte le nombre d'involutions tel que $f(a)=a$ ?
C'est pourtant la clé pour comprendre pourquoi on trouve $u_{n+1}$ pour le premier cas.
En informatique, on appelle cela du débugage. Il faut resserrer autour du détail qui pose problème. Et tu ne le fais pas puisque tu envoies tout balader en disant "je n'ai pas compris". On ne te demande pas de comprendre, mais de mettre en défaut les raisonnements qui te sont proposés.
Tu n'as que deux possibilités pour que fof soit involutif. "a" est seul : f(a)=a. OU ALORS f(a)$\neq$a mais f(f(a))=a, et "a" est en couple avec f(a). Que ne comprends-tu pas la-dedans ?
question 1 (Q1): compter tous les entiers qui ont une propriété P et qui sont pairs.
question 2 (Q2): compter tous les entiers qui ont cette même propriété P et qui sont impairs.
question 3 (Q3): En déduire le nombre d'entiers qui ont cette propriété P.
Ici, on a guidé l'élève, on lui a dit de compter 2 sous-groupes, puis de faire la somme. Parce que, on a bien pris soin de créer 2 sous-groupes disjoints.
Pour cette même propriété P, imaginons maintenant l'exercice suivant.
Question : Compter le nombre d'entiers P qui ont cette propriété P
L'élève peut se dire : je vais prendre une initiative. Je vois bien que compter les entiers pairs qui ont cette propriété, c'est facile. Et compter les entiers impairs qui ont cette propriété P, c'est facile aussi. Il ne restera qu'à faire la somme.
Dans ton exercice, c'est pareil.
Il y a uniquement la question 'finale' (Q3), sans les indications (Q1 et Q2).
Et dans le corrigé, on a cette décomposition en Question1 , puis Question 2, puis Somme.
Si l'énoncé était le suivant, tu comprendrais mieux :
Dans l'exercice du livre, il y a uniquement la dernière ligne : trouver une relation de récurrence sur u(n).
On ne guide pas l'élève, c'est à lui de prendre l'initiative de parler des 2 suites v et w .. ...
Tu parles de RESTRICTIONS. Non, ce ne sont pas des restrictions, c'est une partition en 2 univers, chacun plus simple à traiter.
J'ai bien compris que l'ensemble des involutions qui vérifient $f(a)=a$ et celles qui vérifient $f(a) \ne a$ forment une partition de l'ensemble des involution car $f$ est bijective.
On peut donc sommer les cardinaux des deux ensembles.
Mon problème c'est que je ne comprends pas comment compter le nombre d'involution qui vérifient $f(a)=a$ .
Mon souci ne se situe pas dans la décomposition du problème mais dans le "comptage" des éléments, c'est toujours ça qui me pose problème.
@Petitlutin
Pourquoi si $f(a)=a$ il y a $u_{n+1}$ involutions ?
Il faut pas multiplier $u_{n+1}$ par $n+2$ ? Il y a pas $n+2$ choix pour $f(a)=a$ ?
@PLM est ce que tu peux expliquer un peu ta formule générale $q(n)$. Comment tu l'as eue ?
$a$ est fixé.
On partitionne l'ensemble des involution en deux ensembles voir ci-dessous.
Donc il y a un choix pour $f(a)=a$ puis $u_{n+1}$ involution dans $E$ privé de $a$ donc le nombre d'involutions est $1 \times u_{n+1}$
Si $f(a)=b \ne a$ et $f(b)=a$. On a $n+1$ choix pour $b$ car $a$ est déjà pris, $f \circ f(a))=f(b)=a$ et $f(f(b))=f(a)=b$. $f$ est involution sur $\{a,b\}$. Mais elle est aussi involutive sur $E$ privé des points $a$ et $b$ et il y a $u_n$ involutions.
Il y a donc $(n+1) \times u_n$ involutions.
Les deux cas étants disjoints on fait la somme des cardinaux obtenus.
Les 2 ensembles intéressants, c'est E privé de {a} dans un cas, et E privé de {a,f(a)} dans l'autre.
D'où une relation de récurrence.
Du coup, c'est parfait, je vais pouvoir répondre simultanément à babsgueye et OShine.
On considère un tirage de k couples dans un ensemble E de n éléments.
- Si k=0 :
- Si k=1 :
- Si k=2 :
- Si k quelconque :
D'où la somme :Il n'y a que des singletons tels que f(a)=a. Ceci ne constitue qu'un seul cas. Et ce sera la même quantité pour tout le reste du raisonnement. Les éléments non choisis pour être en couple n'augmentent pas la quantité de cas possibles.
$q_{k=0}=1$
On choisit 2 éléments parmi n, indépendamment de l'ordre et sans répétition. C'est donc une combinaison.
$q_{k=1}=C_n^2=\frac{n(n-1)}{2}$
Intuitivement, on a envie de tirer 2 éléments dans les éléments restants et avoir $C_n^2C_{n-2}^2$. Mais ce raisonnement est faux. C'est un piège typique de dénombrement. Car, en choisissant successivement, on introduit un ordre. Et c'est faux. Tirer (a,b) puis (c,d) est identique au fait de tirer (c,d) puis (a,b). Combien d'ordre sur k éléments ? k! ordres. Il faut donc enlever l'ordre en divisant par k! ordres.
$q_{k=2}=\frac 1 2 C_n^2C_{n-2}^2=\frac 1 2 \times \frac{n(n-1)}{2}\times\frac{(n-2)(n-3)}{2}$
On généralise :
$\displaystyle q_{\forall k}=\frac{1}{k!}\prod_{i=0}^{k-1} C_{n-2i}^2=\frac{1}{k!}\prod_{i=0}^{k-1} \frac{(n-2i)(n-2i-1)}{2} = \frac{1}{2^kk!}\prod_{i=0}^{2k-1} (n-i)$
$\displaystyle q(n)=\sum_{k=0}^{E(\frac n 2)} \frac{1}{2^kk!}\prod_{i=0}^{2k-1} (n-i)$
On pourrait s'arrêter là. Mais cette multiplication me gêne. Et on a entrevu une forme bien connue quand on dénombrait 2 couples.
$n(n-1)(n-2)(n-3)=\frac{n!}{(n-4)!}=A_n^4$
On peut donc généraliser et dire :
$\displaystyle\prod_{i=0}^{2k-1} (n-i)=\frac{n!}{(n-2k)!}=A_n^{2k}$
D'où la formule : $\displaystyle q(n)=\sum_{k=0}^{E(\frac n 2)}\frac 1 {2^kk!}A_n^{2k}$
Si on est tombé sur un autre outil de dénombrement, c'est qu'un autre raisonnement était possible. Effectivement, si on tire les éléments à mettre en couple (2k) parmi n, dans l'ordre et sans répétition, on a un arrangement. Il suffit d'enlever l'ordre dans chacun des couples ($2!^k=2^k$) et l'ordre des couples (k!). Et on retrouve la même quantité.
Si tu choisis "a", tu mets un ordre dans tes couples, comme montré ci-dessus. Et la fonction f n'a que faire de cet ordre sur les couples. Il est important de ne pas choisir a. On ne choisit que f(a).
{(a,b), (c,d)} = {(c,d),(a,b)}
PS: ouf. Désolé pour le pavé.
Mais je voudrais dire que ce résultat se démontre plus facilement, connaissant le nombre $P(2n)$ de partitions par pairs d'un ensemble à $2n$ éléments.
On a en effet $P(2n) = \dfrac{(2n)!}{2^{n}n!}$.
Donc pour $k$ allant de 0 à $E(\frac{n}{2})$, on prend à chaque fois $2k$ éléments parmi $n$ (soit $\binom{n}{2k}$) fois le nombre de partions en pairs de ces $2k$ éléments (soit $P(2k) = \dfrac{(2k)!}{2^{k}k!}$).
Ce qui donne :
$\begin{align} Q(n) & = \sum_{k=0}^{E(\frac{n}{2})}\binom{n}{2k} \dfrac{(2k)!}{2^{k}k!} \\ & = \sum_{k=0}^{E(\frac{n}{2})}\dfrac{n!}{(2k)!(n - 2k)!}\dfrac{(2k)!}{2^{k}k!} \\ & = \sum_{k=0}^{E(\frac{n}{2})}\dfrac{n!}{(n - 2k)!}\dfrac{1}{2^{k}k!}\\
\end{align}$
PS : retouche après la remarque de Alexique.
Cordialement.