Séminaire Lotharingien de Combinatoire 64 (2011), Article B64c

THE NUMBER OF RIBBON SCHUR FUNCTIONS

MARTIN RUBEY

Abstract. We present formulas for the number of distinct ribbon Schur functions of a given size, and of a given size and height.

1. Introduction

An important basis for the space of homogeneous symmetric functions of degree n is the set of Schur functions s_{λ}, indexed by partitions λ of n. A larger set of homogeneous symmetric functions of degree n is the set of skew Schur functions s_{λ/μ}. These are indexed by skew shapes λ/μ of size n, i.e., pairs of partitions (λ, μ) such that

• λ = (λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{k} > 0) is a partition of n + m,

• μ = (μ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{ℓ} > 0) is a partition of m,

• k, the number of parts of λ, is strictly larger than ℓ, the number of parts of μ,

• and μ_{i} ≤ λ_{i} for i ≤ ℓ. When μ is the empty partition, i.e., ℓ = 0, s_{λ/μ} = s_{λ}. Since the set of Schur functions is a basis, there must be relations between skew Schur functions. Equalities between skew functions have been studied by Stephanie van Willigenburg, Peter McNamara, Vic Reiner and Kristin Shaw [8, 5, 4] and, in the multiplicity-free case, by Christian Gutschwager [2]. However, so far only partial results and a conjecture are available.

The situation is very different for the subset of ribbon Schur functions, that are indexed by ribbons, also known as rim hooks or border strips. These are skew shapes that satisfy λ_{i+1} = μ_{i} + 1 for 1 ≤ i < k, where we set μ_{i} = 0 for i > ℓ. Here are the ribbons of size 4:

It can be shown that the space of homogeneous symmetric functions of degree n is also generated by the set of ribbon Schur functions of size n. For these functions, Louis J. Billera, Hugh Thomas, and Stephanie van Willigenburg [1] give a criterion for deciding when they are equal. In this article we use this criterion to count the number of distinct ribbon Schur functions of a given size, see Theorem 3.4. Furthermore, letting the height of a ribbon Schur function be the number of parts of λ minus one, we also find the generating function for the number of distinct ribbon Schur functions of a given size by height, see Theorem 4.2.

Key words and phrases. ribbon Schur functions, compositions, Dirichlet series.

Note that ribbons λ/μ of size n and height m − 1 can be identified with compositions α of size n and length m by setting α_{i} = λ_{i} − μ_{i} for all i. Two compositions α and β are called equivalent, denoted α ∼ β, if and only if the corresponding ribbon Schur functions are equal.

In the following section we recall a binary operation on compositions from [1], that makes the set of compositions into a monoid with (almost) unique factorisation. One of the main theorems of [1] shows that equivalence of compositions is easily determined given their factorisations.

In Section 3 we present a relatively appealing formula for the number of distinct ribbon Schur functions of a given size, while in Section 4 we exhibit a (not nearly as beautiful) formula for the number of distinct ribbon Schur functions of a given size and height. For more information on symmetric functions we refer to Chapter 7 of Enumerative Combinatorics 2 [7].

2. Composition of Compositions and equality of ribbon Schur functions

In this section we collect the definitions and results from [1] that are relevant for our approach. As mentioned before, the basic objects we will be working with are compositions:

Definition 2.1. A composition α of a positive integer m, denoted α ⊨ m, is a list of positive integers (a_{1}, a_{2}, …, a_{k}) such that a_{1} + a_{2} + ⋯ + a_{k} = m. We refer to each of the a_{i} as components, and say that α has length l(α) = k and size |α| = m.

Definition 2.2. Let α = (a_{1}, a_{2}, …, a_{k}) ⊨ m and β = (b_{1}, b_{2}, …, b_{ℓ}) ⊨ n. Then the concatenation of α and β is the composition

α · β = (a_{1}, …, a_{k}, b_{1}, …, b_{ℓ}) ⊨ n + m.

Their near concatenation is

α ⊙ β = (a_{1}, …, a_{k} + b_{1}, …, b_{ℓ}) ⊨ n + m.

Writing

α^{⊙n} = \underbrace{α ⊙ α ⊙ ⋯ ⊙ α}_{n}

we define the composition of α and β as

α ∘ β = β^{⊙a_{1}} · β^{⊙a_{2}} ⋯ β^{⊙a_{k}} ⊨ mn.

