A SYMMETRIC FUNCTIONS APPROACH

TO STOCKHAUSEN’S PROBLEM

Lily Yen

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada lyen@jeeves.uwaterloo.ca

Submitted July 9, 1995. Accepted February 5, 1996.

Abstract. We consider problems in sequence enumeration suggested by Stockhausen’s problem, and derive a generating series for the number of sequences of length k on n available symbols such that adjacent symbols are distinct, the terminal symbol occurs exactly r times, and all other symbols occur at most r − 1 times. The analysis makes extensive use of techniques from the theory of symmetric functions. Each algebraic step is examined to obtain information for formulating a direct combinatorial construction for such sequences.

1. Introduction

The score of the piano work nr. 7 Klavierstück XI by Karlheinz Stockhausen (1957) [S] consists of 19 fragments of music. The performer is instructed to choose at random one of these fragments, and play it; then to choose another, different, fragment and play that, and so on. If a fragment is chosen that has already been played twice, the performance ends. We can state a more general problem as follows: Denote each fragment of music by a symbol. Then an r-Stockhausen sequence on n symbols is a sequence such that

(1) adjacent symbols are distinct,

(2) the terminal symbol occurs exactly r times,

(3) no symbol occurs more than r times,

(4) exactly one symbol occurs r times,

(5) the symbol alphabet is N_{n} = {1, 2, …, n}. The original problem posed by Stockhausen is then the case when r = 3 and n = 19. We shall refer to 3-Stockhausen sequences simply as Stockhausen sequences. We let c_{r}(n, k) be the number of r-Stockhausen sequences of length k on n symbols, and

s_{r}(n) := ∑_{k=2r−1}^{(r−1)n+1} c_{r}(n, k),

Typeset by AMS-TEX

The research for this paper was supported by the Natural Sciences and Engineering Research Council of Canada under a postdoctoral fellowship.

for the minimum (resp. maximum) length of an r-Stockhausen sequence is 2r − 1 (resp. (r − 1)n + 1). The expected length of a performance under the assumption that each fragment is equally likely is given in [RY].

The method of generating series is a major technique in enumeration. In this case, the determination of the exact number of Stockhausen sequences on n symbols is an enumerative question that can be approached using the theory of symmetric functions for coefficient extraction in the generating series approach. A generalization of the problem leads to a combinatorial construction for the Stockhausen sequences. Although only known techniques [G] are used, these are sophisticated, and the problem serves as a useful study of these techniques, and the algebraic analysis gives partial information about the formulation of a bijective proof.

The paper is organized as follows. In Section 2, we define a few classical symmetric functions, and state some properties they satisfy. Section 3 contains the derivation of the generating series for the number of Stockhausen sequences. In Section 4 we generalize the method given in Section 3 and give an analogous derivation for the generating series for the number of r-Stockhausen sequences. By examining the generating series for r-Stockhausen sequences, we give in Section 5 a series of combinatorial constructions that leads to r-Stockhausen sequences.

2. Symmetric Functions

We review some classical symmetric functions, and recall some properties of the ring of symmetric functions. The reader is directed to [M] for a fuller account.

A function f(x_{1}, x_{2}, …) in infinitely many indeterminates is a symmetric function if f is invariant under any permutation of any finite number of the variables. We shall consider such symmetric functions over the rationals. The following symmetric functions are used in the derivation of the generating series for c_{r}(n, k).

The complete symmetric function h_{n} is defined by

h_{n}(x_{1}, x_{2}, …) = ∑_{i_{1}≤i_{2}≤···≤i_{n}} x_{i_{1}}x_{i_{2}} ⋯ x_{i_{n}}.

Moreover, h_{0} = 1. If λ = (λ_{1}, λ_{2}, …, λ_{k}) is a partition, i. e. a non-increasing sequence of positive integers, we let h_{λ} denote h_{λ_{1}}h_{λ_{2}} ⋯ h_{λ_{k}}. The weight of λ is |λ| := ∑_{i} λ_{i}.

The monomial symmetric function m_{λ} is the sum of all distinct monomials of the form x_{i_{1}}^{λ_{1}} ⋯ x_{i_{k}}^{λ_{k}}, where i_{1}, …, i_{k} are distinct.

The power sum symmetric function p_{n} is defined by

p_{n}(x_{1}, x_{2}, …) = ∑_{i} x_{i}^{n}.

Similar to h_{λ}, p_{λ} is defined to be p_{λ_{1}}p_{λ_{2}} ⋯ p_{λ_{k}}.

It is known that [M] each of the sets {h_{λ}}, {m_{λ}}, and {p_{λ}}, where λ ranges over all partitions of n, is a basis of the vector space over ℚ of symmetric functions homogeneous of degree n.

Let m_{j}(λ) denote the number of j’s in the partition λ. The complete symmetric function h_{n} can be expressed in terms of the power sum symmetric functions as follows:

h_{n} = ∑_{λ⊢n} z^{−1}(λ)p_{λ},

where

z(λ) = (∏_{j≥1} j^{m_{j}(λ)}m_{j}(λ)!)

