Formule close — Les-mathematiques.net The most powerful custom community solution in the world

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

Réponses

  • 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.
  • Oui, mais ça va encore donner une somme
  • 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.
  • 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}$$
  • 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).
  • 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 ?
  • C'est le plus probable en effet. Mais je voulais en avoir le coeur net
  • 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]
    
  • GaBuZoMeu a écrit:
    Tu connais une "formule close" pour le nombre de surjections, par exemple ?

    Si cette question s'adressait à moi, réponse : non.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!