The composition α = (a_{1}, a_{2}, …, a_{k}) is symmetric if it coincides with its reversal α^{∗} = (a_{k}, a_{k−1}, …, a_{1}).

The following theorem shows that composition of compositions is a very well behaved operation indeed:

Theorem 2.3 ([1], Propositions 3.3, 3.7, 3.8 and 3.9). The set of compositions together with the operation ∘ is a monoid, i.e., ∘ is associative and has neutral element (1). Furthermore, |α ∘ β| = |α| |β| and l(α ∘ β) = l(α) + |α| (l(β) − 1). Finally, (α ∘ β)^{∗} = α^{∗} ∘ β^{∗}.

Note that composition of compositions is not commutative. For example, (1, 1) ∘ (2) = (2)^{⊙1} · (2)^{⊙1} = (2, 2), but (2) ∘ (1, 1) = (1, 1)^{⊙2} = (1, 1) ⊙ (1, 1) = (1, 2, 1).

Definition 2.4 ([1], Definition 3.5). If a composition α is written in the form α_{1} ∘ α_{2} ∘ ⋯ ∘ α_{k} then we call this a factorisation of α. A factorisation α = β ∘ γ is called trivial if any of the following conditions are satisfied:

(1) one of β and γ is the composition 1,

(2) the compositions β and γ both have length 1,

(3) the compositions β and γ both have all components equal to 1.

A factorisation α_{1} ∘ α_{2} ∘ ⋯ ∘ α_{k} is called irreducible if no α_{i} ∘ α_{i+1} is a trivial factorisation, and each α_{i} admits only trivial factorisations. We call a composition α irreducible, if it has not length 1, not all of its components are equal to 1 and it admits only trivial factorisations.

We remark that irreducible compositions are not defined in [1]. In particular, the notion does not coincide with the notion of irreducible factors.

Theorem 2.5 ([1], Theorem 3.6). The irreducible factorisation of any composition is unique.

It is not surprising that such a theorem is very useful to enumerate the underlying objects. For experimentation it was also of great help to have a relatively efficient test for irreducibility, which is exhibited in Definition 4.11 and Lemma 4.15 of [1].^{1}

Finally, equivalence of compositions and therefore equality of ribbon Schur functions is reduced to factorisation by the following theorem. Note that it was well known before that reversal of compositions yields the same ribbon Schur functions, see for example Exercise 7.56 in Enumerative Combinatorics 2 [7], which includes also the natural extension to skew Schur functions.

Theorem 2.6 ([1], Theorem 4.1). Two compositions β and γ satisfy β ∼ γ if and only if for some k, β = β_{1} ∘ β_{2} ∘ ⋯ ∘ β_{k} and γ = γ_{1} ∘ γ_{2} ∘ ⋯ ∘ γ_{k} where, for each i, either γ_{i} = β_{i} or γ_{i} = β_{i}^{∗}.

3. The number of ribbon Schur functions of a given size

Definition 3.1. We order the set of compositions of a given length lexicographically. Thus, let α = (a_{1}, a_{2}, …, a_{k}) and β = (b_{1}, b_{2}, …, b_{k}) be two compositions. Then α < β if and only if a_{s} < b_{s} for some s, such that a_{r} = b_{r} for all r < s. The composition α is lexicographic minimal if α ≤ α^{∗}.

In view of Theorem 2.5 and Theorem 2.6, we call a composition normalised, if all factors in its irreducible factorisation are lexicographic minimal.

1An implementation can be obtained from the author of the present article.

Thus, to determine the number of distinct ribbon Schur functions, it is sufficient to count normalised compositions. This is not hard to achieve using a suitable combinatorial decomposition. The validity of our decomposition hinges on the following lemma:

Lemma 3.2. Consider a composition α with irreducible factorisation α_{1}∘α_{2}∘⋯∘α_{k}. Then α is symmetric if and only if all α_{i} are symmetric for i ∈ {1, …, k}.

If α is asymmetric, then there is an ℓ ∈ {1, …, k} such that α_{ℓ} is asymmetric, and α_{i} is symmetric for all i > ℓ. In this situation, α < α^{∗} if and only if α_{ℓ} < α_{ℓ}^{∗}.

