Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
237 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Preuve bijective.

Envoyé par CechLM 
Preuve bijective.
il y a deux années
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 ?!)).
Re: Preuve bijective.
il y a deux années
1) Donner une preuve bijective de l'égalité $\displaystyle\sum_{k=0}^n\binom{n}{k}2^k=3^n$ en comptant de deux façons différentes les couples de parties emboîtées $A\subset B\subset\{1,\dots,n\}$.

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.)
Re: Preuve bijective.
il y a deux années
Pour la 1) j'ai une idée : Soit $U = \{(A,B) ; A \subseteq B\}$.
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$.



Edité 4 fois. La dernière correction date de il y a deux années et a été effectuée par CechLM.
Re: Preuve bijective.
il y a deux années
Pour la 2) je ne suis pas motivé, veillez m'excuser les nombres de Fibonacci me stressent.



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par CechLM.
Re: Preuve bijective.
il y a deux années
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 !
Re: Preuve bijective.
il y a deux années
C'est OK. Dans le détail, je vais pinailler, on ne se refait pas.

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) ?



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par Math Coss.
Re: Preuve bijective.
il y a deux années
Merci Math Coss.

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.
Re: Preuve bijective.
il y a deux années
avatar
Saurais-tu démontrer par bijection la formule des coefficients binomiaux ?
Re: Preuve bijective.
il y a deux années
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.
Re: Preuve bijective.
il y a deux années
2) Nombre de suites de $1$ et de $2$ de somme $n$.
(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é.



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par Chaurien.
Re: Preuve bijective.
il y a deux années
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).
Re: Preuve bijective.
il y a deux années
3,5) Calculer $\displaystyle\sum_{k=0}^nk^2\binom{n}{k}$.

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).



Edité 2 fois. La dernière correction date de il y a deux années et a été effectuée par CechLM.
Re: Preuve bijective.
il y a deux années
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).
Re: Preuve bijective.
il y a deux années
Pour 3,5) Tu avais une indication très précise dans le document mis en lien. Tu l'as complètement ignorée.
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é 1 fois. La dernière correction date de il y a deux années et a été effectuée par GaBuZoMeu.
Re: Preuve bijective.
il y a deux années
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...



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par Math Coss.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 137 357, Messages: 1 329 658, Utilisateurs: 24 407.
Notre dernier utilisateur inscrit Louragli.


Ce forum
Discussions: 748, Messages: 6 022.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page