Permutations and Combinations of Colored Multisets

Jocelyn Quaintance Department of Mathematics West Virginia University Morgantown, WV 26506 USA

                 jquainta@math.wvu.edu

Harris Kwong SUNY Fredonia Department of Mathematical Sciences State University of New York at Fredonia Fredonia, NY 14063 USA

                  kwong@fredonia.edu

Abstract

Given positive integers m and n, let S_{n}^{m} be the m-colored multiset {1^{m}, 2^{m}, …, n^{m}}, where i^{m} denotes m copies of i, each with a distinct color. This paper discusses two types of combinatorial identities associated with the permutations and combinations of S_{n}^{m}. The first identity provides, for m ≥ 2, an (m − 1)-fold sum for \binom{mn}{n}. The second type of identities can be expressed in terms of the Hermite polynomial, and counts colorsymmetrical permutations of S_{n}^{2}, which are permutations whose underlying uncolored permutations remain fixed after reflection and a permutation of the uncolored numbers.

1 Introduction

The primary object of study in this paper is a certain class of multisets, namely the m-colored multisets S_{n}^{m} = {1^{m}, 2^{m}, …, n^{m}}, where i^{m} denotes m copies of i with distinct colors. Where does S_{n}^{m} naturally arise in combinatorics? Suppose we want to count the permutations of S_{n}^{m} of length n which consist of distinct integers. First, we ignore the colors of the integers and notice we have a set of n distinct uncolored numbers. There are n! ways to arrange these n uncolored numbers. We then decide what color to paint such numbers. Since there are m colors, this color choice gives us a factor of m^{n}, for a total of m^{n}n! such permutations. In [2], the authors studied properties of multifactorials n!_{m}, where for a positive integer m, n!_{m} = n(n − m)!_{m}, with 0!_{m} = 1. From this recursive definition, we can show that (mn)!_{m} = m^{n}n!. Therefore, the m-colored multiset provides a combinatorial meaning for well-known multifactorial identity.

This observation leads us to wonder if m-colored multisets could provide nice combinatorial proofs for other well known identities. In the process of investigating this question, the authors found two general classes of identities that are readily proven in the context of S_{n}^{m}. The first type of identity provides a (m − 1)-sum formula for the binomial coefficient \binom{mn}{n}. This result is Theorem 3. The second type of identity counts color-symmetrical permutations of S_{n}^{2}, where a color-symmetrical permutation of S_{n}^{2} is a colored permutation whose underlying set partition structure is fixed via vertical reflection. The color-symmetrical permutation identities occur in Section 3 have connections with Hermite polynomials. The techniques used to prove the identities of Section 3 recall the methodology the first author used to enumerate symmetrically inequivalent two dimensional proper arrays [5].

2 Enumerating Combinations and Permutations

Let i, m, and n be positive integers. Let i^{m} denote m copies of i, with the property that each copy of i has a distinct color. Let S_{n}^{m} be the m-colored multiset {1^{m}, 2^{m}, …, n^{m}}. For examples,

S_{4}^{2} = {1, 1, 2, 2, 3, 3, 4, 4}, and S_{4}^{3} = {1, 1, 1, 2, 2, 4, 3, 3, 3, 4, 4, 4}.

Note that |S_{n}^{m}| = mn. If we consider different colored copies of i as distinct, the number of permutations of S_{n}^{m} is (mn)!. From this simple observation, we are able to derive an identity for (mn)! involving an (m − 1)-fold summation. We will now assume m ≥ 2. The proof of this identity utilizes simple combinatorial arguments. We demonstrate the argument for the case of m = 2, and then state the general result for m ≥ 2.

Consider S_{n}^{2} = {1^{2}, 2^{2}, …, n^{2}}, where each number occurs in red and blue. The number of permutations of S_{n}^{2} is (2n)!. We think of a permutation of S_{n}^{2} as a horizontal row of 2n elements arranged in 2n slots. Our analysis proceeds by carefully analyzing the manner in which we fill in the first half, or the first n slots, of the permutation. We say a number i, where 1 ≤ i ≤ n, has a repetition in the first half if and only if both the red i and the blue i can be found there. Let s be the number of repetitions that occur in the first half of the permutation. Note that 0 ≤ s ≤ [\frac{n}{2}]. For each s, the number of ways to fill the first n slots can be computed in three steps (see Figure 1).