Proof. By the last statement of Theorem 2.3, an irreducible factorisation of the reversal of α is α^{∗} = α_{1}^{∗} ∘ α_{2}^{∗} ∘ ⋯ ∘ α_{k}^{∗}. Thus, by Theorem 2.5, if α = α^{∗}, all the factors α_{i} are symmetric. The reverse direction follows immediately from the last statement of Theorem 2.3.

Suppose now that α is asymmetric. We have to show that α < α^{∗} if and only if α_{ℓ} < α_{ℓ}^{∗}, where ℓ is maximal such that α_{ℓ} is asymmetric. Let us first prove for compositions β, γ and δ:

(1) β ∘ δ < γ ∘ δ if and only if β < γ, whenever l(β) = l(γ).

Indeed, if β = (b_{1}, …, b_{r}) < γ = (g_{1}, …, g_{r}), then there is an index j such that b_{j} < g_{j} and b_{i} = g_{i} for all i < j. Since β ∘ δ = δ^{⊙b_{1}} ⋯ δ^{⊙b_{r}} and γ ∘ δ = δ^{⊙g_{1}} ⋯ δ^{⊙g_{r}}, it suffices to compare δ^{⊙b_{j}} and δ^{⊙g_{j}}.

If δ = (d_{1}) has length 1, we have δ^{⊙b_{j}} = (b_{j}d_{1}) < (g_{j}d_{1}) = δ^{⊙g_{j}}. Let us now consider the case that δ = (d_{1}, …, d_{s}) with s ≥ 2. Then the component with index 1 + b_{j} (l(δ) − 1) of δ^{⊙b_{j}}, i.e., its last component, equals d_{s}. However, since b_{j} < g_{j}, the component of δ^{⊙g_{j}} with the same index is d_{s} + d_{1}, which is strictly greater than d_{s}. Hence β ∘ δ < γ ∘ δ. The converse follows by symmetry: given β ∘ δ < γ ∘ δ, assuming that β > γ leads to a contradiction by what we have just shown.

Next, we prove for compositions β, γ, δ and ϵ:

(2) β ∘ δ < γ ∘ ϵ if and only if δ < ϵ, whenever l(β) = l(γ), l(δ) = l(ϵ), |δ| = |ϵ| and δ ≠ ϵ.

Suppose that δ = (d_{1}, d_{2}, …, d_{r}) < ϵ = (e_{1}, e_{2}, …, e_{r}). It suffices to compare the first r−1 components of β ∘δ and γ ∘ϵ, which are d_{1}, d_{2}, …, d_{r−1} and e_{1}, e_{2}, …, e_{r−1}, respectively. Let j be minimal such that d_{j} < e_{j}. Since |δ| = |ϵ|, the two compositions cannot differ only in the last component, so j ≤ r−1, which implies β∘δ < γ∘ϵ. Again, the converse follows by symmetry.

To conclude the proof, we write α = β ∘ α_{ℓ} ∘ γ, where ℓ is maximal such that α_{ℓ} is asymmetric – if ℓ = 1 then β = (1), if ℓ = k then γ = (1). Thus, by the last statement of Theorem 2.3, α^{∗} = β^{∗} ∘ α_{ℓ}^{∗} ∘ γ. By Condition (1) α < α^{∗} if and only if β ∘ α_{ℓ} < β^{∗} ∘ α_{ℓ}^{∗}. By Condition (2), this is the case if and only if α_{ℓ} < α_{ℓ}^{∗}, as desired. □

In the following lemma we collect the facts we need about Dirichlet generating functions:

Lemma 3.3. Let A and B be sets of compositions, let A ·∪ B be their disjoint union and define A ∘ B := {α ∘ β : α ∈ A, β ∈ B}. For any set of compositions A, let A(s) = ∑_{α∈A} |α|^{−s} the associated Dirichlet generating function. Then

(A ·∪ B)(s) = A(s) + B(s) and
(A ∘ B)(s) = A(s)B(s).

The latter equality is equivalent to the statement, that the coefficient of n^{−s} in (A ∘ B)(s) is a_{n} ∗ b_{n}, where a_{n} and b_{n} are the coefficients of n^{−s} in A(s) and B(s), respectively, and a_{n} ∗ b_{n} denotes the Dirichlet convolution ∑_{d|n} a_{d}b_{n/d}.