and λ ⊢ n indicates that λ is a partition of n. For instance, h_{1} = p_{1}, h_{2} = (p_{1}^{2} + p_{2})/2, and h_{3} = (p_{1}^{3} + 3p_{2}p_{1} + 2p_{3})/6.

There is [M] an inner product ⟨·, ·⟩ defined on the vector space of symmetric functions such that ⟨m_{λ}, h_{μ}⟩ = δ_{λ,μ}, so ⟨p_{λ}, p_{μ}⟩ = z(λ)δ_{λ,μ} for any two partitions λ and μ, where δ_{λ,μ} is 1 if λ = μ and zero otherwise. It follows that if f and g are symmetric functions, then ⟨p_{n}f, g⟩ = ⟨f, n\frac{∂g}{∂p_{n}} ⟩, so the action adjoint to multiplication by p_{n} is n\frac{∂}{∂p_{n}}.

For any partition λ, let l(λ) denote the number of parts of λ. Then the number of monomials on n (≥ l(λ)) symbols of the form x_{i_{1}}^{λ_{1}} ⋯ x_{i_{l(λ)}}^{λ_{l(λ)}}, where i_{1}, …, i_{l(λ)} are distinct, is (2.1)

\frac{n!}{(n − l(λ))! m_{1}(λ)! m_{2}(λ)! ⋯ m_{λ_{1}}(λ)!} = m_{λ}(\underbrace{1, …, 1}_{n 1’s}, 0, …) = \frac{(n)_{l(λ)}}{m_{1}(λ)! m_{2}(λ)! ⋯ m_{λ_{1}}(λ)!},

where (n)_{j} = n(n − 1) ⋯ (n − j + 1) denotes the jth falling factorial.

The following proposition is needed and can be regarded as the adjoint form of Taylor’s Theorem on the ring of symmetric functions.

Proposition 2.1. Let f and g be symmetric functions and u a real number, and suppose that f = f(p_{1}, p_{2}, …). Then

⟨f(p_{1}, p_{2}, …), e^{up_{j}}g⟩ = ⟨f(p_{1}, p_{2}, …, p_{j−1}, p_{j} + ju, p_{j+1}, p_{j+2}, …), g⟩.

Proof. We use the adjoint action to multiplication by p_{j},

⟨f(p_{1}, p_{2}, …), e^{up_{j}}g⟩ = ∑_{k≥0} \frac{u^{k}}{k!} ⟨j^{k} \frac{∂^{k}}{∂p_{j}^{k}} f(p_{1}, p_{2}, …), g⟩

= ⟨∑_{k≥0} \frac{(uj)^{k}}{k!} \frac{∂^{k}}{∂p_{j}^{k}} f(p_{1}, p_{2}, …), g⟩

= ⟨exp (ju\frac{∂}{∂p_{j}} ) f(p_{1}, p_{2}, …), g⟩

= ⟨f(p_{1}, p_{2}, …, p_{j} + ju, …), g⟩

using the formal version of Taylor’s Theorem. □

3. A solution for the original problem

We derive a generating series for the number c_{3}(n, k) of Stockhausen sequences on n symbols of length k. To reach this goal, we begin with the generating series for sequences satisfying condition (1) for Stockhausen sequences (Lemma 3.1), then we derive the generating series of sequences satisfying conditions (1) and (2) for r = 3 (Proposition 3.2); and finally we address the generating series for Stockhausen sequences by imposing appropriate restrictions in order to satisfy conditions (3) and (4).

Lemma 3.1. The generating series for all strings on n symbols such that adjacent symbols are different is

D(z, x_{1}, …, x_{n}) = \frac{1}{1 − ∑_{i=1}^{n} \frac{zx_{i}}{1+zx_{i}}} ,

where z is an ordinary marker for the length of the string and x_{i} marks the occurrence of symbol i.

See [RY,§2] for a proof.

Proposition 3.2. Let D_{n}(z, x_{1}, …, x_{n}) be the generating series of sequences on the symbols {1, 2, …, n} (marked by x_{1}, …, x_{n}) of length k (marked by z) such that the terminal symbol occurs exactly three times (non-terminal symbols occur arbitrarily many times) and adjacent symbols are distinct. Then

D_{n}(z, x_{1}, …, x_{n}) = z^{3} (∑_{j=1}^{n} x_{j}^{3} (1 − ∑n ; \begin{matrix}i=1 \\ i≠j \end{matrix} \frac{zx_{i}}{1+zx_{i}} )^{3}^{(∑n ; \begin{matrix}i=1 \\ i≠j \end{matrix} \frac{zx_{i}}{1+zx_{i}} )2} ) .

Proof. Consider such a sequence which terminates with the symbol j. The sequence decomposes into AjBjB′j, where A, B, and B′ are strings on the symbols {1, 2, …, n} \ {j} with distinct adjacent elements, A possibly empty but B and B′ non-empty. By Lemma 3.1, the generating series for all such sequences is

z^{3}x_{j}^{3}L_{w} \frac{1}{1 − w ∑n ; \begin{matrix}i=1 \\ i≠j \end{matrix} \frac{zx_{i}}{1+zx_{i}}} ,

