Grille à colorier

chris93

Bonsoir à tous,
je considère une grille à $n$ colonnes et $p$ lignes (donc $pn$ cases.). On a la possibilité de laisser chaque case blanche ou de la colorier en noir.
Quel est le nombre de grilles possibles telles qu'il y ait au plus une case par ligne et par colonne coloriée en noir ?

Un raisonnement erroné m'avait poussé à écrire $(p+1)p\cdots(p-n+2)$. Mais ça ne fonctionnait pas pour des petites valeurs de $n$ et de $p$.
Ensuite, j'ai fait un arbre en distinguant "on colorie aucune case" ou "on colorie une case" mais je ne trouve pas.

Merci de votre aide.

marsup

Si j'ai envie d'en colorier $r$, je choisis $r$ lignes, et $r$ colonnes, puis je choisis une des $r!$ manières de colorier une case dans chaque.

Ça donne $\quad\displaystyle\sum_{r=0}^{\min({n,p})} \binom{n}{r} \cdot \binom{p}{r} \cdot r!\qquad$ (oups, min au lieu de max !)

Par contre, je ne sais pas combien ça donne !

jandri

C'est la bonne formule et on ne peut pas la simplifier (c'est la suite A88699 de l'OEIS).

chris93

Merci à vous deux.