1. Pick the locations, in the first half of the permutation, where the repetitions will occur. The number of ways to select s pairs of slots from the n slots is

∏_{j=1}^{s} \frac{\binom{n−2j+2}{2}}{s!} = \frac{n!}{s!(n − 2s)!2^{s}} .

2. Pick the numbers to fill these s pairs of slots. In order to do this, we first form an s-permutation from D = {1, 2, …, n}. The k^{th} number in this s-permutation will fill the k^{th} pair of slots. For each pair of slots, we must decide if we want red first, then blue, or vice versa. Hence, the number of ways to fill these s pairs of slots is \frac{n!}{(n−s)!}2^{s}.

3. Fill the remaining n − 2s spaces in the first half of the permutation with numbers that have not been used in Step 2. The number of ways to do this is \frac{(n−s)!}{s!}2^{n−2s}.

[figure: Step 1:; X; X]

Step 2: 2 2 4  4

Step 3: 2 2 4  4 3 Remaining numbers: 1, 1, 3, 5, 5.

Figure 1: Constructing the first half of a permutation of S_{5}^{2}.

After completing these three steps, we have n colored numbers remaining. They fill the second half of the permutation in n! ways. Varying s and combining the aforementioned combinatorial reasoning proves Lemma 1.

Lemma 1. Let n be a nonnegative integer. Then,

(2n)! = n! ∑_{s=0}^{[ \frac{n}{2} ]} \frac{n!n!2^{n−2s}}{s!s!(n − 2s)!} = (n!)^{2} ∑_{s=0}^{[ \frac{n}{2} ]} \binom{n}{s}\binom{n − s}{n − 2s}2^{n−2s}.  (1)

Remark 2. Lemma 1 provides a combinatorial proof of Equation (3.99) in [1] since we may rewrite Equation (1) as follows.

\binom{2n}{n} = ∑_{s=0}^{[ \frac{n}{2} ]} \frac{n!2^{n−2s}}{s!s!(n − 2s)!}

= ∑_{s=0}^{[ \frac{n}{2} ]} \frac{n!}{(2s)!(n − 2s)!} · \frac{(2s)!}{s!s!}2^{n−2s}

= ∑_{s=0}^{[ \frac{n}{2} ]} \binom{n}{2s}\binom{2s}{s}2^{n−2s}.

Here is an alternative argument for deriving Equation (1). Let D = {1, 2, …, n}. The number of permutations of S_{n}^{2} is (n!)^{2} times the number of ways to select the n colored numbers which occur in the first half. Let s denote the number of numbers that occur twice, that is, both the red and blue copies are selected. We note that 0 ≤ s ≤ [\frac{n}{2}]. There are \binom{n}{s} ways to select these s numbers. From the remaining n − s numbers in D, there are \binom{n−s}{n−2s} ways to select n − 2s uncolored numbers, where each uncolored number has a choice of two colors to chose from. Summing over s yields the right side of Equation (1).

We are now in a position to generalize Lemma 1. We will only describe how to generalize the second argument. Those readers interested in the generalization of the first argument may contact the authors. We think of a permutation of S_{n}^{m} as a horizontal arrangement of mn elements into mn slots. Subdivide, from left to right, these mn slots into m sections, each containing n slots. We analyze the number of repetitions that occur the first section, or the leftmost n slots, of the permutation.

We say a number has a repetition of type k if it appears exactly k times in the first section. Let s_{k} be the number of numbers of type k. The number of ways to choose n colored numbers to fill the first section of the permutation is clearly \binom{mn}{n}. Alternatively, we could choose these n colored numbers from D = {1, 2, …, n} as follows. First, we select the type m numbers, then the type m − 1 numbers, and so forth. There are \binom{n}{s_{m}} ways to chose the type m numbers, each of which will use up all m colors. In general, after numbers of types m through k + 1 are chosen, we have n − ∑_{i=k+1}^{m} s_{i} numbers left in D from which to select s_{k} numbers of type k. Each such number can be colored in \binom{m}{k} ways. This argument proves the following theorem.

