Combinatoires et probabilités

  1. Les exercices
  2. Vue compacte

Exercices du dossier Combinatoires et probabilités

Exercice 1329

9 novembre 2022 12:19 — Par Patrice Lassère

Bibliographie


[ID: 2531] [Date de publication: 9 novembre 2022 12:19] [Catégorie(s): Géométrie Topologie Continuité Dérivabilité Intégration Suites et séries Suites et séries de fonctions, séries entières Fonctions holomorphes Calcul différentiel Equations différentielles Analyse fonctionnelle Combinatoires et probabilités En cours... ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Combinatoire : les nombres de Bell *

9 novembre 2022 12:22 — Par Patrice Lassère

Pour tout \(n\in\mathbb N^\star\), on désigne par \(B_n\) le nombre de partitions de l’ensemble \(\mathbb [1,\dots,n]\) avec par convention \(B_0=1\).

  1. Montrer que pour tout \(n\in\mathbb N\) : \(\displaystyle B_{n+1}=\sum_{k=0}^n C_n^k B_k.\)

  2. Montrer que le rayon de convergence \(R\) de la série génératrice exponentielle\(f(z)=\sum_{k=0}^\infty \frac{B_n}{n!}z^n\) de la suite \((B_n)_0^\infty\) est strictement positif et calculer \(f(z)\) pour \(\vert z\vert<R\).

  3. Montrer que\(\displaystyle B_n=\dfrac{1}{e}\sum_{k=0}^\infty \dfrac{k^n}{k!}.\)



[ID: 2532] [Date de publication: 9 novembre 2022 12:22] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Combinatoire : les nombres de Bell
Par Patrice Lassère le 9 novembre 2022 12:22

  1. Associons à tout entier \(0\leq k\leq n\), l’ensemble \(E_k\) des partitions de \([1,2,\dots,n+1]\) telles que la partie de \([1,2,\dots,n+1]\) contenant \(n+1\) soit de cardinal \(k+1\). Le cardinal de \(E_k\) vaut \(C_n^k E_{n-k}\) (car une telle partition est déterminée par les \(k\) éléments restant pour compléter la partie de \([1,2,\dots,n+1]\) contenant \(n+1\) (soit \(C_n^k\) possibilités, à laquelle on peut adjoindre les \(B_{n-k}\) partitions de l’ensemble à \(n-k\) éléments restant). Comme \(E_0,E_1,\dots, E_{n}\) forment une partition de l’ensemble des partitions de \([1,2,\dots,n+1]\), on a bien \[B_{n+1}=\sum_{k=0}^n C_n^k B_{n-k}=B_{n+1}=\sum_{k=0}^n C_n^k B_k.\]

  2. Montrons par récurrence sur \(n\in\mathbb N\) que \(B_n\leq n!\). Comme \(B_0=B_1=1, B_2=2, B_3=5\), la propriété est vérifiée pour \(n\leq 3\). Supposons là vérifiée jusqu’au rang \(n\), alors \[B_{n+1}=\sum_{k=0}^n C_n^k\leq n!\sum_{k=0}^n\dfrac{1}{(n-k)!}\leq n!\sum_{k=0}^n 1=(n+1)!.\] On a donc \(\dfrac{B_n}{n!}\leq 1\) et le rayon de convergence \(R\) de la série entière \(f(z)=\sum_{k=0}^\infty \frac{B_n}{n!}z^n\) est supérieur ou égal à \(1\).

    On va utiliser la formule démontrée dans la première question pour calculer \(f(z)\). Pour \(z\in]-R,R[\) \[f(z)=\sum_{k=0}^\infty \dfrac{B_n}{n!}z^n=1+\sum_{k=0}^\infty \frac{B_{n+1}}{(n+1)!}z^{n+1},\] donc \[\begin{aligned}f'(z)&= \sum_{k=0}^\infty \dfrac{B_{n+1}}{n!}z^{n}\\ &= \sum_{k=0}^\infty \dfrac{1}{n!} \left( \sum_{k=0}^n C_n^k\right) z^{n}\\ &= \sum_{k=0}^\infty \left( \sum_{k=0}^n \dfrac{B_k}{k!}\dfrac{1}{(n-k)!}\right) z^{n} \end{aligned}\] On reconnait alors dans le dernier terme le produit de Cauchy des séries entières \(\sum_{k=0}^\infty \frac{B_n}{n!}z^n=f(z)\) et \(\sum_{k=0}^\infty \frac{z^n}{n!}=e^z\) de rayon de convergence strictement positif : on a donc \[f'(z)=f(z)e^z,\qquad\forall\,z\in]-R,R[.\] En intègrant cette équation différentielle, il existe une constante \(C\in\mathbb R\) telle que \(f(z)=Ce^{e^z}\) sur \(]-R,R[\) ; enfin, comme \(f(0)=B_0=1\), \(C=e^{-1}\) et finalement \[f(z)=e^{e^z-1},\qquad\forall\,z\in]-R,R[.\]

  3. Le rayon de convergence de la série entière \(\sum_{k=0}^\infty \frac{z^n}{n!}=e^z\) étant infini, on a \[e^{e^z}=\sum_{n=0}^\infty\dfrac{e^{nz}}{n!}=\sum_{n=0}^\infty\dfrac{1}{n!}\left( \sum_{k=0}^\infty \dfrac{(nz)^k}{k!}\right),\quad\forall\,z\in\mathbb C.\] La série double \(\sum_{(n,k)\in\mathbb N^2}u_{n,k}\) (où \(u_{n,k}=\frac{(nz)^k}{n!k!}\)) est sommable1 ; il est donc légitime d’échanger l’ordre de sommation \[f(z)=\dfrac{1}{e}\sum_{n=0}^\infty\left( \sum_{k=0}^\infty u_{n,k}\right) = \dfrac{1}{e}\sum_{k=0}^\infty\left( \sum_{n=0}^\infty u_{n,k}\right)= \sum_{k=0}^\infty\left( \dfrac{1}{e}\sum_{n=0}\dfrac{n^k}{n!}\right) z^n,\quad z\in]-R,R[,\] soit par unicité des coefficients \[B_k=\dfrac{1}{e}\sum_{n=0}^\infty \dfrac{n^k}{n!}.\] Q.E.D.

  1. [deswar] (T2, page ...).1  car \(\sum_k\vert u_{n,k}\vert=e^{\vert nz\vert}/n!\) et \(\sum_n\sum_k\vert u_{n,k}\vert=e^{e^{\vert z\vert}}\),voir

Un peu de dénombrement autour d’une série entière *

9 novembre 2022 12:22 — Par Patrice Lassère

Est-ce que le coefficient de \(x^{45}\) dans le développement en série entière à l’origine de \[(1-x)^{-1}(1-x^3)^{-1}(1-x^9)^{-1}(1-x^{15})^{-1}\] vaut \(88\) ?


[ID: 2534] [Date de publication: 9 novembre 2022 12:22] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Un peu de dénombrement autour d’une série entière
Par Patrice Lassère le 9 novembre 2022 12:22

Les pôles de cette fraction rationnelle sont des racines de l’unité : elle est donc développable en série entière à l’origine (et le rayon de convergence vaut \(1\)). On a donc \[\begin{aligned}(1-x)^{-1}(1-x^3)^{-1}(1-x^9)^{-1}(1-x^{15})^{-1}&=\left(\sum_{a=0}^{+\infty}x^a\right)\left(\sum_{b=0}^{+\infty}x^{3b}\right)\left(\sum_{c=0}^{+\infty}x^{9c}\right)\left(\sum_{d=0}^{+\infty}x^{15d}\right)\\ &=\sum_{k=0}^\infty u_kx^{k},\end{aligned}\] où \(u_{k}\) désigne bien entendu le nombre de \(4\)-uplets \((a,b,c,d)\in\mathbb N^4\) vérifiant \(a+3b+9c+15d=k\). Notre mission est donc de dénombrer les \(4\)-uplets \((a,b,c,d)\in\mathbb N^4\) vérifiant \[a+3b+9c+15d=45.{\text{($\star$)}}\] (\(\star\)) assure déja que \(a\) est un multiple de \(3\), disons \(a=3\alpha,\ \alpha\in\mathbb N\), soit \[\alpha+b+3c+5d=15.\] -\(d=3\) implique \(\alpha=b=c=0\) : un cas.

-\(d=2\) implique \(c=1\) (alors trois possibilités : \((\alpha,b)\in\{(0,2),(2,0),(1,1)\}\)) ou \(c=0\) (alors \(\alpha+b=5\) soit \(6\) possibilités) : neuf cas.

-\(d=1\) implique \(c=3,2,1\) ou \(0\) soit \(2,5,8\) et \(11\) possibilités : 26 cas.

-\(d=0\) implique \(c=5,4,3,2,1\) ou \(0\), soit \(1,4,7,10,13\) et \(16\) possibilités : 51 cas.

L’équation (\(\star\)) a donc \(51+26+9+1=87\) solutions : la réponse à la question est donc non.


Autour du nombre de dérangements *

9 novembre 2022 12:22 — Par Patrice Lassère

On désigne par \(D_n\) (\(D_0=1\) par convention) le nombre de permutations de \(\mathscr S_n=\{1,2,\dots,n\}\) n’ayant pas de points fixes (i.e. le nombre de dérangements)

  1. Approche classique : Montrer que \[n!=\sum_{k=0}^nC_n^kD_{k}=\sum_{k=0}^nC_n^kD_{n-k}.{\text{($\star$)}}\] Calculer \(\displaystyle \sum_{k=0}^p (-1)^kC_n^kC_{n-k}^{p-k}\) pour \(0\leq p\leq n\) et en déduire que \[D_n=n!\left( \sum_{k=0}^n\dfrac{(-1)^k}{k!}\right). {\text{($\star$)}}\]

  2. Avec les séries entières : Calculer \(\displaystyle \sum_{k=0}^n C_n^kD_k\). Minorer la rayon de convergence de la série génératrice de \((D_n)_n\) : \(\displaystyle D(z)=\sum_{k\geq 0}\dfrac{D_kz^k}{k!}\) et donner une expression de \(D(z)\). Retrouver la valeur de \(D_n\) et montrer que \(D_k\) est la partie entière de \(\displaystyle \dfrac{k!}{e}+\dfrac{1}{2}.\)

  3. Troisième approche : Montrer que pour tout \(n\geq 2\) : \(D_{n+1}=n(D_n+D_{n-1})\), en déduire que \(D_n=nD_{n-1}+(-1)^n\) et retrouver la valeur de \(D_n\).



[ID: 2536] [Date de publication: 9 novembre 2022 12:22] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Autour du nombre de dérangements
Par Patrice Lassère le 9 novembre 2022 12:22

  1. -Soit \(n\geq 1\) et désignons par \(P_k\) l’ensemble des permutations de \(\mathscr S_n\) ayant exactement \(k\) points fixes. \(\{P_0,\dots,P_n\}\) est une partition de \(\mathscr S_n\), par conséquent \(\rm{card}(\mathscr S_n)=n!=\sum_{k=0}^n\rm{card}(P_k)\). Nous allons vérifier que \(\rm{card}(P_k)=C_n^kD_{n-k}\). Visiblement \(D_n=\rm{card}(P_0)\) et \(\rm{card}(P_n)=1=D_0=C_n^n D_0\) ; si \(1\leq k\leq n-1\) un \(k\)-dérangement est complétement déterminé par le choix de ses \(k\) points fixes (soit \(C_n^k\) possibilités) et par le choix de la permutation induite sur les \(n-k\) éléments restants (soit \(D_{n-k}\) possibilités)1 soit \(\rm{card}(P_k)=C_n^kD_{n-k}\), puis \[n!=\sum_{k=0}^nC_n^kD_{k}=\sum_{k=0}^nC_{n-k}^kD_{k}.\]

    -On a \[\begin{aligned} \sum_{k=0}^p (-1)^kC_n^kC_{n-k}^{p-k}&=\sum_{k=0}^p(-1)^k\dfrac{n!(n-k)!}{k!(n-k)!(p-k)!(n-p)!}\\ &=\sum_{k=0}^p(-1)^kC_n^pC_p^k =C_n^p(1-1)^p=\begin{cases} \ 0\quad&\text{si}\quad p\geq 1,\\ \ 1\quad&\text{si}\quad p=0. \end{cases} \end{aligned}\]

    -Des deux formules précédentes \[\begin{aligned} n!\left( \sum_{k=0}^n\dfrac{(-1)^k}{k!}\right)&=\sum_{k=0}^n(-1)^kC_n^k(n-k)!\\ &=\sum_{k=0}^n(-1)^kC_n^k\left( \sum_{l=0}^{n-k}C_{n-k}^lD_{l}\right) \quad\rm{vu} \quad\text{($\star$)}\\ &=\sum_{l=0}^n\left( \sum_{k=0}^{n-l}(-1)^kC_n^kC_{n-k}^l\right)D_l=D_n \quad\rm{vu} \quad\text{($\star$)}\\ \end{aligned}\] en échangeant l’ordre de sommation.

    - Une variante repose sur la formule du crible en remarquant que \(D_n=n!-\rm{card}\bigcup_{k=1}^n U_k\), \(U_k\) désignant les permutations de \(\mathscr S_n\) qui fixent \(k\).

  2. -La somme est calculée dans la question précédente. Comme \(0\leq D_k\leq k!\) le rayon de convergence \(R\) de la série entière \(D(z)\) est supérieur ou égal à \(1\). En écrivant (\(\star\)) pour tout \(n\in\mathbb N\) sous la forme \[1=\sum_{k=0}^n\dfrac{D_k}{k!}\dfrac{1}{(n-k)!}\] on reconnait y le coefficient de \(z^n\) dans le produit de Cauchy des séries entière \(\sum_k\frac{D_k}{k!}z^k\) et \(\sum_k \frac{z^k}{k!}\) de rayon de convergence au moins \(1\). Ainsi, pour tout \(z\in D(0,1)\) \[D'z e^z=\left( \sum_{k\geq 0}\dfrac{D_k}{k!}z^k\right) \left(\sum_{k\geq 0}\dfrac{z^k}{k!} \right)=\sum_{k\geq 0}z^k=\dfrac{1}{1-z}\] soit \[D(z)=\sum_{k\geq 0}\dfrac{D_k}{k!}z^k =\dfrac{e^{-z}}{1-z},\qquad \forall\,z\in D(0,1).\] Il ne reste plus qu’à déterminer les coefficients du développement en série entière à l’origine de \(z\mapsto \frac{e^{-z}}{1-z}\) pour obtenir \(D_k\). Après un produit de Cauchy des deux séries \(\sum_k \frac{(-1)^k}{k!}z^k\) et \(\sum_k z^k\) on trouve bien \[\dfrac{D_n}{n!} \left( = \sum_{k=0}^n a_k b_{n-k} \right) =\sum_{k=0}^n \dfrac{(-1)^k}{k!}\times 1 = \sum_{k=0}^n \dfrac{(-1)^k}{k!}.\]

    -Nous avons \[\dfrac{1}{e}=\sum_{p=0}^\infty \dfrac{(-1)^l}{l!}=\dfrac{D_k}{k!}+\sum_{l\geq k+1}\dfrac{(-1)^k}{k!}:=\dfrac{D_k}{k!}+R_k,\] soit \[\dfrac{k!}{e}+\dfrac{1}{2}=D_k+\dfrac{1}{2}+k!R_k.\] La série \(\sum_l\frac{(-1)^l}{l!}\) vérifiant le critère des séries alternées, la majoration de son reste \[\vert R_k\vert\leq \dfrac{1}{(k+1)!}\] assure pour pour \(k\geq 1\) : \[\vert k!R_k\vert < \frac{1}{k+1}\leq \frac{1}{2}\] qui nous donne finalement \[D_k=\rm{E}\left( \dfrac{k!}{e}+\dfrac{1}{2}\right).\]

  3. Désignons par \(\mathscr D_n\) les dérangements de \(\mathscr S_n\) ; si \(\sigma\in\mathscr D_{n+1}\) : \(\sigma(n+1)\in\mathscr S_n\) et si \(F_k:=\{\sigma\in\mathscr D_{n+1}\ :\ \sigma(n+1)=k\}\) nous avons la partition \(\mathscr D_{n+1}=\bigcup_{k=1}^n F_k\). Montrons que \(\rm{card}(F_k)=D_n+D_{n+1}\). Pour cela on considère la partition \(F_k=G_k\cup H_k\) où \(G_k=\{\sigma\in F_k\ :\ \sigma(k)=n+1\}\) et \(H_k=F_k\setminus G_k\). Un élément de \(G_k\) est parfaitement déterminé par sa restriction à \(\{1,2,\dots,k-1,k+1,\dots,n\}\) et cette restriction devant être un dérangement nous avons \(\rm{card}(G_k)=D_{n-1}\) ; pour le second terme \(\sigma\in H_k\ \Rightarrow\ \sigma^{-1}(n+1)\neq k\) si bien que la correspondance \[H_k\ni\sigma\quad\longmapsto\quad \tilde{\sigma}\in\mathscr D_n\quad \text{où}\quad \tilde{\sigma}(i)=\begin{cases}\sigma(i)\quad&\text{si}\quad i\neq\sigma^{-1}(n+1)\\ k \quad&\text{si}\quad i=\sigma^{-1}(n+1). \end{cases}\] réalise une bijection et par conséquent \(\rm{card}(H_k)=D_n\). Finalement, nous avons bien \(D_{n+1}=n(D_n+D_{n-1})\) pour tout \(n\geq 2\).

    -La formule \(D_n=nD_{n-1}+(-1)^{n+1}\) se déduit de le précédente par une récurrence élémentaire (elle est vraie pour \(n=2\) car \(D_1=0\) et \(D_2=1\)). En divisant cette formule par \(n!\) il vient pour tout \(n\geq 2\) : \[\dfrac{D_k}{k!}=\dfrac{D_{k-1}}{(k-1)!}+\dfrac{(-1)^k}{k!}\] et en sommant cette dernière pour \(2\leq k\leq n\) on retrouve \((\bigstar)\).

  1. Remarquer que \(D_1\) est toujours égal à zéro et qu’effectivement \(P_{n-1}\) est vide : une permutation ne peut avoir \(n-1\) points fixes !↩︎


Distance entre deux racines d’un polynôme *

9 novembre 2022 12:22 — Par Patrice Lassère

Si l’on choisit deux réels au hasard dans l’intervalle \([0,1]\), quelle est la probabilité que la distance dans le plan complexe des deux racines du polynôme \(p(z)=z^2+bz+c\) soit inférieure ou égale à \(1\) ?


[ID: 2538] [Date de publication: 9 novembre 2022 12:22] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Distance entre deux racines d’un polynôme
Par Patrice Lassère le 9 novembre 2022 12:22

La distance entre les deux racines de \(p\) est égale à \(\sqrt{\vert\Delta\vert}=\sqrt{\vert b^2-4c\vert}\) ; elle est donc inférieure à \(1\) si et seulement si \(-1\leq b^2-4c\leq 1\). Il faut donc que le point \((b,c)\) se trouve dans la région délimitée par le carré \([0,1]\times [0,1]\) et les deux paraboles \(y=\frac{x^2-1}{4}\) \(y=\frac{x^2+1}{4}\). La probabilité cherchée est donc l’aire de ce domaine, soit \(\int_0^1 \frac{x^2+1}{4}dx=\frac{1}{3}\) divisée par l’aire du carré (soit \(1\)) : elle vaut donc \(1/3\).


Distribution de deux points sur un segment (1) *

9 novembre 2022 12:22 — Par Patrice Lassère

(Putnam 1993).

Si \(x\) et \(y\) sont choisis au hasard dans \([0,1]\) (avec une densité uniforme), quelle est la probabilité que l’entier le plus proche de \(\frac{x}{y}\) soit pair ?


[ID: 2540] [Date de publication: 9 novembre 2022 12:22] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Distribution de deux points sur un segment (1)
Par Patrice Lassère le 9 novembre 2022 12:22

image
Les-mathematiques.net

L’entier le plus proche de \(\frac{x}{y}\) est zéro si \(2x<y\) et (pour \(n\geq 1\)) vaut \(2n\) si \(\frac{2x}{4n+1}<y<\frac{2x}{4n-1}\) (on ignore bien entendu les éventuelles extrémités de ces intervalles qui sont de probabilités nulles). La probabilité cherchée est donc l’aire grisée de la figure ci-contre, soit : \[\bigcup_{n\geq 1}\left\lbrace \,(x,y)\in[0,1]^2\quad:\quad \frac{2x}{4n+1}<y<\frac{2x}{4n-1}\right\rbrace\] soit \[p=\dfrac{1}{4}+\left(\dfrac{1}{3}-\dfrac{1}{5} \right)+ \left(\dfrac{1}{7}-\dfrac{1}{9}\right) +\dots\] Mais comme \[\dfrac{\pi}{4}=1-\dfrac{1}{3}+\dfrac{1}{5}-\dfrac{1}{7}+\dots\] on trouve \(p=\dfrac{5}{4}-\dfrac{\pi}{4}\)


Probabilité que deux entiers soient premiers entre-eux *

9 novembre 2022 12:23 — Par Patrice Lassère

On se propose de démontrer que la probabilité \(r_n\) que deux entiers pris au hasard dans \(\{1,\dots,n\}\) soient premiers entre-eux vérifie \[r_n=\dfrac{1}{n^2}\sum_{d\geq 1}\mu(d)E\left( \dfrac{n}{d}\right)^2\quad\text{et}\quad \lim_n r_n=\dfrac{6}{\pi^2}\] où l’application (c’est la fonction de möebius) \(\mu\ :\ \mathbb N^\star\to\ \{-1,0,1\}\) est définie par : \[\mu(n)=\begin{cases} &1\qquad\quad\text{ si }n=1,\\ &0\qquad\quad\text{ si }n\text{ possède au moins un facteur carré, }\\ &(-1)^k\quad\text{ si }n=p_1 \dots p_k\text{où les }p_i\text{ sont des nombres premiers distincts.} \end{cases}\] Soient \(p_1,\dots,p_k\) les nombres premiers \(\leq n\) et pour \(1\leq i\leq k\) : \[V_i:=\left\lbrace (a,b)\in\{1,\dots,n\}^2\ :\ p_i\text{ divise }a\text{ et }b\right\rbrace .\]

Montrer que

\[\begin{aligned}\text{card}\left( \bigcup_{i=1}^k V_i\right) &=\sum_{\emptyset\neq I\subset\{1,\dots,n\}}(-1)^{1+\text{card}(I)}\text{card}\left( \bigcap_{i\in I}V_i\right) \\ &=-\sum_{\emptyset\neq I\subset\{1,\dots,n\}} (-1)^{\text{card}(I)}E\left(\dfrac{n}{\prod_{i\in I}p_i}\right)^2\\ &=-\sum_{d=2}^n\mu(d)E\left( \dfrac{n}{d}\right)^2\end{aligned}\] Et en déduire \(r_n\).

Montrer que \(\displaystyle\left\vert r_n-\sum_{d=1}^n \dfrac{\mu(d)}{d^2}\right\vert=0\left( \dfrac{\log(n)}{n}\right).\)

Montrer que \(\displaystyle\sum_{n\geq 1}\dfrac{1}{n^2}\sum_{d\geq 1} \dfrac{\mu(d)}{d^2}=\sum_{i\geq 1}\sum_{l\text{ divise } i}\dfrac{\mu(l)}{i^2}=1.\)

Conclure.


[ID: 2542] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Probabilité que deux entiers soient premiers entre-eux
Par Patrice Lassère le 9 novembre 2022 12:23

  1. Soit donc \(n\geq 1\) et désignons par \(p_1,p_2,\dots,p_k\) les nombres premiers inférieurs ou égaux à \(n\). Avec la formule du crible \[\text{card}\left( \bigcup_{i=1}^kV_i\right) = \sum_{\emptyset\neq I\subset\{1,\dots,n\}}(-1)^{1+\text{card}(I)}\text{card}\left( \bigcap_{i\in I}V_i\right)\] soit \(I\subset\{1,\dots,n\}\) une partie non vide, le nombre de multiples de \(\prod_{i\in I}p_i\) dans \(\{1,\dots,n\}\) est \(E\left( \frac{n}{\prod_{i\in I}p_i}\right)\) soit \[\text{card}\left( \bigcap_{i\in I}V_i\right)=E\left( \dfrac{n}{\prod_{i\in I}p_i}\right)^2\] si bien qu’avec la formule du crible le nombre de couples d’entiers inférieurs ou égaux à \(n\) est \[\begin{aligned}\text{card}\left( \bigcup_{i=1}^kV_i\right) &= \sum_{\emptyset\neq I\subset\{1,\dots,n\}}(-1)^{1+\text{card}(I)}\text{card}\left( \bigcap_{i\in I}V_i\right)\\ &= \sum_{\emptyset\neq I\subset\{1,\dots,n\}}(-1)^{1+\text{card}(I)}E\left( \dfrac{n}{\prod_{i\in I}p_i}\right)^2, \qquad{(\bigstar)} \end{aligned}\] il faut maintenant remarquer que puisque \(\mu\left({\prod_{i\in I}p_i} \right)=(-1)^{\text{card}(I)}\) et \(\mu(l)=0\) pour tout autre entier \(l\in\{2,\dots,n\}\) (ces derniers possèdent un facteur carré): \[\sum_{\emptyset\neq I\subset\{1,\dots,n\}}(-1)^{1+\text{card}(I)}E\left( \dfrac{n}{\prod_{i\in I}p_i}\right)^2=-\sum_{d=2}^n\mu(d)E\left( \dfrac{n}{d}\right)^2\] soit finalement \[\text{card}\left( \bigcup_{i=1}^kV_i\right)=-\sum_{d=2}^n\mu(d)E\left( \dfrac{n}{d}\right)^2.\] Ainsi, le nombre de couples \((a,b)\in\{1,2,\dots,n\}^2\) premiers entre-eux est \[n^2-\text{card}\left( \bigcup_{i=1}^kV_i\right)=n^2+\sum_{d=2}^n\mu(d)E\left( \dfrac{n}{d}\right)^2=\sum_{d=1}^n\mu(d)E\left( \dfrac{n}{d}\right)^2\] et la probabilité cherchée est \[r_n=\dfrac{\text{cas favorables}}{\text{cas possibles}}=\dfrac{1}{n^2} \sum_{d=1}^n\mu(d)E\left( \dfrac{n}{d}\right)^2.\]

  2. Commencons par remarquer que pour \(1\leq d\leq n\) \[\left( \dfrac{n}{d}\right)^2 \geq E\left(\dfrac{n}{d}\right)^2 > \left( \dfrac{n}{d}-1\right)^2\] qui implique \[0\geq \dfrac{1}{n^2}E\left(\dfrac{n}{d}\right)^2-\dfrac{1}{d^2}\geq \dfrac{1}{n^2}-\dfrac{2}{nd}\] de sorte que \[\begin{aligned} \left\vert r_n-\sum_{d=1}^n\dfrac{\mu(d)}{d^2}\right\vert &= \left\vert\sum_{d=1}^n\dfrac{\mu(d)}{n^2}E\left( \dfrac{n}{d}\right)^2-\sum_{d=1}^n\dfrac{\mu(d)}{d^2}\right\vert\\ &=\left\vert\sum_{d=1}^n\mu(d)\left[ \dfrac{1}{n^2}E\left(\dfrac{n}{d}\right)^2-\dfrac{1}{d^2}\right]\right\vert \\ &\leq \sum_{d=1}^n \vert\mu(d)\vert\left( \dfrac{2}{nd}-\dfrac{1}{n^2}\right) \\ &\leq \sum_{d=1}^n \left( \dfrac{2}{nd}-\dfrac{1}{n^2}\right)\\ &\leq \dfrac{1}{n}+\dfrac{2}{n}\sum_{d=1}^n\dfrac{1}{d}=\dfrac{1}{n}+O\left( \dfrac{\log n}{n}\right)= O\left( \dfrac{\log n}{n}\right). \end{aligned}\]

  3. &

  4. La série \(\sum_d \mu(d)/d^2\) étant convergente \[\lim_{n\to\infty} r_n=\sum_{d=1}^{\infty}\dfrac{\mu(d)}{d^2},{(1)}\] d’un autre coté, nous pouvons écrire \[\begin{aligned}\dfrac{\pi^2}{6}\sum_{d=1}^{\infty}\dfrac{\mu(d)}{d^2} &=\left( \sum_{i=1}^\infty\dfrac{1}{i^2}\right) \left( \sum_{d=1}^{\infty}\dfrac{\mu(d)}{d^2}\right)\\ &=\sum_{(i,d)\in\mathbb N^2}\dfrac{\mu(d)}{i^2d^2} =\sum_{i\geq 1}\dfrac{1}{i^2}\sum_{l/i}\mu(l):= \sum_{i\geq 1}\dfrac{1}{i^2}S(i) \end{aligned}\] où les deux avant dernières égalités sont justifiées par l’absolue convergence des deux premieres séries (on peut alors sommer par paquets). il reste donc à estimer \(S(i)\) pour \(i\geq 1\). \(S(1)=1\) et pour \(i\geq 2\) soit \(i=q_1^{\alpha_1}\dots q_N^{\alpha_N}\) la décomposition de \(i\) en facteurs premiers ; un diviseur \(l\) de \(i\) s’écrit donc sous la forme \(l=q_1^{\beta_1}\dots q_N^{\beta_N}\) avec \(0\leq\beta_j\leq\alpha_j\). Mais \(\mu(l)\ne 0\) signifie que \(\beta_j=0\) ou \(1\) et dans ce cas \(\mu(l)=(-1)^s\) où \(s=\text{card}\{1\leq j\leq N\ :\ \beta_j=1\}\). Il existe donc une bijection entre l’ensemble des diviseurs \(l\) de \(i\) tels que \(\mu(l)=(-1)^s\) et l’ensemble des \(N\)-uplets \((\beta_1,\dots,\beta_N)\in\{0,1\}^N\) avec exactement \(s\) composantes égales à \(1\) et ce dernier est bien entendu de cardinal \(C_N^s\) si bien que \[S(i)=\sum_{l/i}\mu(l)=\sum_{s=0}^N\sum_{l/i \& \mu(l)=(-1)^s}\mu(l)=\sum_{s=0}^N C_N^s(-1)^s=(1-1)^N=0.\] en résumé \[S(i)=\begin{cases} 1&\text{si}\quad i=1\\ 0&\text{si}\quad i\geq 2. \end{cases}\] soit \[\dfrac{\pi^2}{6}\sum_{d=1}^{\infty}\dfrac{\mu(d)}{d^2}=1\] et enfin \[\lim_{n\to\infty}r_n=\sum_{d=1}^{\infty}\dfrac{\mu(d)}{d^2}=\dfrac{6}{\pi^2}.\]


Nombre de matrices symétriques à coefficients dans \(\{0,1\}\) et série entières *

9 novembre 2022 12:23 — Par Patrice Lassère

(Putnam, 1967).

Soit \(u_n\) le nombre de matrices \(n\times n\), symétriques à coefficients dans \(\{0,1\}\) avec exactement un \(1\) sur chaque ligne (on notera \(S_n\) cet ensemble). Avec \(u_0:=1\), montrer que \[u_{n+1}=u_n+nu_{n-1},\quad \sum_{n\geq 0}\dfrac{u_nx^n}{n!}=\exp{(x)+\dfrac{x^2}{2}}:=f(x).\]


[ID: 2544] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Nombre de matrices symétriques à coefficients dans \(\{0,1\}\) et série entières
Par Patrice Lassère le 9 novembre 2022 12:23

Il y a une correspondance bijective entre \(S_n\) et l’ensemble des matrices \(M=((m_{ij}))\in S_{n+1}\) telles que \(m_{11}=1\). De même si \(i\geq 2\), il y aussi une correspondance bijective entre \(S_{n-1}\) et les matrices \(M\in S_{n+1}\) telles que \(m_{1i}=1\) (en effet \(M\) étant symétrique \(m_{i1}=1\), il n’y a donc que des zéros sur les autres coefficients des i-èmes lignes et colonnes : la donnée de \(M\) correspond donc à celle de la matrice \((n-1)\times(n-1)\) déduite de \(M\) en lui supprimant ses ièmes lignes et colonnes). De ces deux correspondances et puisque \(u_0=u_1=1\) on a \[u_{n+1}=u_n+nu_{n-1},\quad n\geq 1.\] Pour la seconde partie, il suffit de remarquer que \(f\) est développable en série entière \(\sum_nv_nx^n\) sur \(\mathbb R\), puis que les coefficients \(v_n\) satisfont à la même relation de récurrence que les \(u_n\) pour conclure facilement.


Distribution aléatoire de deux points sur un segment *

9 novembre 2022 12:23 — Par Patrice Lassère

(Putnam, 1961).

On choisit deux points au hasard et de manière indépendante sur un segment \(I\) de longueur \(d\). Soit \(0<l<d\), quelle est la probabilité que la distance entre ces deux points soit supérieure ou égale à \(l\) ?


[ID: 2546] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Distribution aléatoire de deux points sur un segment
Par Patrice Lassère le 9 novembre 2022 12:23

Sans perdre de généralité, supposons que \(I=[0,d]\), et considérons dans \(\mathbb R^2\) : \[\left\lbrace \ (x,y)\in[0,d]\times[0,d]\ :\ \vert x-y\vert=l\right\rbrace\] Parmi tous les cas possibles soit \([0,d]\times[0,d]\), les couples \((x,y)\) qui nous intéressent sont ceux qui se trouvent dans les deux triangles rectangles de sommets respectifs \((0,l),(0,d),(d-l,d)\) et \((l,0),(d,0),(d,d-l)\) qui se réunissent pour former un carré de coté \(d-l\).

image
Les-mathematiques.net

La probabilité cherchée est donc \(\displaystyle p=\dfrac{(d-l)^2}{d^2}.\)  


Dénombrement et séries entières/génératrices *

9 novembre 2022 12:23 — Par Patrice Lassère

Il s’agit de dénombrer le nombre de manières de distribuer \(n\) euros à \(p\) personnes.


[ID: 2548] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Dénombrement et séries entières/génératrices
Par Patrice Lassère le 9 novembre 2022 12:23

Notons \(d_{n,p}\) la quantité cherchée et voici deux solutions.

  1. Par dénombrement : Les \(p\) personnes sont numérotées de \(1\) à \(p\). Étant donné \(n+p-1\) cases vides, on en sélectionne \(n\) (signalées par \(\text{$\star$}\)), les \(p-1\) autres sont marquées par un trait vertical \(\vert\). Le nombre d’étoiles entre les deux premiers traits représente le nombre d’euros (éventuellement nul) attribués à la première personne et ainsi de suite. Par exemple si \(p=5\) et \(n=6\) la configuration

    \[\vert\ \vert\text{$\star$}\text{$\star$}\text{$\star$}\vert\text{$\star$}\vert\ \vert \text{$\star$}\text{$\star$}\]

    correspond au partage \(0,3,1,0,2\)

    Cette procédure résout visiblement notre problème et il y a clairement \(C_{n+p-1}^n\) choix possibles i.e. \(d_{n,p}=C_{n+p-1}^n\).

  2. 0ù avec les séries entières : Vu le cours sur les séries entières, par convergence absolue on a le produit de Cauchy

    \[\sum_n a_nx^n\sum_n b_nx^n\dots \sum_n c_nx^n=\sum_n d_nx^n\ \ \text { avec } \ \ d_n=\sum_{k+k'+\dots+k''=n} a_k b_{k'}\dots c_{k''}x^k\]

    avec \(\displaystyle c_{n,p}=\sum_{k_1+k_2+\dots+k_p=n}a_{k_1}a_{k_2}\dots a_{k_p}\) où les \(a_{k_i}=1\), donc vu la formule ci-dessus :

    \[{1\over {(1-x)^p}}=\sum_{n\geq 0} C_{n+p-1}^nx^n=\sum_n x^n\sum_n x^n\dots \sum_n x^n=\sum_n c_{n,p}x^n\ \ \]

    et il n’y a plus qu’à identifier les coefficients.

    Remarque : le candidat à l’agrégation externe peut (et doit) se placer dans l’unique cadre des séries formelles.


Groupes et probabilités *

9 novembre 2022 12:23 — Par Patrice Lassère

Soit \(G\) un groupe fini non commutatif. On note \(p(G)\) la probabilité pour que deux éléments de \(G\) tirés au hasard commutent entre eux. Montrer que \(p(G)\leq \frac{5}{8}\) et préciser pour quels groupes cette valeur maximale est atteinte.


[ID: 2550] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Groupes et probabilités
Par Patrice Lassère le 9 novembre 2022 12:23

Soit \(G\) un groupe fini non commutatif, notons \(Z\) son centre et pour \(x\in G\) désignons par \(G_x\) l’ensemble des éléments de \(G\) commutant avec \(x\). \(Z\) et \(G_x\) sont deux sous-groupes de \(G\) ; \(Z\) est lui même un sous groupe de \(C_x\). Le théorème de Lagrange, nous assure de l’existence de trois entiers \(m, k_x, l_x\in\mathbb N\) vérifant \[\vert G\vert=m\vert Z\vert,\quad \vert G\vert=k_x\vert G_x\vert,\quad \text{et}\quad\vert G_x\vert=l_x\vert Z\vert .\] soit \[k_xl_x=m\].

-Si \(x\in Z\), alors \(G_x=G,\ k_x=1\) et \(l_x=m\).

-Sinon, \(G_x\ne G\) (car \(x\not\in Z\)) donc \(k_x>1\) et \(l_x>1\).

Il existe donc \(a\in G\setminus Z\) tel que \[mk_al_a=m^2\geq 4.\]

On a donc : \[\begin{aligned} p(G)&=\dfrac{1}{\vert G\vert^2}\sum_{x\in G}\vert G_x\vert= \dfrac{1}{\vert G\vert^2}\left(\sum_{x\in Z}\vert G_x\vert+ \sum_{x\in G\setminus Z}\vert G_x\vert \right) \\ &=\dfrac{1}{\vert G\vert^2}\left( \vert G\vert \vert Z\vert+ \sum_{x\in G\setminus Z}\vert G_x\vert \right) \\ &\leq \dfrac{1}{\vert G\vert^2}\left( \vert G\vert \vert Z\vert+(\vert G\vert -\vert Z\vert)\dfrac{\vert G\vert}{2}\right) \\ &\leq \dfrac{\vert G\vert +\vert Z\vert}{2\vert G\vert}\\ &\leq \dfrac{1}{2}\left( \dfrac{1}{4}+1\right) =\dfrac{5}{8}. \end{aligned}\]

Pour le cas d’égalité, \(p(G)=\frac{5}{8}\), si, et seulement si \(m=4\). C’est en effet nécessaire vu ce qui précède ; réciproquement, si \(m=4\), on a \(\vert G_x\vert=\frac{1}{2}\vert G\vert\) pour tout \(x\in G\setminus Z\) et on obtient l’égalité.

Remarque : Pour en savoir plus, on peut consulter la rubrique questions-réponses de la RMS [rms], 2003/04, tome 2.


Dénombrement et algèbre linéaire *

9 novembre 2022 12:23 — Par Patrice Lassère

Déterminer le cardinal de \(O_n(\mathbb R)\cap M_n(\mathbb Z).\)



[ID: 2552] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Dénombrement et algèbre linéaire
Par Patrice Lassère le 9 novembre 2022 12:23

Soit \(A=((a_{ij}))\in O_n(\mathbb R)\cap M_n(\mathbb Z)\), \(A\) étant orthogonale, ses colonnes sont de norme \(1\)

\[\forall\ 1\leq j\leq n\quad :\quad \sum_{i=1}^n\,a^2_{ij}=1\]

mais les coefficients \(a_{ij}\in\mathbb Z\), donc

\[\forall\ 1\leq j\leq n,\ \exists\,!\ \sigma(j)\in\{1,\dots,n\}\text{ tel que } a_{\sigma(j)j}=+1\text{ ou }-1\text{ et }\ a_{ij}=0\ \forall\ i\ne\sigma(j)\]

ainsi, dans chaque colonne (ou ligne) un seul coefficient n’est pas nul et vaut \(+\) ou \(-1\).

Toujours par orthogonabilité de \(A\) :

\[\forall\ i\ne j\quad :\quad \sum_{k=1}^n\,a_{ki}a_{kj}=0.\]

Supposons que dans la première colonne le \(k\)-ième coefficient soit non nul : \(a_{k1}\ne 0\), les vecteurs première et seconde colonne étant orthogonaux on a forcément \(a_{2k}=0\) et il ne reste donc que \(2(n-1)\) choix possibles pour completer la seconde colonne. De proche en proche le cardinal de \(O_n(\mathbb R)\cap M_n(\mathbb Z)\) est \(2^n n!\).


Les dés sont pipés *

9 novembre 2022 12:23 — Par Patrice Lassère

Références ???

Montrer qu’il n’est pas possible de piper deux dés de sorte que la variable aléatoire somme des deux faces soit uniformément répartie.

Est-il toutefois possible de piper les deux dés et que la variable aléatoire somme des deux faces continue à suivre la loi usuelle associée à deux dés normaux ?


[ID: 2554] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Les dés sont pipés
Par Patrice Lassère le 9 novembre 2022 12:23

  1. Désignons par \(X_i,\,(i=1,2)\) les variables aléatoires correspondant à la somme des points sur les faces de chacun des deux dés, elles sont indépendantes à valeur dans \(\{1,\dots,6\}\). Notons \(p(X_1=i)=a_i,\,P(X_2=i)=b_i,\,(i=1,\dots 6)\). Supposons donc que \(X_1+X_2\) (à valeur dans \(\{2,\dots,12\}\)) suive une loi uniforme i.e. \[\forall\,i\in\{2,\dots,12\}\ :\ P(X_1+X_2=i)={1\over 11}.\] La fonction de répartition de \(X_1+X_2\) est \[F_{X_1+X_2}(t)={1\over 11}\left( t^2+t^3+\dots +t^{12}\right)\] et celles des \(X_i\) sont \[F_{X_1}(t)=a_1t+a_2t^2+\dots+a_6t^6, \quad\text{ et }\quad F_{X_2}(t)=b_1t+b_2t^2+\dots+b_6t^6.\] Mais \(X_1\) et \(X_2\) sont indépendantes \[F_{X_1+X_2}(t)=F_{X_1}(t) F_{X_2}(t) {(\bigstar)}\] i.e. \[\forall\,t\in\mathbb R:\qquad {1\over 11}\left(1+t+t^2+\dots+t^{10}\right)=(a_1+a_2t+\dots+a_6t^5) (b_1+b_2t+\dots+b_6t^5)\] le coefficient de \(t^{10}\) étant \(1\over{ 11}\), nécessairement \(a_6>0\) et \(b_6>0\) et par suite \(a_1+a_2t+\dots+a_6t^5\) et \(b_1+b_2t+\dots+b_6t^5\) possèdent chacun une racine réelle comme polynômes de degré impair mais ceci est absurde car \(1+t+t^2+\dots+t^{10}\) est sans racines réelles, contradiction.

  2. Avec deux dés normaux, on a bien entendu \[P(X_1+X_2=2)=\dfrac{1}{36},\quad P(X_1+X_2=3)=\dfrac{2}{36},\quad P(X_1+X_2=4)=\dfrac{3}{36},\dots\text{ect}\dots P(X_1+X_2=12)=\dfrac{1}{36}.\] de sorte que la formule \((\bigstar)\) deviens maintenant \[\begin{aligned} \dfrac{F_{X_1+X_2}(t)}{t^2}&=\dfrac{1}{36}\left( 1+2t+3t^2+4t^3+5t^4+6t^5 +5t^6+4t^7+3t^8+2t^9+t^{10}\right) \\ &=\dfrac{1}{36}\left( 1+t+t^2+t^3+t^4+t^5\right)^2\\ &=\dfrac{1}{36}\left(\dfrac{1-t^6}{1-t} \right)^2\\ &=\dfrac{F_{X_1}(t)F_{X_2}(t)}{t^2}\\ &=(a_1+a_2t+\dots+a_6t^5) (b_1+b_2t+\dots+b_6t^5) \end{aligned}\] les racines du premier polynôme sont les racines sixièmes de l’unité, exepté \(1\) et toutes avec une multiplicité \(2\) : \[\omega, \omega^2, -1, -\omega, -\omega^2\] (où \(\omega\) est une racine primitive de l’unité) ainsi les dix racines du polynôme \(t^{-2}F_{X_1}(t)F_{X_2}(t)\) sont les dix nombres complexes \[\omega,\omega^2,-1, -\omega,-\omega^2, \omega,\omega^2,-1, -\omega,-\omega^2.\] cinq d’entre-eux sont les racines de \(a_1+a_2t+\dots+a_6t^5\) les cinq autres étant celles de \(b_1+b_2t+\dots+b_6t^5\). En choisissant les cinq premières pour le premier polynôme et les cinq autres pour le second on obtient \[\dfrac{F_{X_1}(t)}{a_6t}=(t+1)(t-\omega)(t-\omega^2)(t+\omega)(t+\omega^2)= =1+t+t^2+t^3+t^4+t^5\] on fait de même pour le second dé, soit \[a_1=a_2=\dots=a_6=\dfrac{1}{6}=b_1=b_2=\dots=b_6\] i.e. les deux dés ne sont pas pipés. Il ne reste plus qu’à vérifier à la main qu’aucune autre partition des dix racines ne convient. La seule alternative est donc le cas classique de deux dés non pipés.

    Remarque : voici une autre manière pour résoudre la première partie de ce problème, elle est un peu plus simple mais (à mon goût), moins élégante. On conserve les mêmes notations qu’au dessus.

    On a \[\begin{aligned} &P(X_1+X_2=2)&=&\ a_1b_1=\dfrac{1}{11}\\ &P(X_1+X_2=12)&=&\ a_6b_6=\dfrac{1}{11}\\ &P(X_1+X_2=7)&=&\ a_1b_6+a_2b_5+a_3b_4+a_4b_3+a_5b_2+a_6b_1=\dfrac{1}{11} \end{aligned}\] des deux premières égalités on tire \[b_1=\dfrac{1}{11a_1}\quad b_6=\dfrac{1}{11a_6}\] l’inégalité classique \(\dfrac{x^2+y^2}{xy}\geq 2\) nous donne \[\dfrac{1}{11}\left( \dfrac{a_1}{a_6}+\dfrac{a_6}{a_1}\right) \geq \dfrac{2}{11}>\dfrac{1}{11}\] soit, sur le troisième terme \[\begin{aligned}P(X_1+X_2=7)&=\ a_1b_6+a_2b_5+a_3b_4+a_4b_3+a_5b_2+a_6b_1\\ &=\dfrac{1}{11}\left( \dfrac{a_1}{a_6}+\dfrac{a_6}{a_1}\right)+ a_2b_5+a_3b_4+a_4b_3+a_5b_2\\ &> \dfrac{1}{11}+a_2b_5+a_3b_4+a_4b_3+a_5b_2>\dfrac{1}{11} \end{aligned}\] i.e. \[P(X_1+X_2=7)>\dfrac{1}{11}\] contradiction.


Avec un peu d’algèbre linéaire *

9 novembre 2022 12:23 — Par Patrice Lassère

Soient \(A_1,A_2,\dots,A_{n+1}\) des parties non vides de \(\{1,2,\dots,n\}\). Montrer qu’il existe deux ensembles \(I,J\subset\{1,2,\dots,n+1\}\) non vides et disjoints tels que \[\bigcup_{i\in I}A_i=\bigcup_{j\in J}A_j.\]


[ID: 2556] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Avec un peu d’algèbre linéaire
Par Patrice Lassère le 9 novembre 2022 12:23

Soit l’identification naturelle \(\mathscr P(\{1,2,\dots,n\})\simeq\{0,1\}^n\) donnée par \[A\in\mathscr P(\{1,2,\dots,n\})\quad \leftrightsquigarrow\quad e_A=(e_A(i))_{i=1}^n \quad\text{où}\quad e_A(i)=\begin{cases}0\quad&\text{si}\ i\not\in A,\\ 1\quad&\text{si}\ i\in A.\end{cases}\] Dans le \(\mathbb Q\)-espace vectoriel \(\mathbb Q^n\) de dimension \(n\), les \(n+1\) vecteurs \(e_{A_1},\dots,e_{A_{n+1}}\) sont \(\mathbb Q\)-linéairement dépendants ce qui peut se traduire facilement par \[\exists\,\lambda_1,\dots,\lambda_n\in\mathbb Z\ \text{\rm{non tous nuls, tels que}}\quad \sum_{k=1}^{n+1}\lambda_i e_{A_i}=0.\] et qui équivaut à \[\sum_{i\in I}\lambda_i e_{A_i}=\sum_{j\in J}\lambda_je_{A_j}\] où \(I:=\{k\in\{1,2,\dots,n+1\},\ \text{tels que}\ \lambda_k>0\}\neq\emptyset\) (resp. \(J:=\{k\in\{1,2,\dots,n+1\},\ \text{tels que}\ \lambda_k<0\}\neq\emptyset\)) qui fourni immédiatement l’égalité \[\bigcup_{i\in I}A_i=\bigcup_{j\in J}A_j,\] si désirée.


Probabilité d’obtenir un multiple de cinq en jetant \(n\) dés *

9 novembre 2022 12:23 — Par Patrice Lassère

On jette \(n\) fois un dé équilibré ; quelle est la probabilité que la somme des \(n\) faces obtenues soit divisible par \(5\) ?


[ID: 2558] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Probabilité d’obtenir un multiple de cinq en jetant \(n\) dés
Par Patrice Lassère le 9 novembre 2022 12:23

  1.  première solution : Désignons pour \(n=r(5)\in\mathbb N\) par \(p_n^{(r)}\) la probabilité qu’aprés \(n\) tirages la somme des faces soit congrue à \(r\) modulo \(5\). Nous avons bien entendu \[p_0^{(0)}=1\quad\text{et}\quad p_0^{(1)}=p_0^{(2)}=p_0^{(3)}=p_0^{(4)}=0\] et il est facile de vérifier que pour \(n\in\mathbb N^\star\) \[p_n^{(r)}=\sum_{j=1}^6 \dfrac{p_{n-1}^{r-j}}{6}.{\text{($\star$)}}\] Ces formules nous permettent de calculer \(p_n^{(r)}\) pour quelques petites valeurs de \(n\) pour conjecturer que \[p_n^{(r)}=\dfrac{1}{5}+\dfrac{4}{5.6^n}\quad\text{si}\quad n\equiv 0(5)\quad\text{et}\quad p_n^{(r)}=\dfrac{1}{5}-\dfrac{4}{5.6^n}\quad\text{sinon}.\] Ces conjectures se démontrent alors facilement par récurrence avec (\(\star\)).

  2.  seconde solution : On considère la partition suivante de l’ensemble \(\mathscr S=\{1,2,3,4,5,6\}^n\setminus\{(6,6,\dots,6)\}\) : chaque famille sera constitué des suites de la forme \[\begin{matrix} \underbrace{66\dots 6}\!&\!XY_1\dots Y_{n-k-1} \\ {k\ \text{fois}}& \end{matrix}\] où \(X\in\{1,2,3,4,5\}\) et \(Y_1,\dots,Y_{n-k-1}\) sont fixés. Chaque élément de la partition est donc constituée de \(5\) suites dont, modulo \(5\) la somme des chiffres est exactement \(0,1,2,3,4\) soit exactement une dont la somme de chiffres est \(0(5)\). Ainsi le nombre de suites dont la somme des chiffres est divisible par \(5\) est \(\text{card}(\mathscr S)/5=(6^n-1)/5\) si \(n\) est pas un multiple de \(5\) et \(1+\text{card}(\mathscr S)/5=1+(6^n-1)/5\) sinon (dans ce cas \((6,6,\dots,6)\) est aussi solution).

    La probabilité cherchée est donc (cas favorables sur cas possibles) \[\dfrac{1}{5}+\dfrac{4}{5.6^n}\quad \text{si}\quad n\equiv 0(5)\quad\text{et}\quad \dfrac{1}{5}-\dfrac{4}{5.6^n}\quad\text{sinon}.\]

  3.  troisième solution : Désignons par \(p_k\) la probabilité que la somme des faces soit égale à \(k\) et considérons la série génératrice associée \[f(z)=\sum_{k\geq 1}p_kx^k=\left( \dfrac{z+z^2+z^3+z^4+z^5+z^6}{6}\right)^n\] où la seconde égalité peut être vérifiée facilement par récurrence sur \(n\). Il s’agit donc de calculer \(\sum_{k\geq 1}p_{5k}\) ; pour cela soit \(\varepsilon=e^{2i\pi/5}\) la première racine cinquième de l’unité, nous avons \[\sum_{k\geq 1}p_{5k}= \dfrac{f(\varepsilon)+f(\varepsilon^2)+f(\varepsilon^3)+f(\varepsilon^4)}{6}.\] Il est clair que \(f(1)=1\) et pour \(j=1,2,3,4\) \(f(\varepsilon^j)=\frac{\varepsilon^{jn}}{6^n}\) si bien que \[f(\varepsilon)+f(\varepsilon^2)+f(\varepsilon^3)+f(\varepsilon^4)=\begin{cases} \dfrac{4}{6^n}\quad\text{si}\quad n\equiv 0(5),\\ \dfrac{-1}{6^n}\quad\text{sinon.}\end{cases}\] et finalement \[\sum_{k\geq 1}p_{5k}= \begin{cases} \dfrac{1}{5}+\dfrac{4}{5.6^n}\quad\text{si}\quad n\equiv 0(5),\\ \\ \dfrac{1}{5}-\dfrac{-1}{5 . 6^n}\quad\text{sinon.}\end{cases}\]


Combinatoire et matrices *

9 novembre 2022 12:23 — Par Patrice Lassère

Soient \(A_0=B_0=((1))\in M_1(\mathbb R)\). Pour \(n\geq 1\) on définit les suites de matrices par \[A_n=\begin{pmatrix}A_{n-1}&A_{n-1}\\A_{n-1}&B_{n-1}\end{pmatrix},\quad \rm{et}\quad B_n=\begin{pmatrix}A_{n-1}&A_{n-1}\\A_{n-1}& 0\end{pmatrix}\in M_{2n}(\mathbb R).\] Montrer que \[S(A_n^{k-1})=S(A_k^{n-1}),\forall\,n,k\in\mathbb N^\star\] avec \(S(M)=\sum_{1\leq i,j\leq n}m_{ij}\) où \(M=((m_{ij}))\).


[ID: 2560] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Combinatoire et matrices
Par Patrice Lassère le 9 novembre 2022 12:23

L’astuce (redoutable) consiste à donner un sens combinatoire à la quantité \(S(A_n^{k-1})\). Pour cela soit \(T\) un tableau \(n\times k\) à coefficients \(0\) et \(1\) (i.e. un élément de \(M_{n,k}(0,1)\)) vérifiant la propriété suivante : il n’existe dans \(T\) aucune sous matrice \(2\times 2\) constituée uniquement de \(1\) et soit \(F_{n,k}\) le nombre de tels tableaux.

Chaque ligne d’un tableau correspond à un entier entre \(0\) et \(2^n-1\) écrit en base \(2\). \(F_{n,k}\) est donc le nombre de \(k\)-uplets d’entiers dont toute paire d’entiers consécutifs correspond à un tableau \(n\times 2\) sans sous-matrice . \(2\times 2\) constituée uniquement de \(1\).

Soient \(\overline{i_n i_{n-1}\dots i_1},\ \overline{j_nj_{n-1}\dots j_1}\) les écritures en base \(2\) de deux entiers \(i,j\in\{0,\dots,2^n-1\}\). Deux cas sont à envisager :

-Si \(i_nj_n=0\) alors \(\overline{i_n i_{n-1}\dots i_1}\) et \(\overline{j_nj_{n-1}\dots j_1}\) sont consécutifs si et seulement si \(\overline{ i_{n-1}\dots i_1}\) et \(\overline{j_{n-1}\dots j_1}\) le sont.

-Si \(i_nj_n=1\) alors \(\overline{i_n i_{n-1}\dots i_1}\) et \(\overline{j_nj_{n-1}\dots j_1}\) sont consécutifs si et seulement si \(i_{n-1}j_{n-1}=0\) et \(\overline{ i_{n-2}\dots i_1}\) et \(\overline{j_{n-2}\dots j_1}\) le sont.

Ainsi


\(10^{2006}\) divise \(n!\) *

9 novembre 2022 12:23 — Par Patrice Lassère

Déterminer les entiers \(n\in\mathbb N^\star\) tels que l’écriture décimale de \(n!\) se termine par 2006 zéros exactement.


[ID: 2562] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

\(10^{2006}\) divise \(n!\)
Par Patrice Lassère le 9 novembre 2022 12:23

Dans la décomposition en facteurs premiers de \(n!\), l’exposant du nombre premier \(p\) vaut (pourquoi ?) \[\sum_{i=1}^\infty\left[\dfrac{n}{p^i}\right]\] qui est bien entendu une somme finie puisque \([n/p^i]=0\) pour \(i>\log_p(n)\). Ainsi \[n!=\prod_{p,\ p/n!}p^{\alpha_p}=2^{\alpha_2}3^{\alpha_3}5^{\alpha_5}\dots\] où \[\alpha_2=\sum_{i=1}^\infty\left[\dfrac{n}{2^i}\right],\quad \alpha_5=\sum_{i=1}^\infty\left[\dfrac{n}{5^i}\right].\] Mais pour \(n\geq 2\) \[\alpha_5=\sum_{i=1}^\infty\left[\dfrac{n}{5^i}\right]<\alpha_2=\sum_{i=1}^\infty\left[\dfrac{n}{2^i}\right].\] Par conséquent, pour que l’écriture décimale de \(n!\) se termine par exactement \(2006\) zéros il est essentiel que \(\alpha_5=2006\). Il faut donc déterminer les entiers \(n\) tels que \(n!=2^{\alpha_2}3^{\alpha_3}5^{2006}\dots\). Comme \[\alpha_5=2006=\sum_{i=1}^\infty\left[\dfrac{n}{5^i}\right]<\sum_{i=1}^\infty \dfrac{n}{5^i} =\dfrac{n}{5}\sum_{i=0}^{\infty}5^{-i}=\dfrac{n}{4},\] nous avons \(n>4\times 2006=8024\). Avec un calcul facile l’exposant de \(5\) dans la décomposition de \(8025!\) vaut \[\alpha_5=\sum_{i=1}^\infty\left[\dfrac{8025}{5^i}\right]=1605+321+64+2=2004.\] Il faut nous faut donc deux zéros supplémentaires, par conséquent, le plus petit entier \(n\) tel que \(n!\) se termine par \(2006\) zéros est \(n=8035\) et l’ensemble cherché est \(8035, 8036, 8037, 8038, 8039\).


Dénombrement dans les groupes *

9 novembre 2022 12:23 — Par Patrice Lassère

Soient \(G\) un groupe fini, \(A,B\) deux parties de \(G\) telles que \[\text{card}(A)+\text{card}(B)>\text{card}(G).\] Montrer que \(AB=G\) (où \(AB=\{\ ab,\ a\in A,\ b\in B\}\)).



[ID: 2564] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]
Solution

Dénombrement dans les groupes
Par Patrice Lassère le 9 novembre 2022 12:23

Soit \(g\in G\), il s’agit de montrer que \(g\) s’écrit sous la forme \(g=ab\) où \(a\in A,\ b\in B\).

Soit \(A^{-1}g:=\{\,a^{-1}g,\ a\in A\,\}\), l’application \(A\ni a\mapsto a^{-1}g\in A^{-1}g\) étant bijective \(\text{card}(A)=\text{card}(A^{-1}g)\) et par suite \(\text{card}(A^{-1}g)+\text{card}(B)>\text{card}(G)\). Il en résulte immédiatement que \(\text{card}(A^{-1}g)\cap\text{card}(B)\neq\emptyset\) i.e. il existe \(a\in A\) tel que \(a^{-1}g=b\in B\) soit \(g=ab\).


Les-Mathematiques.net Mathématiques vivantes

Thématiques

;
Success message!