Décomposition des m-Stirling permutations en m-cycles
1. Rappel : m-Stirling permutations
Une m-Stirling permutation d’ordre n est une permutation du multiensemble
{1m , 2m , . . . , nm }
(c’est-à-dire que chaque entier de 1 à n apparaît exactement m fois) telle que, entre deux
occurrences d’un même entier i, tous les éléments intermédiaires sont supérieurs ou égaux
à i.
On note par Qm [n] l’ensemble des m-Stirling permutations d’ordre n.
2. Définition d’un m-cycle
Soit
σ = σ1 σ2 . . . σmn ∈ Qm [n].
Une sous-suite consécutive
σ 0 = σi σi+1 . . . σs
est appelée un m-cycle si :
1. σ 0 est une m-Stirling permutation sur un sous-ensemble A ⊂ [n] ;
2. σi = min A ;
3. σi > σs+1 (si s < mn).
3. Exemple
Considérons
σ = 6624423311.
On obtient la décomposition en m-cycles :
{[66], [244233], [11]}.
En revanche :
– 2442 n’est pas un m-cycle (il ne contient pas toutes les occurrences nécessaires) ;
– 24423311 n’est pas un m-cycle (le minimum du bloc n’est pas respecté).
4. Minima de gauche à droite
Un élément σi est un minimum de gauche à droite si
σi < σj pour tout j < i.
Autrement dit, c’est un nouvel élément strictement plus petit que tous ceux qui le
précèdent.
Exemple :
1
Pour
σ = 5512214433,
les minima de gauche à droite sont 5 et 1.
La décomposition correspondante est
{[55], [12214433]}.
5. Lemme
Lemme. Toute m-Stirling permutation se décompose de manière unique en un en-
semble disjoint de m-cycles.
La décomposition est obtenue en coupant la permutation à chaque minimum de gauche
à droite.
6. Série génératrice
On pondère chaque permutation σ par
β(σ) = µk xmn ,
où k est le nombre de m-cycles.
On obtient alors la série génératrice :
Qm,β (t) = (1 − mxm t)−µ/m .
De plus,
Hg (t) = z(1 − mxm t)−µ/m .
Ce résultat correspond à l’énumération des m-Stirling permutations selon leur nombre
de minima de gauche à droite (résultat de Park).
Énumération des m-Stirling permutations selon le nombre
de m-cycles
Théorème 1. Soit cm (n, k) le nombre de m-Stirling permutations d’ordre n ayant exac-
tement k m-cycles.
Alors n
X
g
Hn (z) = cm (n, k) µk z xmn ,
k=1
et la suite (cm (n, k)) satisfait la relation de récurrence :
cm (n, k) = cm (n − 1, k − 1) + m(n − 1) cm (n − 1, k), (18)
avec conditions initiales :
cm (0, 0) = 1, cm (n, 0) = 0 pour n ≥ 1, cm (0, k) = 0 pour k ≥ 1.
Autrement dit,
cm (n, k) = cm,0 (n, k), (19)
où cm,r (n, k) désignent les nombres de Whitney non signés de première espèce.
2
Explication combinatoire
On veut compter les m-Stirling permutations selon leur nombre de m-cycles (c’est-à-
dire selon le nombre de minima de gauche à droite).
Idée de la récurrence
Considérons une m-Stirling permutation d’ordre n − 1 ayant k ou k − 1 m-cycles, et
insérons les m occurrences du nouvel élément n.
Deux situations peuvent se produire :
1. Création d’un nouveau m-cycle.
Si l’on place les m copies de n de manière à former un bloc indépendant à gauche, on
crée un nouveau minimum de gauche à droite.
On obtient donc une permutation ayant k cycles à partir d’une permutation à k − 1
cycles :
cm (n − 1, k − 1).
2. Insertion dans un cycle existant.
Sinon, les m copies de n sont insérées à l’intérieur d’un des cycles existants.
Une permutation d’ordre n−1 contient m(n−1) positions possibles d’insertion (chaque
élément apparaît m fois).
Pour chaque permutation à k cycles, on a donc :
m(n − 1) cm (n − 1, k).
En additionnant les deux contributions, on obtient :
cm (n, k) = cm (n − 1, k − 1) + m(n − 1)cm (n − 1, k).
Interprétation
Cette relation est exactement celle des nombres de Whitney non signés de pre-
mière espèce (cas r = 0).
Elle généralise la récurrence classique des nombres de Stirling de première es-
pèce :
c(n, k) = c(n − 1, k − 1) + (n − 1)c(n − 1, k),
qui correspond au cas particulier m = 1.
Ainsi, les m-Stirling permutations jouent, du point de vue des cycles, le même rôle
que les permutations ordinaires, avec un facteur multiplicatif m dû à la multiplicité des
occurrences.
3
Démonstration. Une structure (T Hg )n (Z) s’obtient en appliquant la construction (T Hg )
à une structure (T Hg )n−1 (Z).
À partir d’une structure de taille n−1, on insère le nouvel élément n. Deux possibilités
se présentent.
Premier cas : création d’un nouveau m-cycle.
On remplace une feuille pondérée par z par un nœud de type T , étiqueté par n, suivi
d’une feuille z et de m feuilles x.
On crée ainsi un nouveau m-cycle, de poids
µzxm .
Cette opération correspond aux structures comptées par cm (n − 1, k − 1).
Deuxième cas : insertion dans un cycle existant.
On remplace une feuille pondérée par x par un nœud de type T , étiqueté par n, suivi
de m + 1 feuilles x.
Le nombre de m-cycles reste inchangé, mais on ajoute m nouvelles feuilles pondérées
par x.
Or une structure sur [n − 1] possède exactement m(n − 1) feuilles pondérées par x. On
obtient donc
m(n − 1)cm (n − 1, k)
structures de taille n ayant k m-cycles.
En additionnant les deux contributions, on obtient la relation de récurrence :
cm (n, k) = cm (n − 1, k − 1) + m(n − 1)cm (n − 1, k).
Cela complète la preuve.
Corollaire 1. Pour tout n ≥ 0, on a
n
X
cm (n, k) µk = µ(µ + m)(µ + 2m) · · · (µ + m(n − 1)). (20)
k=0
Démonstration. Partons de la relation de récurrence :
cm (n, k) = cm (n − 1, k − 1) + m(n − 1)cm (n − 1, k).
Multiplions cette égalité par µk et faisons la somme sur k. On obtient
X X X
cm (n, k)µk = cm (n − 1, k − 1)µk + m(n − 1) cm (n − 1, k)µk .
k k k
Dans le premier terme, en effectuant le changement d’indice j = k − 1, on obtient
X X
cm (n − 1, k − 1)µk = µ cm (n − 1, j)µj .
k j
Ainsi, X X
cm (n, k)µk = (µ + m(n − 1)) cm (n − 1, k)µk .
k k
4
En itérant cette relation et en utilisant la condition initiale
X
cm (0, k)µk = 1,
k
on obtient
n
X n−1
Y
k
cm (n, k)µ = (µ + mi) = µ(µ + m)(µ + 2m) · · · (µ + m(n − 1)).
k=0 i=0
On remarque enfin que
µ µ µ
n
µ(µ + m) · · · (µ + m(n − 1)) = m + 1 ··· +n−1 ,
m m m
ce qui montre le lien avec les nombres de Whitney (et, dans le cas m = 1, avec les nombres
de Stirling de première espèce).
Corollaire 2. On a
cm (n, k) = m n−k c(n, k), (21)
où c(n, k) désigne le nombre de Stirling non signé de première espèce, c’est-à-dire le
nombre de permutations de [n] ayant exactement k cycles.
Démonstration. D’après le corollaire précédent, on a
n
X n−1
Y
k
cm (n, k) µ = (µ + mi).
k=0 i=0
On factorise chaque terme :
µ
µ + mi = m +i .
m
Ainsi,
n−1 n−1
Y Y µ
(µ + mi) = mn +i .
i=0 i=0
m
Or on sait que les nombres de Stirling non signés de première espèce satisfont :
n
X n−1
Y
c(n, k) xk = (x + i).
k=0 i=0
µ
En remplaçant x par m
, on obtient :
n−1 n
Y µ X µ k
+i = c(n, k) .
i=0
m k=0
m
5
Donc n n
X X µ k
k n
cm (n, k) µ = m c(n, k) .
k=0 k=0
m
En simplifiant,
n
X n
X
cm (n, k) µk = m n−k c(n, k) µk .
k=0 k=0
k
Par identification des coefficients de µ , on obtient :
cm (n, k) = m n−k c(n, k).
Cela montre que les nombres comptant les m-Stirling permutations selon les m-cycles
sont simplement des multiples des nombres de Stirling classiques, pondérés par un facteur
m n−k .
Remarque 1 (Rappel). La solution du système d’équations différentielles associé à une
grammaire G est le n-uplet
~ ~ = (A ~ )i∈[n] ,
AF F ,i
formé d’espèces mixtes d’arbres enracinés enrichis par F~ . Les séries génératrices des types
d’isomorphisme
AF~ ,i = TX=~
~ x AF~ ,i , (1 ≤ i ≤ n),
sont précisément les solutions du système analytique d’équations différentielles associé.
Si G est une grammaire sur A = {x1 , . . . , xn } et F = F (X1 , . . . , Xn ) une B-espèce,
alors la L-espèce des types d’isomorphisme de G(F ) est notée G(F ).
Soient H et K deux grammaires définies sur deux alphabets disjoints A et B, et soit
g ∈ R[[B]]. On note Hg la grammaire sur A obtenue en remplaçant chaque règle u → v
de H par u → vg. La grammaire
HK,g = Hg ∪ K
définie sur A ∪ B est appelée la composition de H et K en g.
~ sont
Plus généralement, si (Hi (Z1 , . . . , Zk ))i∈[k] , (Kj (X1 , . . . , X` ))j∈[`] et G = G(X)
des B-espèces de séries génératrices
hi = Hi (~z), kj = Kj (~x), g = G(~x),
alors la grammaire composée
HK,g = Hg ∪ K,
où H : zi → hi (i ∈ [k]) et K : xj → kj (j ∈ [`]), correspond à la composition des
grammaires H et K en g.
Theoreme 1. Pour 1 ≤ i ≤ k et 1 ≤ j ≤ `, on a :
tHK,g
e ~ ◦ Z
(Zi ) = AH,i , (7)
G (AK,j
~ )j∈[`]
etHK,g (Xj ) = AK,j
~ . (8)
6
~ 2 (X),
Plus généralement, pour toute B-espèce F = F1 (Z)F ~ on a :
h i
~~ ◦ Z ~
etHK,g (F ) = F1 ◦ A ~~ ,
H G(A ~ ) · F2 ◦ AK (9)
K
où
~ ~ = F1 (A ~ , . . . , A ~ ) = etH (F1 ),
F1 ◦ A H H,1 H,k
et
~ ~ = F2 (A ~ , . . . , A ~ ) = etK (F2 ).
F2 ◦ AK K,1 K,`
Nous nous intéressons aux grammaires de type (E), c’est-à-dire aux grammaires de la
forme
Hg = { z → zg(~x), xi → hi (~x), 1 ≤ i ≤ k }.
Cette grammaire est la composition de
H = {z → z} et K = {xi → hi (~x), 1 ≤ i ≤ k}
en g(~x).
Les types d’isomorphisme des solutions vérifient :
h i
tHg ~
Hg = TX=~
~ x e (Z) = zE ◦ R G T ~ x
X=~ (A ~
H ) .
Considérons maintenant deux grammaires de type (E) :
Hg = {z → zg(~x), xi → hi (~x), 1 ≤ i ≤ k},
Kg1 = {v → vg1 (~u), uj → kj (~u), 1 ≤ j ≤ `}.
La grammaire
Pg = {v → vg1 (~u)g(~x), uj → kj (~u)g(~x), xi → hi (~x)}
(1 ≤ i ≤ k, 1 ≤ j ≤ `) est la composition de
H1 = {v → v}
avec
K1 = {uj → kj (~u)g(~x), xi → hi (~x)}
en
g(~u, ~x) = g1 (~u)g(~x).
Elle est encore de type (E).
Soit E la L-espèce des ensembles, G une L-espèce telle que G(∅) = ∅, et F = E ◦ G.
Si s est une structure de F , chaque élément de s est appelé une composante connexe de
s.
La matrice M = (a(n, k))n,k∈N , où a(n, k) est le nombre d’éléments de F [n] ayant k
composantes connexes, est appelée la matrice de F .
7
Théorème 2. Soient
M = (a(n, k))n,k∈N , N = (b(n, k))n,k∈N , λ = (λ(n, k))n,k∈N
les matrices associées respectivement à Hg , Kg1 et Pg . Alors
λ = M N,
c’est-à-dire X
λ(n, k) = a(n, i)b(i, k). (10)
i≥0
Plus généralement, si
~ 2 (U
F = F1 (X)F ~)
est une B-espèce, et si
λF = (λF (n, k)), λF1 = (λF1 (n, k)), λF2 = (λF2 (n, k))
sont les matrices associées respectivement à Pg (vF ), Hg (zF1 ) et Kg1 (vF2 ), alors
λF = λF1 λF2 .
Cas des nombres de Whitney r du premier type
On déduit facilement le cas des nombres de Whitney r du premier type wm,r (n, k) de
la relation
wm,r (n, k) = (−1)n−k cm,r (n, k).
En utilisant la grammaire
H1,g = { z → µzxm , x → −xm+1 }, (30)
et en prenant F (X) = X r , on obtient le modèle combinatoire
H1,g (zF ) = z Qm,β 0 · (Qm,α0 )r , (31)
où Qm,β 0 (resp. Qm,α0 ) est l’L-espèce des m-permutations de Stirling pondérées par
β 0 (σ) = (−1)n−k µk xmn , α0 (σ) = (−1)n−1 µk xmn+1 ,
si σ ∈ Qm [n] possède k m-cycles.
La série génératrice est
µ−r
H1,g (zF )(t) = zxr (1 + mxm t) m . (32)
En posant
n
X
H1,g (z) = wm (n, k)µk zxm ,
k=0
on obtient
wm (n, k) = (−1)n−k cm (n, k) = mn−k s(n, k), (33)
8
où s(n, k) sont les nombres de Stirling du premier type.
De plus,
Xn
wm (n, k)µk = µ(µ − m) · · · (µ − m(n − 1)). (34)
k=0
Plus généralement,
n
X
wm,r (n, k)µk = (µ − r)(µ − r − m) · · · (µ − r − m(n − 1)). (35)
k=0
Enfin,
n
X i
wm,r (n, k) = m n−i r i−k (−1)i−k s(n, i). (36)
i=k
k
4. Les nombres de Whitney r du second type
Considérons la grammaire
H2,g := { z → zxm , x → x }.
Dans [?], Hao et al. montrent que
n
X
n
H2,g (zx) = z Wm,1 (n, k)xmk+1 ,
k=0
où Wm,1 (n, k) est le nombre de Whitney du second type (Benoumhani [?]).
Dans [?], Méndez et Ramírez montrent que
n
X
n
H2,g (zxr ) = Wm,r (n, k)zxmk+r .
k=0
On modifie cette grammaire comme suit :
H2,g := { z → µzxm , x → x }. (37)
On obtient alors les polynômes de r-Dowling, définis par Shattuck [?], donnés par
n
X
Dm,r (n; µ) = Wm,r (n, k)µk .
k=0
On considère une grammaire différentielle Hg associée aux m-Stirling permutations. L’éga-
lité
Hg = z Qm,β
signifie que l’opérateur grammatical Hg s’interprète comme le produit d’une variable ini-
tiale z par la L-espèce Qm,β , qui représente la classe combinatoire des m-Stirling permu-
tations pondérées.
9
La pondération est définie par
β(σ) = µk xmn ,
si la permutation σ possède k m-cycles. Autrement dit, chaque m-cycle contribue un
facteur µ, tandis que la taille totale (liée à mn) intervient par la variable x.
On sait que la série génératrice exponentielle associée au poids β est
Eβ (t) = eµt .
En utilisant l’équation (12), on obtient alors les séries génératrices suivantes :
µ
Hg (t) = z(1 − mxm t)− m
et µ
Qm,β (t) = (1 − mxm t)− m .
Cette forme fermée provient de la résolution de l’équation différentielle combinatoire
associée à la grammaire. L’expression
µ
(1 − mxm t)− m
est caractéristique des structures construites à partir de cycles pondérés et correspond à
une série génératrice de type binomial généralisé.
Ainsi, Qm,β (t) est la série génératrice des m-Stirling permutations pondérées, et Hg (t)
s’obtient simplement par multiplication par z. On considère la grammaire à une variable
G := {x → xm+1 }.
1. Équation différentielle combinatoire associée
La grammaire G correspond à l’équation différentielle combinatoire :
Y 0 = Y m+1 , Y (0) = X.
Interprétation combinatoire :
– La dérivation Y 0 correspond à l’ajout d’un nouveau sommet interne.
– Le terme Y m+1 signifie qu’un sommet interne engendre exactement m + 1 sous-
structures.
Ainsi, chaque sommet interne possède exactement m + 1 descendants.
2. Solution combinatoire : arbres (m + 1)-aires complets
La solution combinatoire est l’espèce mixte
eT G (X) = Am+1 (T, X),
qui représente les arbres (m + 1)-aires complets :
– Chaque sommet interne a exactement m + 1 enfants ;
– Les feuilles sont de type X ;
– Les sommets internes sont marqués par T .
10
Autrement dit, la grammaire construit récursivement un arbre où chaque dérivation
ajoute un sommet interne avec m + 1 sous-arbres.
3. Espèce L et arbres croissants
En oubliant les étiquettes X, on obtient l’espèce L
Am+1,α (T ) = TX=x eT G (X),
qui correspond aux arbres (m + 1)-aires croissants.
Un arbre croissant signifie que les sommets internes sont étiquetés par 1, 2, . . . , n de
manière strictement croissante le long de tout chemin partant de la racine.
Le poids est donné par
α(b) = xmn+1
si l’arbre b possède n sommets internes.
En effet, dans un arbre (m + 1)-aire complet :
– Chaque sommet interne ajoute m + 1 arêtes descendantes ;
– Le nombre total de feuilles est égal à mn + 1.
4. Lien avec les m-Stirling permutations
Il existe une bijection entre :
– les arbres (m + 1)-aires croissants à n sommets internes ;
– les m-Stirling permutations d’ordre n.
L’idée de la bijection est la suivante :
– Chaque sommet interne correspond à une valeur apparaissant m fois dans la per-
mutation ;
– La structure hiérarchique de l’arbre encode l’imbrication des occurrences dans la
permutation.
Ainsi,
arbres croissants (m + 1)-aires ←→ m-Stirling permutations.
Résumé
La grammaire x → xm+1 :
– génère récursivement des arbres (m + 1)-aires ;
– l’équation différentielle traduit cette construction ;
– la solution combinatoire est une espèce d’arbres complets ;
– en version étiquetée croissante, on obtient une structure en bijection avec les m-
Stirling permutations.
Par conséquent, elle est isomorphe à l’espèce L Qm,α des m-Stirling permutations pondé-
rées par
α(σ) = xmn+1 si σ ∈ Qm [n].
La série génératrice exponentielle, obtenue en résolvant l’équation différentielle
y 0 (t) = y m+1 (t), y(0) = x,
est donnée par
X tn 1
Am+1,α (t) = Gn (x) = x(1 − mxm t)− m , si m ≥ 1,
n≥0
n!
11
et
A1,α (t) = xet .
Il est clair que
Gn (x) = (m + 1)(2m + 1) · · · (m(n − 1) + 1) xmn+1 .
On en déduit le résultat de Park [?], qui affirme que le nombre de m-Stirling permu-
tations sur [n] est
|Qm [n]| = (m + 1)(2m + 1) · · · (m(n − 1) + 1).
Considérons maintenant la grammaire suivante, où µ est une variable formelle comptant
le nombre de composantes connexes :
Hg = { z → µzxm , x → xm+1 }. (14)
Cette grammaire est la composition de
H = { z → µz } et K = { x → xm+1 }
via la substitution g(x) = xm .
On a
eT H (Z) = ZEβ (T ),
où Eβ est l’espèce L des ensembles pondérés par
β(A) = µ|A| ,
et
eT K (X) = Am+1 (T, X).
Ainsi,
eT Hg (Z) = ZEβ ◦R Am+1 (T, X).
On en déduit que
TZ=z, X=x eT Hg (Z) = Hg = zEβ ◦Z Am+1,α = zEβ ◦Z Qm,α .
(15)
L’équation (15) montre qu’une composante connexe d’une structure Hg est une struc-
ture RQm,α
m
.
Autrement dit, il s’agit d’un m-cycle au sens suivant. Les nombres eulériens et leurs
généralisations ont été largement étudiés (cf. [?]). Dans le présent article, nous nous in-
téressons à une généralisation récente appelée nombres eulériens de Whitney d’ordre r,
notés Am,r (n, k) dans [?]. Cette nouvelle suite est définie par l’expression
n
X
j n−j
Am,r (n, k) = Wm,r (n, j) m j! (−1)k−j , (3)
j=0
k − j
où Wm,r (n, k) désignent les nombres de Whitney d’ordre r de seconde espèce.
Les nombres de Whitney d’ordre r de seconde espèce Wm,r (n, k) ont été définis par
Mezö [?] comme coefficients de connexion entre certains polynômes particuliers. Plus
12
précisément, pour des entiers non négatifs n, k et r avec n > k > 0, et pour tout entier
m > 0, on a
Xn
n
(mx + r) = mk Wm,r (n, k) xk , (4)
k=0
où
xn = x(x − 1) · · · (x − n + 1) si n > 1, et x0 = 1.
Les nombres de Whitney d’ordre r de seconde espèce satisfont la relation de récurrence
suivante [?] :
Wm,r (n, k) = Wm,r (n − 1, k − 1) + (km + r) Wm,r (n − 1, k).
Remarquons que si (m, r) = (1, 0), on obtient les nombres de Stirling de seconde espèce. Si
(m, r) = (1, r), on obtient les nombres de Stirling r (ou nombres de Stirling non centraux)
[?], et si (m, r) = (m, 1), on obtient les nombres de Whitney [?]. Pour plus de détails sur
les nombres de Whitney r, voir par exemple [?, ?, ?, ?, ?, ?, ?, ?].
À partir de (3) et de la relation de récurrence (5), on obtient que les nombres eulériens
de Whitney r vérifient la relation de récurrence suivante :
Am,r (n, k) = (km + r)Am,r (n − 1, k) + m(n − (k − 1)) − r Am,r (n − 1, k − 1), (6)
avec les valeurs initiales
Am,r (0, 0) = 1,
et
Am,r (n, k) = 0 si k > n + 1 ou k < −1.
Si (m, r) = (1, 0), on retrouve les nombres eulériens classiques A(n, k). Si (m, r) =
(1, r), on obtient les nombres cumulatifs étudiés par Dwyer [?, ?], voir aussi les nombres
d’Euler–Frobenius étudiés par Gawronski et Neuschel [?]. Si (m, r) = (q + 1, 1), on obtient
les nombres eulériens q étudiés par Brenti [?].
Les polynômes eulériens de Whitney r sont définis par
n
X
An,m,r (x) := Am,r (n, k)xk .
k=0
Pour des entiers non négatifs r, n et m > 0, on sait [?] qu’ils satisfont l’identité
suivante : ∞
X An,m,r (x)
(mi + r)n xi = ,
i=0
(1 − x)n+1
et leur fonction génératrice exponentielle est
∞
X yn (1 − x) exp ry(1 − x)
An,m,r (x) = . (7)
n=0
n! 1 − x exp my(1 − x)
Pour une classe similaire de nombres eulériens liés aux nombres de Whitney, voir les
travaux de Rahmani [?] et Mező [?].
13
Dans le présent article, nous donnons une interprétation combinatoire des nombres
eulériens de Whitney r au moyen de permutations signées colorées. Ensuite, nous éta-
blissons plusieurs identités combinatoires en termes de cette nouvelle suite. De plus, nous
montrons que les nombres eulériens de Whitney r sont log-concaves et donc unimodaux.
Enfin, nous établissons certaines congruences intéressantes faisant intervenir cette suite.
Theoreme 2. Pour n > 1, les polynômes eulériens de Whitney r satisfont la relation de
récurrence
An,m,r (x) = (mx − mx2 )A0n−1,m,r (x) + r + (mn − r)x An−1,m,r (x).
(8)
Démonstration. À partir de la relation de récurrence (6), nous obtenons
n
X
An,m,r (x) = Am,r (n, k)xk
k=0
n h
X i
(km + r)Am,r (n − 1, k)xk + m(n − (k − 1)) − r Am,r (n − 1, k − 1)xk .
=
k=0
En séparant les sommes, on obtient
n−1
X n−1
X
k−1
= mx kAm,r (n − 1, k)x +r Am,r (n − 1, k)xk
k=0 k=0
n−1
X n−1
X n−1
X
k 2 k−1
+mnx Am,r (n − 1, k)x − mx kAm,r (n − 1, k)x − rx Am,r (n − 1, k)xk .
k=0 k=0 k=0
En reconnaissant
n−1
X
A0n−1,m,r (x) = kAm,r (n − 1, k)xk−1 ,
k=0
et
n−1
X
An−1,m,r (x) = Am,r (n − 1, k)xk ,
k=0
nous obtenons finalement
An,m,r (x) = (mx − mx2 )A0n−1,m,r (x) + r + (mn − r)x An−1,m,r (x).
Ce qui achève la démonstration.
14