Theorem 3. Let n be a positive integer. Let m be a positive integer, m ≥ 2. Then,

\binom{mn}{n} = ∑_{{s_{1},s_{2},...,s_{m}≥0 \atop s_{1}+2s_{2}+···+ms_{m}=n}} ∏_{k=1}^{m} \binom{n − ∑_{i=k+1}^{m} s_{i}}{s_{k}}\binom{m}{k}^{s_{k}}.  (2)

Two important non-trivial examples of Theorem 3 occur when m = 3 and m = 4. Let m = 3, and s_{3} = s, and s_{2} = t. Then, Equation (2) becomes

\binom{3n}{n} = ∑_{s=0}^{[ \frac{n}{3} ]} ∑_{t=0}^{[ \frac{n−3s}{2} ]} \binom{n}{3s + 2t}\binom{3s + 2t}{s, t, 2s + t}3^{n−3s−t}.

If m = 4, Equation (2) becomes

\binom{4n}{n} = ∑_{s_{4}=0}^{[ \frac{n}{4} ]} ∑_{s_{3}=0}^{[ \frac{n−4s_{4}}{3} ]} ∑_{s_{2}=0}^{[ \frac{n−4s_{4}−3s_{3}}{2} ]} A\binom{n}{n − 4s_{4} − 3s_{3} − 2s_{2}}\binom{4s_{4} + 3s_{3} + 2s_{2}}{s_{4}, s_{3}, s_{2}, s_{2} + 2s_{3} + 3s_{4}},

where,

A = \frac{4^{n−4s_{4}−3s_{3}−2s_{2}}(4 · 3 · 2)^{s_{3}}(4 · 3)^{s_{2}}}{(3!)^{s_{3}}(2!)^{s_{2}}} .

On closer inspection of the proof of Theorem 3, we see that argument describes how to select any l colored numbers from S_{m}^{n}. Thus, we have actually proven the next result.

Theorem 4. Let n and m be positive integers. Let l be a positive integer such that 1 ≤ l ≤ mn. Then,

\binom{mn}{l} = ∑_{{s_{1},s_{2},...,s_{m}≥0 \atop s_{1}+2s_{2}+···+ms_{m}=l}} ∏_{k=1}^{m} \binom{n − ∑_{i=k+1}^{m} s_{i}}{s_{k}}\binom{m}{k}^{s_{k}}.

3 Color-Symmetrical Permutations of S_{n}^{2}

We now study a special kind of reflective symmetry in the permutations of S_{n}^{2}. Think of a permutation σ of S_{n}^{2} as a way to fill the 2n squares of a 1 × 2n rectangular array, and associate with it a partition of {1, 2, …, 2n} in the form π(σ) = {S_{1}, S_{2}, …, S_{n}} such that S_{i} is the 2-subset containing the two positions occupied by i. We call π(σ) the set partition associated with σ. We say a permutation is color-symmetrical if, upon reflection about the vertical line through its middle, the resulting permutation has the same collection of 2-subsets in its associated set partition. For example, the permutation p_{2} in Figure 2 is obtained from p_{1} by reflection. Notice that

π(p_{1}) = π(p_{2}) = {{2, 6}, {5, 9}, {3, 4}, {7, 8}, {1, 10}}.

Therefore p_{1} is color-symmetrical, and, so is p_{2}.

p_{1}: 5 1 3 3 2 1 4 4 2 5  ^{p_{2}: 5 2 4 4 1 2 3 3 1 5}

Figure 2: Two color-symmetrical permutations of S_{5}^{2}.

Another way to understand this notion of color-symmetry is as follows. Let p_{2} be the permutation obtain from p_{1} via reflection. The reflection can be viewed as a function ϕ : S_{n}^{2} → S_{n}^{2} such that ϕ(p_{1}) = p_{2}. We say that σ is color-symmetrical if, for each i, ϕ(i^{2}) = j^{2}, for some j (recall that i^{2} means the two copies of i colored red and blue). In other words, p_{1} is color-symmetrical if one could obtain p_{2} by renaming the colored numbers while preserving the associated set partition. Due to symmetry, if ϕ(i^{2}) = j^{2}, we also ϕ(j^{2}) = i^{2}. So in effect we are interchanging i^{2} with j^{2} in the reflection. For example, in the two permutations p_{1} and p_{2} in Figure 2, the numbers 1 and 2 are interchanged, and so are 3 and 4. Note that it is possible for ϕ(i^{2}) = i^{2}, as are the two copies of 5 in Figure 2.

