Irreducible and Connected Permutations
Irreducible and Connected Permutations
Irreducible and Connected Permutations
Martin Klazar∗
Abstract
A permutation π of [n] = {1, 2, . . . , n} is irreducible if π([m]) = [m]
for no m ∈ [n], m < n, and it is connected if for no interval I ⊂ [n],
2 ≤ |I| ≤ n − 1, the image π(I) is an interval. We review enumera-
tion of irreducible permutations and their appearances in mathemat-
ics. Then we enumerate connected permutations. Asymptotically,
there are n!/e2 of them and exactly (for n > 2) their number equals
2(−1)n+1 minus the coefficient of xn in the compositional inverse of
1!x + 2!x2 + · · ·. We show that their numbers are not P-recursive, are
congruent modulo high powers of 2 to 2(−1)n+1 , and are congruent
modulo 3 to −Cn−1 + (−1)n where Cn is the Catalan number.
1
(or even, in [29], connected) and were introduced and enumerated by Comtet
[9]. Then they appeared in several contexts which we review in Section 2. The
notion of connected permutations seems almost new—Albert [1] calls them
absolutely irreducible permutations but considers them only in the restricted
context of (2, 1, 3)-free permutations. What are the numbers copn ? This was
the starting point for the present article. We shall see that the numerical
answer is again hidden in Comtet’s book [9].
In the rest of this section we give further definitions. In Section 2, be-
sides giving some references for the appearances of irreducible permutations,
in Proposition 2.1 and Theorem 2.2 we review their enumeration (in fact,
we need it for the enumeration of connected permutations). In Proposi-
tion 3.1 we characterize connected permutations by means of the permu-
tation containment and in Proposition 3.4 and Theorem 3.5 we enumer-
ate them exactly. Their numbers copn provide a combinatorial interpre-
tation for the coefficients of the compositional inverse of 1!x + 2!x2 + · · ·.
In Proposition 4.2 we present a graph sieve that is needed to prove the
asymptotics copn = (e−2 + O(n−1 ))n! of Theorem 4.3. Theorem 5.2 gives
a general criterion for non-P-recursiveness of super-exponential sequences
whose ogf’s satisfy certain first order differential equations. It implies that
(cop)n≥1 and (ipn )n≥1 are not P-recursive. In Corollaries 6.3 and 6.5 we
prove, for n > 2, the congruences copn ≡ 2(−1)n+1 mod 2d(n−1)/2e and
copn ≡ − n1 2n−2 n−1
+ (−1)n mod 3, respectively.
The set of n! permutations of [n] is denoted Sn . An interval {a, a +
1, . . . , b} is denoted [a, b], so [1, n] = [n]. For π ∈ Sn the reverted permutation
σ = π ∈ Sn is defined by σ(i) = π(n + 1 − i). With the exception of (1, 2) and
(2, 1), every connected permutation π is irreducible and so is π. However,
if π is disconnected, then π or π or both may be still irreducible—consider,
e.g., π = (5, 4, 2, 1, 6, 3) that is disconnected but π and π are irreducible.
Obviously, the number of π ∈ Sn such that π is irreducible equals ipn as well.
We denote the identical permutation (1, 2, . . . , n) as ιn . Thus ιn = (n, n−
1, . . . , 1). The substitution of σ1 ∈ Sn1 , σ2 ∈ Sn2 , . . . , σr ∈ Snr in σ ∈ Sr is
the permutation π = σ(σ1 , σ2 , . . . , σr ) ∈ Sn1 +n2 +···+nr given by
2
disjoint intervals Ii = [n1 + n2 + · · · + ni−1 + 1, n1 + · · · + ni ], i = 1, 2, . . . , r,
is the interval partition associated with σ(σ1 , σ2 , . . . , σr ). For example, if
σ = (2, 3, 1), σ1 = (4, 2, 3, 1), σ2 = (1), and σ3 = (1, 5, 4, 2, 3), then
and the associated interval partition is [1, 4], [5, 5], and [6, 10]. It is clear that
ι1 (σ) = σ(ι1 , ι1 , . . . , ι1 ) = σ for every permutation σ.
We say that two injections f : X → N and g : Y → N, where X and
Y are finite subsets of N of the same cardinality, are equivalent iff, with
u : X → Y and v : g(Y ) → f (X) being the unique increasing bijections,
for every x ∈ X we have f (x) = v(g(u(x))). For example, the f given by
f (3) = 2, f (1) = 8, and f (100) = 7 is equivalent to the permutation (3, 1, 2).
Every injection from a finite set X ⊂ N, |X| = n, to N is equivalent to a
unique permutation π ∈ Sn . If π ∈ Sn and X ⊂ [n] with |X| = m, we say
that the σ ∈ Sm equivalent with the restricted mapping π : X → [n] is the
restriction of π (to X). We say that a permutation σ is contained in another
permutation π, and write σ ≺ π, if σ is a restriction of π. For example,
(3, 1, 2) ≺ (6, 7, 2, 8, 5, 4, 3, 1) but ι4 6≺ (6, 7, 2, 8, 5, 4, 3, 1). For a permutation
π we set Forb(π) = {σ : π 6≺ σ}. This is an example of a hereditary (or
closed) permutation class X, which is a set of permutations with the property
that σ ≺ π ∈ X always implies σ ∈ X. A set of permutations X is closed
under substitutions if σ(σ1 , σ2 , . . . , σr ) ∈ X whenever all σ, σ1 , . . . , σr are in
X.
If π ∈ Sn and I ⊂ [n] is an interval such that π(I) is an interval, the
contraction of π on I produces the permutation σ ∈ Sn−|I|+1 defined as
the restriction of π to ([n]\I) ∪ {i}, where i ∈ I is arbitrary (σ does not
depend on the choice of i). If I = {I1 , I2 , . . . , Ir } are mutually disjoint
subintervals of [n] such that every π(Ii ) is an interval, the contraction of π on
I is defined as the restriction of π to ([n]\(I1 ∪ I2 ∪ . . . ∪ Ir )) ∪ {i1 , i2 , . . . , ir },
where ij ∈ Ij are arbitrary. Note that if π = σ(σ1 , σ2 , . . . , σr ) ∈ Sn and
I = {I1 < I2 < . . . < Ir } is the associated interval partition of [n], then σ is
the contraction of π on I and every σi is the restriction of π to Ii .
For a power series F ∈ C[[x]], the coefficient at xn is denoted [xn ]F .
Recall that if F ∈ C[[x]] is such that F = a1 x + a2 x2 + · · · with a1 6= 0, then
there exists a unique G ∈ C[[x]] of the same form, the compositional inverse
G = F h−1i of F , such that F (G) = G(F ) = x. By the Lagrange inversion
3
formula (see [35, Theorem 5.4.2]), its coefficients satisfy
!n
n h−1i 1 x
[x ]F = [xn−1 ] .
n F (x)
2 Irreducible permutations
The results in Proposition 2.1 and Theorem 2.2 are well known. We state and
prove them for completeness because we need them later. We give Proposi-
tion 2.1 also for comparison with the less straightforward Proposition 3.4.
Irreducible permutations were introduced by Comtet [9, p. 262] (he called
them indecomposable permutations) who in [8] derived the asymptotic series
for their numbers ipn (see also [9, p. 295]); it begins ipn = n!(1 − 2n−1 −
(n(n − 1))−1 − 4(n(n − 1)(n − 2))−1 + O(n−4 )). The sequence starts
n 1 2 3 4 5 6 7 8 9 10
ipn 1 1 3 13 71 461 3447 29093 273343 2829325
4
i ∈ [n]; κ arises by permuting λ by π. The interval exchange transform
T = T (π, λ) is the permutation of [0, 1) which sends x ∈ Ii to T (x) =
x − |I1 | − · · · − |Ii−1 | + |J1 | + · · · + |Jπ(i)−1 |. Thus Ii , sent by π to Jπ(i) , carries
with itself the point x to its new place T (x). Keane [17] proved that if π is
irreducible and λ is irrational (this means that the lengths |Ii | are linearly
independent over Q), then the orbit Ox = {T k (x) : k ∈ Z} of every point x is
dense in [0, 1). In 1979 he conjectured that for every irreducible π and almost
every λ (in the sense of the probabilistic Lebesgue measure on the set of all
λ’s) every orbit Ox is uniformly distributed in [0, 1). This conjecture was
proved independently by Masur [27] and Veech [36]. For further properties
and applications of interval exchange transforms associated with irreducible
permutations, see de Oliveira and Gutierrez [10], Chaves and Noguiera [7],
Kontsevich and Zorich [23], Rauzy [32], and Vuillon [37].
Interestingly, there is a link between irreducible permutations and the
Prime number theorem. The PNT says that π(x), the number of primes not
exceeding x, satisfies π(x) = x(1 + o(1))/ log x. In 1808, Legendre made a
more precise but incorrect conjecture that π(x) is roughly x/(log x−1.08366).
Panaitopol [30] pointed out that for every r ∈ N,
x
π(x) = −n
x − kr (1 + o(1)) log−r x
Pr−1
log x − 1 − n=1 kn log
where, in fact, kn = ipn+1 .
π = ιr (σ1 , σ2 , . . . , σr ) = ιs (ρ1 , ρ2 , . . . , ρs ) ∈ Sn
where all σi and ρi are irreducible. Let the associated interval partitions
I1 < I2 < . . . < Ir and J1 < J2 < . . . < Js of [n] be distinct. Then there is a
5
k ≥ 1 such that I1 = J1 , I2 = J2 , . . . , Ik−1 = Jk−1 , and Ik 6= Jk . So Ik = [a, b]
and Jk = [a, c] with b 6= c. If b < c, ρk ([b−a+1]) = σk ([b−a+1]) = [b−a+1]
and ρk is reducible, which is a contradiction. Similarly, b > c contradicts the
irreducibility of σk . Hence we must have r = s, I1 = J1 , . . . , Ir = Jr , and
σ1 = ρ1 , . . . , σr = ρr . The uniqueness is proved. 2
ϕ(x) 1
I(x) = =1−
1 + ϕ(x) 1 + ϕ(x)
and thus ipn = −[xn ](1 + ϕ(x))−1 for every n ∈ N.
I(x)r = (1 −
P
Proof. It follows from Proposition 2.1 that 1 + ϕ(x) = r≥0
I(x))−1 . Solving this for I(x) we get the stated formula. 2
Thus we have the recurrence ipn = [xn ]I(x) = [xn ]ϕ(x)(1 − I(x)) = n! −
Pn−1
k=1 (n − k)! · ipk .
3 Connected permutations
The following result was our motivation to introduce connected permutations.
τ ≺ π = σ(σ1 , σ2 , . . . , σr ) ∈ Sn
6
Let τ be disconnected. Then t ≥ 3 and τ ([i, j]) is an interval for some i, j
with 1 ≤ j − i ≤ t − 2. Let σ ∈ St−j+i be the contraction of τ on [i, j] and
ρ be the restriction of τ to [i, j]. Then τ = σ(ι1 , . . . , ι1 , ρ, ι1 , . . . , ι1 ) with ρ
on the i-th place. But none of σ, ι1 , and ρ contains τ because all are shorter
than τ . So Forb(τ ) is not closed under substitutions. 2
Lemma 3.3 If π ∈ Sn and I, J are intervals in [n] such that I 6= [n], J 6= [n],
I ∪ J = [n], and both π(I) and π(J) are intervals, then π is reducible or π is
reducible.
Proof. It follows from the assumptions that 1 ∈ I and n ∈ J or vice versa.
Let us assume that 1 ∈ I. By the same argument, 1 ∈ π(I) and n ∈ π(J)
or vice versa. In the former case π is reducible, and in the latter case π is
reducible. 2
7
Proof. It is clear that the sets (i), (ii), and (iii) are mutually disjoint, as
well as the sets (i) and (iv). We show that every π ∈ Sn of the form (iv) is
irreducible. Suppose that π = σ(σ1 , σ2 , . . . , σr ) ∈ Sn as in (iv) and π([a]) =
[a] for some 1 ≤ a < n. Let I1 < I2 < . . . < Ir be the interval partition of [n]
associated with the substitution and I1 , I2 , . . . , Ik , 1 ≤ k ≤ r, be all intervals
intersected by [a]. It follows that σ([k]) = [k], σ([k + 1, r]) = [k + 1, r], and if
k = r then σ([r − 1]) = [r − 1]. For any k we have a contradiction with the
connectedness of σ (r > 2). Thus the sets in (iv) and (ii) are disjoint, and
similarly for (iv) and (iii).
To prove the second claim, we take an arbitrary π ∈ Sn , n ≥ 2, such that
π and π are irreducible and express π in the form (iv). We define a maximal
interval I as a subinterval I ⊂ [n] such that 1 ≤ |I| ≤ n − 1, π(I) is an
interval, and I is maximal to inclusion with respect to these properties. It
follows that maximal intervals are pairwise disjoint. Indeed, let I and J be
distinct maximal intervals with I ∩J 6= ∅. If I ∪J 6= [n] then I ∪J contradicts
the maximality of I or of J because π(I ∪ J) is interval. If I ∪ J = [n],
Lemma 3.3 shows that we have a contradiction with the irreducibility of π
and of π. Hence we have an interval partition I1 < I2 < . . . < Ir of [n] into
maximal intervals. We have r ≥ 2 but r = 2 is impossible by Lemma 3.3.
Thus r ≥ 3. We define σ ∈ Sr as the contraction of π on {I1 < I2 < . . . < Ir }
and σi , 1 ≤ i ≤ r, as the restriction of π to Ii . Then π = σ(σ1 , σ2 , . . . , σr ).
Suppose that for some interval I ⊂ [r], 2 ≤ |I| ≤ r − 1, σ(I) is an interval.
S
It follows that π( i∈I Ii ) is an interval, which contradicts the maximality of
each of the intervals Ii , i ∈ I. So σ is connected and r = 3 is impossible
because no permutation in S3 is connected.
To prove the last claim, we assume that
π = σ(σ1 , σ2 , . . . , σr ) = ρ(ρ1 , ρ2 , . . . , ρs ) ∈ Sn
where r, s ≥ 4 and both σ and ρ are connected. Let I1 < I2 < . . . < Ir
and J1 < J2 < . . . < Js be the associated interval partitions of [n]. If they
are distinct, we apply Lemma 3.2. By Lemma 3.3, the cases (i) and (ii)
cannot occur (we know from the proof of the first claim that π and π are
irreducible). Suppose that the case (iii) occurs and Ii intersects the intervals
Jk , Jk+1 , . . . , Jl where 1 ≤ l − k ≤ s − 2. Since ρ is connected, there are
j ∈ [s]\[k, l] and p, q ∈ [k, l] such that ρ(p) < ρ(j) < ρ(q). But then π(Jp ) <
π(Jj ) < π(Jq ) which implies min π(Ii ) < π(Jj ) < max π(Ii ), and thus π(Ii )
is not an interval. On the other hand, π(Ii ) must be an interval because Ii
8
is one of the intervals associated with the substitution π = σ(σ1 , σ2 , . . . , σr ).
This contradiction shows that the case (iii) of Lemma 3.3 cannot occur. By
an analogous argument, the case (iv) cannot occur as well. Thus the two
interval partitions must be equal and we have r = s, I1 = J1 , . . . , Ir = Jr ,
σ1 = ρ1 , . . . , σr = ρr , and σ = ρ. The uniqueness is proved. 2
Theorem 3.5 Let C(x) = n≥1 copn xn = x + 2x2 + 2x4 + · · · be the ogf of
P
x2
!
C(x) = 2 x + x − 2
− ϕ(x)h−1i
1+x
and thus cop1 = 1, cop2 = 2 and copn = −[xn ]ϕ(x)h−1i + (−1)n+1 · 2 for every
n > 2.
Proof. By Proposition 2.1 and Theorem 2.2, the ogf of the numbers of
reducible permutations π equals
X
r I(x)2 ϕ(x)2
I(x) = =
r≥2 1 − I(x) 1 + ϕ(x)
2ϕ(x)2
ϕ(x) = x + + (C(x) − x − 2x2 ) ◦ ϕ(x)
1 + ϕ(x)
where on the right the first x counts the set (i), the second summand counts
the sets (ii) and (iii), and the last composition counts the set (iv). Substi-
tuting for x the inverse series ϕ(x)h−1i and solving the result for C(x), we
get the stated formula. 2
9
n 1 2 3 4 5 6 7 8 9 10
Comn 1 −2 2 −4 −4 −48 −336 −2928 −28144 −298528
copn 1 2 0 2 6 46 338 2926 28146 298526
The sequence (Comn )n≥1 (normalized by omitting the minus signs) is in [34]
listed as A059372.
We remark that the notion of connected permutations has counterpart
in the class of set partitions. A set partition P of [n] is called connected
(see Bender, Odlyzko and Richmond [5], Bender and Richmond [6], Lehner
[25], and Klazar [21]) iff there is no interval I ⊂ [n], 1 ≤ |I| ≤ n − 1, such
that every block of P lies either completely inside I or completely outside I.
Similarly to the relation of C(x) and ϕ(x) in Theorem 3.5, the ogf of numbers
of connected partitions can be expressed in terms of the compositional inverse
of the total ogf of Bell numbers.
X⊂V v6∈X⊂V
X independent X independent
10
Proof. By the product formula, we may assume that F is a tree. We proceed
by induction on |V (F )|. For |V (F )| ≤ 2 the statement holds: α± (K1 ) = 0
and α± (K2 ) = −1. Let |V (F )| ≥ 3, u be a leaf of F , v the neighbor of u,
and u1 , . . . , uk , k ≥ 1, be the neighbors of v distinct from u. Let F 0 = F − u
and Fi be the component of F − v containing ui . To obtain α± (F ), we split
F in ({u}, ∅) = K1 and F 0 and use the product formula. But since u and
F 0 are connected by the edge {u, v}, we must subtract the choices of the
independent sets X1 in ({u}, ∅) and X2 in F 0 such that u ∈ X1 and v ∈ X2 .
The contribution of the only X1 is −1 and the contribution of the X2 ’s is
− ki=1 α± (Fi , ui ). Thus
Q
k k
!
± ± ± 0 ±
α± (Fi , ui ).
Y Y
α (F ) = α (K1 )α (F ) − (−1) · − α (Fi , ui ) = −
i=1 i=1
±
If Fi = K1 then α (Fi , ui ) = 1. If Fi has more than one vertex then, denoting
the components of Fi − ui by G1 , . . . , Gl , we have α± (Fi , ui ) = lj=1 α± (Gj )
Q
11
Proof. By Rényi’s 0-1 principle ([13, Theorem I.1] and [26, Problem 2.6]),
it suffices to prove the inequality only when every Pr[Ai ] is 0 or 1. Without
loss of generality we assume that every Pr[Ai ] is 1. Then we have to prove,
denoting the sum of (−1)|X| over all dependent X ⊂ [n] by S, that |S| ≤ |E|.
Since the sum of (−1)|X| over all subsets X ⊂ [n] is zero, we have
0 = α± (F ) + S
and it suffices to prove |α± (F )| ≤ |E|. This is by Lemma 4.1 obviously true
if F has at least one edge. If F has no edge, it is also true because then
α± (F ) = 0 and |E| = 0. 2
12
k-set are equiprobable and mutually exclusive). Thus
!−1
n
Pr[AI ] = (n − k + 1)2 ·
X
Pr[Ek ] ≤ .
|I|=k
k
It follows that
(−1)|X| Pr[BX ]
X
Pr[E2 ] = Pr[B1 ∨ B2 ∨ . . . ∨ Bn−1 ] = −
∅6=X⊂[n−1]
where BX = i∈X Bi . Let P be the path with the vertex set [n − 1] and
V
the edges {i, i + 1}, i ∈ [n − 2]. We split the last sum in the sum over X
independent on P and the sum over X dependent on P . By Proposition 4.2
and the above calculations,
n−2
(−1)|X| Pr[BX ] ≤ Pr[AI ] = O(n−1 ).
X X X
Pr[Bi ∧ Bi+1 ] ≤
X⊂[n−1] i=1 |I|=3
X dependent
Thus
13
π({i, i + 1}) = Jj . The probability of a fixed restriction of π to a given
A ⊂ [n] is 1/(n(n − 1) . . . (n − |A| + 1)). Thus
k!2k
!
n−k
Pr[BX ] =
k n(n − 1) . . . (n − 2k + 1)
and
n/2 !2
n−k (−1)k+1 k!2k
+ O(n−1 ).
X
Pr[π is disconnected] =
k=1 k n(n − 1) . . . (n − 2k + 1)
Rearranging the summand, we rewrite the last sum as
n/2 k−1 n/2
(−2)k (−2)k
!
X Y k X
− · 1− =− · P (k, n).
k=1 k! i=0 n−i k=1 k!
For all k ≤ n/2, 0 ≤ P (k, n) < 1 and for 0 < k ≤ n1/4 , by standard estimates,
uniformly P (k, n) = 1 − k 2 /n + O(n−1 ). Hence the last sum equals
1/4
nX 1/4
(−2)k (1 + O(n−1 )) 1 nX k 2 (−2)k X (−2)k
− + · P (k, n)
k=1 k! n k=1 k! n1/4 <k≤n/2
k!
∞
(−2)k
+ O(n−1 ) + O(
X
2k /k!)
P
= k>n1/4
k=1 k!
= e−2 − 1 + O(n−1 )
and Pr[π is disconnected] = 1 − e−2 + O(n−1 ). Finally,
Pr[π is connected] = 1 − (1 − e−2 + O(n−1 )) = e−2 + O(n−1 )
and copn = (e−2 + O(n−1 )) · n!. 2
Theorems 3.5 and 4.3 give the asymptotics of Comn .
Corollary 4.4 For n → ∞,
∞
!h−1i
Comn = [xn ] n!xn = (−e−2 + O(n−1 )) · n!.
X
n=1
14
5 Non-P-recursiveness
A sequence of numbers (an )n≥0 is called P-recursive if it satisfies a linear
recurrence with polynomial coefficients. A power series is called D-finite
if it satisfies a linear differential equation with polynomial coefficients. A
sequence (an )n≥0 is P-recursive if and only if its ogf A(x) = n≥0 an xn is
P
differential equations
0 −2 2 −2 −1 −1 0 ψ2
I = −x I + (x + x )I − x and ψ = .
x − (1 + x)ψ
Proof. It follows from the recurrence for n! that ϕ(x) = n≥1 n!xn satisfies
P
In Klazar [20] we used the following method to show that (an )n≥0 is
not P-recursive. Suppose that the ogf A(x) is nonanalytic and satisfies a
first order differential equation A0 = R(x, A) where R is some expression.
Differentiating it and replacing A0 by R(x, A), we express the derivatives of
A as A(k) = Rk (x, A); R0 (x, A) = A and R1 (x, A) = R(x, A). Substituting
Rk (x, A) in the equation of D-finiteness
b0 A + b1 A0 + b2 A00 + · · · + bs A(s) = 0,
15
To state the result of [20] precisely, we remind the reader that a power se-
ries R(x, y) ∈ C[[x, y]] is analytic if it absolutely converges in a neighborhood
of the origin and that R(x, y) ∈ C((x, y)) is an analytic Laurent series if, for
some k ∈ N, (xy)k R(x, y) ∈ C[[x, y]] is analytic. Theorem 1 of [20] says that
if A ∈ C[[x]] is nonanalytic, R(x, y) ∈ C((x, y)) is analytic, A0 = R(x, A),
and R contains at least one monomial axi y j , a 6= 0, with j < 0, then A is not
D-finite. This result applies directly neither to I(x) nor ψ(x) (see Proposi-
tion 5.1) because in the case of I(x) the last condition on R is not satisfied
and in the case of ψ(x) the right hand side R even cannot be expanded as a
Laurent series.
However, the substitution x − (1 + x)ψ(x) = θ(x) turns the second dif-
ferential equation of Proposition 5.1 to
x2 1 1 + 2x
θ0 = − · + .
1+x θ 1+x
Now all conditions are satisfied (ϕ(x) is clearly nonanalytic which implies that
ψ(x) and θ(x) are nonanalytic) and thus θ(x) is not D-finite by Theorem 1
of [20]. The dependence of ψ(x) and C(x) = n≥1 copn xn on θ(x) and the
P
fact that D-finite power series form a C(x)-algebra ([35, Theorem ?]) show
that ψ(x) and C(x) are not D-finite too. We conclude that the sequences
(Comn )n≥0 and (copn )n≥0 are not P-recursive.
We use this opportunity to complement Theorem 1 of [20] in which R ∈
C((x, y)) by the following theorem which treats the case R ∈ C(x, y). Neither
of the theorems subsumes the other because not every rational function in x
and y can be represented by an element of C((x, y)) (as we have seen) and,
of course, not every Laurent series sums up to a rational function. However,
the next theorem seems to be more useful because in both examples in [20]
and both examples here the right hand side R(x, y) is, in fact, a rational
function.
16
Proof. The first claim is clear. If degy Q = 0 and r = degy P ≥ 2 then
A0 = a0 +a1 A+· · ·+ar Ar where ai ∈ C(x), r ≥ 2, and ar 6= 0. Differentiation
by x gives
A(k) = Rk (x, A) = a0,k + a1,k A + · · · + akr−k+1,k Akr−k+1
where ai,j ∈ C(x) and
akr−k+1,k = r(2r − 1)(3r − 2) . . . ((k − 1)r − k + 2)akr 6= 0.
Thus Rk (x, y) ∈ C(x)[y] have y-degrees kr − k + 1, k = 0, 1, 2, . . ., which is
for r ≥ 2 a strictly increasing sequence. Therefore R0 , R1 , R2 , . . . are linearly
independent over C(x) and, by the above discussion, A is not D-finite.
In the remaining case degy Q ≥ 1. Differentiation of A0 = R(x, A) =
P (x, A)/Q(x, A) by x gives A(k) = Rk (x, A) where Rk (x, y) ∈ C(x, y). For
example,
(Px + Py R1 )Q − P (Qx + Qy R1 )
R2 =
Q2
Px Q − P Qx P (Py Q − P Qy )
= + .
Q2 Q3
Let α, Q(x, α) = 0, be a pole of R1 (x, y) of order ordα (R1 ) = ordα (P/Q) =
−ordα (Q) = l ≥ 1. We have ordα ((Px Q−P Qx )Q−2 ) ≤ 2l and ordα (P (Py Q−
P Qy )Q−3 ) = 3l + ordα (Py Q − P Qy ) = 2l + 1 since ordα (P ) = 0, ordα (Py Q) ≤
−l, and ordα (P Qy ) = −l + 1. So ordα (R2 ) = 2l + 1. In general, the same
argument shows that ordα (Rk+1 ) = 2 · ordα (Rk ) + 1. Hence ordα (Rk ) =
2k−1 l + 2k−1 − 1, k = 1, 2, . . .. This is a strictly increasing sequence and we
conclude again, since R0 , R1 , R2 , . . . are linearly independent over C(x), that
A is not D-finite. 2
Proposition 5.1 and Theorem 5.2 give the following corollary.
Corollary 5.3 The sequences (ipn )n≥1 , (Comn )n≥1 , and (copn )n≥1 are not
P-recursive.
6 Congruences
By the Lagrange inversion formula (recalled at the end of Section 1),
n
k≥0
17
We use this representation to derive modular properties of the numbers
Comn . For a prime p, let ordp (n) denote the largest m ∈ N0 such that
pm divides n. It is an interesting fact that the Comtet numbers are divisible
by high powers of 2:
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ord2 (Comn ) 0 1 1 2 2 4 4 4 4 5 5 15 13 12 12
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
8 8 9 9 10 10 12 12 14 14 15 15 17 17 22
In Theorem 6.2 we give a lower bound on ord2 (Comn ) which is tight for
infinitely many n and we completely characterize the values of n for which
the equality is attained.
Recall some properties of ordp (·): ordp (ab) = ordp (a) + ordp (b), ordp (a +
b) ≥ min(ordp (a), ordp (a)), and ordp (a + b) = min(ordp (a), ordp (b)) whenever
ordp (a) 6= ordp (b).
18
Theorem 6.2 Let n ∈ N and m = bn/2c. Then
n−1
ord2 (Comn ) ≥
2
and the equality holds if and only if 3m
m
is odd. In other words, the equality
holds if and only if the binary expansion of m has no two consecutive unit
digits.
k≥0 k≥0
By Lemma 6.1, ord2 ((c + 1)!) ≥ c/2 for every c ∈ N. Hence, for every k ≥ 0
and n ∈ N,
k n−1
ord2 (bk ) ≥ and ord2 (n · Comn ) ≥ .
2 2
In particular, for odd n we have ord2 (Comn ) = ord2 (n · Comn ) ≥ (n − 1)/2.
We claim that, more precisely,
= k/2
. . . for even k
ord2 (bk ) = (k + 1)/2 . . . for k ≡ 1 mod 4
> (k + 1)/2 . . . for k ≡ 3 mod 4.
For the proof we look more closely at the sum for bk . Let k be even. Then
the sum has exactly one summand with ord2 equal to k/2, namely that with
c1 = c2 = . . . = ck/2 = 2 (by Lemma 6.1, ord2 ((c + 1)!) = c/2 only if c = 2),
and the other summands have ord2 bigger than k/2. Hence ord2 (bk ) = k/2.
Let k be odd. Then each summand has an odd number of odd ci ’s. The
19
summands t with three and more odd ci ’s satisfy ord2 (t) ≥ (k + 3)/2 (each
odd ci contributes 1/2 to k/2). The same is true if t has only one odd ci but
that ci is not 1 (by Lemma 6.1, ord2 ((c + 1)!) ≥ (c + 3)/2 for odd c > 1), or
if some even ci is not 2 (Lemma 6.1). The remaining summands t, in which
ci = 2 with multiplicity (k − 1)/2 and once ci = 1, satisfy ord2 (t) = (k + 1)/2.
We see that, for odd k, ord2 (bk ) = (k + 1)/2 iff the number of the remaining
summands is odd. This number equals (k − 1)/2 + 1 = (k + 1)/2. So
ord2 (bk ) = (k + 1)/2 iff k is of the form 4l + 1.
Let n = 2m + 1 be odd. If s is a summand of the above sum for n · Comn ,
then ord2 (s) = (n − 1)/2 iff all ki in s are even; other summands t have
ord2 (t) > (n − 1)/2. It follows that ord2 (Comn ) = (n − 1)/2 iff the number
of the former summands s is odd. This number equals
n ! !
1 X n+r−1 3m
n−1 2r n−1 n−1
x2r =
X
[x ] x = [x ] 2 n
= [x ] .
r≥0 (1 − x ) r≥0 r m
Let n = 2m be even. We know that ord2 (bk ) = k/2 for even k and
ord2 (bk ) ≥ (k + 1)/2 for odd k. In the sum for n · Comn , every composition
k1 + k2 + · · · + kn = n − 1 of n − 1 has an odd number of odd parts. For any
t-tuple l1 , l2 , . . . , lt , where t and all li are odd and l1 + · · · + lt ≤ n − 1, we let
S(l1 , l2 , . . . , lt ) denote the sum of those bk1 bk2 . . . bkn with k1 + k2 + · · · + kn =
n − 1 in which ki = li , 1 ≤ i ≤ t, and ki is even for i > t. It follows that
!
X n
n · Comn = S(l1 , l2 , . . . , lt )
t
In the last sum still many summands have ord2 bigger than n/2: if l ≡ 3
mod 4 then ord(S(l)) > n/2. On the other hand, if l ≡ 1 mod 4 then each
summand bl bk2 . . . bkn in S(l) has ord2 (bl bk2 . . . bkn ) = n/2. We conclude that
20
ord2 (Comn ) = n/2 iff the number c(n) of compositions of n − 1 into n parts,
where the first part is ≡ 1 mod 4 and the remaining n − 1 parts are even
(zero parts are allowed), is odd. We have
x 1 x 1
c(n) = [xn−1 ] 4
· 2 n−1
= [xn−1 ] ·
1 − x (1 − x ) 1 + x (1 − x2 )n
2
x 1 x
≡ [xn−1 ] 2
· 2 n
= [xn−1 ] mod 2
1 − x (1 − x ) (1 − x2 )n+1
! !
3m − 1 3m 3m − 1
= ≡ mod 2
m−1 m m−1
!
3m
= .
m
It was noted by Kummer in [24], see also Singmaster [33], that ordp ( a+b
b
)
equals to the number of carries required when adding a and b in the p-ary
notation. Applying this for p = 2, a = m, and b = 2m, we get the stated
criterion. 2
Let !
1 2n
Cn =
n+1 n
be the nth Catalan number.
21
with ak (x) ∈ Z[[x]]. Thus
1
(−1)k (2!x + 3!x2 + · · ·)k = + 3 (−1)k ak (x)
X X
k≥0 1 + 2x k≥0
1
= + 3b(x)
1 + 2x
with b(x) ∈ Z[[x]]. Let m = ord3 (n). Since ord3 (k!) ≤ k − 1 for every k ∈ N
(Lemma 6.1), we have
n
ord3 3k k
≥ m + 1 for k = 1, 2, . . . , n.
(−2)n−1 2n − 2
! !
n 1 2n − 2
m
· Comn ≡ m
≡ m mod 3.
3 3 n−1 3 n−1
References
[1] M. H. Albert, The fine structure of 321-avoiding permutations,
Archiv:math.CO/0212163
22
[2] M. Aguiar and F. Sottile, Structure of the Malvenuto–Reutenauer
Hopf algebra of permutations, Archiv:math.CO/0203282.
n!tn ,
P
[8] L. Comtet, Sur les coefficients de l’inverse de la série formelle
C. R. Acad. Sci., Paris, Sér. A, 275 (1972), 569–572.
23
[14] I. M. Gessel and R. P. Stanley, Algebraic enumeration. In: R. L.
Graham, M. Grötschel and L. Lovász (ed.), Handbook of Combinatorics,
Volume II, North-Holland, Amsterdam, 1995; pp. 1021–1061.
24
[26] L. Lovász, Combinatorial Problems and Exercises, Akadémiai Kiadó,
Budapest, 1993.
25