Théorème inconnu d'analyse combinatoire — Les-mathematiques.net The most powerful custom community solution in the world

Théorème inconnu d'analyse combinatoire

Modifié (July 2023) dans Combinatoire et Graphes
Bonjour
Il y a un peu plus de 17 ans, j'avais découvert ou redécouvert un théorème très général d'analyse combinatoire des permutations dont je ne sais pas s'il est déjà connu, puis je suis passé à autre chose et je n'en ai parlé à personne.
C'est en rencontrant un enseignant chercheur qui a fait une thèse sur le problème des 4 couleurs, le jour où j'ai aidé une amie à déménager, que j'ai repensé à tout ça.
 Le théorème en question est le tout premier de ce document.
En relisant le document que j'avais écrit à l'époque, et dans lequel je démontre ce théorème, parmi d'autres, je me suis aperçu que mes raisonnements sont un peu rapides et qu'il est difficile de me suivre (par exemple, la manière dont je passe du théorème démontré en bas de la page 5 à celui en bas de la page 7 est assez acrobatique), donc j'ai pris le temps d'y apporter quelques précisions afin qu'on puisse me comprendre.
C'est un théorème très court, facile à mémoriser, et qui permet, en variant les ensembles K et L, d'obtenir facilement beaucoup d'autres théorèmes, dont celui-ci.
Pour tout entier naturel n, le nombre de permutations d'un ensemble de n éléments dont la décomposition en produits de cycles à supports disjoints n'a que des cycles d'ordre pair est égal au carré du nombre de permutations d'un ensemble de n éléments dont la décomposition en produits de cycles à supports disjoints n'a que des cycles d'ordre 2.
Savez-vous si le tout premier théorème de ce document est déjà connu ?
Merci d'avance.

Ajout du 24 juillet 2023 à 02h48 :

Voici le théorème en question écrit en LaTeX :

Soient n un entier naturel, $K$ un sous-ensemble de $\N$, et $L$ un sous-ensemble de $\N^*$. Si on note $F_n(K,L)$ l'ensemble des permutations de l'ensemble des n plus petits entiers naturels non nuls dont le nombre de cycles dans la décomposition en produit de cycles à supports disjoints appartient à $K$, et pour lesquelles tous les cycles de cette décomposition sont de longueur appartenant à $L$, alors pour tout sous-ensemble $K$ de $\N$, pour tout sous-ensemble $L$ de $\N^*$, et pour tout nombre z de module strictement inférieur à 1 : $$\sum_{n=0}^{\infty} \frac{|F_n(K,L)|}{n!}z^n=\sum_{k \in K}\frac{1}{k!}(\sum_{l \in L}\frac{z^l}{l})^k$$Pour certains ensembles $K$ et $L$, la fonction génératrice peut s'exprimer simplement à l'aide de fonctions bien connues, comme l'exponentielle et le logarithme. Parfois, ces deux fonctions transcendantes se neutralisent entre elles pour donner une fonction algébrique.