The idea of fixing set partition structure and interchanging labels was described by Ross Drewe in sequence \underline{A047974} of the OEIS [3]. The difference between our context, and that of Drewe’s, is that our set label, namely the numbers, contain an extra parameter of color.

Our goal is to describe a formula for SS_{n}^{2}, the number of color-symmetrical permutations of S_{n}^{2}. Our strategy is to divide the 1×2n rectangle into two halves, each with n squares. We fill the first half, or the leftmost n squares, with an arbitrary colored permutation of length n derived from the elements of S_{n}^{2}. We then use reflective symmetry to complete the second half of the 1 × 2n rectangle. Since reflective symmetry must preserve the set partition structure, there are three types of numbers that can occur in the first half of the 1 × 2n rectangle. These possibilities are the same possibilities the first author used to calculate H_{2m} in [5]. In particular,

• A number could map to a number that does not occur in the first half.

• A number could map to itself under reflection.

• A number could map to another number which also appears in the first half. If this happens, we say a first-half interchange (or simply FHI) occurs.

Figure 3 illustrates these three cases for a color-symmetric permutation of S_{5}^{2}.

Filling in the first half: 5 1 2 1 3

Vertical reflection, with 1 ↔ 4, 2 ↔ 3, 5 ↔ 5:  5 1 2 1 3 2 4 3 4 5

Figure 3: Constructing a color-symmetrical permutation of S_{5}^{2}.

Going through these three possibilities, we are able to derive a formula that counts colorsymmetrical permutations of S_{n}^{2}, as follows.

1. Determine, in the first half, where the repetitions occur. Under reflection, a repetition must map to a different repetition in the second half. We arbitrarily assign a color scheme to each repetition. If s is the number of repetitions that occur in the first n squares, the number of ways to complete these s double repetitions in a colorsymmetrical manner is

\frac{n!}{2^{s}s!(n − 2s)!} · \frac{n!2^{2s}}{(n − 2s)!}.

2. There are now n − 2s spaces in the first half that remain to be filled. We must fill these n − 2s spaces with a colored permutation that does not have any repetitions. The number of ways to do that is (n − 2s)!2^{n−2s}.

3. Determine where the FHIs occur. Notice that any numbers that do not form a FHI pair must map to themselves. Let t be the number of FHI pairs that occur among the n − 2s non-repeating positions in the first n slots. The number of ways to place these t FHI pairs is \frac{(n−2s)!}{2^{t}t!(n−2s−2t)!}.

Lemma 5. For n ≥ 1,

SS_{n}^{2} = ∑_{s=0}^{[ \frac{n}{2} ]} ∑_{t=0}^{[ \frac{n−2s}{2} ]} \frac{n!n!2^{n−s−t}}{s!t!(n − 2s − 2t)!},

By standard convolution arguments, it is easy to show that

∑_{n=0}^{∞} SS_{n}^{2} \frac{x^{n}}{(n!)^{2}} = ∑_{n=0}^{∞} ∑_{{r,s,t≥0 \atop r+2s+2t=n}} \frac{(2x^{2})^{s}}{s!} · \frac{(2x^{2})^{t}}{t!} · \frac{(2x)^{r}}{r!} = e^{2x^{2}} · e^{2x^{2}} · e^{2x} = e^{4x^{2}+2x}. (3)

We can write the right hand side of Equation (3) as

e^{4x^{2}+2x} = ∑_{k,j=0}^{∞} \frac{(4x^{2})^{k}}{k!} · \frac{(2x)^{j}}{j!} = ∑_{k,j=0}^{∞} \frac{(2x)^{2k+j}}{k!j!} = ∑_{j=0}^{∞} ∑_{k=0}^{[ \frac{j}{2} ]} \frac{2^{j}}{k!(j − 2k)!} x^{j}.  (4)