where L_{w} is the linear transform defined by

L_{w}f(w) = \frac{1}{2!} \frac{∂^{2}f}{∂w^{2}} |_{w=1} .

Although we introduce L_{w} here to simplify the expression for the generating series, it will be seen later that it has combinatorial significance. To get the sequences described in the statement, we take the union over j, and so, summing the above generating series over j we obtain

D_{n} = z^{3} ∑_{j=1}^{n} x_{j}^{3}L_{w} \frac{1}{1 − w ∑n ; \begin{matrix}i=1 \\ i≠j \end{matrix} \frac{zx_{i}}{1+zx_{i}}} . □

We remark that a very easy direct proof is possible, but L_{w} is introduced in order to illustrate how its counterpart, L_{w}^{(r)}, will be used in Section 4, where for r > 3, this linear transform helps in carrying out the calculations with symmetric functions.

To restrict the frequency of occurrence of symbols, we let P_{3} be the set of all partitions with exactly one 3 as the largest part. For α in P_{3}, let x^{α} denote x_{1}^{α_{1}}x_{2}^{α_{2}} ⋯ and let [x^{α}]f denote the coefficient of x^{α} in f; then

[x^{α}]D_{n} = [x^{α}]z^{3}p_{3}L_{w} \frac{1}{1 − w(zp_{1} − z^{2}p_{2})}

for the power sums p_{1}, p_{2}, p_{3} in x_{1}, x_{2}, …, x_{n}.

Let

(3.1)  G(z, x_{1}, …, x_{n}) = z^{3}p_{3}L_{w} \frac{1}{1 − w(zp_{1} − z^{2}p_{2})},

where p_{1}, p_{2}, and p_{3} are power sum symmetric functions in infinitely many indeterminates. Then

[x^{α}]D_{n} = [x^{α}]G(z, x_{1}, x_{2}, …, x_{n}, 0, 0, …).

Therefore the generating series for the set of all Stockhausen sequences on n symbols is

F_{n}(z, x_{1}, …, x_{n}) = ∑_{α∈P_{3}} ∑_{β}[x^{β}]G(z, x_{1}, x_{2}, …, x_{n}, 0, 0, …),

where the inner sum is over all distinct permutations β of α.

The sequences defined in the statement of Proposition 3.2 satisfy conditions (1) and (2). Conditions (3) and (4) are imposed by the restriction that all partitions α are in P_{3}. The last condition is imposed by evaluating G with x_{n+1} = x_{n+2} = ⋯ = 0 to exclude n + 1, n + 2, … from the alphabet, and by the sum over β so that each element of the alphabet N_{n} is permitted to occur.

Since G is a symmetric function in the x_{i}’s, we may expand it in terms of the monomial symmetric functions:

G = ∑_{θ∈P_{3}} m_{θ}(x_{1}, x_{2}, …)a_{θ}z^{|θ|},

where the a_{θ}’s are scalars.

Then another way of expressing F_{n} is

F_{n} = ∑_{α∈P_{3}} m_{α}(\underbrace{1, 1, …, 1}_{n}, 0, 0, …)[m_{α}]G = ∑_{α∈P_{3}} \frac{(n)_{l(α)}}{m_{1}(α)! m_{2}(α)!}a_{α}z^{|α|},

because from (2.1) m_{α}(\underbrace{1, 1, …, 1}_{n}, 0, 0, …) is the number of terms in the monomial symmet-

ric function m_{α} on x_{1}, x_{2}, …, x_{n}, which is equal to the number of sequences over {0, 1, 2, 3} of length n with n − l(α) occurrences of 0, m_{1}(α) occurrences of 1, m_{2}(α) occurrences of 2 and one occurrence of 3 (as specified by P_{3}).

We use the property ⟨m_{α}, h_{θ}⟩ = δ_{α,θ} of the inner product to extract the coefficient of m_{α} in G. In order to have m_{1}(α)! and m_{2}(α)! in the denominator and one part of size 3 in α, we consider

uh_{3}e^{u(h_{1}+h_{2})} = ∑_{α∈P_{3}} h_{α} \frac{u^{l(α)}}{m_{1}(α)! m_{2}(α)!}.

Clearly,

⟨G, uh_{3}e^{u(h_{1}+h_{2})}⟩ = ∑_{α∈P_{3}} \frac{u^{l(α)}}{m_{1}(α)! m_{2}(α)!}a_{α}z^{|α|}.

With the help of the mapping Ξ_{n}: u^{j} ↦ (n)_{j}, for j = 0, 1, 2, …, extended linearly to the power series ring in u, we obtain

F_{n} = ∑_{k≥0} c_{3}(n, k)z^{k} = Ξ_{n} ⟨G, uh_{3}e^{u(h_{1}+h_{2})}⟩ .

We are now in a position to work on Φ_{3}(z, u) := ∑_{n} F_{n}(z)u^{n}/n!, our goal for this section.