Réponses

  • J'ai commencé à lire mais je ne vois pas comment, grâce à ce théorème, tu obtiens celui sur les permutations dont la décomposition en cycles à supports disjoints n'a que des cycles d'ordre pair.
  • Je ne suis pas assez calé dans ce domaine pour te répondre. Néanmoins, si tu espères être lu du plus grand nombre, il serait bon d'envisager réécrire tout cela en Latex...
  • JeremyLebre a dit :
    Pour tout entier naturel n, le nombre de permutations d'un ensemble de n éléments dont la décomposition en produits de cycles à supports disjoints n'a que des cycles d'ordre pair est égal au carré du nombre de permutations d'un ensemble de n éléments dont la décomposition en produits de cycles à supports disjoints n'a que des cycles d'ordre 2.
    C'est faux pour $n=4$, il y a $15$ permutations du 1er type, et $9$ du 2ème type.
    On parle de cycles de longueur paire, et d'éléments d'ordre pair.
  • Modifié (July 2023)
    Je ne suis pas sûr de ce que tu entends par "1er type" et "2ème type", mais parmi les 24 permutations d'un ensemble de 4 éléments, il n'y en a que 3 dont la décomposition en produits de cycles à supports disjoints n'a que des cycles de longueur 2, et 9 dont la décomposition en produits de cycles à supports disjoints n'a que des cycles de longueur paire.

    Plus généralement, si n est un entier naturel pair, alors de tête, on voit facilement que le nombre de permutations d'un ensemble de n éléments dont la décomposition en produit de cycles à supports disjoints n'a que des cycles de longueur 2 est égal au produit de tous les entiers naturels impairs inférieurs à n, et on le démontre facilement par récurrence. Le cas où n est égal à 0 ne fait pas exception à cette règle pour les 2 raisons suivantes :

    1. Rien n'exclut que l'ensemble de définition d'une fonction soit vide. Et on démontre très facilement qu'il n'existe qu'une seule fonction dont l'ensemble de définition est vide. Son ensemble image est vide, donc c'est une permutation de l'ensemble vide. Sa décomposition en produit de cycles à supports disjoints ne contient aucun cycle, donc tous les cycles de cette décomposition sont d'ordre appartement à L pour n'importe quel ensemble L. En particulier, ils sont tous d'ordre pair, et ils sont également tous d'ordre impair !

    2. Le produit d'un nombre nul de facteurs n'est pas égal à 0, mais à l'élément neutre de la multiplication (donc 1), de même que la somme d'un nombre nul de termes est égale à l'élément neutre de l'addition (donc 0).

    On parle de cycles de longueur paire, et d'éléments d'ordre pair.

    On parle de l'ordre d'un élément, mais aussi de l'ordre d'une permutation (qui est égal au PPCM des longueurs des cycles de sa décomposition en produit de cycles à supports disjoints). Et un cycle est une permutation dont l'ordre est égal à la longueur. C'est pourquoi quand il s'agit de cycles, les termes "ordre" et "longueur" sont utilisés indifféremment, pour désigner la même chose.

    @bisam En effet, difficile d'être pris au sérieux sur un forum de maths quand on n'y connaît rien à LaTeX. Je vais apprendre. Donc voici le théorème en question écrit en LaTeX :

    Soient n un entier naturel, $K$ un sous-ensemble de $\N$, et $L$ un sous-ensemble de $\N^*$. Si on note $F_n(K,L)$ l'ensemble des permutations de l'ensemble des n plus petits entiers naturels non nuls dont le nombre de cycles dans la décomposition en produit de cycles à supports disjoints appartient à $K$, et pour lesquelles tous les cycles de cette décomposition sont de longueur appartenant à $L$, alors pour tout sous-ensemble $K$ de $\N$, pour tout sous-ensemble $L$ de $\N^*$, et pour tout nombre z de module strictement inférieur à 1 : $$\sum_{n=0}^{\infty} \frac{|F_n(K,L)|}{n!}z^n=\sum_{k \in K}\frac{1}{k!}(\sum_{l \in L}\frac{z^l}{l})^k$$
    Pour certains ensembles $K$ et $L$, la fonction génératrice peut s'exprimer simplement à l'aide de fonctions bien connues, comme l'exponentielle et le logarithme. Parfois, ces deux fonctions transcendantes se neutralisent entre elles pour donner une fonction algébrique.

    @Antooane Je vais prendre le temps de te répondre ce soir, sauf si entre temps, un membre du forum peut le faire à ma place grâce à ce que je viens de dire.
  • Un mot clé, vu cette dernière formule : formule exponentielle, cf. https://fr.m.wikipedia.org/wiki/Formule_exponentielle.
  • Modifié (July 2023)
    1er type : permutations d'un ensemble de 4 éléments dont la décomposition en produits de cycles à supports disjoints n'a que des cycles d'ordre pair, il y a les $6$ transpositions (d'ordre 2), les $3$ bi-transpositions (d'ordre 2), et les $6$ 4-cycles (d'ordre 4), total $15$,
    2ème type : permutations d'un ensemble de 4 éléments dont la décomposition en produits de cycles à supports disjoints n'a que des cycles d'ordre 2, il y a les $6$ transpositions et les $3$ bi-transpositions, total $9$.
  • On peut arguer que les transpositions ont deux cycles de longueur un.
  • @Julia Paule Je comprends mieux ton erreur. Comme le dit Math Coss, les 6 transpositions dont tu parles se décomposent en 1 cycle de longueur 2 et 2 cycles de longueur 1. Il faut donc soustraire 6 aux 2 nombres que tu obtiens (1er type : 9, 2ème type : 3).
  • Modifié (July 2023)
    ??? Pour moi, les transpositions sont les cycles de longueur 2, les cycles de longueur 1 sont les points fixes, donc l'identité, et la décomposition d'une permutation en un produit de cycles à supports disjoints est unique à l'ordre des facteurs près.
    Peux-tu expliquer comment tu décomposes la transposition $(3,4)$ en 2 cycles de longueur 1 ?
  • C'est une question de langage, maintenant que l'ambiguïté est éclaircie, on ferait mieux de passer à la suite : est-ce qu'on comprend cette relation ? Est-ce qu'elle est vraie ? nouvelle ? surprenante ?
  • Modifié (July 2023)
    Il faut donc comprendre que dans cette relation, les transpositions ne sont pas comptées ? Parce que cela marche (pour n=4) si on ne les compte pas. Mais pour moi, ce sont à la fois des cycles de longueur 2 donc paire, et en aucun cas, ne peuvent être décomposées en 2 cycles de longueur 1, ce n'est pas une question de langage, ou tu as peut-être @Math Coss une autre définition que la mienne pour les cycles de longueur 1 ?
    Du coup, je n'ai pas regardé la suite.
  • Modifié (July 2023)
    Bonjour,
    La relation incriminée par Julia Paule me paraît exacte.
    Pour tout $n\in \N^*,\:\:$soit $T_n $ l'ensemble des éléments de $\mathfrak S([2n])$ dont les orbites sont toutes de cardinal $2$. $\:\:t_n =|T_n|=\dfrac {(2n)!}{2^n n!}=\displaystyle \prod_{k=1}^n(2k-1).\:\:$(nombre de partitions de $[\![1;2n]\!]$ en paires)
    $U_n $  désigne l'ensemble des éléments de $\mathfrak S([2n])$ dont les orbites sont toutes de cardinal pair.  $\:\: u_0=1,\: u_n :=|U_n|, \: v_n: =\dfrac{u_n}{(2n)!}.$
    En distinguant  les permutations de $U_{n+1}$  telles que $2n+1$ et $2n+2$ appartiennent à la même orbite de celles où ce n'est pas le cas, on obtient la relation de récurrence:
    $$u_{n+1} =\displaystyle \sum_{k=0}^n\binom{2n}{2k}(2k+1)!\:u_{n-k}+\sum_{k=0}^{n-1}\binom{2n}{2k+1}(2k+1)!\:u_{n-k}=\sum_{k=0}^n \binom{2n+1}{2k+1}(2k+1)!\:u_{n-k}$$
    $$\forall n \in \N,\quad 2(n+1)v_{n+1}=\displaystyle\sum_{k=0}^n\dfrac{u_{n-k}}{(2n-2k)!} = \sum_{k=0}^n v_k$$ 
    Avec l'introduction de la série formelle $S(X) =\displaystyle \sum_{n=0}^{+\infty}v_nX^n,\:$ l'égalité précédente s'écrit:  $ \:\:2S'(X) =\dfrac{S(X)}{1-X}.$
    Avec $S(0)=1,\: $ il vient :$\:\:S(X)=\dfrac 1{\sqrt{1-X}}=\displaystyle \sum_{n=0}^{+\infty}\binom{-1/2}n(-X)^n,\quad v_n =(-1)^n\binom{-1/2}n.$
    On obtient enfin: $\displaystyle u_n=(2n)!v_n=(-1)^n(2n)! \:\binom{-1/2}n=\left(\dfrac{(2n)!}{2^n n!}\right)^2.\qquad \boxed{u_n =t_n^2.}$

  • @Julia Paule : remplace simplement "cycle" par "orbite" dans les messages précédents. 
  • Modifié (July 2023)
    @Julia Paule En te relisant, tu verras qu'il y a des incohérences dans la façon dont tu conçois les choses, ce qui ne t'aide pas à comprendre. En effet, dans tes premiers messages, tu considères d'abord les transpositions comme des permutations qui échangent deux éléments et laissent tous les autres inchangés (ce qui est correct), mais tu exclus les points fixes de la décomposition en cycles disjoints, ce qui te conduit à compter 6 permutations en trop.
    Puis, dans les messages suivants, tu admets que les points fixes sont dans des cycles de longueur 1, mais par contre tu considères cette fois-ci les transpositions comme des cycles de longueur 2 d'un ensemble de 2 éléments. Partant de cette confusion, tu demandes comment un cycle de longueur 2 d'un ensemble de 2 éléments se décompose en 2 cycles de longueur 1, mais personne n'a dit ça. Ce qui a été dit, c'est qu'une transposition d'un ensemble de 4 éléments se décompose en 1 cycle de longueur 2, et 2 cycles de longueur 1 (les 2 points fixes de la transposition).
    @LOU16 Oui, c'est une façon de le démontrer. Tu dois être doué pour trouver ça aussi facilement.
    @Antooane Pour tout nombre z non nul, on peut définir le logarithme de z comme l'unique nombre $x$ dont la partie imaginaire est dans l'intervalle $\left]-\pi;\pi\right]$, et tel que $e^x = z$. Pour tout nombre $a$, on note alors $z^a$ le nombre $e^{a \times ln(z)}$. Dans ces conditions, pour tout nombre z de module strictement inférieur à 1 : $$-\ln(1 - z)=\sum_{n \in \N^*}\frac{z^n}{n}$$ $$(1 - z)^{-a}=\sum_{n=0}^{\infty}(\prod_{k=0}^{<n}a+k)\frac{z^n}{n!}$$
    Ce deuxième développement en série s'obtient facilement grâce aux dérivées d'ordre n en 0 de la fonction qui à un nombre z de module strictement inférieur à 1 associe le nombre $(1 - z)^{-a}$.
    Maintenant, si on s'intéresse aux permutations dont la décomposition en cycles disjoints ne contient que des cycles de longueurs multiples de p (p étant un entier naturel non nul), alors on peut appliquer le théorème que j'ai mentionné dans les messages précédents à l'ensemble (noté $p\N^*$) des entiers naturels non nuls multiples de p. Pour tout nombre z de module strictement inférieur à 1 : \begin{align*}
    \sum_{n=0}^{\infty} \frac{|F_n(\N,p\N^*)|}{n!}z^n&=\sum_{k \in \N}\frac{1}{k!}(\sum_{l \in p\N^*}\frac{z^l}{l})^k=\exp(\sum_{l \in p\N^*}\frac{z^l}{l})=\exp(\frac{-1}{p} \times ln(1 - z^p))\\
    &=(1 - z^p)^{\frac{-1}{p}}=\sum_{n=0}^{\infty}(\prod_{k=0}^{<n}{\frac{1}{p}}+k)\frac{z^{pn}}{n!}=\sum_{n=0}^{\infty}(\prod_{k=0}^{<n}pk+1)\frac{z^{pn}}{p^n \times n!}
    \end{align*} Donc pour tout entier naturel n et pour tout entier naturel non nul p : $$|F_{pn}(\N,p\N^*)| = \frac{(pn)!}{p^n \times n!}(\prod_{k=0}^{<n}pk+1)$$
    En particulier, si p = 2 : $$|F_{2n}(\N,2\N^*)| = \frac{(2n)!}{2^n \times n!}(\prod_{k=0}^{<n}2k+1)=(\frac{(2n)!}{2^n \times n!})^2= (\prod_{k=0}^{<n}2k+1)^2$$
    Et bien sûr, pour tout nombre z de module strictement inférieur à 1 : $$\sum_{n=0}^{\infty} \frac{|F_n(\N,\{2\})|}{n!}z^n=\exp(\frac{z^2}{2})=\sum_{n=0}^{\infty}\frac{z^{2n}}{2^n \times n!}$$
    Donc pour tout entier naturel n : $$|F_{2n}(\N,\{2\})|=\frac{(2n)!}{2^n \times n!}=\prod_{k=0}^{<n}2k+1$$

  • Bah j'abandonne. @JeremyLebre C'est toi qui n'es pas clair, en parlant d'abord de cycle d'ordre pair, puis de cycle de longueur paire, alors qu'il s'agit en fait d'orbites de cardinal pair, et qui te mélanges dans les notions. Plus clairement, les transpositions ne sont évidemment pas à compter dans les permutations dont les orbites sont de cardinal pair, mais elles sont à compter dans les cycles de longueur paire.
    En fait, cela ne m'intéresse pas plus que ça, je n'aurais pas dû m'en mêler et vais m'en tenir à la démonstration de @LOU16, que je remercie, qui tient en une page, quand ton document en fait 61, avec un ajout de précisions dans un autre document.
  • Modifié (July 2023)
    Je viens de passer un peu de temps à lire ton document... et le moins que l'on puisse dire, c'est qu'il manque de clarté car les énoncés et démonstrations sont juxtaposés et non séparés en plus petits morceaux, avec des notations claires et pratiques.
    Par ailleurs, tu passes autant de temps sur des évidences (genre l'additivité de $|F_n(K,L)|$ par rapport à l'ensemble $K$) et sur des calculs pas du tout triviaux (comme le passage de la page 4 à la page 5, ou la fin du calcul de la page 5).
    Cependant, le résultat démontré dans ces 5 premières pages m'a l'air correct et intéressant, pour peu que l'on prenne le temps de l'écrire correctement.
    Les applications que tu dis en découler ne m'ont pas l'air si simples... mais je n'ai pas lu la suite pour l'instant.
  • Le document fait 61 pages, mais c'est un recueil de théorèmes, et celui avec les ensembles K et L qu'on peut remplacer par ce qu'on veut est en fait démontré à la fin de la page 5.

    En cherchant sur le web, j'ai vu que certaines sources disent qu'il faut une longueur au moins égale à 2 pour parler de cycle, d'autres acceptent les cycles de longueur 1. Le théorème déjà connu sur le nombre moyen de cycles dans la décomposition d'une permutation implique d'accepter les cycles de longueur 1.
    Même chose pour celui qui relie le nombre de cycles aux nombres de Stirling.

    @JeremyLebre OK. Maintenant j'ai compris pour les cycles d'ordre pair. Mais je suis un peu largué pour celui à la fin de la page 7.
  • Modifié (July 2023)
    @bisam En effet, beaucoup de choses ne sont pas claires. C'est pour ça que j'ai ajouté des précisions.
    @Antooane J'essayais juste d'expliquer les choses patiemment sans aucune animosité. En fait je pensais qu'il y avait un consensus sur la notion de cycle et l'existence de cycles de longueur 1. Je viens de me rendre compte qu'il y a en réalité un désaccord sur ça. Si seulement les cycles étaient définis comme des permutations n'ayant qu'une seule orbite, ça éviterait beaucoup de confusion et d'incohérences. La définition d'un cycle comme une permutation n'ayant qu'une seule orbite de cardinal supérieur ou égal à 2 et pouvant tout de même avoir un ou plusieurs point(s) fixe(s) est incompatible avec l'unicité de la décomposition en produit de cycles à supports disjoints.
    Mais je suis un peu largué pour celui à la fin de la page 7.
    Oui, la façon dont je passe du théorème de la fin de la page 5 à celui de la page 7 est hallucinante. Je vais prendre le temps de bien expliquer ma démarche et de rendre ça plus clair.
  • Modifié (July 2023)
    Bonjour,
    Quelques manipulations algébriques permettent d' obtenir directement , dans l'anneau $\Q[[X]]$ des séries formelles, l'identité $$\displaystyle\sum_{n=0}^{+\infty} \frac{|F_n(K,L)|}{n!}X^n=\sum_{k \in K}\frac{1}{k!}\left(\sum_{l \in L}\frac{X^l}{l}\right)^k.$$
    $a_n$ désignant le coefficient de  $X^n$ dans le membre de droite,il s'agit donc d'établir que:$\quad \boxed{|F_n(K,L)|=n!a_n.}$
    $\forall n \in \N,\:\:\mathcal P_n: =\displaystyle \left\{ x\in \N^{\N^*}\mid\sum_{k=1}^{+\infty}kx_k =n \right\}$ est l'ensemble des partitions de $n$.
    Soit $\Phi$ la bijection "naturelle" de $\mathcal P_n$ vers l'ensemble des classes de conjugaison de $\mathfrak S_n.\:$Pour $x\in \mathcal P_n,\:$ un dénombrement "classique"  assure que $\:|\Phi(x)|=\displaystyle \dfrac{n!}{\prod_{k=1}^{+\infty}k^{x_k}(x_k)!}.\:$(cardinal de la classe de conjugaison "de type $x$".)
    $\mathcal P_n(K,L):= \displaystyle\left\{x\in\N^L\mid \sum_{l\in L} lx_l =n, \:\:\sum_{l\in L}x_l\in K\right\}$ est l'ensemble des partitions de $n$  dont les "sommants" sont dans $L$ et le nombre de "sommants" est dans K. Il résulte du point précédent que:
    $$\boxed{|F_n(K,L)|= \displaystyle \sum_{x\in\mathcal P_n(K,L)} \dfrac{n!}{\prod_{l\in L}l^{x_l}(x_l)!}}$$
    D'autre part, notons , pour $ k\in K, \:\:\mathcal S_k =\displaystyle \left\{x\in \N^{L}\mid \sum_{l\in L}x_l=k\right\}.$ 
    La "formule du multinôme" donne: $\forall k\in K, \quad\left(\displaystyle\sum_{l\in L}\dfrac{X^l}l\right)^k =\displaystyle\sum _{x\in \mathcal S_k}\dfrac {k!}{\prod_{l\in L}(x_l)!}\prod_{l\in L}\left(\dfrac{X^l}l\right) ^{x_l}=\sum _{x\in \mathcal S_k}\dfrac {k!}{\prod_{l\in L}(x_l)!} \dfrac{X^{\sum_{l\in L}lx_l}}{\prod_{l\in L}l^{x_l}},\:\:$ 
    de sorte que:$\:\:\displaystyle\sum _{k\in K}\dfrac 1{k!}\left(\displaystyle\sum_{l\in L}\dfrac{X^l}l\right)^k=\sum_{n=0}^{+\infty}\left(\sum_{x\in \mathcal P_n(K,L)}\dfrac 1{\prod_{l\in L}l^{x_l}(x_l)!}\right) X^n\qquad \boxed{a_n=\sum_{x\in \mathcal P_n(K,L)}\dfrac 1{\prod_{l\in L}l^{x_l}(x_l)!}\quad \square}$.
  • JeremyLebre a dit : Si seulement les cycles étaient définis comme des permutations n'ayant qu'une seule orbite, ça éviterait beaucoup de confusion et d'incohérences. 
    Tu sembles ignorer ce que sont les orbites pour l'action de groupe. C'est une définition. Il s'agit ici de l'action du sous-groupe $\langle \sigma \rangle \subset \mathfrak S_n$ sur $\N_n$ et de ses orbites. Elles forment une partition de $\N_n$, donc un cycle de longueur $< n$ ne peut pas avoir une seule orbite. Les cycles (de longueur $\geq 2$) sont les permutations ayant une seule orbite non ponctuelle.
    JeremyLebre a dit : La définition d'un cycle comme une permutation n'ayant qu'une seule orbite de cardinal supérieur ou égal à 2 et pouvant tout de même avoir un ou plusieurs point(s) fixe(s) est incompatible avec l'unicité de la décomposition en produit de cycles à supports disjoints.
    On appelle orbites ponctuelles les points fixes, et cela ne peut pas être incompatible puisque c'est un théorème (tu as peut-être oublié de préciser à l'ordre des facteurs près).
  • Bravo @LOU16. Je n'ai pas contrôlé mais je te fais confiance.
  • Modifié (July 2023)
    Par permutation n'ayant qu'une seule orbite, je veux dire que pour n'importe quel élément de l'ensemble de définition de la permutation, l'orbite de cet élément est égal à l'ensemble de définition de la permutation. C'est une définition équivalente à celle de la page anglophone de Wikipedia.
    cela ne peut pas être incompatible puisque c'est un théorème
    Mais les démonstrations de ce théorème reposent sur une définition du cycle qui n'est pas celle que donne la page francophone de Wikipedia. Avec cette dernière définition, quand une permutation a au moins un point fixe et au moins une orbite de cardinal k supérieur ou égal à 2, alors une décomposition de cette permutation en produit de cycles à supports disjoints peut contenir ce cycle de longueur k, avec un ensemble de définition contenant k éléments, et une autre peut contenir une extension de ce cycle, en ajoutant le point fixe à son ensemble de définition.
    Comme le rappelle Antooane, un théorème connu dit que le nombre moyen de cycles dans la décomposition d'une permutation d'un ensemble de n éléments en produit de cycles à supports disjoints est égal à la somme des inverses des n plus petits entiers naturels non nuls. Et un autre également connu relie le nombre de cycles de cette décomposition aux nombres de Stirling de première espèce non signés. Ces deux théorèmes sont compatibles avec la définition du cycle donnée dans la page anglophone de Wikipedia, mais pas avec celle de la page francophone.
    @Antooane Puisque j'ai le droit de remplacer $K$ par n'importe quel sous-ensemble de $\N$, et $L$ par n'importe quel sous-ensemble de $\N^*$, je me décide à les remplacer respectivement par l'ensemble (noté $(p\N + r)$) des entiers naturels dont le reste de la division euclidienne par p est égal à r (p étant un entier naturel non nul, et r un entier naturel strictement inférieur à p), et par l'ensemble (noté $q\N^*$) des entiers naturels non nuls multiples de q (q étant un entier naturel non nul), histoire de voir ce que ça donne.
    Pour ça, j'ai besoin du lemme de la page 61 :
    Si $z_0$ est un nombre complexe, a un réel strictement positif, et f une fonction holomorphe sur $\{ z \in \C | \lvert z - z_0 \rvert < a \}$, alors pour tout nombre z de cet ensemble :$$\sum_{k \in (p\N + r)}\frac{f^{(k)}(z_0)}{k!}z^k= \frac{1}{p} \sum_{k=0}^{<p} e^{-2kri\pi/p}f(z_0 + e^{2ki\pi/p}z)$$
    L'intérêt de ce lemme est, quand on connaît la série entière d'une fonction f, de pouvoir exprimer à partir de cette même fonction f, la série entière dont tous les coefficients sont nuls, à l'exception de ceux dont le rang est de la forme (pn + r), où n est entier, qui ont la même valeur que ceux du même rang pour la fonction f. En l'appliquant, j'obtiens :$$\sum_{n=0}^{\infty} \frac{|F_n((p\N + r),q\N^*)|}{n!}z^n=\sum_{k \in (p\N + r)}\frac{1}{k!}(\sum_{l \in q\N^*}\frac{z^l}{l})^k=\sum_{k \in (p\N + r)}\frac{1}{k!}(\frac{-ln(1 - z^q)}{q})^k$$
    $$=\frac{1}{p} \sum_{k=0}^{<p} e^{-2kri\pi/p}\exp(-(e^{2ki\pi/p}ln(1 - z^q))/q)=\frac{1}{p} \sum_{k=0}^{<p} e^{-2kri\pi/p}(1 - z^q)^{e^{-2ki\pi/pq}}$$
    $$=\frac{1}{p} \sum_{k=0}^{<p} e^{-2kri\pi/p}(\sum_{n=0}^{\infty} (\prod_{j=0}^{<n}(e^{2ki\pi/pq}+j)) \frac{z^{qn}}{n!})=\frac{1}{p} \sum_{k=0}^{<p} e^{-2kri\pi/p}(\sum_{n=0}^{\infty} (\prod_{j=0}^{<n}(e^{2ki\pi/p}+qj)) \frac{z^{qn}}{q^n \times n!})$$
    Donc pour tout entier naturel n :$$|F_{qn}((p\N + r),q\N^*)|=\frac{(qn)!}{p \times q^n \times n!} \sum_{k=0}^{<p} e^{-2kri\pi/p} (\prod_{j=0}^{<n}(e^{2ki\pi/p}+qj))$$
    $$|F_{pn}((p\N + r),p\N^*)|=\frac{(pn)!}{p \times p^n \times n!} \sum_{k=0}^{<p} e^{-2kri\pi/p} (\prod_{j=0}^{<n}(e^{2ki\pi/p}+pj))$$
    Si n est non nul, et r un entier compris entre 0 (inclus) et n (exclu), alors :$$|F_{pn}((n\N + r),p\N^*)|=\frac{(pn)!}{n \times p^n \times n!} \sum_{k=0}^{<n} e^{-2kri\pi/n} (\prod_{j=0}^{<n}(e^{2ki\pi/n}+pj))$$
    Ces formules sont compliquées mais elles me permettent d'appliquer le lemme mentionné plus haut en sens inverse. En effet, si f est la fonction polynomiale qui à tout nombre z associe le nombre $\frac{(pn)!}{p^n \times n!} \prod_{j=0}^{<n}(z+pj)$, alors la ligne ci-dessus peut se réécrire comme ça :$$|F_{pn}((n\N + r),p\N^*)|=\frac{1}{n} \sum_{k=0}^{<n} e^{-2kri\pi/n} f(e^{2ki\pi/n})$$
    En remplaçant dans le lemme, p par n, $z_0$ par 0, z par 1, et k par l, on obtient :$$\sum_{l \in (n\N + r)}\frac{f^{(l)}(0)}{l!}=\frac{1}{n} \sum_{k=0}^{<n} e^{-2kri\pi/n} f(e^{2ki\pi/n})$$
    Donc : $$|F_{pn}((n\N + r),p\N^*)|=\sum_{l \in (n\N + r)}\frac{f^{(l)}(0)}{l!}$$
    Soit k l'entier égal à r si r > 0, et à n si r = 0. Comme f est une fonction polynomiale de degré n qui s'annule en 0, k est le seul entier l de $(n\N + r)$ pour lequel la dérivée d'ordre l de f en 0 n'est pas nécessairement nulle, donc : $$|F_{pn}((n\N + r),p\N^*)|=\frac{f^{(k)}(0)}{k!}$$
    Et d'ailleurs, puisqu'une permutation de pn éléments se décompose en au minimum un cycle (pn étant forcément non nul), et en au maximum n cycles de longueurs multiples de p, k est aussi le seul entier l de $(n\N + r)$ pour lequel $|F_{pn}(\{l\},p\N^*)|$ n'est pas nécessairement nul, donc : $$|F_{pn}((n\N + r),p\N^*)|=|F_{pn}(\{k\},p\N^*)|=\frac{f^{(k)}(0)}{k!}$$
    Cette dernière ligne signifie que pour tout entier k compris entre 1 (inclus) et n (inclus), $|F_{pn}(\{k\},p\N^*)|$ est le coefficient d'ordre k de la fonction polynomiale f. Comme c'est aussi vrai quand k = 0, on en déduit :$$\sum_{k=0}^{n}|F_{pn}(\{k\},p\N^*)|z^k=f(z)=\frac{(pn)!}{p^n \times n!} \prod_{k=0}^{<n}(z+pk)$$
    Et on vérifie facilement que ça reste vrai quand n = 0. Je ne sais pas si ce théorème est déjà connu, mais en remplaçant p par 1, on obtient le théorème déjà connu qui relie le nombre de cycles dans la décomposition en produit de cycles à supports disjoints d'une permutation aux nombres de Stirling de première espèce non signés :
    $$\sum_{k=0}^{n}|F_{n}(\{k\},\N^*)|z^k=\prod_{k=0}^{<n}(z+k)$$
  • Modifié (July 2023)
    En effet, dans le site anglophone, c'est ambigu, on peut parler d'un cycle sans faire référence à une permutation. En fait, tout dépend si on compte les cycles ponctuels ou non dans la décomposition d'une permutation en produit de cycles à supports disjoints. Si on les compte (ce qui me parait le plus logique), il ne faut pas prendre en compte les transpositions dans les permutations en produits de cycles à supports disjoints de longueur paire (pour $n \geq 3$). Du coup, je ne comprends plus mon objection du début. Je crois que c'est le mot "ordre" au lieu de "longueur" qui m'a perturbée.
    Du coup, cela me parait beaucoup plus évident, et je me demande si une simple récurrence sur $2n$ ne pourrait pas suffire à la démonstration, en juxtaposant une transposition aux cycles de longueur paire $2k$, dont le support donne des cycles de longueur $2k+2$, et un dénombrement adéquat. Mais évidemment, il faut généraliser. Ton théorème ne s'applique pas seulement aux cycles de longueur paire.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!