Comparing the coefficients in (3) and (4) yields the next result.

Lemma 6. For n ≥ 1,

SS_{n}^{2} = ∑_{k=0}^{[ \frac{n}{2} ]} \frac{n!n!2^{n}}{k!(n − 2k)!} = 2^{n}n! ∑_{k=0}^{[ \frac{n}{2} ]} \binom{n}{k}\binom{n − k}{k}k!.  (5)

We should note that the right sum of Equation (5) is reminiscent of H_{n}(x), the Hermite polynomial of degree n, whose explicit formula is [1]

H_{n}(x) = ∑_{k=0}^{[ \frac{n}{2} ]}(−1)^{k}\binom{n}{k}\binom{n − k}{k}k!(2x)^{n−2k}.  (6)

If we let x = \frac{i}{2} in Equation (6), we obtain another representation for SS_{n}^{2}.

Corollary 7. For n ≥ 1,

SS_{n}^{2} = (−2i)^{n}n!H_{n} (\frac{i}{2}) .

4 Three Variations on SS_{n}^{2}

When we defined the notion of a color-symmetrical permutation of S_{n}^{2}, we only concerned ourselves with fixing the set partition associated with the permutation. The color scheme for each part of the set partition was arbitrarily assigned, and hence played no role in determining whether a permutation of S_{n}^{2} was color-symmetric. We now want to put restrictions on our color scheme.

The most natural restriction is to require colors to map to themselves whenever possible. Recall that for S_{n}^{2} = {1^{2}, 2^{2}, …, n^{2}}, we have one red i and one blue i for each i. The aforementioned color restriction would require that if the set partition structure maps i to j, where 1 ≤ i < j ≤ n, we also require that a red i maps to a red j, and hence, a blue i maps to a blue j.

Note that there is no color restriction on i if the reflection maps i to itself. One possibility for color restriction involves the repetitions in the first half of the 1 × 2n rectangle, since

1 1 3 3 2 2 1 1 3 3 2 2 1 1 3 3 2 2 1 1 3 3 2 2
1 1 3 3 2 2 1 1 3 3 2 2 1 1 3 3 2 2 1 1 3 3 2 2

No color restrictions

1 1 3 3 2 2 1 1 3 3 2 2 1 1 3 3 2 2 1 1 3 3 2 2

Color restricted

Figure 4: Color-symmetrical permutations of S_{3}^{2} with and without color restrictions.

these repetitions have an arbitrarily assigned color scheme. Figure 4 illustrates how the color restriction (or lack thereof) applies to a subset of color-symmetrical permutation of S_{3}^{2} which has repetitions in the first half.

The only change in the formula associated with Step 1 in Section 3 is that the factor 2^{2s} in the numerator of the second fraction becomes a 2^{s}. Note that Steps 2 and 3 stay the same. We find the following double sum formula for ŜS_{n}^{2}, the number of color-symmetrical permutations of S_{n}^{2} whose double repetition blocks obey the color restriction.

Lemma 8. For n ≥ 1,

ŜS_{n}^{2} = ∑_{s=0}^{[ \frac{n}{2} ]} ∑_{t=0}^{[ \frac{n−2s}{2} ]} \frac{n!n!2^{n−2s−t}}{s!t!(n − 2s − 2t)!}.

Using standard convolution arguments, we can show that

∑_{n=0}^{∞} ŜS_{n}^{2} \frac{x^{n}}{(n!)^{2}} = e^{3x^{2}+2x}.

With the appropriate changes to the argument used to prove Lemma 6, we can prove the following result.

Lemma 9. For n ≥ 1,

ŜS_{n}^{2} = ∑_{k=0}^{[ \frac{n}{2} ]} \frac{n!n!3^{k}2^{n}}{2^{2k}k!(n − 2k)!} = 2^{n}n! ∑_{k=0}^{[ \frac{n}{2} ]} \binom{n}{k}\binom{n − k}{k} (\frac{3}{4})^{k} k!.

An alternative proof to Lemma 9, which could also prove Lemma 8, is as follows.

