TD1 : Dénombrement

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\limits_{i=0}^n \vert F\vert = \sum\limits_{i=0}^n i \sum\limits_{F ⊆ ⟦1,n⟧, \vert F\vert =i} \vert F\vert = \sum\limits_{i=0}^n i \binom{n}{i}\) et \(\sum\limits_{i=0}^n \vert F\vert = \sum\limits_{i=0}^n \vert \{F ⊆ ⟦1,n⟧; i ∈ F\} \vert = \sum\limits_{i=0}^n 2^{n-1} = n 2^{n-1}\)

M2: On utilise \(\sum\limits_{i=0}^n i \binom{n}{i} = \sum\limits_{i=0}^n (n-i) \binom{n}{i} = \sum\limits_{i=0}^n (n-i) \binom{n}{n-i}\)

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

EX 2

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

$\vert P_j\vert = j$,

\[E_2 = \bigcup\limits_{j=1}^n P_j\] \[⟹ \binom{n}{2} = \sum\limits_{j=1}^n j\]

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

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

\[\vert Y_m\vert = 3(m-1)^2 + 3(m-1) + 1 = 3m^2 - 3m + 1\]

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

Pour avoir \(\sum\limits_{j=1}^n j^2\)

EX3

Regarder \(f: \{n_1, ⋯, n_{12}\} ⟶ ⟦0,10⟧, n \mapsto n \, { \rm mod } \, \, 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.

\[\vert MDP^c\vert = \vert L∪C∪S\vert \\ = \vert L\vert + \vert C\vert + \vert S\vert - \vert L∩C\vert - \vert L∩S\vert - \vert S∩C\vert + \vert L∩C∩S\vert \\ = (10+7)^8 + (26+7)^8 + (10+26)^8 - 10^8 - 7^8 - 26^8 + 0\] \[MDP = 43^8 - \vert MDP^c\vert \\ = 43^8 - (10+7)^8 - (26+7)^8 - (10+26)^8 + 10^8 + 7^8 + 26^8\]

EX6

\[\vert \bigcup_i E_i\vert = \sum\limits_{1 \leq i_1 < ⋯ < i_k \leq n} (-1)^{k-1} \bigcap_j E_{i_j}\]

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⟧\backslash {i_1, ⋯, i_k}$, pour des $i_1, ⋯, i_k ∈ ⟦1,n⟧$ deux à deux distincts.

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

\[\begin{align*} n^m - s(m,n) &= \vert \bigcup_i E_i\vert \\ &= \sum\limits_{1 \leq i_1 < ⋯ < i_k \leq n} (-1)^{k-1} \vert \bigcap_j E_{i_j}\vert \\ &= \sum\limits_{1 \leq i_1 < ⋯ < i_k \leq n} (-1)^{k-1} (n-k)^m \\ &= \sum\limits_{k = 1}^n \sum\limits_{F ⊆ ⟦1,n⟧, \vert F\vert = k} (-1)^{k-1} (n-k)^m \\ &= \sum\limits_{k = 1}^n \binom{n}{k} (-1)^{k-1} (n-k)^m &&\text{(dernier terme nul)}\\ \end{align*}\]

Donc : \(s(m,n) = n^m + \sum\limits_{k = 1}^{n-1} \binom{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.