Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
165 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Nombre d'involutions

Envoyé par OShine 
Nombre d'involutions
il y a trois mois
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$.
Re: Nombre d'involutions
il y a trois mois
Donc tu ne sais pas trouver les fonctions qui vont de $E=\{a,b\}$ dans lui-même ? Ca nécessite de savoir ce qu'est une fonction, je reconnais que c'est pas facile surtout sans corrigé. Peut-être que c'est traité dans un sujet d'ENS ou d'agreg, qui sait...
Mais dans un manuel de 2nd, très certainement !
Seigneur, je prie pour que tu ne parviennes jamais au lycée !



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par Alexique.
Re: Nombre d'involutions
il y a trois mois
Pour $n=2$, il y a $f_1=(a \ b)=\sigma_{ab}$ et $f_2=Id$

Les deux sont involutives. $f_1 \circ f_1 (a)=f_1 (b)=a$

Réponse : il y en a $2$ pour $n=2$.
Re: Nombre d'involutions
il y a trois mois
Pour $n=3$ il y a $f_1=(a \ b)$ , $f_2=(a \ c)$ $f_3=(b \ c)$ et $f_4= id$ il y en a 4.

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.
Re: Nombre d'involutions
il y a trois mois
Bonjour,

À établir une formule de récurrence, je pense.
Re: Nombre d'involutions
il y a trois mois
avatar
Il y a eu un fil très récent à ce sujet... mais je ne vais pas donner de lien : il se pourrait qu'il y ait un corrigé.
Re: Nombre d'involutions
il y a trois mois
Oui mais je ne comprends pas la correction.


Re: Nombre d'involutions
il y a trois mois
Bonjour

Citation
OShine
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<>a je ne comprends pas ça sert à quoi de faire ça.
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.
Re: Nombre d'involutions
il y a trois mois
O'Shine, la correction que tu as scannée est tout à fait explicite.
Qu'est-ce que tu ne comprends pas dedans ?
Re: Nombre d'involutions
il y a trois mois
Oui je pense que le corrigé est bien rédigé c'est juste que j'ai des difficultés en dénombrement.

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.
Re: Nombre d'involutions
il y a trois mois
Première question : qu'est-ce que $u_{n+1}$ ? Combien d'éléments a $E\setminus\{a\}$ ? Si $f$ est une involution de $E$ telle que $f(a)=a$, que peux tu dire de la restriction de $f$ à $E\setminus \{a\}$ ?
Deuxième question : je ne te comprends pas. Qu'appelles-tu "faire des restrictions" ???
Re: Nombre d'involutions
il y a trois mois
Citation
OShine
Je ne comprends pas pourquoi si f(a)=a il y a un+1 involution f de ce type.
Je l'ai dit : soit ton élément a sera seul, soit il sera en couple. S'il reste seul, la quantité d'involutions est la même que s'il n'était pas là. Donc u(n+1).
Si, en revanche, il est en couple, il faut lui trouver un partenaire.

Citation
OShine
Je ne comprends pas pourquoi on fait des restrictions pour dénombrer le nombre d'involution dans les deux cas.
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.
Re: Nombre d'involutions
il y a trois mois
@Petitlutin
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$ ?
Re: Nombre d'involutions
il y a trois mois
Tu n'as pas répondu à ma dernière question : que peux-tu dire de la restriction de $f$ à $E\setminus\{a\}$ ?
C'est pourtant la clé pour comprendre pourquoi on trouve $u_{n+1}$ pour le premier cas.
Re: Nombre d'involutions
il y a trois mois
Si $f$ est une involution sur $E$, alors la restriction de $f$ à $E \backslash \{a\}$ est aussi une involution.
Re: Nombre d'involutions
il y a trois mois
Citation
OShine
@Petitlutin
Je ne comprends pas mieux qu'avec le corrigé.
Voilà une phrase un peu trop vite dégainée. Tu ne comprends pas que les éléments de E doivent être en couple ?

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 ?
Re: Nombre d'involutions
il y a trois mois
avatar
Imagine l'exercice suivant :
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 :
Citation

Soit E un ensemble fini de cardinal n, soit a un élément de cet ensemble E
On note :
v(n) = le nombre d'involutions de E dans E qui vérifient f(a)=a
w(n) = le nombre d'involutions d de E dans E qui vérifient f(a) <>a
u(n) = le nombre d'involutions d de E dans E

Question 0 . Montrer que u(n)=v(n)+w(n)
Question 1 : Etablir une relation de récurrence permettant de calculer v(n+1) à partir de v(n) et w(n)
Question 2 : Etablir une relation de récurrence permettant de calculer w(n+1) à partir de v(n) et w(n)
Question 3 : En déduire une relation de récurrence sur u(n)


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.
Re: Nombre d'involutions
il y a trois mois
@Lourran

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 ?



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par OShine.
Re: Nombre d'involutions
il y a trois mois
f(a)=a. Donc "a" est dans le groupe des singletons. Il y a n+2 éléments. Donc les n+1 éléments restant doivent s'organiser de manière à ce que f soit une involution. Combien y a-t-il d'involutions sur un ensemble de n+1 éléments ? u(n+1). Par définition. Quelque soit ce nombre.
Re: Nombre d'involutions
il y a trois mois
Le groupe des singletons ?

Il faut pas multiplier $u_{n+1}$ par $n+2$ ? Il y a pas $n+2$ choix pour $f(a)=a$ ?
Re: Nombre d'involutions
il y a trois mois
avatar
Salut.
@PLM est ce que tu peux expliquer un peu ta formule générale $q(n)$. Comment tu l'as eue ?
Re: Nombre d'involutions
il y a trois mois
Je crois que je viens de comprendre.

$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.
Re: Nombre d'involutions
il y a trois mois
avatar
Oui, tout à fait.
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.
Re: Nombre d'involutions
il y a trois mois
Ce genre de raisonnement est aussi utilisé pour déterminer le nombre de surjections.
Re: Nombre d'involutions
il y a trois mois
Bravo OShine.

Du coup, c'est parfait, je vais pouvoir répondre simultanément à babsgueye et OShine.

Citation
babsgueye
@PLM est ce que tu peux expliquer un peu ta formule générale q(n). Comment tu l'as eue ?
On considère un tirage de k couples dans un ensemble E de n éléments.
  • Si k=0 :
    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$
  • Si k=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}$
  • Si k=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}$
  • Si k quelconque :
    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)$
D'où la somme :
$\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é.


Citation
OShine
Il y a pas n+2 choix pour f(a)=a ?
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é.
Re: Nombre d'involutions
il y a trois mois
avatar
Merci @PLM.
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.



Edité 2 fois. La dernière correction date de il y a trois mois et a été effectuée par babsgueye.
Re: Nombre d'involutions
il y a trois mois
Bravo babsgueye. Je ne connaissais pas la partition par paires.
Re: Nombre d'involutions
il y a trois mois
Je n'ose même pas lire ce que vous avez écrit tellement ça a l'air compliqué.



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par AD.
Re: Nombre d'involutions
il y a trois mois
C'est moi ou je vois des $2k!$ au lieu de $(2k)!$ ?
Re: Nombre d'involutions
il y a trois mois
Tu as raison Alexique. J'ai tiqué aussi.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 604, Messages: 1 497 690, Utilisateurs: 28 280.
Notre dernier utilisateur inscrit Section Paloise.


Ce forum
Discussions: 886, Messages: 7 497.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page