Nombre de doubles fonctions bijectives

marco

Bonjour,

Soit $E$ un ensemble fini à $n$ éléments. Soit $F$ une partie de $E \times E$, telle que, pour tout $x \in E$, $F \cap (\{x \} \times E)$ a deux éléments, et $F \cap (E \times \{x \})$ a deux éléments. On dit alors que $F$ est une double fonction bijective de $E$ dans $E$.

Quel est le nombre de doubles fonctions bijectives de $E$ dans $E$ ? (en fonction de $n$)

De même, soit un entier $k \leq n$, on dit que $F \subset E \times E$ est une $k$-fonction bijective de $E$ dans $E$ si, pour tout $x \in E$, $F \cap (\{x \} \times E)$ a $k$ éléments, et $F \cap (E \times \{x \})$ a $k$ éléments.

Quelle est le nombre de $k$-fonctions bijectives de $E$ dans $E$ ?

Merci.

samok

Cela fait une infinité de questions.

Notons $\text{m}_n^k$ avec $n$ et $k$ entiers naturels tels que $2\leqslant k \leqslant n$, les nombres cherchés par sieur marco : le nombre de matrices de taille $n\times n$ constituées de $0$ ou de $1$ tels que la somme des colonnes et la somme des lignes vaillent $k$.

$\text{m}_2^2=1$

$\text{m}_3^2=0$

J'ai bien reformulé, mes égalités sont justes ? Sans doute que non car je ne vois pas le lien avec la dénomination "$k$-fonction bijective".

marco

Oui, c'est bien reformulé. Mais je trouve $m^2_3=6$. Car $m^k_n=m^{n-k}_n$. Donc $m^2_3=m^1_3$.

$m^1_3$ est le nombre de bijections (au sens habituel) d'un ensemble à $3$ éléments dans lui-même. Donc, $m^1_3=3!=6$.

samok

Pourrais-je voir un des 6 tableaux, que je comprenne où je me suis trompé (une énumération assez proche de la force brute).

marco

$\begin{pmatrix} 1 & 1 &0 \\ 0&1&1 \\ 1 &0&1 \end{pmatrix}$

jandri

J'avais aussi trouvé 6 pour $n=3$ et $k=2$ mais l'interprétation de @samok facilite beaucoup le travail.

Avec les premières valeurs on trouve qu'il s'agit de la suite A8300 de l'OEIS.

Il semble qu'il n'y a pas de formule générale.

samok

Merci.

marco

Merci @samok et @jandri .