ŜS_{n}^{2} = ∑_{k=0}^{[ \frac{n}{2} ]} \frac{2^{n−k}(n!)^{2}}{(n − 2k)!} ∑_{{s,t≥0 \atop s+t=k}} \frac{1}{s!t!2^{s}}

= ∑_{k=0}^{[ \frac{n}{2} ]} \frac{2^{n−k}(n!)^{2}}{k!(n − 2k)!} ∑_{s=0}^{k} \binom{k}{s}\frac{1}{2^{s}}

= ∑_{k=0}^{[ \frac{n}{2} ]} \frac{2^{n−k}(n!)^{2}}{k!(n − 2k)!} (\frac{3}{2})^{k}

= 2^{n}n! ∑_{k=0}^{[ \frac{n}{2} ]} \binom{n}{k}\binom{n − k}{k} (\frac{3}{4})^{k} .

We should also note that we can use the Hermite polynomial to calculate ŜS_{n}^{2}.

Corollary 10. For n ≥ 1,

ŜS_{n}^{2} = (−i\sqrt{3})^{n}n!H_{n} (\frac{i}{\sqrt{3}}) .

The second way to place the color restriction is in a FHI pair. This is done in the following manner. Let 1 ≤ i < j ≤ n. Suppose both i and j appear in the first n slots. Furthermore, suppose vertical reflection maps i to j. If we determine which color of i occurs in the first n slots, we have also determined the color scheme for j. We demonstrate in Figure 5 the color restriction for those color-symmetrical permutations of S_{3}^{2} which have a FHI.

1 2 3 3 1 2 1 2 3 3 1 2 1 2 3 3 1 2 1 2 3 3 1 2
1 2 3 3 1 2 1 2 3 3 1 2 1 2 3 3 1 2 1 2 3 3 1 2

No color restrictions

1 2 3 3 1 2 1 2 3 3 1 2 1 2 3 3 1 2 1 2 3 3 1 2

Color restricted

Figure 5: Color-symmetrical permutations of S_{3}^{2} with 1 and 2 interchanged.

We construct an isomorphism between those color-symmetrical permutations of S_{n}^{2} with color restriction on the repetitions and those with color restriction on the interchanges, as follows. For each pair of slots where a repetition occurs in the first half of the permutation, switch the second colored number with its reflective image. This operation changes a repetition into a FHI. This procedure is reversible, that is, it maps a FHI to a repetition .

For example, this isomorphism maps the first four permutations in Figure 4 to the first four permutations in Figure 5 (and vice versa). If we let S̃S_{n}^{2} be the number of color-symmetrical permutations of S_{n}^{2} whose FHIs obey the color restriction, the previous reasoning leads to our next lemma.

Lemma 11. Let S̃S_{n}^{2} be as previously defined. Then,

S̃S_{n}^{2} = ŜS_{n}^{2} = ∑_{s=0}^{[ \frac{n}{2} ]} ∑_{t=0}^{[ \frac{n−2s}{2} ]} \frac{n!n!2^{n−2s−t}}{s!t!(n − 2s − 2t)!}.  (7)

We could also derive Equation (7) by carefully analyzing how we place the FHI pairs, and their associated color scheme, in the first half of the permutation. Details of this method are available upon request from the authors.

For the third variation, we will place the color restriction on both the repetitions and the FHI pairs. Combining the techniques for the previous two variations, we obtain the following result.

Lemma 12. Let {... \atop SS}_{n}^{2} be the number of color-symmetrical permutations of S_{n}^{2} which have the color restriction on repetitions and the interchange pairs. Then,

{... \atop SS}_{n}^{2} = ∑_{s=0}^{[ \frac{n}{2} ]} ∑_{t=0}^{[ \frac{n−2s}{2} ]} \frac{n!n!2^{n−2s−2t}}{s!t!(n − 2s − 2t)!}.

By applying standard convolution arguments, we find

∑_{n=0}^{∞} {... \atop SS}_{n}^{2} \frac{x^{n}}{(n!)^{2}} = e^{2x^{2}+2x}.

The next result is obtained from an argument similar to that of Lemma 9.

Lemma 13. For n ≥ 1,