Lemma 3.3. Let c be independent of u. Then Ξ_{n}e^{uc}u^{k} = (n)_{k}(1 + c)^{n−k}. If, moreover, g(u) = 1 + g_{1}u + g_{2}u^{2} + ⋯ is a power series in u, then Ξ_{n}e^{uc}g(u) = [\frac{u^{n}}{n!}]e^{u(1+c)}g(u).

Proof. The first statement follows from direct computation. Now

Ξ_{n}e^{uc}g(u) = Ξ_{n} ∑_{k≥0} e^{uc}g_{k}u^{k} = ∑_{k≥0} g_{k} · (n)_{k}(1 + c)^{n−k} = ∑_{k=0}^{n} g_{k} \frac{n!}{(n−k)!}(1 + c)^{n−k},

and the second statement follows. Note that (n)_{k} = 0 if n < k. □

It now follows that the generating series for c_{3}(n, k) is

Corollary 3.4.

Φ_{3}(z, u) := ∑_{k,n≥0} c_{3}(n, k)z^{k} \frac{u^{n}}{n!} = e^{u}⟨G, uh_{3}e^{u(h_{1}+h_{2})}⟩.

Proof. We know that

∑_{k≥0} c_{3}(n, k)z^{k} = ⟨G, Ξ_{n}uh_{3}e^{u(h_{1}+h_{2})}⟩ = ⟨G, [\frac{u^{n}}{n!}]e^{u}uh_{3}e^{u(h_{1}+h_{2})}⟩

by Lemma 3.3. Since G is independent of u, the last expression is

[\frac{u^{n}}{n!}]⟨G, e^{u}uh_{3}e^{u(h_{1}+h_{2})}⟩ = [\frac{u^{n}}{n!}]e^{u}⟨G, uh_{3}e^{u(h_{1}+h_{2})}⟩.

It follows that

Φ_{3}(z, u) = e^{u}⟨G, uh_{3}e^{u(h_{1}+h_{2})}⟩.

To evaluate the inner product, we expand G and uh_{3}e^{u(h_{1}+h_{2})} in terms of the power sums, and use the property ⟨p_{λ}, p_{μ}⟩ = z(λ)δ_{λ,μ} of the inner product, the adjoint action to multiplication by p_{j}, and Taylor’s Theorem on the ring of symmetric functions. We know that upon substitution of G using (3.1)

Φ_{3}(z, u) = e^{u} ⟨L_{w} \frac{z^{3}p_{3}}{1 − w(zp_{1} − z^{2}p_{2})}, \frac{u}{6}(p_{1}^{3} + 3p_{2}p_{1} + 2p_{3})e^{u(p_{1}+(p_{1}^{2}+p_{2})/2)}⟩

by linearity of ⟨, ⟩ and ignoring terms in the second argument that are independent of p_{3}, we get

= L_{w}e^{u} ⟨\frac{z^{3}p_{3}}{1 − w(zp_{1} − z^{2}p_{2})}, \frac{u}{3}p_{3}e^{u(p_{1}+(p_{1}^{2}+p_{2})/2)}⟩

by adjoint action of p_{3}, we have

= L_{w}e^{u} ⟨\frac{z^{3}}{1 − w(zp_{1} − z^{2}p_{2})}, ue^{u(p_{1}+(p_{1}^{2}+p_{2})/2)}⟩

using Proposition 2.1 we obtain

= L_{w}e^{u} ⟨\frac{z^{3}}{1 − w(z(p_{1} + u) − z^{2}(p_{2} + u))}, ue^{up_{1}^{2}/2}⟩

again by the property of the inner product we ignore terms in the first argument independent of p_{1} and reach

= L_{w}e^{u} ⟨\frac{z^{3}}{1 − wzu + wz^{2}u − wzp_{1}} , ue^{up_{1}^{2}/2}⟩ .

Since

\frac{1}{1 − wzu + wz^{2}u − wzp_{1}} = ∑_{j≥0} \frac{(wzp_{1})^{j}}{(1 − wzu + wz^{2}u)^{j+1}} ,

we have that

Φ_{3}(z, u) = z^{3}ue^{u}L_{w} ∑_{j≥0} \frac{(wz)^{j}}{(1 − wzu + wz^{2}u)^{j+1}} ⟨p_{1}^{j}, e^{up_{1}^{2}/2}⟩

= z^{3}ue^{u}L_{w} ∑_{j≥0} \frac{(wz)^{2j}}{(1 − wzu + wz^{2}u)^{2j+1}} ⟨p_{1}^{2j}, e^{up_{1}^{2}/2}⟩

= z^{3}ue^{u}L_{w} ∑_{j≥0} \frac{(wz)^{2j}}{(1 − wzu + wz^{2}u)^{2j+1}} ⟨p_{1}^{2j}, u^{j} \frac{p_{1}^{2j}}{2^{j}j!}⟩

= z^{3}ue^{u}L_{w} ∑_{j≥0} \frac{u^{j}(wz)^{2j}}{(1 − wzu + wz^{2}u)^{2j+1}} \frac{(2j)!}{2^{j}j!}.

We summarize the result in the following.

