Preuve bijective.

C'est quand même mal rédigé pour montrer que $|U| = \displaystyle\sum_{k=0}^n\binom{n}{k}2^k$, d'autant plus si tu veux en faire une preuve bijective !

Le 4), si simple qu'il soit, me semble vraiment intéressant alors je le corrige moi-même. C'est un double dénombrement de l'ensemble $F=\{(x,A),\ x\in A\subset E\}$ où $E=\{1,\dots,n\}$. On a deux applications évidentes $p_1:F\to E$, $(x,A)\mapsto x$ et $p_2:F\to\mathcal{P}_k(E)$, $(x,A)\to A$.

Pour $x\in E$, $p_1^{-1}(x)$ est en bijection avec l'ensemble des parties à $k$ éléments qui contiennent $x$, en correspondance naturelle avec l'ensemble des parties à $k-1$ éléments de $E\setminus\{x\}$ : le cardinal est $\binom{n-1}{k-1}$ et le lemme des bergers donne $|F|=n\binom{n-1}{k-1}$. Pour $A\in\mathcal{P}_k(E)$, $p_1^{-1}(A)$ est en bijection avec $A$, ce qui donne : $|F|=k\binom{n}{k}$.

----

3,5) Calculer $\displaystyle\sum_{k=0}^nk^2\binom{n}{k}$. (Hint.)

5) Donner une preuve bijective de $\sum_{k=0}^n(-1)^k\binom{n}{k}=0$. En déduire une preuve combinatoire de $\cos^2x+\sin^2x=1$.

5,5) Démontrer l'identité de Vandermonde. Cas particulier (je crois) : $\displaystyle\binom{2n}n=\sum_{k=0}^n\binom{n}{k}^2$.

6) Dénombrer l'ensemble des $k$-listes de parties $(A_1,\dots,A_k)$ de $E=\{1,\dots,n\}$ (facile) puis l'ensemble des $k$-listes telles que $\bigcup_{i=1}^kA_i=E$. Donner une preuve combinatoire de $\sum_{i=0}^n(-1)^i2^{k(n-i)}\binom{n}{i}=(2^k-1)^n$.

6,5) Démontrer le petit théorème de Fermat grâce aux bracelets de $p$ perles ayant $k$ couleurs possibles avec au moins deux couleurs (Hint.)

7) Démontrer qu'un entier a autant de partitions ayant un nombre impair de parts que de partitions dont toutes les parts sont distinctes.

8) Dénombrer de trois façons différentes les permutations de $\mathfrak{S}_n$ sans point fixe : a) par une relation de récurrence, puis avec une série génératrice ; b) par inclusion-exclusion (introduire pour chaque $k$ les permutations qui fixent $k$) ; c) j'ai oublié...

9) Donner 12 interprétations combinatoires des nombres de Catalan et expliciter des bijections entre elles.

10) Relier le développement en série entière de $\frac{1}{\cos x}+\tan x$ aux permutations alternantes.

11) Trouver et lire le livre recensé ici.

12) Idem avec ce livre.

Pour 8c, à la dénomination près que je ne connais(sais) pas, c'est bien ce qui est dans Oraux X-ENS, Algèbre 1 de Francinou-Gianella-Nicolas. Il y est également mentionné que [Comtet] demande de donner une preuve directe de $d_n=nd_{n-1}+(-1)^n$ (qui dérive facilement de $d_{n+1}=n(d_n+d_{n-1})$ sinon).

3,5) Ce n'est pas une preuve bijective !

Quitte à faire des manipulations algébriques, voici une autre méthode : reconnaître dans cette somme quelque chose de très proche de $\sum_{k=0}^nk(k-1)\binom{n}{k}t^{k-2}$, qui est visiblement une dérivée seconde ; la différence est, à une puissance de $t$ près, $\sum_{k=0}^nk\binom{n}{k}t^{k-1}$ qui est une dérivée.

5) Il faut trouver une bijection entre parties de cardinal pair et parties de cardinal impair (pour un ensemble non vide).

3,5) C'est amusant que les deux preuves, bijective et algébrique, utilisent le même découpage en deux : les couples $(x,y)$ selon que $x=y$ ou $x\ne y$ d'une part, le terme $k^2$ comme somme de $k$ et $k(k-1)$ d'autre part.

Edit : À la réflexion, vu la forme du résultat, ce n'est pas si surprenant...