Formule close

michal

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

GaBuZoMeu

Notons $F$ l'ensemble des parties de $X$ de cardinal $b$ et $G_i$ l'ensemble des parties de $X$ de cardinal $a$ disjointes de $X_i$.
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.

michal

Oui, mais ça va encore donner une somme

GaBuZoMeu

Oui, mais une plus jolie somme. indexée par $\{0,1,\ldots,c\}$. Qu'espères-tu de mieux ?

Enfin, si ça ne t'intéresse pas, tant pis.

michal

Ce n'est pas que ça ne m'intéresse pas, mais je cherche une expression sans somme... Enfin si c'est possible... (:D
La deuxième somme en question est $$\sum_{i=0}^c(-1)^i\binom{c}{i}\binom{b-Ni}{a}$$

noix de totos

Avec tes notations, lorsque $N=1$, cette somme est égale à
$${b-c \choose a-c}.$$

Référence. H. W. Gould, Combinatorial Identities, Morgantown, 1972, identité (3.49).

GaBuZoMeu

Oui, ça c'est trivial : compter le nombre le nombre des parties à $a$ éléments d'un sous-ensemble à $b$ éléments contenant une partie donnée à $c$ éléments.
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 ?

michal

C'est le plus probable en effet. Mais je voulais en avoir le coeur net

GaBuZoMeu

Tu voulais une somme qui puisse être calculée. Ça se calcule très bien

from scipy.special import comb

def nombre(a,b,c,N) :
    return sum((-1)**i*comb(c,i,exact=True)*\
               comb(b-N*i,a,exact=True) for i in range(c+1))

print([nombre(12,20,2,N) for N in range(11)])

[0, 43758, 90662, 113685, 122331, 125060, 125788, 125944, 125968, 125970, 125970]

noix de totos

GaBuZoMeu a écrit:

Tu connais une "formule close" pour le nombre de surjections, par exemple ?

Si cette question s'adressait à moi, réponse : non.