Formule close
Bonjour
On se donne un ensemble $X$ de cardinal $b$ et $c$ parties $X_1,\dots,\, X_c$ de cardinal $N$ deux à deux disjointes.
On cherche le nombre de parties $A$ de $X$ de cardinal $a$ telles que pour tout $j$, $X_j\cap A\neq \emptyset$.
En appelant $p_j$ le cardinal de $X_j\cap A$ et $q$ celui de $A\setminus (X_1 \cup \dots \cup X_c)$ je trouve que le nombre cherché est $$
\sum \binom{N}{p_1}\dots \binom{N}{p_c}\binom{b-Nc}{q},
$$ où la somme porte sur tous les entiers naturels non nuls $p_1,\dots,\, p_c$ et $q$ vérifiant $p_1+\dots+p_c+q=a$ ($q$ peut être nul).
Je me demande si cette somme peut être calculée. Si les $p_j$ pouvaient être nuls, on tombe sur la formule de Vandermonde donc on obtient $\binom{b}{a}$.
Merci d'avance,
Michal
On se donne un ensemble $X$ de cardinal $b$ et $c$ parties $X_1,\dots,\, X_c$ de cardinal $N$ deux à deux disjointes.
On cherche le nombre de parties $A$ de $X$ de cardinal $a$ telles que pour tout $j$, $X_j\cap A\neq \emptyset$.
En appelant $p_j$ le cardinal de $X_j\cap A$ et $q$ celui de $A\setminus (X_1 \cup \dots \cup X_c)$ je trouve que le nombre cherché est $$
\sum \binom{N}{p_1}\dots \binom{N}{p_c}\binom{b-Nc}{q},
$$ où la somme porte sur tous les entiers naturels non nuls $p_1,\dots,\, p_c$ et $q$ vérifiant $p_1+\dots+p_c+q=a$ ($q$ peut être nul).
Je me demande si cette somme peut être calculée. Si les $p_j$ pouvaient être nuls, on tombe sur la formule de Vandermonde donc on obtient $\binom{b}{a}$.
Merci d'avance,
Michal
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
On veut compter le nombre d'éléments de $F\setminus \bigcup_{i=1}^c G_i$. Ça peut se faire par le principe d'inclusion-exclusion.
Enfin, si ça ne t'intéresse pas, tant pis.
La deuxième somme en question est $$\sum_{i=0}^c(-1)^i\binom{c}{i}\binom{b-Ni}{a}$$
$${b-c \choose a-c}.$$
Référence. H. W. Gould, Combinatorial Identities, Morgantown, 1972, identité (3.49).
Mais je suis prêt à parier qu'il n'y a aucune "formule close" pour le cas général. Tu connais une "formule close" pour le nombre de surjections, par exemple ?
Si cette question s'adressait à moi, réponse : non.