Dénombrement formule du crible
Bonjour,
J'ai un ensemble fini $E$, avec $n$ sous-ensembles que je vais appeler $A_1,\ldots,A_n$. Pour des raisons de symétries, j'ai $Card(A_1) = \cdots = Card(A_n)$. Notons ce cardinal $C_1$. De même, toutes les intersections $2$ à $2$ (de parties distinctes) sont de même cardinal, que je note $C_2$. Idem pour les intersections $3$ à $3$ : tous les $Card(A_i\cap A_j\cap A_k)$ (avec $Card({i,j,k}) = 3$) sont égaux. Je note ce cardinal $C_3$, etc. jusqu'à $C_n$.
Ma question est la suivante : y a-t-il un moyen de calculer facilement à l'aide de $C_1,\ldots,C_n$ le cardinal de $B_k$, où $B_k$ est l'ensemble des éléments de $E$ qui appartiennent à au moins $k$ parties parmi $A_1,\ldots,A_n$ ?
En fait, $B_k = \displaystyle \bigcup_{\substack{I\subset \{1,\ldots,n\} \\ Card(I)=k}} \bigcap_{i \in I} A_i$. Il "suffit" alors d'appliquer la formule du crible. Ça se fait bien quand $k=1$, ou à la rigueur $k=2$, mais j'ai un peu de mal à me dépatouiller avec le dénombrement dans le cas général.
J'ai un ensemble fini $E$, avec $n$ sous-ensembles que je vais appeler $A_1,\ldots,A_n$. Pour des raisons de symétries, j'ai $Card(A_1) = \cdots = Card(A_n)$. Notons ce cardinal $C_1$. De même, toutes les intersections $2$ à $2$ (de parties distinctes) sont de même cardinal, que je note $C_2$. Idem pour les intersections $3$ à $3$ : tous les $Card(A_i\cap A_j\cap A_k)$ (avec $Card({i,j,k}) = 3$) sont égaux. Je note ce cardinal $C_3$, etc. jusqu'à $C_n$.
Ma question est la suivante : y a-t-il un moyen de calculer facilement à l'aide de $C_1,\ldots,C_n$ le cardinal de $B_k$, où $B_k$ est l'ensemble des éléments de $E$ qui appartiennent à au moins $k$ parties parmi $A_1,\ldots,A_n$ ?
En fait, $B_k = \displaystyle \bigcup_{\substack{I\subset \{1,\ldots,n\} \\ Card(I)=k}} \bigcap_{i \in I} A_i$. Il "suffit" alors d'appliquer la formule du crible. Ça se fait bien quand $k=1$, ou à la rigueur $k=2$, mais j'ai un peu de mal à me dépatouiller avec le dénombrement dans le cas général.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je ne connais pas la combinatoire, du coup ce que je vais faire peut paraître ultra-tortueux et passe sûrement à côté de bons gros théorèmes dont je n'ai pas la moindre idée, il est même possible que les formules finales puissent être simplifiées:
D'abord on va ajouter ces deux notations:
-$\forall J \in \mathcal{P}([\![ 1, n ]\!] )$ On notera $A_J= \displaystyle \bigcap_{i\in J} A_i$ (avec, au cas où, $A_\emptyset = E$).
- $\forall k \in [\![ 1, n ]\!], d_k=\card(B_k)$
Nommons $N=\min\{ k\mid k\in\mathbb{N}\wedge \forall l \in \mathbb{N},\ l\geq k \rightarrow C_l=0\}-1$, (nécessairement $N\leq n$).
On notera tout d'abord que l'ensemble $\{A_J\mid \card(J)=N\}$ compose une partition de $B_N$ (ils sont d'intersection vide deux à deux). Du coup, on a $d_N=\binom{n}{N}c_N$ et on trouve assez rapidement, que $\forall J \subset [\![ 1, n ]\!]:$ $\card( A_J \cap B_N)= \binom{n-\card(J)}{N-\card(J)} c_N$, et par conséquent, $\card( A_J \setminus B_n) = c_{\card(J)} -\binom{n-\card(J)}{N-\card(J)}c_N$.
Que se passe-t-il si on recommence l'opération sur $E\setminus B_N$ avec les $A_i \setminus B_N$ ?
Du coup, si je ne me suis pas planté à l'assemblage, en introduisant: $\forall k \in [\![ 1, n ]\!]:\ c^{(n)}_k=c_k$ et $\forall (k,i) \in [\![ 1, n ]\!]^2,\ k< i:\ c^{(i-1)}_k=c^{(i)}_k - \binom{n-k}{i-k}c^{(i)}_i$, on doit avoir ça:
$\forall k \in [\![ 1, n ]\!]$ $d_k=\displaystyle \sum_{i=k}^n c^{(i)}_i \binom{n}{i}$
Pour ma part, j'ai tenté une démarche expérimentale. En faisant faire le dénombrement à un ordinateur pour des petites valeurs de $k$ et de $n$, je conjecture : $Card(B_k) = \displaystyle \sum_{j=k}^n (-1)^{j+k} \binom{j-1}{k-1}\binom{n}{j} C_j$.
@Guego
En suivant la voie assez tentante que tu avais indiquée, je suis parvenu à établir la formule conjecturée, mais il y a peut-être plus simple.
Je note: $\:\:E_k = \mathcal P_k ([\![1;n]\!]).\:\: F_k =\mathcal P(E_k) \setminus \{\emptyset\}.\:\:\:\:\quad\forall I \in E_k,\:\:\mathcal A_I =\displaystyle \bigcap_{i\in I} A_i.\:\:\:\quad \:\forall J \in F_k,\:\: U_J = \bigcup _{I \in J} I.$
$\text{Card}(B_k) = \displaystyle \text{Card}\left(\bigcup _{I\in E_k}\mathcal A_I \right) = \sum _{J \in F_k} (-1)^{|J|+1} \text{Card}\left(\bigcap _{I \in J} \mathcal A_I\right) =\sum _{j=1}^n C_j \binom nj a_j.\:\:(\star)\quad\quad\quad \text{où}\quad\:\:a_j= \displaystyle \sum_{ J \in E_k ;\: U_J =[\![1;j]\!] }(-1)^{|J|+1}.$
$a_j$ s'écrit aussi: $\quad a_j =\displaystyle \sum_{s\geqslant1} (-1)^{s+1} b_{s,j}. \quad(\star\star)\quad\quad\quad \text{où}\quad b_{s,j} =\text{Card} \Big\{ J\in \mathcal P\big(\mathcal P_k ([\![1;j]\!] )\big)\mid \text{Card} J= s,\:\: U_J =[\![1;j]\!] \Big \}.$
L'évaluation de $b_{s,j}$ s'obtient en utilisant à nouveau la formule du crible:
$\:\:b_{s,j} \displaystyle =\text{Card} \left( \bigcap_{t=1}^j \Big\{ J\in \mathcal P\big(\mathcal P_k([\![1;j]\!])\big) \mid \text{Card} J=s,\:\: t\in U_J \Big\} \right) =\sum_{t=0} ^{j} (-1)^t \binom jt \binom { \binom {j-t}k}s= \sum _{t=0}^{j-k} (-1)^t \binom jt \binom{ \binom {j-t}k}s.\:\:$
Avec $(\star\star)$, on obtient : $\:\: a_j=\displaystyle \sum_{t=0}^{j-k} (-1)^t \binom jt \sum _{s\geqslant1} (-1)^{s+1} \binom {\binom {j-t}k} s = \displaystyle \sum_{t=0}^{j-k} (-1)^t \binom j t \times 1 = (-1)^{k+j} \binom {j-1}{k-1}, \:\:\:$ la dernière égalité pouvant être justifiée par une récurrence sur $j.\quad$ En reportant dans $\:(\star) ,\:$ on peut enfin conclure:
$$ \text{Card}(B_k)= \displaystyle \sum_ {j=1}^n (-1)^{j+k}\binom{j-1}{k-1}\binom nj C_j.$$
Une démonstration alternative de la formule de Guego par les $c_k^{(k)}$ que j'avais précédemment introduit (pas plus simple et ça passe par des formules franchement moches):
En partant des formules de récurrences que j'ai donné pour les $c_k^{(i)}$, on peut montrer que: $\forall k\in [\![1,n]\!]: c_k^{(k)} = \displaystyle \sum_{j=k}^{n} (-1)^{j-k}\binom{n-k}{j-k}c_j$, pour cela, j'en ai un peu sué, il faut passer par des formules un peu compliqués qui sont équivalentes à celle-ci $\forall (p,q)\in \mathbb{N}, p\leq q:\ \displaystyle \sum_{j=0}^p \binom{q}{j}\binom{q-j}{p-j}(-1)^j=0$, celle-ci se démontre assez bien parce que $\binom{q}{j}\binom{q-j}{p-j}= \binom{q}{p}\binom{p}{j}$ et via le binôme de Newton on arrive à $\binom{q}{p}(1-1)^p = 0$.
Du coup: $card(B_k)=\displaystyle \sum_{i=k}^n c_i^{(i)}\binom{n}{i}=\sum_{j=k}^n c_j \left(\sum_{i=k}^{j}(-1)^{j-i}\binom{n}{i}\binom{n-i}{j-i}\right)$
Par $\binom{n}{i}\binom{n-i}{j-i}= \binom{n}{j}\binom{j}{i}$, on a: $card(B_k =\displaystyle \sum_{j=k}^n c_j \binom{n}{j}\left(\sum_{i=k}^{j}(-1)^{j-i}\binom{j}{i}\right)= \sum_{j=k}^n c_j \binom{n}{j}\left(\sum_{i=0}^{j-k}(-1)^{i}\binom{j}{i}\right)$
On montre finalement par récurrence sur $j-k$ (via la formule de Pascale) que $\displaystyle \sum_{i=0}^{j-k}(-1)^i \binom{j}{i}=(-1)^{j-k}\binom{j-1}{k-1}$
La formule est plus jolie avec
$X_k = B_k \backslash B_{k+1}$ l'ensemble des éléments de $E$ qui appartiennent à exactement $k$ parties parmi $A_1,\ldots,A_n$.
En effet :
$$\def\card{\text{Card}}
\begin{align}
\card(X_k)
& =
\card(B_k)
-
\card(B_{k+1}) \\
& = \sum_ {j=1}^n (-1)^{j+k}\binom{j-1}{k-1}\binom nj C_j
-
\sum_ {j=1}^n (-1)^{j+k+1}\binom{j-1}{k}\binom nj C_j \\
& = \sum_ {j=1}^n (-1)^{j+k}\Bigg[\binom{j-1}{k-1}+\binom{j-1}{k}\Bigg]\binom nj C_j \\
& = \sum_ {j=1}^n (-1)^{j+k}\binom{j}{k}\binom nj C_j. \\
\end{align}
$$
Dans cette écriture, on remarque que
$$\binom nj C_j
= \sum_{\substack{I\subset1:n\\|I|=j}}
\left|
\bigcap_{i\in I}
A_i
\right|,
$$
ce qui nous pousse à nous demander si on peut écrire une formule plus générale sans supposer que $\displaystyle\left|
\bigcap_{i\in I}
A_i
\right|$ ne dépend que de $I\subset 1:n$ (c'est à dire sans l'existence des $C_j$)
Et en fait c'est le cas même sans cette hypothèse. Je vais écrire dans un autre post pourquoi.
Je pars de cette formule, que j'ai trouvée sur Wikipedia (anglais).
$\def\parties{\mathcal{P}}$
Si $f,g : \parties(E) \to \R$ vérifient pour $A \in \parties(E)$, $\quad\displaystyle
g(A)=\sum _{S\subseteq A}f(S),\ $ alors : $$
f(A)=\sum _{S\subseteq A}(-1)^{|A|-|S|}g(S).
$$ L'exemple générique, pour $B\subseteq E$, est $f(S) = 1_{S=B}$, alors on a $g(S) = 1_{S \supset B}$.
En remplaçant $f(S)$ par $f(\bar S)$ et $g(S)$ par $g(\bar S)$, il vient de même (mêmes formules, mais inclusions en sens inverse) : $$
g(A)=\sum _{S\supseteq A}f(S),$$ alors : $$ f(A)=\sum _{S\supseteq A}(-1)^{|A|-|S|}g(S).
$$ L'exemple générique, pour $B\subseteq E$, est $f(S) = 1_{S=B}$, devient $g(S) = 1_{S \subset B}$.
$
\def\card{\text{Card}}
\def\inter#1#2{\bigcap\limits_{i\in #1}#2_i}
\def\A#1{\inter{#1}{A}}
\def\Abar#1{\inter{#1}{\overline A}}
$
Une partition de $\A{I}$.
$\def\entiers#1#2{#1:#2}\def\parties{\mathcal{P}}$
Pour $I \in\parties(\entiers{1}{n})$, on a : $$
\A{I} =
\bigsqcup_{J\supset I}
\Bigg[
\A{J}
\cap
\Abar{\bar J}
\Bigg]
$$ Notons donc : $g(I) =
\card(\A{I})$, et $f(J)
= \card
\Bigg(
\A{J}
\cap
\Abar{\bar J}
\Bigg)$.
Ainsi : $\displaystyle g(I) = \sum_{J\supseteq I} f(J)$.
Par la formule ci-dessus : $$
\begin{align}
f(I) & = \sum _{J\supseteq I}(-1)^{|J|-|I|}g(J) \\
\text{soit : }\quad\card\Bigg(
\A{I}
\cap
\Abar{\bar I}
\Bigg)
& = \sum _{J\supseteq I}(-1)^{|J|-|I|}
\card\Bigg( \A{J}\Bigg) \\
\end{align}
$$ Pour obtenir la version "exacte" (sans "au moins $k$") de la formule de Guego, il reste à sommer sur toutes les parties $I\in\parties(\entiers{1}{n})$ de cardinal $k$.
Je détaillerai plus tard si ça intéresse quelqu'un, parce que là, je fatigue.
$ \text{Card}(X_k)= \displaystyle\sum_ {j=1}^n (-1)^{j+k}\binom{j}{k}\binom nj C_j=\binom{n}{k}\sum_ {j=k}^n (-1)^{j+k}\binom{n-k}{j-k}C_j=\binom{n}{k}\sum_ {i=0}^{n-k} (-1)^i\binom{n-k}{i}C_{k+i}$.
C'est exactement la formule du crible après avoir choisi les $\displaystyle\binom{n}{k}$ parties $A_j$.