Leçon 310 agrégation interne : exercices faisant intervenir des dénombrements

gai requin

Tu n’as rien fait @OShine !

OShine

J'ai donné une réponse.

gai requin

On doit déduire le théorème de Wilson donc tu n’as donné aucune réponse !

Ericpasloggue

OShine a dit :

J'ai trouvé un autre exercice mais je ne sais pas s'il correspond à cette leçon.
C'est le problème du scrutin.

Je crois me souvenir qu'il est traité en détail dans la seconde édition de mon bouquin... (attention, ça tape un peu plus haut que ton tout-en-un).

OShine

L'exercice sur le Scrutin est difficile, mais le corrigé est très bien expliqué dans le DUNOD.
Il n'y a pas de dessin, mais j'ai compris l'exercice en faisant un dessin, un dessin est indispensable pour résoudre la question 1.b.
C'est un exercice très intéressant.

OShine

@gai requin 
Peut-être, bon nombre d'exercices proposés ici sont très durs, et je pense que plus de 90% des gens qui ont eu l'agreg interne ne savent pas les résoudre. 
Je pense que je ne vais pas passer 1 mois sur cette leçon, il y a plein d'autres choses à voir.

$E=\{0, \cdots, p-1 \}$.
Un $k$ cycle s'écrit $(a_1 \cdots a_k)$.
Le nombre de cycles de longueur $k$ est $\dfrac{p!}{(p-k)! k}$
Donc le nombre de permutation qui ont exactement un cycle est :    
$\boxed{S=\displaystyle\sum_{k=1}^{p} \dfrac{p!}{(p-k)! k}}$
Pas compris le lien avec le théorème de Wilson.

Dans le Liret, le théorème de Wilson est démontré avec de l'arithmétique.

gai requin

Avec de l’arithmétique, c’est deux lignes.

OShine

Ah d'accord.
Sinon j'ai cet exo sur les anneaux quotients.

bisam

@bisam : Comment tu as fait ?

J'ai juste suivi l'indication donnée par @noobey.

Quand on cherche une expression d'une suite $(C(n))_{n\in\N}$ (d'entiers la plupart du temps, mais pas uniquement) , il est classique de faire intervenir la série génératrice $\sum_{n\geq 0} C(n) x^n$. Ainsi, le coefficient $C(n)$ est celui du monôme de degré $n$ dans cette décomposition en série entière.

Si on peut déterminer celle-ci par un autre moyen, soit en utilisant la définition de la suite pour l'exprimer (par exemple dans le cas présent, ou encore dans le cas où $C(n)$ serait le cardinal de $\{(a,b)\in\N^2, 3a+5b=n\}$) ou bien si on arrive à trouver une relation de récurrence (par exemple avec les nombres de Bell ou ceux de Catalan), on a de bonnes chances d'obtenir l'expression cherchée.

Ici, avec l'indication de @noobey, on constate que le produit infini qu'il donne répond précisément au problème... et il suffit de le calculer autrement pour trouver le résultat. Dans ce cas précis, les questions de convergence des objets impliqués se règlent en un tournemain donc l'exercice se conclut rapidement.

Je n'aurais probablement pas pensé tout seul à ce produit "magique"... mais l'indication est suffisante pour trouver en quelques minutes à peine.

Je le répète : c'est une méthode hyper classique et le fait que tu n'aies pas vu le lien me fait dire que tu es loin de maîtriser les techniques usuelles de dénombrement.

OShine

@bisam
Je n'ai pas encore vu les séries génératrices je n'ai pas de recul sur le lien entre denombrement et série génératrice.
Je ne comprends pas le lien entre le produit infini et l'exercice.

noobey

Dans 
$(1 + x + x^{1 + 1} + x^{1+1+1})(1 + x^2 + x^{2 + 2} + x^{2 + 2 + 2}) (1 + x^4 + x^{4 + 4} + x^{4 + 4 + 4})(1 + x^8 + x^{8 + 8} + x^{8 + 8 + 8})...$

Le monôme de degré 8 est obtenu par : 
$$(1 \times 1 \times 1 \times x^8) + (1 \times 1 \times x^{4 + 4} \times 1) + ( 1 \times 1 \times x^{2 + 2} \times x^4) + ... = 5x^8$$


Je t'ai proposé cet exo pour que tu fasses un peu d'analyse, c'est un raisonnement un peu moins combinatoire ça aurait du te plaire et ça change un peu des autres exo
Les séries génératrices y a pas vraiment de théorie là dessus

OShine

