Chargé de TDs : Anthony Lick

TD1 : Maths Discrètes

EX1

1. L’ensemble des parties à un nb pair et impair d’éléments sont en bijection (ajouter $n$ si il n’y est pas, l’enlever si il n’y est pas) et forment une partition de $𝒫(⟦1,n⟧)$ 2. M1: $\sum _{i=0}^n|F|=\sum _{i=0}^{n}i\sum _{F\subseteq ⟦1,n⟧,|F|=i}|F|=\sum _{i=0}^{n}i(\genfrac{}{}{0ex}{}{n}{i})$ et $\sum _{i=0}^n|F|=\sum _{i=0}^n|\{F\subseteq ⟦1,n⟧;i\in F\}|=\sum _{i=0}^n{2}^{n-1}=n{2}^{n-1}$

M2: On utilise $\sum _{i=0}^{n}i(\genfrac{}{}{0ex}{}{n}{i})=\sum _{i=0}^n(n-i)(\genfrac{}{}{0ex}{}{n}{i})=\sum _{i=0}^n(n-i)(\genfrac{}{}{0ex}{}{n}{n-i})$

1. A tout couple formé d’une partie $F$ de $⟦1,n⟧$ à $l\ge k$ élément et d’une partie à $G\subseteq F$, on associe de manière bi-univoque le couple $(G,F\mathrm{\setminus }G)$.
2. cf. dessin

EX 2

1. On note $P_j$ l’ensemble des paires dont le max vaut $j$.

$|P_j|=j$,

1. Soit $X$ l’ensemble des triplets. $X\stackrel{\scriptscriptstyle\mathrm{def}}{=}\bigcup _{m=1}^N\underset{Y_m}{\underbrace{(x,y,z);max(x,y,z)=m}}$

Selon que $m$ soit atteint 1, 2 ou 3 fois :

Puis, on utilise $m^3=|X|=\sum _{m=1}^{N}3m^2-3m+1$

Pour avoir $\sum _{j=1}^n{j}^2$

EX3

Regarder $f:\{n_1,\cdots ,n_{12}\}⟶⟦0,10⟧,n\mapsto n\mathrm{m}\mathrm{o}\mathrm{d}11$

Puis : principe des tiroirs.

EX4

cf. dessin

EX5

On note $L$ les mots sans lettre, $C$ les mots sans chiffres, $S$ ceux sans caractère spéciaux.

EX6

On dénombre les applications qui ne sont PAS des surjections (qui sont au nombre de $n^m-s(m,n)$) : de telles applications sont de la forme $f:⟦1,n⟧⟶⟦1,n⟧$ à valeurs dans $⟦1,n⟧\mathrm{\setminus }{i}_1,\cdots ,i_k$, pour des $i_1,\cdots ,i_k\in ⟦1,n⟧$ deux à deux distincts.

Donc, en notant, pour $i\in ⟦1,n⟧$, $E_i$ l’ensemble des applications dont l’image ne contient pas $i$,

Donc : $s(m,n)=n^m+\sum _{k=1}^{n-1}(\genfrac{}{}{0ex}{}{n}{k})(-1{)}^k(n-k{)}^m$

EX7

Généralisation de l’exo 4.

Conjecture (FAUSSE) :

Dans un groupe de $2n$ personnes, il existe $n$ personnes qui se connaissent mutuellement ou $n$ qui ne se connaissent pas mutuellement.