Remark. A full-fledged combinatorial theory of Dirichlet series within the theory of combinatorial species was developed by Manuel Maia and Miguel Méndez [3]. Although the proofs below are written in the spirit of that theory, they are quite elementary.

Theorem 3.4. The number of normalised compositions of size n is

2 · 2^{n−1} ∗ 2^{⌊ \frac{n}{2} ⌋} ∗ (2^{n−1} + 2^{⌊ \frac{n}{2} ⌋})^{−1} ,

where a_{n} ∗b_{n} denotes the Dirichlet convolution, and the reciprocal is the inverse with respect to Dirichlet convolution.

Remark. Thus, the numbers of ribbon Schur functions of size 1 to 33 turn out to be:

1, 2, 3, 6, 10, 20, 36, 72, 135, 272, 528, 1052, 2080, 4160, 8244, 16508, 32896, 65770, 131328, 262632, 524744, 1049600, 2098176, 4196200, 8390620, 16781312, 33558291, 67116944, 134225920, 268451240, 536887296, 1073774376, 2147515424.

This is sequence http://oeis.org/A120421 in the on-line encyclopedia of integer sequences [6].

It may be interesting to compare the number of ribbon Schur functions with the number of lexicographic minimal compositions. Since |α ∘ β| = |α| · |β|, it is clear that the numbers coincide when n is prime. For n = 9, there are 136 lexicographic minimal compositions, but two of them are equivalent. Here are the differences and their positions up to n = 33:

n :  9 12 15 16 18 20 21 24 25 27 28 30 32 33
difference : 1 4 12 4 22 24 56 152 36 237 112 600 216 992

Proof. Let R be the set of normalised compositions. Let S be the set of symmetric compositions, P^{×} be the set of (normalised) asymmetric irreducible compositions and

(3)  R^{1} = P^{×} ∘ S,

i.e., the set of (normalised) compositions whose first factor in the irreducible factorisation is asymmetric, and all remaining factors (if any) are symmetric. We can then decompose the set of normalised compositions recursively as

(4)  R = S ·∪(R ∘ R^{1}),

since a normalised composition is either symmetric, or can be written in a unique way as a product of a normalised composition, an asymmetric irreducible factor and a symmetric composition.

The set R^{1} can be described in terms of the set of all compositions C and the set of asymmetric lexicographic minimal compositions L^{×} by Lemma 3.2. Namely,

(5)  L^{×} = C ∘ R^{1},

since an asymmetric composition is lexicographic minimal, if and only if the last asymmetric factor in its irreducible factorisation is lexicographic minimal.

Finally, we have (again by Lemma 3.2)

2L^{×} = C \ S,

where 2L^{×} is interpreted as the set of asymmetric compositions whose last asymmetric factor is either lexicographic minimal or lexicographic maximal.

We can now apply Lemma 3.3 to obtain the Dirichlet generating function for the set of normalised compositions. We have

L^{×}(s) = 1/2 (C(s) − S(s))
R^{1}(s) = L^{×}(s)/C(s)

and therefore

R(s) = \frac{S(s)}{1 − R^{1}(s)}

= \frac{2C(s)S(s)}{2C(s) − (C(s) − S(s))}

= \frac{2C(s)S(s)}{C(s) + S(s)}.

Since C(s) = ∑_{n≥1} 2^{n−1}n^{−s} and S(s) = ∑_{n≥1} 2^{⌊ \frac{n}{2} ⌋}n^{−s}, the claim follows. □

Remark. It is not difficult to obtain more information using the preceding theorem and the decompositions in its proof. In particular, we can easily refine the count of normalised compositions by taking into account the number of asymmetric irreducible factors. Denoting the number of asymmetric irreducible factors of a composition ρ by α(ρ) and defining R(s, z) = ∑_{ρ∈R} |ρ|^{−s}z^{α(s)}, we find

R(s, z) = \frac{S(s)}{1 − zR^{1}(s)} = \frac{2C(s)S(s)}{2C(s) − z (C(s) − S(s))}.

Perhaps more interesting, we can determine the generating function for irreducible compositions by size using the following proposition:

Proposition 3.5. Let P (s) be the Dirichlet generating function for (normalised) irreducible compositions, P^{∗}(s) the Dirichlet generating function for symmetric irreducible compositions and R(s) the Dirichlet generating function for normalised compositions by size.

