175. Dénombrer les permutations de l’ensemble {1,...,n} dont les cycles, dans la décomposition en cycles à support disjoints, sont tous de longueur paire.

Toute permutation de [ [1,n]] distincte de l’identité se décompose de façon unique (à l’ordre près des facteurs) comme produit de cycles à supports disjoints : cette décomposition sera dite canonique.

Pour n ∈ N * , notons En l’ensemble des permutations de [ [1,n]] sans point fixe dont tous les cycles de la décomposition canonique sont de longueur paire et posons en = cardEn. Pour tout σ ∈ En, les supports des cycles de la décomposition canonique de σ forment une partition de [ [1,n]] ; donc En si et seulement si n est pair. Ainsi en = 0 si n est impair, ce que l’on retrouve ci-dessous. Dans la suite, on convient que e0 = 1. On propose deux solutions pour le calcul de en, la seconde étant purement combinatoire.

1re  solution. Soient k ∈[[ ⌊  ⌋]]
 1, n2 et En,k l’ensemble des σ ∈ En tels que 1 figure dans un cycle de longueur 2k. Les ensembles (En,k)1kn
2 forment une partition de En. Tout σ ∈ En,k est déterminé par la donnée du couple (α,τ)α = (a1,...,a2k-1) est un arrangement de 2k - 1 éléments de [ [2,n]] tel que (1,a1,...,a2k-1) est le cycle de la décomposition canonique de σ contenant 1 et τ est une permutation de l’ensemble [[2, n]] \ {a1,...,a2k-1} sans point fixe, dont la décomposition canonique ne contient que des cycles de longueur paire. Les permutations τ forment un ensemble équipotent à En-2k .

Ainsi card En,k = (n-1)!
(n-2k)!en-2k, d’où

         ⌊n2⌋
--en---= ∑  --en-2k-⋅
(n- 1)!  k=1(n - 2k)!
(1)

Considérons la série entière +∑ ∞

