Niveau exercices

Combinatoire

Posté par
matheux14 14-02-26 à 15:37

Soit $n$ un entier naturel. Montrer que $\forall n \ge 3, \sqrt{n} < \sqrt[n]{n!}$ .

Je pars du fait que $\dfrac{(n^2)!}{(n!)^n}$ est la façon de repartir $n^2$ éléments en $n$ paquets de $n$ éléments. (D'après la remarque de Rintaro ici Démonstration )..

Ici on veut montrer que $\dfrac{n}{(n!)^n}$ pour $n \ge 3$ .

Prenons E l'ensemble des matrices $n \times n$ dont chaque ligne est une permutation de $\{1, 2, \dots, n\}$

Donc $card(E) = (n!)^n$ .

On peut construire $n + 1$ matrices tous différents dans $E$ , on montre que $(n!)^n \ge n + 1$

Pour $n \ge 3, (n!)^n \ge n + 1 > n$

Donc $(n!)^n > n \iff (n!)^{\frac{1}{2}} > n^{\frac{1}{2}}$ .

Cette preuve tient elle la route ?

Merci.

Posté par re : Combinatoire 14-02-26 à 17:18

Bonjour,

Je n'ai rien compris à ta démo.

On te demande de montrer $\forall n \ge 3, \sqrt{n} < \sqrt[n]{n!}$ et tu aboutis en fin de démo à quelque chose de tout à fait différent ... et je pense que la manière d'arriver au résultat qui n'était pas celui demandé est fait également avec des erreurs.

Attends l'avis d'autres.

Posté par re : Combinatoire 14-02-26 à 17:31

Il y a deux erreurs de frappe

matheux14 @ 14-02-2026 à 15:37

Soit $n$ un entier naturel. Montrer que $\forall n \ge 3, \sqrt{n} < \sqrt[n]{n!}$ .

Je pars du fait que $\dfrac{(n^2)!}{(n!)^n}$ est la façon de repartir $n^2$ éléments en $n$ paquets de $n$ éléments. (D'après la remarque de Rintaro ici

Démonstration )..

Ici on veut montrer que $\dfrac{n}{(n!)^n} {\red{< 1}}$ pour $n \ge 3$ .

Prenons E l'ensemble des matrices $n \times n$ dont chaque ligne est une permutation de $\{1, 2, \dots, n\}$

Donc $card(E) = (n!)^n$ .

On peut construire $n + 1$ matrices tous différents dans $E$ , on montre que $(n!)^n \ge n + 1$

Pour $n \ge 3, (n!)^n \ge n + 1 > n$

Donc $(n!)^n > n \iff (n!)^{\frac{{\red{n}}}{2}} > n^{\frac{1}{2}}$ .

Cette preuve tient elle la route ?

Merci.

Posté par re : Combinatoire 14-02-26 à 19:20

Rebonjour,

L'énoncé demande de démontrer que $\sqrt{n} < \sqrt[n]{n!}$ (pour n >= 3)

Ceci est équivalent à : $n^{\frac{1}{2}} < (n!)^{\frac{1}{n}}$ , donc : $n^{\frac{n}{2}} < n!$ ou encore : $n < (n!)^{\frac{2}{n}}$

Ce n'est pas la même chose que $\frac{n}{(n!)^n} < 1$ , là tu arrives à $n < (n!)^n$

Posté par re : Combinatoire 14-02-26 à 20:31

Ah oui

Merci candide2

Posté par re : Combinatoire 15-02-26 à 14:00

Notons $[r]={1,2,\dots,r}$ . On veut montrer, pour $n\ge 3$ , $\sqrt n<\sqrt[n]{n!}\ \Longleftrightarrow\ n^{\frac{n}{2}}<n!.$

$\star$ Une injection clé : $[n]\hookrightarrow [k]\times[n+1-k]$

Fixons $1\le k\le n$ et posons $A_k=[k]\times[n+1-k].$

Définissons l'application $\iota_k:[n]\to A_k$ par $\iota_k(t)= \begin{cases} (t,1) & \text{si } 1\le t\le k,\\ (k,t-k+1) & \text{si } k<t\le n. \end{cases}$

Elle est bien à valeurs dans $A_k$ (car si $t>k$ , alors $2\le t-k+1\le n-k+1=n+1-k$ ).

Elle est injective (les deux branches ne se recouvrent pas, et dans chaque branche on distingue $t$ ).

Donc $|A_k|\ge |[n]|=n$ .

$\star$ Cas pair : $n=2m$ (donc $m\ge 2$ )

Considérons l'ensemble $E=\prod_{k=1}^{m}\bigl([k]\times[n+1-k]\bigr).$

Alors $|E|=\prod_{k=1}^{m}k(n+1-k)=1\cdot2\cdots m\cdot(m+1)\cdots n=n!.$

Par l'injection précédente, pour chaque $k$ on a $[n]\hookrightarrow [k]\times[n+1-k]$ . En prenant le produit, on obtient une injection $[n]^m\hookrightarrow E.$
Donc $n^m=|[n]^m|\le |E|=n!.$

De plus, pour $n\ge 4$ , on a $|[2]\times[n-1]|=2(n-1)>n$ , donc l'injection n'est pas une bijection et on a en fait
$n!>|[n]^m|=n^m=n^{\frac{n}{2}}.$

$\star$ Cas impair : $n=2m+1$ (donc $m\ge 1$ )

On reprend $E=\prod_{k=1}^{m}\bigl([k]\times[n+1-k]\bigr).$

Cette fois, $|E|=\prod_{k=1}^{m}k(n+1-k)=\dfrac{n!}{m+1}$ (car il manque exactement le facteur central $m+1$ ).

Comme précédemment, on a une injection $[n]^m\hookrightarrow E$ , donc $n^m\le |E|=\dfrac{n!}{m+1} \Longrightarrow n!\ge (m+1)n^m.$

Enfin, comme $n=2m+1$ , on a $n^2=2m+1+m^2>2m+1=n$ , donc
$m+1>\sqrt n.$

Ainsi $n!\ge (m+1)n^m>\sqrt n,n^m=n^{m+\frac12}=n^{\frac{n}{2}}.$

Posté par re : Combinatoire 15-02-26 à 17:27

Bonjour,

$(n!)^2 = n! * n! = (1 * 2 * 3 * . . . * n) * (1 * (n-1) * (n-2) * . . . * 1) = \Pi_{k=1}^n\ [k*(n+1-k)]$ (1)

Pour k entre 2 et (n-1), on a k(n+1-k) > n
Pour k = 1 et k = n, on a k(n+1-k) = n

Remis dans (1) : $(n!)^2 > \Pi_{k=1}^n\ n$

$(n!)^2 > n^n$ qui est équivalent à CQFD