Preuve bijective.
Salut à tous.
J'aimerais améliorer ma capacité à réaliser des preuves bijectives.
Je cherche des planches d'exercices résolus sur Internet.
Ou mieux, si vous le souhaitez, vous pouvez me donner des exercices de preuves bijectives que vous estimez indispensables car utile sous différentes formes à différents moments.
(Sur ce point là, j'aimerais répondre à la question sur le post pour que vous me corrigiez donc je souhaite que vous me testiez afin de ne pas me donner un exercice que je ne pourrais résoudre (du moins pour l'instant car je vais progresser n'est-ce pas ?!)).
J'aimerais améliorer ma capacité à réaliser des preuves bijectives.
Je cherche des planches d'exercices résolus sur Internet.
Ou mieux, si vous le souhaitez, vous pouvez me donner des exercices de preuves bijectives que vous estimez indispensables car utile sous différentes formes à différents moments.
(Sur ce point là, j'aimerais répondre à la question sur le post pour que vous me corrigiez donc je souhaite que vous me testiez afin de ne pas me donner un exercice que je ne pourrais résoudre (du moins pour l'instant car je vais progresser n'est-ce pas ?!)).
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
2) Donner une preuve bijective du fait que la suite définie par
\[s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots\]
est la suite de Fibonacci. Indication : Montrer que les mots de longueur $n+1$ avec deux lettres $0$ et $1$ qui n'ont pas deux $1$ consécutifs sont comptés par la suite de Fibonacci et, parmi eux, compter ceux qui contiennent exactement $k$ lettres $1$. (Source.)
Soit $f : U \rightarrow 3^{n} : (A,B) \mapsto f$ avec $f(i) = 0, i \notin B$, $f(i) = 1, i \in B-A$, $f(i) = 2, i \in A$ pour $i\in {1,..,n}$.
Cette opération est bijective car si je prend $g\in 3^{n}$ je peux construire deux ensembles $A = \{i ; f(i) = 2\}$ et $B = \{i ; f(i) \ne 0\}$
Soit $(A,B) \in U$,on remarque que choisir $B$ c'est choisir $k$ éléments parmi $n$ puis choisir $A$ c'est choisir $f \in \{0,1\}^{k}$ telle que $A = \{f(i) = 1\}$.
Ainsi on a une surjection, la somme $\ge |U|$
Réciproquement prendre une partie et une fonction définie de la sorte permet de construire un élément de $U$.
D'abord, je ne crois pas que ce soit une bonne idée de noter $3^n$ plutôt que $\{0,1,2\}^n$. Quelque fanatique de la théorie des ensembles risque de monter au créneau pour expliquer doctement que $0=\emptyset$, $1=\{\emptyset\}=\{0\}$, $2=\{\emptyset,\{\emptyset\}\}=\{0,1\}$ et $3=\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\}=\{0,1,2\}$ (si les accolades sont bonnes), ça ne me paraît pas pertinent.
Pour le deuxième comptage, il faut justifier la somme (sur $k$) et le produit (du coefficient binomial par la puissance). Pour cela, on peut commencer par nommer $\mathcal{C}$ l'ensemble des couples $(A,B)$ tels que $A\subset B$ et, pour $k\in\{0,\dots,n\}$, $\mathcal{C}_k$ l'ensemble de ceux tels que $|B|=k$. On a alors $\mathcal{C}=\bigcup_{k=0}^n\mathcal{C}_k$ (réunion disjointe).
Fixons $k$ et dénombrons $\mathcal{C}_k$. À tout $(A,B)$, on associe la partie $B$. On obtient une application $f_k$ de $\mathcal{C}_k$ vers l'ensemble des parties à $k$ éléments de $\{1,\dots,n\}$. Pour $B$ fixé, l'ensemble des antécédents de $B$ par $f_k$ est l'ensemble des $(A,B)$ avec $A\subset B$ : il y en a donc $2^k$, qui est indépendant de $B$. Par le lemme des bergers, le cardinal de $\mathcal{C}_k$ est $2^k\binom{n}{k}$.
Puisque la réunion des $\mathcal{C}_k$ est disjointe, on a bien la formule annoncée.
----
3) (même esprit) Donner une preuve bijective de $\displaystyle \sum_{k=0}^nk\binom{n}{k}=n\times2^{n-1}$.
4) Donner une preuve bijective de $\displaystyle k\binom{n}{k}=n\binom{n-1}{k-1}$. Est-ce que ça peut servir à donner une autre preuve de 3) ?
Je suis désolé j'aurais du être un peu plus précis. Je vous remercie sincèrement pour votre exercice et vos précisions.
Je ne souhaite pas faire les exercices 3) et 4) car je pense savoir les faire et donc, j'estime (c'est personnel) qu'ils ne me feront pas progresser.
Pouvez vous m'en donner qui me feront voir de nouvelles méthodes pour progresser s'il vous plaît.
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.
(Le petit Archimède, problème 142, PA 86-87, octobre 1982).
8)c) Somme des $(_{k}^{n})d_k$, et formule d'inversion de Désiré André.
En utilisant plusieurs fois $\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$ j'ai trouvé $n(n-1)2^{n-2}+n2^{n-1}$
> 5) Donner une preuve bijective de
> $\sum_{k=0}^n(-1)^k\binom{n}{k}=0$. En déduire
> [url=https://www.maa.org/sites/default/files/26913
> 7731390.pdf]une preuve combinatoire[/url] de
> $\cos^2x+\sin^2x=1$.
Je le fait pas mais mon idée c'est de mettre en bijection le partie de cardinal pair alors les parties de $\{1,...,n-1\}$.
Merci pour le lien. D'ailleurs les séries génératrices m'intéressent (Formelle, exponentielle et Dirichlet exclusivement).
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).
Compter les triplets $(x,y,S)$ où $S$ est une partie de $E=\{1,2,\ldots,n\}$ et $(x,y)$ un couple d'éléments de $S$. Une façon de compter :
- on compte les $(x,T)$ avec $x\in E$ et $T\subset E\setminus\{x\}$ (c'est en bijection avec l'ensemble des triplets $(x,x,S)$ par $S=T\cup\{x\}$),
- on compte les $(x,y,U)$ avec $x\in E$, $y\in E$, $y\neq x$ et $U\subset E\setminus \{x,y\}$ (en bijection avec l'ensemble des triplets $(x,y,S)$ où $x\neq y$ par $S=U\cup\{x,y\}$),
- on additionne.
Edit : À la réflexion, vu la forme du résultat, ce n'est pas si surprenant...