n=0en
 n!xn dont le rayon de convergence est supérieur ou égal à 1 puisque en n! et notons f(x) sa somme pour x ∈] - 1,1[. La série entière +∞
∑
k=1x2k a pour rayon de convergence 1 et pour somme sur ] - 1,1[,  x2
1-x2

La fonction f est dérivable et

              ʹ    +∑∞  --en---n
∀x ∈]- 1,1[,xf (x) =    (n - 1)!x .
                   n=1
(2)

Le résultat sur le produit de deux séries entières permet d’écrire :

x ∈] - 1, 1[, f(x)1x-2x2 = (           )
 ∑+m∞=0 emm!xm(        )
 ∑+k∞=1x2k = +∑ ∞

n=1cnxn

cn = ⌊n2⌋∑

k=1en-2k(n-2k)! = (enn-1! d’après (1), d’où d’après (2) :

x ∈] - 1, 1[, xfʹ(x) =  2
1-xx2-f(x), puis

∀x ∈]- 1,1[\{0},(1- x2)fʹ(x)- xf(x) = 0.
(3)

En remarquant que la fonction x↦→(     )
 1 - x2-1
2f(x) a pour dérivée sur ] - 1,1[, x↦→ ()
1-x2-1
2(                  )
 (1- x2)fʹ(x) - xf (x ), on déduit de (3) qu’il existe λ,μ ∈ R tels que :

x ∈]0, 1[, f(x) = λ(     )
 1- x2-1
2 et x ∈] - 1,0[,f(x) = μ(      )
 1 - x2-1
2.

Or f est continue en 0 de valeur f(0) = 1, donc λ = μ = 1 et

                  (    2)- 12
∀x ∈]- 1,1[,f (x) =  1- x    .
(4)

On montrer aisément que x↦→(1- x2)-12 se développe en série entière sur ] - 1,1[ sous la forme :

                  + ∞
      (    2)- 12  ∑   1×-3-×⋅⋅⋅×-(2m---1) 2m
f(x) = 1- x     = m=0        2mm!        x  .
(5)

En comparant avec la définition de f, on retrouve que en = 0 si n est impair et si n est pair, on obtient en posant n = 2m,

   1× 3× ⋅⋅⋅× (2m - 1)
e2m=  -------2mm!--------⋅(2m)!                           (6)
                                       (2m )!(2m )
=  (1 × 3× ⋅⋅⋅× (2m - 1))2 = ((2m - 1)!!)2 =--2m-      .    (7)
                                        2     m

2nde solution. En est l’ensemble des permutations de [ [1,n]] dont toutes les orbites sont paires. Supposons n pair et écrivons n = 2m m ∈ N*. Considérons le procédé suivant consistant à ranger et à séparer les entiers de 1 à n pour former une liste correspondant à un élément de En : on effectue n tirages successifs. Au premier tirage, on prend 1 (le plus petit élément de [ [1,n]] ) qui est le début de la liste. On complète la liste en effectuant n - 1 autres tirages. Au tirage de rang r r ∈ [ [ 2, n]] , si r est pair, on choisit l’un des 2m- (r - 1) entiers restants (ie ne figurant pas dans la liste déjà formée) et on l’ajoute à la liste en cours de formation. Il y a donc kr = 2m + 1 - r choix.

Si r est impair, on choisit l’un des 2m - (r - 1) entiers restants ou le symbole de séparation que l’on note : .

Si l’on choisit , on l’ajoute à la liste en cours et on le fait suivre par le plus petit des 2m- (r - 1) entiers restants. Si l’on choisit un des 2m - (r - 1) entiers restants, on l’ajoute à la liste en cours.

Pour un tel tirage, il y a donc kr = 2m - (r - 1) + 1 = 2m + 2 - r choix.

Associons à la liste obtenue au terme des n tirages la permutation σ ∈ En dont les cycles sont les blocs d’entiers déterminés par les séparateurs . Par exemple, pour m = 3, la liste 1,6,5,23,4 signifie que l’on a choisi 6,5,2 aux tirages de rangs respectifs 2,3,4. Au 5e tirage, on a choisi le séparateur qui est suivi de 3, le plus petit entier restant. Au 6e tirage, on prend 4 (le seul entier restant). À cette liste correspond σ = (1,6,5,2) (3,4) qui appartient à E3 .

Il est clair que la correspondance entre les listes formées en suivant le procédé considéré et les éléments de En est biunivoque. Ainsi e2m est le nombre de ces listes, donc e2m = 2m
∏
i=1kik1 = 1. Or, pour tout q ∈ [ [1,m - 1]], k2q = k2q+1 = 2(m - q) + 1 et k1 = k2m = 1, donc

m∏               m∏                              (   )
e2m=(2(m - q)+ 1)2 =   (2ℓ- 1)2 = ((2m - 1)!!)2 = (2m)! 2m .
q=1               ℓ=1                         22m    m

Notons pour n ∈ N*, Fn l’ensemble des permutations de [ [1,n]] dont tous les cycles de la décomposition canonique sont de longueur paire et posons un = cardFn. on a :

     ⌊∑n2⌋   (n )      ⌊∑n2⌋   ( n)
un =    e2k 2k  = 1+    e2k 2k  .
     k=0             k=1
(8)

En effet, si σ ∈ Fn \{     }
 id[[1,n]], la réunion Xσ des supports des cycles de la décomposition canonique de σ est une partie de [ [1,n]] de cardinal 2k k ∈[[  ⌊n⌋]]
 1, 2 (l’ensemble [ [1,n]] \ Xσ étant l’ensemble des points fixes de σ). Notons Fn,Y l’ensemble des σ ∈ Fn tels que Xσ = Y Y est une une partie de cardinal 2k de [ [1,n]]. L’ensemble Fn,Y étant équipotent à E2k a pour cardinal e2k et il y a (n )
 2k façons de choisir Y , donc un = 1 +  n
⌊∑2⌋

k=1e2k(2k)
 k.

Ainsi, compte tenu de (6) et (7),

    ⌊∑n2⌋(  )                   ⌊∑n2⌋(  )
un=1 +     n   ((2k - 1)!!)2 = 1 + n!   2k  ----1-----⋅
    k=1  2k                    k=1  k  22k(n - 2k)!
(9)


[Liste des corrigés]