Un problème de combinatoire...

Bonjour, Je dois résoudre un problème de combinatoire qui est le suivant : Soit $p$, un nombre premier impair. Pour toute permutation $\sigma : [\![1,p]\!]\to[\![1,p]\!]$, on définit : $ f(\sigma) = \left|\left\{n\in[\![1,p]\!]\;\text{tel que}\; p\mid \sigma(1)+\ldots+\sigma(n) \right\}\right| $ Trouver $\frac{1}{p!}\cdot\sum_{\sigma\in\mathfrak{S}_p}f(\sigma)$ (où $\mathfrak{S}_p$ est l’ensemble des permutations de $[\![1,p]\!]$).

Néanmoins je ne vois pas du tout comment faire ? Des pistes ? Merci d’avance !

Pas simple du tout en première lecture.

Une première étape, ça peut être de faire ce calcul pour p=3 ou p=5, à la main, en recensant toutes les permutations. Peut-être qu’on va trouver une piste ? Mais vraiment aucune certitude.

Considérant l’heure à laquelle j’écris, je risque de pas être très clair, mais voilà mes premières pensées sur comment on pourrait assez naïvement aborder le problème. Déjà on peut essayer de se ramener à quelque chose de plus simple. La somme que tu veux exprimer c’est la « moyenne de $f(\sigma)$ », ce qu’on peut écrire en termes probabilistes : on prend $\sigma$ suivant une loi uniforme sur $S_p$ et on cherche $E(f(\sigma))$. Or :

Donc :

Essentiellement, on tire maintenant uniformément $k$ éléments distincts dans $\{1, \ldots p\}$ (disons $n_1, \ldots, n_k$), et on se demande pour combien d’entrées $p$ divise $n_1 + \ldots + n_k$. À partir de là, il y a probablement plusieurs manières de faire, tu peux par exemple commencer essayer de voir ça pour des petites valeurs de $k$, et comment on pourrait utiliser l’hypothèse sur $p$.

Note que j’ai tout exprimé en termes probabilistes, mais comme on travaille sur des distributions uniformes, tout peut sans nul doute s’exprimer en termes uniquement combinatoires.

On veut donc la probabilité qu’un arrangement de $k$ éléments de $\mathbb{Z}/(p)$ ait une somme nulle. Si $k=p$, alors c’est toujours vrai (car $p$ est impair).

Sinon, on réécrit ça comme $\mathbb{P}(\sigma(1) + \cdots + \sigma(k) = 0 \land \text{les }\sigma(i)\text{ sont tous distincts})$. Puis on utilise une notion probabilistique fondamentale (qui n’a pas trop d’équivalent combinatoire).

Je me suis mal exprimé. Je voulais dire que l’on se place dans le contexte probabiliste plus général où $\sigma$ est une fonction quelconque et plus uniquement une permutation. La probabilité qu’on cherche est $\mathbb{P}(\sigma(1) + \cdots + \sigma(k) = 0 \,|\, \text{les }\sigma(i)\text{ sont tous distincts})$. Il faut ensuite utiliser une notion probabiliste importante qui n’a pas trop d’équivalent combinatoire (?).

Bon, et puis en fait avec un peu d’astuce on peut faire plus élémentaire (généraliser à $\sigma(1)+\cdots+\sigma(k)=x$ pour tout $x$).

Sinon, d’où vient ce problème ? Il n’est pas très intéressant en lui-même, mais sa résolution l’est. Ça m’intéresserait de savoir comment il a été inventé (ou aurait pu être inventé), malheureusement je doute de le savoir un jour.

Considérant l’heure à laquelle j’écris, je risque de pas être très clair

Moi aussi. L’heure de se coucher est passée.

Ca m’intrigue, et donc je viens de faire très vite un petit programme pour calculer les premières valeurs

f(n) = le nombre de combinaisons qui conviennent. Reste donc à diviser par n!.

f(3) = 10  ; f(5) = 216  ; f(7) = 9360.

A suivre.

C’est quoi la contrainte sur $n$ ? Il est quelconque ?

Bonjour,

Le problème a attiré mon attention. Après y avoir réfléchit voilà ce que je propose : On groupe les permutations $p$ par $p$ : deux permutations $\sigma$ et $\tau$ sont mises ensemble si et seulement si il existe $k\in\mathbb{Z}/p\mathbb{Z}$ tel que $\sigma(i)\equiv k+\tau(i) \pmod p \quad\forall\,i\in[\![1,p]\!]$. Nos sous-ensembles ont donc la forme de $ [\sigma_0] = \left\{ \sigma_0,\, \sigma_0+1,\,\ldots,\,\sigma_0+p-1\right\} $ Où l’on a choisit "le $\sigma_0$ de chaque groupe" arbitrairement (par exemple, la permutation qui fixe $1$).