Proposition 3.5. Let L_{w}^{(r)}(f(w)) = \frac{1}{r!} \frac{∂^{r}f}{∂w^{r}} |_{w=1}, then

Φ_{3}(z, u) = z^{3}ue^{u}L_{w} ∑_{j≥0} \frac{u^{j}(wz)^{2j}}{(1 − wzu + wz^{2}u)^{2j+1}} \frac{(2j)!}{2^{j}j!}.

We remark that the original Stockhausen number s_{3}(n) is

[\frac{u^{n}}{n!}]Φ_{3}(1, u) = [\frac{u^{n}}{n!}]\frac{1}{2}ue^{u} ∑_{j≥0}(2j)(2j − 1)\frac{(2j)!}{2^{j}j!}u^{j},

so

s_{3}(n) = n ∑_{j=0}^{n−1} \binom{n − 1}{j}\binom{2j}{2}\frac{(2j)!}{2^{j}}.

A direct combinatorial proof of this expression is given in [RY].

4. A generating series for r-Stockhausen sequences

We use the method suggested by the previous section to derive a generating series for r-Stockhausen sequences.

Theorem 4.1. Let

Φ_{r}(z, u) := ∑_{n,k≥0} c_{r}(n, k)z^{k} \frac{u^{n}}{n!}

be the generating series for the number c_{r}(n, k) of sequences of length k on n symbols such that adjacent symbols are distinct, the terminal symbol occurs exactly r times, and all other symbols occur at most r − 1 times. Then

Φ_{r}(z, u) = uz^{r}L_{w}^{(r−1)}Θ_{w} exp (u[t^{r−1}]\frac{e^{wzt/(1+zt)}}{1 − t} ) ,

where z is the ordinary marker for the length of the sequence, u is the exponential marker for the number of available symbols, L_{w}^{(r)}(f(w)) = \frac{1}{r!} \frac{∂^{r}f}{∂w^{r}} |_{w=1} and Θ_{w} is the inverse

Laplace transform Θ_{w}: w^{j} ↦ j! w^{j}.

We may take advantage of the analysis of the original problem (when r = 3).

Proof. Let

F_{n,r} := z^{r}p_{r} \begin{matrix}(∑_{j≥1}(−1)^{j−1}z^{j}p_{j}) & r−1 \\ (1 − ∑_{j≥1}(−1)^{j−1}z^{j}p_{j}) & r \end{matrix} .

Then

c_{r}(n, k) = [z^{k}]Ξ_{n} ⟨F_{n,r}, uh_{r}e^{u(h_{1}+h_{2}+···+h_{r−1})}⟩ .

Now

F_{n,r} = z^{r}L_{w}^{(r−1)}p_{r}(1 − w ∑_{j≥1}(−1)^{j−1}z^{j}p_{j})^{−1},

and

∑_{k≥0} c_{r}(n, k)z^{k} = Ξ_{n}z^{r}L_{w}^{(r−1)} ⟨p_{r}(1 − w ∑_{j≥1}(−1)^{j−1}z^{j}p_{j})^{−1}, uh_{r}e^{u(h_{1}+h_{2}+···+h_{r−1})}⟩

= [\frac{u^{n}}{n!}]z^{r}L_{w}^{(r−1)} ⟨p_{r}(1 − w ∑_{j≥1}(−1)^{j−1}z^{j}p_{j})^{−1}, uh_{r}e^{u(1+h_{1}+h_{2}+···+h_{r−1})}⟩

= [\frac{u^{n}}{n!}]Φ_{r}(z, u),

by definition. So

(4.1) Φ_{r}(z, u) = uz^{r}L_{w}^{(r−1)} ⟨p_{r}(1 − w ∑_{j≥1}(−1)^{j−1}z^{j}p_{j})^{−1}, h_{r}e^{u(1+h_{1}+h_{2}+···+h_{r−1})}⟩ .

In order to extract the coefficients from (4.1), we perform some technical maneuvers using the properties of symmetric functions stated in Section 2.

It is convenient for expository purposes to isolate these into a series of steps.

Step 1. Apply the adjoint action to multiplication by p_{j} to remove p_{j} from the first argument of the inner product.

Since h_{r} = ∑_{α∈P} z^{−1}(α)p_{α}, where z(α) = 1^{m_{1}(α)}m_{1}(α)! 2^{m_{2}(α)}m_{2}(α)! ⋯, it follows that \frac{∂h_{r}}{∂p_{r}} = \frac{1}{r}. Also, e^{u(1+h_{1}+···+h_{r−1})} expanded in terms of the power sums using the formula above is independent of p_{r}, so

\begin{aligned}Φ_{r} & = uz^{r}L_{w}^{(r−1)} ⟨(1 − w ∑_{j≥1}(−1)^{j−1}z^{j}p_{j})^{−1} , e^{u(1+h_{1}+···+h_{r−1})}⟩ \\ & = uz^{r}L_{w}^{(r−1)} ⟨1, (1 − w ∑_{j≥1}(−1)^{j−1}z^{j}j \frac{∂}{∂p_{j}} )^{−1} e^{u(1+h_{1}+···+h_{r−1})}⟩ . \end{aligned}