Furthermore, let S(s) = ∑_{n≥1} 2^{⌊ \frac{n}{2} ⌋}n^{−s} be the Dirichlet generating function of symmetric compositions, and ζ(s) = ∑_{n≥1} n^{−s} the Riemann zeta function. We then have

(6)  P (s) = 2ζ^{−1}(s) − 1 − R^{−1}(s)
(7)  P^{∗}(s) = 2ζ^{−1}(s) − 1 − S^{−1}(s)

and

(8)  P^{×}(s) = S^{−1}(s) − R^{−1}(s).

Remark. Thus, the numbers of (normalised) irreducible compositions of size 1 to 33 are:

0, 0, 1, 2, 8, 10, 34, 56, 126, 234, 526, 972, 2078, 4018, 8186, 16240, 32894, 65164, 131326, 261544, 524530, 1047490, 2098174, 4191680, 8390520, 16772994, 33557508, 67100304, 134225918, 268416590, 536887294, 1073708400, 2147512258.

Note that, whenever n is prime, there are precisely two normalised compositions (or, equivalently, lexicographic minimal compositions) that are not irreducible, namely the composition with all components equal to 1 and the composition (n).

For n = 4, the irreducible normalised compositions are (1, 3) and (1, 1, 2). For n = 6, they are (1, 5), (1, 1, 4), (1, 4, 1), (1, 2, 3), (2, 1, 3), (1, 1, 1, 3), (1, 1, 2, 2), (1, 1, 3, 1), (2, 1, 1, 2), (1, 1, 1, 1, 2).

Proof. Let E be the set of compositions with at least two components, all equal to 1. Let K be the set of compositions different from 1 with only one component. Let R be the set of all normalised compositions. Let R_{E} be the set of normalised compositions with no factors in the irreducible factorisation having only one component, i.e., all factors being irreducible compositions or having at least two components, all equal to 1. Finally, let P be the set of (normalised) irreducible compositions.

By Theorem 2.5, R_{E} is the disjoint union of the sets P, P ∘ R_{E}, E, E ∘ P and E ∘ P ∘ R_{E}. Passing to (Dirichlet) generating functions, we obtain

(9)  R_{E}(s) = E(s) + (1 + E(s))P (s)(1 + R_{E}(s)).

Similarly, R is the disjoint union of the composition (1) and the sets R_{E}, K, K∘R_{E} and R_{E} ∘ K ∘ R. Informally, we decompose the set of normalised compositions into subsets depending on the position of the first factor with only one component in the irreducible factorisation, if such a factor occurs. Hence

(10)  R(s) = (1 + K(s))(1 + R_{E}(s)) + R_{E}(s)K(s)R(s).

We can now extract R_{E}(s) from Equation (10) and plug it into Equation (9) to obtain P (s) in terms of E(s), K(s) and R(s). Observing that E(s) = K(s) = ζ(s) − 1 we obtain Equation (6). Equation (8) can be derived by combining Equations (3) and (4). Equation (7) then follows from Equations (6) and (8). □

4. The number of ribbon Schur functions of a given size and length

Apart from the size of a composition, the most natural statistic that comes to mind is its length. In this section we derive an expression for the number of normalised compositions with a given size and a given length.

By Theorem 2.3, it is possible to determine the length of a composition of compositions, knowing the size and the length of the factors. However, since the length of a composition of compositions is neither multiplicative or additive, we cannot expect a result as appealing as in Theorem 3.4.

Let us first collect some elementary results:

Proposition 4.1. Let C_{n}(x) = ∑_{α∈C,|α|=n} x^{l(α)} be the ordinary generating function of all compositions of size n, where x marks length. Similarly, let S_{n}(x) = ∑_{α∈S,|α|=n} x^{l(α)} the generating function of symmetric compositions, and L_{n}^{×}(x) = ∑_{α∈L^{×},|α|=n} x^{l(α)} the generating function of asymmetric lexicographic minimal compositions. Then