Soit $n\in[\![1,p-1]\!]$, l’ensemble des sommes $\sum_{i=1}^{n}\sigma(i)$ dans le sous-ensemble est donné par $\left\{\sum_{i=1}^{n}\sigma_0(i),\,n+\sum_{i=1}^{n}\sigma_0(i),\,\ldots,\, (p-1)\cdot n + \sum_{i=1}^{n}\sigma_0(i)\right\} $ Or, comme $n$ est inversible, c’est un ensemble complet de résidus modulo $p$. Ainsi, il existe exactement une permutation dans cet ensemble telle que $p\mid \sum_{i=1}^{n}\sigma(i)$.

Pour $n=p$, on a $\sum_{i=1}^{n}\sigma(i)=\frac12\cdot p\cdot(p-1)$ et donc, puisque $p\neq 2$, $p\mid \sum_{i=1}^{n}\sigma(i)$.

Ainsi dans chaque sous-ensemble, on a $\sum_{\sigma\in[\sigma_0]}f(\sigma) = (p-1)\cdot 1 + 1\cdot p$. La valeur moyenne est donc de $ \frac{1}{p!}\cdot\sum_{\sigma\in\mathfrak{S}_p}f(\sigma) = \frac{p-1}{p}+1$

Quel $n$ ? Le seul que je vois est quantifié sur les entiers entre $1$ et $p$.

@Thinking : Oui, c’est ce à quoi je voulais mener maxd en disant « généraliser à $\sigma(1) + \cdots + \sigma(k) = x$ ». Je crois qu’il voulait juste des indices et pas un solution complète (?).

On peut aussi voir ça comme suit. Soit $n$ entre $1$ et $p$. On a une action de $\mathbb{Z}/(p)$ sur l’ensemble des permutations, il s’agit d’ajouter une constante à chaque terme comme tu as fait (on peut aussi voir ça comme post-composition par une certaine permutation). On a aussi l’action de $\mathbb{Z}/(p)$ sur lui-même définie par $k \mapsto (\cdot+nk)$. On définit $\sum_n : S_p \to \mathbb{Z}/(p)$ par $\sum_n(\sigma) := \sum_{i=1}^n \sigma(i)$. Alors $\sum_n$ est une transformation naturelle entre les deux actions (vues comme foncteurs de $\mathbb{Z}/(p)$ vers les ensembles). Si on note $F$ le foncteur correspondant à l’action de $\mathbb{Z}/(p)$ sur lui-même, ça donne un morphisme de $(* \downarrow F)$ vers les ensembles, avec $x \in \mathbb{Z}/(p)$ envoyé sur sa fibre par $\sum_n$. Comme $(* \downarrow F)$ est un groupoïde et que l’action de $\mathbb{Z}/(p)$ sur lui-même est transitive (ça vient du fait que $k \mapsto nk$ est inversible car $n$ est premier avec $p$), ça donne que toutes les fibres sont en bijection.

Il y a un autre raisonnement, c’est de voir que la variable aléatoire $\sum_n(\sigma)$ est indépendante de la famille de booléens aléatoires $(\sigma(i) = \sigma(j))_{i,j}$ (on se place dans le contexte où $\sigma \in (\mathbb{Z}/(p))^n$ uniformément). Il faut pour cela montrer que $\sum_n$ est indépendante de tout système d’équations de la forme $\sigma(i) = \sigma(j)$. Un tel système d’équations définit une relation d’équivalence sur $[\![1,n]\!]$. Sous hypothèse d’un tel système, $\sum_n(\sigma)$ s’écrit de la forme $\alpha_1 \sigma(1) + \alpha_2 \sigma(1+\alpha_1) + \alpha_3 \sigma(1+\alpha_1+\alpha_2) + \cdots$. On pourrait dire qu’il existe $\alpha_i$ inversible car $p$ est premier, mais on peut ne se servir que du fait que $n = \alpha_1 + \alpha_2 + \cdots$ est inversible modulo $p$, et donc $\alpha_1 x_1 + \alpha_2 x_2 + \cdots$ est surjectif. De là, on déduit qu’on a une probabilité de $1/p$ d’être dans son noyau et il y a donc indépendance.

Ce deuxième raisonnement utilise des résultats sur l’indépendance de variables aléatoires, et on peut se demander s’il est faisable de déplier tous ces résultats pour obtenir une preuve plus élémentaire (peut-être qu’on retomberait sur quelque chose de similaire à la preuve de Thinking ?).

Moi aussi j’avais fait un programme, pour bien vérifier ne pas m’être trompé (cette suite est bien $(2-1/p)p!$). Cette suite n’est pas dans l’oeis (ni en généralisant à $p$ non premier) !