Step 2. Introduce the mapping Θ_{w}: w^{j} ↦ j! w^{j} to express

(1 − w ∑_{j≥1}(−1)^{j−1}z^{j}j \frac{∂}{∂p_{j}} )^{−1}

as an exponential function, and h_{j}’s in terms of the power sums so that the ring theoretic Taylor’s Theorem can be used.

Since (1 − w ∑_{j≥1}(−1)^{j−1}z^{j}p_{j})^{−1} = Θ_{w}e^{w ∑_{j≥1}(−1)^{j−1}z^{j}p_{j}},

Φ_{r} = uz^{r}L_{w}^{(r−1)}Θ_{w} ⟨1, e^{w ∑_{j≥1}(−1)^{j−1}z^{j}j \frac{∂}{∂p_{j}}} e^{u(1+h_{1}+···+h_{r−1})}⟩

The generating series for the complete symmetric functions is ∑_{k≥0} h_{k}t^{k} = ∏_{i=1}^{∞}(1 − tx_{i})^{−1}, so

1 + h_{1} + ⋯ + h_{r−1} = [t^{r−1}]\frac{1}{1 − t} ∏_{i=0}^{∞}(1 − tx_{i})^{−1}

= [t^{r−1}]\frac{1}{1 − t} exp ∑_{i≥1} ln(1 − tx_{i})^{−1}

= [t^{r−1}]\frac{1}{1 − t}e^{p_{1}t+p_{2}t^{2}+···}.

Thus e^{u(1+h_{1}+···+h_{r−1})} = exp (u[t^{r−1}]^{\frac{e^{p_{1}t+p_{2} \frac{t^{2}}{2} +···}}{1−t}} ).

Step 3. Apply Taylor’s Theorem to get

Φ_{r} = uz^{r}L_{w}^{(r−1)}Θ_{w} ⟨1, e^{w ∑_{j≥1}(−1)^{j−1}z^{j}j \frac{∂}{∂p_{j}}} exp (u[t^{r−1}]\frac{e^{p_{1}t+p_{2} \frac{t^{2}}{2} +···}}{1 − t} )⟩

= uz^{r}L_{w}^{(r−1)}Θ_{w} ⟨1, exp (u[t^{r−1}]\frac{e^{(wt+p_{1})+(−2wz^{2}+p_{2}) \frac{t^{2}}{2} +···}}{1 − t} )⟩

= uz^{r}L_{w}^{(r−1)}Θ_{w} ⟨1, exp (u[t^{r−1}]\frac{e^{wzt−wz^{2}t^{2}+···}}{1 − t} )⟩

since the inner product is with 1, all p_{i}, i ≥ 1, are set to 0 in the second argument of the inner product.

We conclude that Φ_{r} = uz^{r}L_{w}^{(r−1)}Θ_{w} exp (u[t^{r−1}]\frac{e^{wzt/(1+zt)}}{1−t} ). □

We remark that the exponential e^{wzt/(1+zt)} is the generating function for Laguerre polynomials. A short proof of the r-Stockhausen problem that is inspired by this analysis is given in [RY, §5]. An explicit formula derived from this expression for the number of r-Stockhausen sequences and a direct combinatorial proof are given in [Y].

5. Combinatorial constructions

We have shown that the generating series for generalized Stockhausen sequences is

Φ_{r+1}(z, u) := ∑_{n,k≥0} c_{r+1}(n, k)z^{k} \frac{u^{n}}{n!}

= uz^{r+1}L_{w}^{(r)}Θ_{w} exp (u[t^{r}]\frac{1}{1 − t} exp \frac{wzt}{1 + zt}) ,

where

L_{w}^{(r)}(f) = \frac{1}{r!} \frac{w^{r}∂^{r}f}{∂w^{r}} |_{w=1}

and Θ_{w} : w^{k} → k!w^{k}.

The combinatorial nature of the transformations leads one to ask whether combinatorial objects and constructions exist for each expression so that one can obtain generalized Stockhausen sequences directly. In this section, we present a series of constructions that has generalized Stockhausen sequences as the final consequence. The set-wise actions of the constructions are suggested by the algebraic analysis, although the element-wise actions (the combinatorial content) have to be supplied. Therefore we define first the set A generated by

A = \frac{1}{1 − w(∑_{i=1}^{n} \frac{zt_{i}}{1+zt_{i}})},

which is a fundamental structure in the series of constructions. Next, we convert the univariate series in t into a multivariate series in t_{1}, t_{2}, …, t_{n} to obtain n non-terminal symbols in the Stockhausen sequences. To this end, we exhibit a bijection between sets which are enumerated by

[\frac{u^{n}}{n!} ] Θ_{w} exp (u[t^{r}]\frac{1}{1 − t} exp \frac{wzt}{1 + zt})

and

[t_{1}^{r}t_{2}^{r} … t_{n}^{r}]\frac{1}{1 − w(∑_{i=1}^{n} \frac{zt_{i}}{1+zt_{i}})} ∏_{i=1}^{n} \frac{1}{1 − t_{i}} .