{... \atop SS}_{n}^{2} = ∑_{k=0}^{[ \frac{n}{2} ]} \frac{n!n!2^{n−k}}{k!(n − 2k)!} = 2^{n}n! ∑_{k=0}^{[ \frac{n}{2} ]} \binom{n}{k}\binom{n − k}{k} (\frac{1}{2})^{k} k!.  (8)

Corollary 14. For n ≥ 1,

{... \atop SS}_{n}^{2} = (−i\sqrt{2})^{n}n!H_{n} (\frac{i}{\sqrt{2}}) .

We end this section with a table that records the values of SS_{n}^{2}, ŜS_{n}^{2} = S̃S_{n}^{2}, and {... \atop SS}_{n}^{2} for 1 ≤ n ≤ 8.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ SS_{n}^{2} & 2 & 24 & 336 & 9600 & 311040 & 15252480 & 840591360 & 61281239040 \\ ŜS_{n}^{2} & 2 & 20 & 264 & 6432 & 191040 & 8081280 & 401990400 & 25439016960 \\ {... \atop SS}_{n}^{2} & 2 & 16 & 192 & 3840 & 99840 & 3502080 & 149667840 & 7865946880 \end{matrix}

Table 1: Values for SS_{n}^{2}, ŜS_{n}^{2} = S̃S_{n}^{2}, and {... \atop SS}_{n}^{2}.

5 Closing Remarks and Open Questions

In this paper, we have discussed two classes of identities which are readily proven using colored permutations and colored combinations. The first such identity is, for m ≥ 2, an (m − 1)-fold sum for \binom{mn}{n}. The second class of identities enumerates the color-symmetrical permutations of the 2-colored multiset S_{n}^{2}. It is natural to ask for a generalization in S_{n}^{m}. Currently, the authors are working on the cases of m = 3 and m = 4. There are two basic differences between the m = 2 situation and the m = 3 case. When m = 3, no number can be mapped to itself under vertical reflection. Also, one must analyze the case of even n separately from odd n.

Another possible topic for future research involves arranging the colored permutations of S_{n}^{m} into an m × n rectangular grid, and then using a symmetry operation of the m × n rectangle to enumerate those colored permutations whose set partition structure is fixed with respect to this symmetry operation. Such an enumeration will rely on the techniques the first author used to count the symmetrical inequivalent m × n × p letter representations [5].

Instead of using the colored multiset S_{n}^{m}, we could relate the problems to the set [mn] = {1, 2, …, mn} by matching the integer i colored k from S_{n}^{m} with the integer (i − 1)m + k from [mn]. Essentially we are grouping the integers from S_{n}^{m} according to their values, and within the same value, lining up the integers according to their colors.

Of course, we can also match the integer i colored k from S_{n}^{m} with the integer (k −1)n+i from [mn]. This time, all the integers of the same color are grouped together, and within the same color, the integers are lined up in ascending order.

These two correspondences could lead to other questions. For instance, the symmetry in the permutations can be defined according to certain number-theoretic properties. These symmetries may be rather different from what we have discussed above. The options are plentiful, and we invite the readers to explore them.

6 Acknowledgment

The authors would like to thank the anonymous referee for the suggestions that have improved the exposition in this paper.

References

[1] H. W. Gould, Combinatorial Identities, Revised Edition, Morgantown, WV, 1972.

[2] H. W. Gould and J. Quaintance, Double fun with double factorials, preprint, April 2009.

[3] N. J. Sloane, Online Encyclopedia of Integer Sequences,

   http://www.research.att.com/njas/sequences/.

[4] J. Quaintance, Combinatoric enumeration of two-dimensional proper arrays, Discrete Math. 307 (2007), 1844–1864.

[5] J. Quaintance, Letter representations of m × n × p proper arrays, Australas. J. Combin. 38 (2007), 289–308.

2000 Mathematics Subject Classification: Primary 05A05; Secondary 05A15, 05A19, 33C45. Keywords: permutations, combinations, colored multisets, Hermite polynomials.

(Concerned with sequence \underline{A047974}.)

Received June 22 2009; revised versions received July 3 2009; November 9 2009; December 21 2009; February 18 2010. Published in Journal of Integer Sequences, February 18 2010.

Return to Journal of Integer Sequences home page.