Oui je vais passer à la bibliothèque voir si je trouve des exos qui lient analyse et dénombrement.
J'ai déjà des exos qui font le lien entre dénombrement et arithmétique, anneaux, et probabilités.

De combien de façons $C(n)$ peut-on décomposer $n$ comme somme décroissante de puissances de $2$ où chaque puissance apparait au maximum $3$ fois?

Je n'ai toujours pas compris le lien avec :  $$\prod_{i = 0}^{\infty} (1 + x^{2^i} + x^{2 \times 2^i} + x^{3 \times 2^i})$$

Je ne vois pas le rapport entre $C(n)$ et le produit infini, ni comment trouver $C(n)$. 

noobey

Mais tu lis mon exemple?

OShine

Oui mais je ne comprends pas d'où sortent ces calculs, je ne vois pas le rapport avec l'exercice.
Même pour $n=8, je ne comprends pas le rapport entre l'exercice et tes calculs de produits.

bisam

Ce qui est intéressant dans le calcul de @noobey, ce sont les puissances des $x$.

On constate que si l'on prend une puissance $n$ fixée, celle-ci va apparaître dans le développement du produit à chaque fois qu'il existe une suite d'entiers $(k_i)_{i\in\N} \in \{0,1,2,3\}^{\N}$ telle que l'on peut écrire $n$ sous la forme \[n=\sum_{i=0}^{+\infty}k_i 2^i\]

Il se trouve que le nombre de fois où cela est possible est précisément la définition de $C(n)$.

Ensuite, pour calculer la somme de la série génératrice, on constate que l'on peut écrire le produit infini sous une forme où il est télescopique, ce qui nous donne une fraction rationnelle que l'on décompose en éléments simples avant de la décomposer en série entière et de conclure par identification des coefficients de deux séries entières convergentes (il n'est pas difficile de majorer $C(n)$ par $n+1$, ce qui permet d'assurer que le rayon de convergence est supérieur ou égal à $1$ puis égal à $1$).

OShine

bisam a dit :

On constate que si l'on prend une puissance $n$ fixée, celle-ci va apparaître dans le développement du produit à chaque fois qu'il existe une suite d'entiers $(k_i)_{i\in\N} \in \{0,1,2,3\}^{\N}$ telle que l'on peut écrire $n$ sous la forme \[n=\sum_{i=0}^{+\infty}k_i 2^i\]

Il se trouve que le nombre de fois où cela est possible est précisément la définition de $C(n)$.

Merci, je crois avoir compris ce passage. 
Le terme $a_n$ devant $x^n$ vaut : 
$\displaystyle\sum_{(i,j,k) \in \N^{3}} x^{2^i} x^{2 \times 2^j} x^{3 \times 2^i}= \boxed{\displaystyle\sum_{(i,j,k) \in \N^{3} \\ 2^i+ 2 \times 2^j +3 \times 2^k =n
} x^{2^i+ 2 \times 2^j +3 \times 2^k}}$.
On a donc en puissance : $2^i+2 \times 2^j+3 \times 2^k$ avec $i,j,k \in \N$.
Donc $n$ peut s'écrire sous la forme $\displaystyle\sum_{i=0}^{+\infty} k_i 2^i$ avec $(k_i)_{i\in\N} \in \{0,1,2,3\}^{\N}$

OShine

Niveau ENS cet exercice @noobey ? Un livre ? Si je le mets dans ma fiche pour les oraux, il me faudrait un corrigé, c'est du très haut niveau.
Je continue, en suivant l'indication de @bisam.
Je ne vois pas de télescopage du produit.

Notons : $P_N =\displaystyle\prod_{i = 0}^{N} (1 + x^{2^i} + x^{2 \times 2^i} + x^{3 \times 2^i})$.
Soit $i \in [|0,N|]$.
On a : $1 + x^{2^i} +( x^{ 2^i})^2 + (x^{2^i})^3 $
Pour $x \ne 1$, on a : $P_i(x)= 1 + x^{2^i} +( x^{ 2^i})^2 + (x^{2^i})^3 =\dfrac{1-(x^{2^i})^4}{1-x}$
Donc $P_i(x)=\dfrac{1-x^{2^{i+2}}}{1-x}$
Ainsi : 
$P_N(x)=\dfrac{1-x^{4}}{1-x} \times \dfrac{1-x^{8}}{1-x} \times \dfrac{1-x^{8}}{1-x} \cdots \times  \dfrac{1-x^{N+1}}{1-x} \times \dfrac{1-x^{N+2}}{1-x}$
Je ne vois pas où ça se télescope.

