analyse combinatoire
On se fixe un entier naturel n>=1. On dit qu'un élément m de [1;n] est un point fixe d'une application f de [1;n] dans lui-même si on a f(m)=m.
Pour 0<=k<=m, on appelle H(n,k) le nombre d'application de [1;n] dans lui-même ayant exactement k points fixes et G(n,k) le nombre de celles qui sont des bijections.
1) Montrer qu'on a "somme de k=o à n des H(n,k) = n^n". Pour n>0, de combien d'application un élément ko fixé de [1;n] est-il point fixe? En déduire qu'on a alors aussi " somme des k=0 à n de k*H(n,k)=n^n".
2) Montrer qu'on a pour tout n>0 :
somme de k=0 à n des G(n,k)= somme des k=0 à n des k*G(n,k)=n!
3) Montrer que G(n+1,1)=(n+1)G(n,0).
Montrer plus généralement : G(n+1,k+1)=((n+1)*G(n,k))/(k+1)
merci de répondre le plus clairement possible
Pour 0<=k<=m, on appelle H(n,k) le nombre d'application de [1;n] dans lui-même ayant exactement k points fixes et G(n,k) le nombre de celles qui sont des bijections.
1) Montrer qu'on a "somme de k=o à n des H(n,k) = n^n". Pour n>0, de combien d'application un élément ko fixé de [1;n] est-il point fixe? En déduire qu'on a alors aussi " somme des k=0 à n de k*H(n,k)=n^n".
2) Montrer qu'on a pour tout n>0 :
somme de k=0 à n des G(n,k)= somme des k=0 à n des k*G(n,k)=n!
3) Montrer que G(n+1,1)=(n+1)G(n,0).
Montrer plus généralement : G(n+1,k+1)=((n+1)*G(n,k))/(k+1)
merci de répondre le plus clairement possible
Réponses
-
"somme de k=o à n des H(n,k) = n^n"
"somme des k=0 à n de k*H(n,k)=n^n"
J'ai l'impression que les deux énoncés ne peuvent pas être vrai ensemble. -
Salut ;
Si : car dans le deuxième cas, la somme commence en réalité à k=1...
Notons au passage qu'il faut faire une preuve uniquement combinatoire, sans chercher à donner la valeur explicite de H(n,k). -
n^n est le nombre des applications de [1,n] dans lui même. On peut réaliser une partition de ces applications selon le nombre de leurs points fixes (0 point fixe ou 1 point fixe, etc.). Le premier résultat s'en déduit immédiatement.
-
Pour Richard André-Jeanin :
Peux-tu développer tes idées s'il te plaît car ceci ne nous aide pas forcément -
1) Il y a n^n applications de [1,n] dans lui même. En effet, on a n choix pour l'image de 1. A chacun de ces choix, on peut associer n choix pour l'image de 2, soit déjà n² choix pour les images de 1 et 2, etc. (vous pouvez faire un arbre).
2) L'ensemble de ces applications est la réunion de parties disjointes: une application a 0 point fixe, ou bien 1 point fixe,.., ou bien n points fixes. Il y a H(n,k) applications qui ont k points fixes, d'où le résultat, par addition. -
Voici une autre manière d'aborder le problème, par le calcul direct des
H(n,k).
Il y a C(n,k) façons de choisir la place des k points fixes. Les points fixes étant déterminés, chacun des (n-k) points restants a pour image un point parmi (n-1) (ils peut aller partout sauf sur lui même), ce qui donne:
(n-1)^(n-k) applications.
Finalement: H(n,k)=C(n,k)*(n-1)^(n-k).
Soit maintenant Fn(x) la fonction génératrice de la suite H(n,k):
Fn(x)=(somme de k=0 à n)H(n,k)*x^k
=(somme de k=0 à n)C(n,k)*(n-1)^(n-k)*x^k
=(x+n-1)^n
On en déduit que:
Fn(1)=(somme de k=0 à n)H(n,k)=n^n
De plus:
F'n(x)=(somme de k=0 à n)H(n,k)*k*x^(k-1)
=n*(x+n-1)^(n-1)
D'où:
F'n(1)=(somme de k=0 à n)H(n,k)*k=n*n^(n-1)=n^n -
Pour la première partie du 2), pas de soucis puisqu'il y a n! bijection dans un ensemble à n éléments. En revanche mener le même calcul que Richard dans son dernier message pour expliciter H(n,k) semble difficile puisque si l'on fixe les k points fixes, il faut dénombrer les bijections à n-k éléments n'ayant pas de points fixes (c'est pas des dérangements ça ?). Du coup je ne vois pas trop comment calculer somme de k=0 à n des k*G(n,k)...
La suite je cherche, j'ai bon espoir
-
Ca déchaîne pas les passions on dirait.
Concernant la question 3, on a par raisonnement que G(n+1,k+1) = C(k+1,n+1)*G(n-k,0), et de même G(n,k) = C(k,n)*G(n-k,0), d'où le résultat en combinant les deux égalités.
La question 2 je ne vois pas comment démontrer "somme des k=0 à n des k*G(n,k)=n!", si quelqu'un a une idée, ça m'intéresse ! -
bonjour,
La question 2 je ne vois pas comment démontrer "somme des k=0 à n des k*G(n,k)=n!", si quelqu'un a une idée, ça m'intéresse !
N'est-ce pas faux ? Comment peut-on avoir somme des G(n,k) = n!, ce qui est vrai,
et somme des k*G(n,k) = n! ? -
j'ai parlé trop vite oubliez mon message ...
-
Toi aussi ça te l'a fait
-
Depuis hier, j'ai le même sentiment que Gilles (que je salue au passage): "Ca déchaîne pas les passions on dirait".
Je bute aussi, pour l'instant, sur le problème des dérangements.
Mais le 2ème mi-temps va commencer. C'est pas le moment de me déranger. -
Les dérangements d'un ensemble à $n$ éléments sont au nombre de $G(n,0)=n! \sum_{k=0}^n\frac{(-1)^k}{k!}$, par conséquent
$$\sum_{k=1}^n kG(n,k) = \sum_{k=1}^n k \binom{n}{k} G(n-k,0) = n! \sum_{k=1}^n \left( \frac{1}{(k-1)!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i}\right)$$
Reste à prouver que $\sum_{k=1}^n \left( \frac{1}{(k-1)!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i}\right) = 1$. Je ne suis pas trop à l'aise avec ces sommes, mais j'y retourne.
A mon avis il a bien plus simple, mais c'est mieux que rien ! -
J'ai une solution élémentaire pour le 1°) et le 2°) , il suffit de suivre les indications du sujet , je rédige la solution ( en latex siouplait ) si je trouve un moment .
PS : oublier les dérangements .
Domi -
En fait il nous manque qu'une seule partie de la question 2, ce n'est pas si mal. Bon je retourne quand même à ma somme, je vais l'avoir !!
-
1) J'en suis au même point que Gilles (tout aussi dérangé que lui).
2) Je signale à Domi que je n'ai pas laissé tomber le problème du casino.
3) Je fais remarquer à tous les deux que l'auteur du problème est singulièrement absent depuis hier. Parti en week-end ? -
Je note :
$F_n = \{ applications , f : [1;n] \rightarrow [1;n] \}$.
$G_n = \{ f \in F_n / f\ $bijective \} .
$H(n;k) = $\{ $f \in F_n / f$ a exactement $k$ points fixes $\}$ .
$h(n;k) = Card (H(n,k))$ .
$G(n:k) = H(n;k) \cap G_n$ .
$g(n,k) = Card(G(n;k)$ .
1°) $Card F_n = n^n$ , ( classique ) .
Si $k \in [1;n]$ , $H_i =\{f \in F_n / f(i) = i \}$ et $h_i = CardH_i$ .
$Card H_i = n^{n-1}$ ( sans commentaire ) .
Considérons maintenant $S = \sum_{i = 1}^n h_i = n.n^{n-1} = n^n$ .
$S$ compte $i$ fois chaque élément de $F_n$ ayant $i$ points fixes .
Donc $n^n = \sum_{k = 0}^n k.h(n;k))$ .
La démonstration est identique pour le 2°) et le 3°) se ramène à des restrictions de fonctions .
Domi . -
Bonsoir
ayant déjà fait face à un exo du meme genre je vous expose ma methode:
je m'y prend à l'aide des fonctions indicatrices :
soit Sn l'ensemble des permutations de [1;n]
pour tout k dans [1;n] définissons $\phi k$ une application de Sn dans {0;1} par $\phi k(f)=1$ ssi f a k points fixes.
Alors $\forall k\in [0;n]$ , G(n,k)=$\sum_{f\in Sn}^{} {\phi k(f)}$
A partir de là :
$\sum_{k=0}^{n}{kG(n,k)}$=$\sum_{k=0}^{n}{\sum_{f\in Sn}^{}{k\phi k(f)}}$=$\sum_{f\in Sn}^{}{\sum_{k=0}^{n}{k\phi k(f)}}$=$\sum_{f\in Sn}{}{nombre\, de\, points\, fixes \, de \, f}$
Et rebelote soit $\chi f$ une application de [1;n] dans {0;1} qui à x associe 1 ssi x est point fixe de f.
Notre somme devient:
$\sum_{x=1}^{n}{\sum_{f\in Sn}^{}{\chi f(x)}}$
Or on voit que la quantité $ \sum_{f\in Sn}^{}{\chi f(x)}$ n'est rien d'autre que le nombre de permutations qui laisse fixe l'élément x, c'est la question précédente où on doit trouver (n-1)!, et le résultat arrive tout seul. -
Pour Richard et Gilles ,
il est vrai que ce problème fait réellement penser à celui du casino , du coup j'ai repris mes notations et la solution est apparue immédiatement ( désolé pour Gilles mais je suis hors compétition car surentraîner) )
Encore merci à Richard pour son intérêt à mon problème de casino , des pistes restent à exploiter alors ... à bientôt .
Quant à l'auteur du problème ...
Domi -
Gilles ,dans ta dernière somme, sum((sum(((-1)^i)/i,i=1..(n-k)))/((k-1)!),k=1..n) , il fallait mettre i=1.. et non i=0..
Et en définissant f(n)=sum((sum(((-1)^i)/i,i=1..(n-k)))/((k-1)!),k=1..n) , on costate avec des exemples que f(n)<=0 , donc apparemment il y'a une erreur quelque part -
bien joué Domi
On peut le voir aussi comme le dénombrement de deux manières différentes des applications (bijections) ayant des points fixes dont on distingue un point fixe (i.e. des (f,x) avec f(x)=x).
Je ne connaissais pas ces deux élémentaires et jolies formules. -
Bonjour aux insomniaques (qui dorment encore donc...).
Merci Domi et Vintz d'avoir éclairé les dérangés que nous sommes avec Richard pour reprendre son expression C'est l'argument "$S$ compte $i$ fois chaque élément de $F_n$ ayant $i$ points fixes" qui me manquait, et c'est également pour cette raison qu'il intervient un facteur $\frac{1}{k+1}$ dans la question 3.
Par contre, je suis toujours dans ma somme, auriez-vous une idée ? Yalcin, ma somme commence bien à $i=0$, et je l'ai testé à la main pour de $n=1$ à $n=4$, ça a l'air de fonctionner. Il s'agit de montrer que
$$\sum_{k=1}^n \left( \frac{1}{(k-1)!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i}\right) = 1$$
ou encore en changeant les indices
$$\sum_{k=0}^{n-1}\left( \frac{1}{(n-k-1)!} \sum_{i=0}^k \frac{(-1)^i}{i!} \right) = 1$$
Je cherche à faire apparaître un binôme de Newton, mais il y a toujours quelque chose qui ne va pas. -
Ah ça y est, j'ai compris le problème, il faut lire $i!$ au dénominateur de la fraction et non pas $i$, ça a donc un sens pour $i=0$...
-
Bien vu, Domi, la preuve de (somme de k=0 à n)k*H(n,k)=n^n
On peut aussi utiliser les dérangements sans connaître leur expression
Si une bijection contient k points fixes, les n-k restants sont "dérangés". Donc si d(n) désigne le nombre de dérangements d'un ensemble à n éléments, on a:
G(n,k)=C(n,k)*d(n-k).
La formule: k*C(n,k)=n*C(n-1,k-1) permet d'écrire:
(somme de k=1 à n)k*G(n,k)
=n*(somme de k=1 à n)C(n-1,k-1)d(n-1-k+1)
=n*(somme de k=0 à n-1)C(n-1,k)*d(n-1-k)
=n*(n-1)!=n!.
De même:
G(n+1,k+1)=C(n+1,k+1)*d(n+1-k-1)
=(n+1)/(k+1)*C(n,k)*d(n-k)
=(n+1)/(k+1)*G(n,k). -
Gilles , ta formule ( la première ) se démontre facilement par récurrence sur $n$ .
Domi -
Oui , Richard .
Ils sont amusants ces dérangements en fin de compte .
Domi -
Bon alors je vais essayer la récurrence...
Je crois qu'on lui a tordu le cou à cet exercice
-
Application des résultats sur les G(n,k): on place au hasard n lettres dans n enveloppes. Soit X le nombre de personnes qui recevront la lettre qui leur est destinée. Il est clair que: P(X=k)=G(n,k)/n!, et:
E(X)=(somme de k=0 à n)k*P(X=k)
=(1/n!)*(somme de k=0 à n)k*G(n,k)=n!/n!=1.
Donc, quel que soit n, en moyenne une personne reçoit la bonne lettre. -
Une petite explication pour la réccurrence de Gilles :
Notons :
$$u_n = \sum _{k=1}^n \frac {1}{(k-1)!} \sum _{ i = 0}^{n-k} \frac {(-1)^i}{i!}$$
Monstrons que $u_{n+1} = u_n$ pour $n > 0$ .
$$u_{n+1} = \sum _{k=1}^{n+1} \frac {1}{(k-1)!} \sum _{ i = 0}^{n+1-k} \frac {(-1)^i}{i!}$$
$$u_{n+1} = u_n + \frac{1}{n!} + \sum _{k=1}^n \frac {(-1)^{n+1-k}}{(k-1)!(n+1-k)!}$$
$$u_{n+1} = u_n + \frac{1}{n!} + \sum _{k=0}^{n-1} \frac {(-1)^{n-k}}{(k)!(n-k)!}$$
$$u_{n+1} = u_n + \frac{1}{n!} - \frac{1}{n!}+ \frac{1}{n!}\sum _{k=0}^n \frac {(-1)^{n-k}n!}{(k)!(n-k)!}$$
$$u_{n+1} = u_n + \frac{1}{n!}(1-1)^n$$
$$u_{n+1} = u_n$$
et c'est fini .
Domi -
donc Gilles c'est la manque de ! qui m'a fait perdre le temps,pas grave sinon avec i! c'est facile ,voir la démonstration donnée par Domi
-
Merci Domi, avec un peu de retard. J'avoue que je me suis pas encore penché dessus, mais je vais le faire ce week-end (non prolongé !)
-
C'était avec avec plaisir Gilles , et moi je ne travaille pas lundi)
Domi
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 14
+13 Invités