Once we have all n non-terminal symbols, we give a combinatorial interpretation for the transformation L_{w}^{(r)}. After the application of L_{w}^{(r)} to A, the last step is the placement of r + 1 copies of the terminal symbol to make (r + 1)-Stockhausen sequences.

Step 1. Signed Divided Strings. To construct strings with distinct adjacent elements, an argument involving the principle of inclusion–exclusion can be applied. However, one can also consider signed sets as described in [SW]. The set of signed divided strings is a signed set of strings with dividers such that

(1) different symbols are separated by dividers,

(2) the same symbol appearing in a block may be separated by dividers, (3) no dividers are adjacent, and no string ends with a divider,

(4) the sign of the string is

(−1)^{# (undivided even sub-strings)}.

An example of a typical signed divided string is +t_{1}t_{1}wt_{1}wt_{2}t_{2}wt_{3}wt_{1}, where w marks the divider and t_{1}, t_{2} and t_{3} are symbols.

Let A be the set of strings on n symbols such that a non-empty string begins with a divider. Let the symbols be zt_{1}, zt_{2}, …, zt_{n}, and let w be an ordinary marker for dividers. Then the ordinary generating series for A is

A(w, z, t_{1}, …, t_{n}) = \frac{1}{1 − w(∑_{i=1}^{n} \frac{zt_{i}}{1+zt_{i}})}.

Step 2. A Bijection. We define sets generated by

[t_{1}^{r}t_{2}^{r} … t_{n}^{r}]\frac{1}{1 − w(∑_{i=1}^{n} \frac{zt_{i}}{1+zt_{i}})} ∏_{i=1}^{n} \frac{1}{1 − t_{i}} ,

and

[\frac{u^{n}}{n!} ] Θ_{w} exp (u[t^{r}]\frac{1}{1 − t} exp \frac{wzt}{1 + zt}) ,

and show a bijection between the sets. From the previous section, the series

A(w, z, t_{1}, …, t_{n}) = \frac{1}{1 − w(∑_{i=1}^{n} \frac{zt_{i}}{1+zt_{i}})}

generates all, possibly empty, signed divided strings where a non-empty string begins with a divider marked by w. The multiplication of A by ∏_{i=1}^{n} \frac{1}{1−t_{i}} and the extraction of the coefficient of t_{1}^{r}t_{2}^{r} ⋯ t_{n}^{r} in the result corresponds at the set theoretic level to the concatenation of the signed divided strings in A with t_{1}^{i_{1}}t_{2}^{i_{2}} ⋯ t_{n}^{i_{n}} for 0 ≤ i_{1}, i_{2}, …, i_{n} and the restriction to only those concatenated strings with exactly r t_{i}’s, i = 1, 2, …, n. But this is equivalent to considering the strings in A with no more than r t_{i}’s for i = 1, 2, …, n. Thus we conclude that

[t_{1}^{r}t_{2}^{r} … t_{n}^{r}]\frac{1}{1 − w(∑_{i=1}^{n} \frac{zt_{i}}{1+zt_{i}})} ∏_{i=1}^{n} \frac{1}{1 − t_{i}}

generates all signed divided strings (⊂ A) with no more than r t_{i}’s (i = 1, …, n) in each string.

For

[\frac{u^{n}}{n!} ] Θ_{w} exp (u[t^{r}]\frac{1}{1 − t} exp \frac{wzt}{1 + zt}) ,

or equivalently,

Θ_{w} ([t^{r}]\frac{1}{1 − t} exp \frac{wzt}{1 + zt})^{n} ,

where Θ_{w} is an inverse Laplace transform on w, i. e. Θ_{w}: w^{k} ↦ k! w^{k}, we describe a set generated by the inner expression

([t^{r}]\frac{1}{1 − t} exp \frac{wzt}{1 + zt})^{n}

first, and then apply Θ_{w} combinatorially to the set.

Consider a labelled ordered n-tuple (S_{1}, S_{2}, …, S_{n}) of possibly empty, ordered sets of all possible sizes. That is, given a label set (⊂ N := {1, 2, … }) of size n, label S_{1} with the smallest label, S_{2} with the next label, etc, and S_{n} with the largest one. Every coordinate in S_{i}, i ∈ N_{n}, is also labelled from a label set ⊂ N in the same way. A typical entry of S_{i} has the form (−1)^{k+1}w_{x}(zt)^{k} (k ≥ 1), where x is the label associated with that entry of S_{i}. Let w be an exponential marker for the labels w_{x}’s. When we restrict the number of t’s in each S_{i} to no more than r, then the generating series for S_{i} is

[t^{r}]\frac{1}{1 − t} \frac{w^{|S_{i}|}}{|S_{i}|!} (\frac{zt}{1 + zt})^{|S_{i}|}.

Summing over all |S_{i}| from 0 to ∞, we get

([t^{r}]\frac{1}{1 − t} exp \frac{wzt}{1 + zt})^{n}

as the generating series for the n tuple of tuples. To apply Θ_{w}, or inverse Laplace transform, i. e. removal of labels marked by w, we form signed divided strings in the following way. Take the entry in some S_{x} that has the label w_{1}, and put down the entire entry including its sign as the first segment, w_{1}zt_{i}zt_{i} ⋯ zt_{i} writing t_{i} instead of t if the set S_{x} has the symbol i assigned to it. In the second segment, find some set S_{y} that contains w_{2}, and write w_{2}zt_{j} … zt_{j} if S_{y} has symbol j assigned to it. Continue in a similar manner until the w’s are exhausted. Now combine the signs multiplicatively and erase the subscripts on w to get a signed divided string on n available symbols because there are n S_{x}’s, such that every t_{i} appears no more than r times (since we start out with r or fewer t’s in each S_{x}).

Step 3. Application of L_{w}^{(r)}. Let B be the set of non-empty strings on n symbols such that a non-empty string begins without a divider. Let the symbols be zx_{1}, zx_{2}, …, zx_{n}, and let w be an ordinary marker for dividers. Then the ordinary generating series for B is

B(w, z, x_{1}, …, x_{n}) = \frac{∑{n \atop i=1} \frac{zx_{i}}{1+zx_{i}}}{1 − w(∑_{i=1}^{n} \frac{zx_{i}}{1+zx_{i}})}.

Let ω be a divider. Define ω^{r} × (\frac{∂}{∂ω})^{r}/Σ_{r} (see [GJ, p.36]) to be an operation on the elements of the sets A (as defined in Step 1) and B that marks r distinct dividers in all possible ways regardless of the order in which dividers are marked. (Here Σ_{r} denotes the symmetric group on r elements.) Then

(ω^{r} × (\frac{∂}{∂ω})^{r}/Σ_{r})A ⟶^{∼} Aω̂ \underbrace{Bω̂Bω̂ ⋯ ŵB}_{r B’s}

by induction on r, since

\frac{ω∂}{∂ω} A ⟶^{∼} Aω̂B and \frac{ω∂}{∂ω} B ⟶^{∼} Bω̂B.

Notice that A(1, zx_{1}, …, zx_{n}) (respectively B(1, zx_{1}, …, zx_{n})) is the ordinary generating series for possibly empty (respectively non-empty) strings on n symbols zx_{1}, …, zx_{n} such that adjacent symbols are distinct. Therefore, the operator L_{w}^{(r)} applied to A gives the generating series for (Ã, B̃, …, B̃) with r B̃’s, where Ã (respectively B̃) is the result of ignoring dividers in the set A (respectively B). This is an (r + 1)-tuple of strings such that adjacent symbols are distinct, and the first string (but no others) may be empty.

In short, the purpose of L_{w}^{(r)} is first to mark ω’s and secondly get rid of strings that have at least one undivided sub-string of length greater than or equal to 2 (by setting w = 1 algebraically or ignoring dividers, ω’s, set theoretically).

Step 4. Placement of the terminal symbol. Given n + 1 symbols such that the terminal symbol occurs r + 1 times, let u be an exponential marker for the available symbols, z be an ordinary marker for the length of the string, and t_{1}, …, t_{n} be ordinary markers for the occurrence of the non-terminal symbols, then

uz^{r+1}L_{w}^{(r)}Θ_{w} exp (u[t^{r}]\frac{1}{1 − t} exp \frac{wzt}{1 + zt})

is the generating series for T ∗ S (see [GJ, p. 163] for the definition of ∗), where T is the set containing r + 1 copies of the terminal symbol t, and S is (A|_{w=1}, B|_{w=1}, …, B|_{w=1}) with r B’s. The ∗ product is used because the symbols t, t_{1}, …, t_{n} form the label set {1, 2, …, n, n + 1}. To obtain Stockhausen sequences from T ∗ S, place zt in front of each B, and at the final position, then remove all commas, and let z commute with the t’s. Therefore, z marks the length of the string, and the string is faithfully represented by the t’s.

Acknowledgements

The author would like to thank L. Butler and D. M. Jackson for teaching her the theory of symmetric functions and D. M. Jackson for guiding her through the symmetric maze, and comments that have improved the presentation of the paper. The author would also like to thank the reviewer for many helpful suggestions.

References

[G] I. Gessel, Symmetric functions and P-recursiveness, J. Combinatorial Theory 53 (1990), 257–285.

[GJ] I. P. Goulden & D. M. Jackson, Combinatorial Enumeration, Wiley Interscience, New York, 1983.

[M] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Edition 1, Clarendon Press, Oxford, 1979.

[RY] R. C. Read & L. Yen, A Note on The Stockhausen Problem, J. Combin. Theory Ser. A (to appear).

[SW] D. Stanton & D. White, Constructive Combinatorics, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1986.

[S] K. Stockhausen, nr. 7 Klavierstück XI, 12654 LW, Universal Edition, London, 1979.

[Y] L. Yen, A direct combinatorial proof for Stockhausen’s problem, Research Report, University of Waterloo, Dept. of Combinatorics & Optimization (1995), pp. 7.