Avec le ln sinon, j'ai eu l'idée mais $\ln(P_n)=\displaystyle\sum_{i=0}^N 1 + x^{2^i} + x^{2 \times 2^i} + x^{3 \times 2^i}$.
Toujours pas de télescopage en vue.

raoul.S

Je ne vois pas où ça se télescope.

C'est parce que tu as une coquille, c'est $P_i(x)= 1 + x^{2^i} +( x^{ 2^i})^2 + (x^{2^i})^3 =\dfrac{1-(x^{2^i})^4}{1-x^{2^i}}$

OShine

Merci @raoul.S   
J'avoue que c'est un exercice très intéressant et qui utilise beaucoup de connaissances différentes.

noobey

C'est un exercice de mathtraining. Donc niveau olympiades. Néanmoins avec l'indic il devient abordable

OShine

@noobey
Ok merci, à mon avis le jury aimerait beaucoup un exercice de ce genre. 

Je continue.
On a $\forall x \ne 1 \ P_N(x)=\displaystyle\prod_{i=0}^N \dfrac{1-x^{2^{i+2}}}{1-x^{2^i}}$.
$P_N(x)=\dfrac{\displaystyle\prod_{j=2}^{N+2} (1-x^{2^j})}{\displaystyle\prod_{i=0}^N  (1-x^{2^i})} $
Donc : $P_N(x)=\dfrac{1-x^{2^{N+1}}}{(1-x)(1-x^2)}$
Ainsi : $\boxed{P_N(x)=\dfrac{(1-x^{2^{N+1}})(1-x^{2^{N+2}}) }{(1-x)^2 (1+x)}}$

J'ai des difficultés à déterminer la décomposition en éléments simples.
Je dois calculer la partie entière de la fraction rationnelle, pour l'instant, je ne vois pas j'ai essayé de poser la division euclidienne, ça me semble trop compliqué, on ne connaît pas $N$....

raoul.S

$\dfrac{1}{(1-x)^2 (1+x)}=\dfrac{1/4}{1+x}+\dfrac{1/4}{1-x}+\dfrac{1/2}{(x-1)^2}$

OShine

@raoul.S
Je sais faire cette décomposition en éléments simples élémentaire, mais le degré du numérateur de la fraction rationnelle est supérieur à celui du dénominateur, il reste une partie entière que je n'arrive pas à déterminer.
Je trouve : 
$P_N(x)=\dfrac{(1-x^{2^{N+1}})(1-x^{2^{N+2}}) }{(1-x)^2 (1+x)}$

OShine

raoul.S a dit :

$\dfrac{1}{(1-x)^2 (1+x)}=\dfrac{1/4}{1+x}+\dfrac{1/4}{1-x}+\dfrac{1/2}{(x-1)^2}$

$P_4(x)=\dfrac{(1-x^{32})(1-x^{64})}{(1-x)^2 (1+x)}$.

Comment trouver la partie entière de la fraction rationnelle ? 

raoul.S

On se fiche de $P_N$, ce qui nous intéresse c'est le produit infini $\prod_{i = 0}^{\infty} (1 + x^{2^i} + x^{2 \times 2^i} + x^{3 \times 2^i})$, et ce produit infini est égal à $\dfrac{1}{(1-x)^2 (1+x)}$.

En fait il n'y a pas besoin de notion de convergence ici, car ce qui nous intéresse c'est la série formelle. Mais vu que je suppose que tu ne connais pas les séries formelles, tu peux te dire que si $|x|<1$ alors le produit infini converge et vaut $\dfrac{1}{(1-x)^2 (1+x)}$ et cette dernière expression vaut $\dfrac{1/4}{1+x}+\dfrac{1/4}{1-x}+\dfrac{1/2}{(x-1)^2}$. Il ne reste plus qu'à redévelopper en série les trois fractions et à trouver l'expression du coefficient devant $x^n$...

OShine

D'accord merci.
Donc $P_N(x) \longrightarrow \dfrac{1}{(1-x)^2(1+x)}=P(x)$
On a $P(x)=\dfrac{1}{4} \displaystyle\sum_{n=0}^{+\infty} (-x)^n +\dfrac{1}{4} \displaystyle\sum_{n=0}^{+\infty} x^n+ \dfrac{1}{2} \displaystyle\sum_{n=0}^{+\infty} \left( \displaystyle\sum_{k=0}^n \right) x^n$
Donc $P(x)= \displaystyle\sum_{n=0}^{+\infty} \dfrac{(-1)^n+2n+3}{4} x^n$
Donc : $\boxed{C(n)=\dfrac{(-1)^n+2n+3}{4}}$
Soit $\boxed{C(n)= \lfloor \dfrac{n}{2} \rfloor +1}$.