Combinatoire et relation d'équivalence

mathematico

On dispose d'un ensemble fini $X$ et on note par $F$ l'ensemble des fonctions $f: X \to \mathbb{N}$.
Soit $\pi_1, \pi_2 \in F$. On définit la relation $\mathcal{R}$ comme suit $$\pi_1 \mathcal{R} \pi_2\iff\big(\forall i,j \in X, \ \pi_1(i) \leq \pi_1(j) \Leftrightarrow \pi_2(i) \leq \pi_2(j)\big).
$$ En d'autres termes, les deux fonctions sont en relation si elles "ordonnent" de la même manière les éléments de $X$.
Il s'agit évidemment d'une relation d'équivalence.
Comment calculer la cardinalité de l'ensemble quotient $F/ \mathcal{R}$

LOU16

Bonjour,
C'est la question du nombre de "classements avec ex aequo possibles " évoquée, me semble-t-il , dans un récent fil.

$\forall n \in \N^*, \quad u_n:= \# (\N^n/\mathcal R).\:\:\quad $ Alors on peut accéder à $u_n$ par:
$u_n = \displaystyle \sum _{k=1}^n S(n,k)\:$ où $S(n,k)$ est le nombre de surjections de $[\![1;n]\!]$ dans $[\![1;k]\!]$ et est défini par:$\quad S(n,k)=\displaystyle \sum_ {i=1}^k (-1)^{k-i} \binom k i i^n.$
$$\begin{array}{|c|c|c|c|c|c|c|} \hline n &1&2&3&4&5&6 \\\hline u_n&1&3&13&75&541&4683 \\\hline \end{array} $$

On peut aussi caractériser $u_n$ par la récurrence: $\quad u_0=1,\quad \forall n \in N^*,\:\: u_n =\displaystyle \sum_{k=0} ^{n-1} \binom nk u_k,\:$
ou bien avec la relation:$\quad \forall n \in \N, \:\:u_n=\displaystyle \sum _{k=0}^{+\infty}\dfrac {k^n}{2^{k+1}}.\qquad$Cette dernière égalité fournit l'équivalent: $\quad u_n \underset {n\to +\infty}{\sim}\dfrac {n!}{2(\log2)^{n+1}}.$
Une autre définition de $u_n$ est l'égalité de séries formelles: $\quad \displaystyle \sum_{n=0}^{+\infty}\dfrac {u_n}{n!}X^n=\dfrac 1{2-\exp X}$

mathematico

Bonjour,
Merci pour votre réponse.
Ça fait un bon moment que je n'ai pas fait de maths.
Pourriez-vous m'indiquer pourquoi vous avez considérer les surjections de $[\![1;n]\!]$ vers $[\![1;k]\!]$ ?

LOU16

Re
Définir un élément de $F/\mathcal R$, c'est opérer un "classement avec ex aequo possibles" des éléments de $X,\:\:(\text{Card}X=n)$, c'est à dire partitionner les éléments de $X$ en $k \:\ (1\leqslant k \leqslant n)$ groupes d' ex aequo, puis classer ces groupes en les numérotant de $1$ à $k$.
Pour $k\in [\![1;n]\!]$ fixé, cela revient à assigner à chaque élément $x$ de $X$, l' élément $i \in [\![1;k]\!]$ correspondant au numéro du groupe auquel $x$ va appartenir. Cette opération définit ainsi une surjection de $[\![1;n]\!]$ dans $ [\![1,k]\!]$ et réciproquement, toute surjection de ce type caractérise un "classement avec $k$ groupes d'ex aequo".
$$ \text{Card}( F/\mathcal R)= \displaystyle \sum _{k=1}^n S(n,k).$$

mathematico

Si j'ai bien compris $k$ est inférieur à $n$ car il peut y avoir des éléments de $X$ ayant la même valeur pour $f$ (e.g $f(x_1) = f(x_2)$). Est-ce que c'est ça ?

jandri

$k$ est inférieur ou égal à $n$ car $n$ personnes ne peuvent pas occuper plus de $n$ places.

Le nombre de "classements avec ex aequo possibles" a été évoqué dans le fil récent Équivalents