Divisibilité du cardinal des permutations d'un tuple — Les-mathematiques.net The most powerful custom community solution in the world

Divisibilité du cardinal des permutations d'un tuple

Modifié (November 2023) dans Combinatoire et Graphes
Soient $p$ un nombre premier, et $(a_1,...,a_p)$ un $p$-uple d'ensembles tels que $\cancel{a_1=a_2}$ edit: $a_1 \neq a_2$.

Est-il vrai que $p$ divise le cardinal de l'ensemble $X = \{(a_{\sigma(1)},\dots,a_{\sigma(p)})  \mid \sigma \in \mathfrak{S}_p\}$ ?

Une idée naturelle est de regarder l'indice du stabilisateur de $(a_1,a_2,\dots,a_p)$ sous l'action transitive évidente de $\mathfrak{S}_p$ sur $X$. Il faudrait montrer que le cardinal du stabilisateur divise $(p-1)!$, ou simplement n'est pas divisible par $p$. Mais je n'y arrive pas.

Réponses

  • Modifié (November 2023)
    Je précise que si $p=4$ (premier en fermant un œil), $a_1=a_2=a_3$ et $a_4 \neq a_1$, alors le cardinal de $X$ est $6=3!$, qui n'est pas très divisible par $4$ même en fermant un œil.
  • Modifié (November 2023)
    Bonjour,
    Ta question est bizarre. Si $a_1=a_2=\ldots=a_p$, alors le cardinal de $X$ est 1.
    Et pour l'exemple que tu donnes dans ton deuxième message, le cardinal de $X$ est en fait 4.
    Je pense que tu as quelque chose d'autre derrière la tête et que ta question est une reformulation pas très heureuse de ton problème. Peut-être vaudrait-il mieux nous dire ton vrai problème ?
  • Ah pardon @GaBuZoMeu, légère erreur d'énoncé, je voulais écrire $a_1 \neq a_2$.

    En fait j'ai fini par trouver une solution: si $a_1$ n'apparaît qu'une fois dans la liste, alors le stabilisateur est isomorphe aux "permutations de $(a_2,...,a_p)$" car alors ses éléments doivent fixer $1$.

    Si $a_1$ apparaît au moins une seconde fois, alors le stabilisateur est en bijection avec un produit cartésien de $n$ copies de l'ensemble des "permutations de $(a_2,...,a_p)$", où $n+1$ est le nombre de copies de $a_1$ dans la liste. Et comme $a_2 \neq a_1$, cet $n$ est strictement inférieur à $p$.

    Dans tous les cas, le cardinal de $X$ est un produit $n \times d$ où $d$ divise $(p-1)!$ et $n$ n'est pas divisible par $p$. Donc l'indice du stabilisateur est divisible par $p$.
  • Ah oui tu as raison, c'est $4$. Bon désolé pour les grands cafouillages.
    Si $p=4$, $a_1=a_3$, $a_2=a_4$ et $a_1 \neq a_2$, alors le cardinal est $6$ mais peut-être pas parce que $6=3!$...
  • Modifié (November 2023)
    Pas très clair, ce que tu écris avec tes stabilisateurs.
    Si le $p$-uple $(a_1,\ldots,a_p)$ comprend $k_i$ fois l'élément $b_i$ pour $i=1,\ldots,r$ où les $b_i$ sont deux à deux différents $(\sum_{i=1}^rk_i=p$), alors l'orbite de $(a_1,\ldots,a_p)$ sous l'action du groupe des permutations $\mathfrak S_p$ a $\dfrac{p!}{\prod_{i=1}^r k_i!}$ éléments. Si aucun $k_i$ n'est égal à $p$, alors cet entier est divisible par $p$.
  • Modifié (November 2023)
    Si les $a_i$ sont tous différents, le cardinal de $X$ est $p!$, qui est un multiple de $p$.
    Si certains $a_i$ sont égaux , on doit diviser ce $p!$ par des nombres de type $k!$  
    Par exemple si on a quelque chose comme (a,a,a, b,b,b,b, c, d, e ... ) on va diviser $p!$ par  $3! \times 4!$

    Quand $p$ est premier, on est tranquille, on peut diviser par $3!$ ou $4!$ ou ce qu'on veut, le résultat restera divisible par $p$.
    Quand $p$ n'est pas premier, on n'est pas à l'abri.

    Par exemple, si $p = 22$, non premier, si on a (a,a,a, a,a,a, a,a,a, a,a, b,b,b, b,b,b, b,b,b, b,b) le cardinal de X sera $\frac{22!}{11! \times 11!}$ et ce nombre n'est pas multiple de $11$, donc pas multiple de $p$.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Modifié (November 2023)
    Ah, donc il y a une formule générale pour le cardinal. Merci à vous deux! Bon en fait ça se déduit de mon raisonnement pas très clair (et où $n+1$ devrait être $n$), par induction.

    J'imagine que c'est une formule connue, voire nommée?
  • Coefficient multinomial.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!