(http://oeis.org/A007318)  C_{n}(x) = x(1 + x)^{n−1},

(http://oeis.org/A051159)  S_{n}(x) = \begin{cases}x(1 + x)(1 + x^{2})^{(n−2)/2} & n even \\ x(1 + x^{2})^{(n−1)/2} & n odd, \end{cases}
(http://oeis.org/A034852)  L_{n}^{×}(x) = 1/2 (C_{n}(x) − S_{n}(x)) .

Theorem 4.2. Let R_{n}(x) = ∑_{ρ∈R,|ρ|=n} x^{l(ρ)} be the ordinary generating function of normalised compositions of size n, where x marks length. Similarly, let R_{n}^{1}(x) = ∑_{ρ∈R^{1},|ρ|=n} x^{l(ρ)} be the ordinary generating function of (normalised) compositions whose first factor in the irreducible factorisation is asymmetric, and all remaining factors (if any) are symmetric. Then we have

R_{n}^{1}(x) = ∑_{\begin{matrix}k≥0 \\ 1=d_{0}|d_{1}|...|d_{k}|n \\ d_{i} ≠ d_{i+1} for i ∈ \{0, …, k − 1\} \end{matrix}} (−1)^{k}L_{n/d_{k}}^{×}(x^{d_{k}}) ∏_{i=0}^{k−1} C_{d_{i+1}/d_{i}}(x^{d_{i}})/x^{d_{i}} (11)

and

R_{n}(x) = ∑_{\begin{matrix}k≥0 \\ d_{1}|d_{2}|...|d_{k+1}=n \\ d_{i} ≠ d_{i+1} for i ∈ \{1, …, k\} \end{matrix}} S_{d_{1}}(x) ∏_{i=1}^{k} R_{d_{i+1}/d_{i}}^{1}(x^{d_{i}})/x^{d_{i}}. (12)

Proof. We reuse the decompositions from the proof of Theorem 3.4. From Equation (5), we obtain the equality of sets (subscripts denoting the size of the compositions we are restricting our attention to)

L_{n}^{×} = ˙⋃_{d|n} C_{d} ∘ R_{n/d}^{1}.

Since l(α ∘ β) = l(α) − |α| + |α| l(β), it follows that

(13)  L_{n}^{×}(x) = ∑_{d|n} C_{d}(x)x^{−d}R_{n/d}^{1}(x^{d}).

Equation (11) then follows from Equation (15) in Lemma 4.3 below, with A_{n}(x) = L_{n}^{×}(x), B_{n}(x) = C_{n}(x)/x^{n} and D_{n}(x) = R_{n}^{1}(x).

Similarly, from Equation (4), we obtain the equality of sets

R_{n} = S_{n} ·∪ ˙⋃_{d|n,d≠n} R_{d} ∘ R_{n/d}^{1},

and therefore

(14)  R_{n}(x) = S_{n}(x) + ∑_{d|n,d≠n} R_{d}(x)x^{−d}R_{n/d}^{1}(x^{d}).

Equation (12) then follows from Equation (16) in Lemma 4.3 below, with A_{n}(x) = R_{n}(x), B_{n}(x) = S_{n}(x) and D_{n}(x) = R_{n}^{1}(x)/x. □

Remark. Note that for actually computing the generating function for normalised compositions using a computer, Equations (13) and (14) may be easier to implement than the ‘explicit’ expressions given in the statement of the theorem.

Again, we can refine the count be marking the number of asymmetric irreducible factors with an additional variable z: every summand in Equation (12) has to be multiplied by z^{k}, since every composition in R_{n}^{1} contains exactly one asymmetric irreducible factor.

Lemma 4.3. Suppose that B_{1}(x) = 1 and

A_{n}(x) = ∑_{d|n} B_{d}(x)D_{n/d}(x^{d}).

Then we have

(15)  D_{n}(x) = ∑_{\begin{matrix}k≥0 \\ 1=d_{0}|d_{1}|...|d_{k}|n \\ d_{i} ≠ d_{i+1} for i ∈ \{0, …, k − 1\} \end{matrix}} (−1)^{k}A_{n/d_{k}}(x^{d_{k}}) ∏_{i=0}^{k−1} B_{d_{i+1}/d_{i}}(x^{d_{i}}).

Given

A_{n}(x) = B_{n}(x) + ∑_{d|n,d≠n} A_{d}(x)D_{n/d}(x^{d}),

we have

(16)  A_{n}(x) = ∑_{\begin{matrix}k≥0 \\ d_{1}|d_{2}|...|d_{k+1}=n \\ d_{i} ≠ d_{i+1} for i ∈ \{1, …, k\} \end{matrix}} B_{d_{1}}(x) ∏_{i=1}^{k} D_{d_{i+1}/d_{i}}(x^{d_{i}}).

Proof. We prove the statements by induction on n. For n = 1, the hypothesis is A_{1}(x) = B_{1}(x)D_{1}(x) = D_{1}(x), and the right hand side of Equation (15) indeed evaluates to A_{1}(x).

Now suppose that Equation (15) holds for n < N. Then

D_{N}(x) = A_{N}(x) − ∑_{1<d|N} B_{d}(x)D_{N/d}(x^{d})

= A_{N}(x) − ∑_{1<d|N} B_{d}(x) ∑_{\begin{matrix}k≥0 \\ 1=d_{0}|d_{1}|...|d_{k}|N/d \\ d_{i} ≠ d_{i+1} for i ∈ \{0, …, k − 1\} \end{matrix}} (−1)^{k}A_{N/(d_{k}d)}(x^{d_{k}d}) ∏_{i=0}^{k−1} B_{d_{i+1}/d_{i}}(x^{d_{i}d}).

Substituting d′_{i+1} = d_{i}d we obtain

D_{N}(x) = A_{N}(x) − ∑_{1<d|N} B_{d}(x) ∑_{\begin{matrix}k≥0 \\ d=d′_{1}|d′_{2}|...|d′_{k+1}|N \\ d′_{i} ≠ d′_{i+1} for i ∈ \{1, …, k\} \end{matrix}} (−1)^{k}A_{N/(d′_{k+1})}(x^{d′_{k+1}}) ∏_{i=1}^{k} B_{d′_{i+1}/d′_{i}}(x^{d′_{i}})

= A_{N}(x) − ∑_{\begin{matrix}k≥0 \\ 1=d′_{0}|d′_{1}|...|d′_{k+1}|N \\ d′_{i} ≠ d′_{i+1} for i ∈ \{0, …, k\} \end{matrix}} (−1)^{k}A_{N/(d′_{k+1})}(x^{d′_{k+1}}) ∏_{i=0}^{k} B_{d′_{i+1}/d′_{i}}(x^{d′_{i}}).

The final expression is equivalent to the claimed Equation (15), since A_{N}(x) is precisely the summand corresponding to the chain 1 = d′_{0}|N.

Equation (16) can be shown using the same strategy; the calculations are actually a bit easier. □

Acknowledgements

I would like to express my gratitude to Stephanie van Willigenburg for suggesting the problem and for her enthusiasm. I would also like to thank two anonymous referees for carefully reading the manuscript and spotting several inaccuracies.

References

[1] Louis J. Billera, Hugh Thomas, and Stephanie van Willigenburg. Decomposable compositions, symmetric quasisymmetric functions and equality of ribbon Schur functions. Advances in Mathematics, 204(1):204–240, 2006, math.CO/0405434.

[2] Christian Gutschwager. Equality of multiplicity free skew characters. Journal of Algebraic Combinatorics, 30(2):215–232, 2009, math.CO/0806.1879.

[3] Manuel Maia and Miguel Méndez. On the arithmetic product of combinatorial species. Discrete Math., 308(23):5407–5427, 2008, math.CO/0503436.

[4] Peter R. W. McNamara and Stephanie van Willigenburg. Towards a combinatorial classification of skew Schur functions. Transactions of the American Mathematical Society, 361(8):4437–4470,

2009, math.CO/0608446.

[5] Victor Reiner, Kristin M. Shaw, and Stephanie van Willigenburg. Coincidences among skew Schur functions. Advances in Mathematics, 216(1):118–152, 2007, math.CO/0602634.

[6] Neil J. A. Sloane. The on-line encyclopedia of integer sequences. Notices of the American Math-

ematical Society, 50(8):912–915, 2003. http://www.research.att.com/~njas/sequences.

[7] Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

[8] Stephanie van Willigenburg. Equality of Schur and skew Schur functions. Annals of Combinatorics, 9(3):355–362, 2005, math.CO/0410044.

Institut für Algebra, Zahlentheorie und Diskrete Mathematik, Leibniz Universität Hannover, Welfengarten 1, D-30167 Hannover, Germany

  E-mail address: martin.rubey@math.uni-hannover.de
  URL: http://www.iazd.uni-hannover.de/~rubey/