On q-Analogs of Recursions for the Number of Involutions and Prime Order Elements in

Symmetric Groups

Max B. Kutler Department of Mathematics Harvey Mudd College 301 Platt Boulevard Claremont, CA 91711 USA

                    mkutler@hmc.edu

C. Ryan Vinroot Department of Mathematics College of William and Mary P. O. Box 8795 Williamsburg, VA 23187 USA

                  vinroot@math.wm.edu

Abstract

The number of elements whose square is the identity in the symmetric group S_{n} is recursive in n. This recursion may be proved combinatorially, and there is also a nice exponential generating function for this sequence. We study q-analogs of this phenomenon. We begin with sums involving q-binomial coefficients which come up naturally when counting elements in finite classical groups which square to the identity, and we obtain a recursive-like identity for the number of such elements in finite special orthogonal groups. We then study a q-analog for the number of elements in the symmetric group whose pth power is the identity, for some fixed prime p. We find an Eulerian generating function for these numbers, and we prove the q-analog of the recursion for these numbers by giving a combinatorial interpretation in terms of vector spaces over finite fields.

1 Introduction

Let S_{n} denote the symmetric group on the first n positive integers, and let T_{n} be the number of elements g in S_{n} such that g^{2} is the identity permutation. Chowla, Herstein, and Moore [2] studied the sequence \{T_{n}\} (\underline{A000085}), and they began by observing that it is recursive. In particular, T_{0} = T_{1} = 1 (where we let S_{0} and S_{1} be trivial groups), and for n ≥ 1,

T_{n+1} = T_{n} + nT_{n−1}.  (1)

There is a direct combinatorial argument that gives (1). Namely, an element in S_{n+1} whose square is the identity either fixes the point n + 1, the number of which is T_{n}, or moves n + 1. In the latter case, n + 1 can be paired with one of the n other points to form a transposition, which may be combined with a permutation of the remaining n − 1 points whose square is the identity, giving nT_{n−1} such elements.

Another property of the sequence {T_{n}} noticed by Chowla, Herstein, and Moore [2], is that it has a particularly nice exponential generating function, in that we have

∑_{n=0}^{∞} \frac{T_{n}}{n!} x^{n} = e^{x+x^{2}/2}.

Chowla, Herstein, and Moore [2] applied the above properties of the numbers T_{n} to obtain asymptotic formulas in n for T_{n}/T_{n−1} and T_{n}, as well as several divisibility properties of T_{n}. Jacobsthal [8] studied similar properties of the number of elements in S_{n} of order some fixed prime (which we discuss in Section 4.1); Chowla, Herstein, and Scott [3] gave an exponential generating function for the number of elements g of S_{n} that satisfy g^{d} = 1 for any fixed positive integer d; and Moser and Wyman [10] obtained further results on asymptotic formulas for these quantities. More recently, these ideas have been applied to study related exponential generating functions for larger classes of groups, such as in the papers of Chigira [1] and Müller [11].

The purpose of this paper is to study q-analogs of recursions similar to (1). In Section 2, we introduce properties of the q-binomial coefficients. In Section 3, we study sums involving q-binomial coefficients that are related to counting elements in finite classical groups whose square is the identity. We prove a recursive-like formula for these numbers in Theorem 5, and we apply this to obtain an interesting result on the number of order two elements in finite special orthogonal groups in Corollary 6.

In Section 4, we turn to the problem of counting elements g in the symmetric group S_{n} which satisfy g^{p} = 1, for some fixed prime p (yielding the sequence \underline{A052501} when p = 5). Section 4.1 summarizes the classical results on this problem. In Section 4.2, we give a q-analog for these numbers, for which we give a combinatorial interpretation in terms of 𝔽_{q}-vector spaces (Proposition 7) and an Eulerian generating function (Proposition 8). We then prove Theorem 9, a recursive-like formula for these numbers. Finally, in Section 4.3, we specialize to the case p = 2, and relate our results to other results on involutions in the symmetric groups.

2 Properties of q-binomial coefficients

Let q denote a parameter different from 1. For the sake of combinatorial interpretation it will often be useful to think of q as the power of some prime. For any positive integer n, we let [n] denote the nth q-integer, defined as

[n] = q^{n−1} + q^{n−2} + ⋯ + q + 1 = \frac{q^{n} − 1}{q − 1}.

The q-integer [n] is an example of a q-analog of an expression, since we have lim_{q→1}[n] = n. We define the q-factorial of the integer n ≥ 0, denoted [n]!, recursively as

[n]! = \begin{cases}1, & if n = 0; \\ [n][n − 1]!, & if n > 0. \end{cases}

Once we have the q-factorial, we may define the q-binomial coefficients in a natural way. That is, if n and k are non-negative integers with n ≥ k, we define \binom{n}{k}_{q} as

\binom{n}{k}_{q} = \frac{[n]!}{[k]![n − k]!}.  (2)

We recognize the q-binomial coefficient as a q-analog of the classical binomial coefficient since we have lim_{q→1} \binom{n}{k}_{q} = \binom{n}{k}.

The q-binomial coefficient has an important combinatorial interpretation when q is the power of a prime. In this case, \binom{n}{k}_{q} is equal to the number of k-dimensional subspaces of an n-dimensional vector space over the finite field 𝔽_{q} with q elements [13, Proposition 1.3.18].

Note that it follows immediately from (2) that we have

\binom{n}{k}_{q} = \binom{n}{n − k}_{q}.  (3)

The q-binomial coefficients have many other properties which are very similar to those of the classical binomial coefficients, and these properties can be proven using the definition (2) directly, as well as bijectively in terms of 𝔽_{q}-vector spaces.

The following result is the q-Pascal identity for the q-binomial coefficients, which follows quickly from (2). In a bijective proof of the Proposition 1, the key observation is that in an n-dimensional 𝔽_{q}-vector space V, the number of k-dimensional subspaces of V which are not contained in some fixed (n − 1)-dimensional subspace of V is exactly q^{n−k}\binom{n−1}{k−1}_{q}.

Proposition 1. The q-binomial coefficients satisfy the following property, when n, k ≥ 1:

\binom{n}{k}_{q} = \binom{n − 1}{k}_{q} + q^{n−k}\binom{n − 1}{k − 1}_{q}.

It follows from Proposition 1 and an induction argument that the q-binomial coefficients are always polynomials in q. The next result is also most directly obtained by the definition (2), although an 𝔽_{q}-vector space proof may be obtained by induction on d.

Proposition 2. The q-binomial coefficients satisfy the following property, for any d ≥ 1, and any n and k such that n ≥ k ≥ d:

[k][k − 1] ⋯ [k − d + 1]\binom{n}{k}_{q} = [n][n − 1] ⋯ [n − d + 1]\binom{n − d}{k − d}_{q}.

Finally, define a q-analog of the exponential function as e_{q}^{x} = ∑_{j=0}^{∞} \frac{x^{j}}{[j]!}. If \{A_{n}\}_{n=0}^{∞} is any sequence, then we define the Eulerian generating function for the sequence {A_{n}} to be the power series ∑_{j=0}^{∞} \frac{A_{j}}{[j]!}x^{j}. That is, an Eulerian generating function is just a q-analog of an exponential generating function.

3 Counting order 2 elements in finite classical groups

For q the power of a prime, and n ≥ 1 an integer, define

I_{n}(q) = ∑_{k=0}^{n} q^{k(n−k)}\binom{n}{k}_{q}.

The following result is given by Morrison [9, Section 1.11].

Proposition 3. If q is the power of an odd prime, then I_{n}(q) is the number of elements in GL(n, 𝔽_{q}) whose square is the identity.

We note that Proposition 3 also follows by noticing that an element in GL(n, 𝔽_{q}) whose square is the identity is determined by a choice of the eigenspaces for +1 and −1, which are complementary subspaces in 𝔽_{q}^{n}. The number of ways to choose one of these spaces of dimension k is \binom{n}{k}_{q}, and the number of complements is q^{k(n−k)} [12, Lemma 3].

If q is the power of an odd prime, and V is an n-dimensional vector space over 𝔽_{q}, let ⟨·, ·⟩ be a non-degenerate symmetric form on V. The special orthogonal group for ⟨·, ·⟩ is defined to be the group of invertible 𝔽_{q}-linear transformations of V with determinant 1 which preserve the form ⟨·, ·⟩. See [7], for example, for the classification of symmetric bilinear forms over 𝔽_{q}, and the isomorphism classes of the corresponding special orthogonal groups. In particular, when n is odd, there is exactly one isomorphism class of special orthogonal group, which we denote by SO(n, 𝔽_{q}), and when n is even, there are two classes of these groups, which we denote by SO^{+}(n, 𝔽_{q}) and SO^{−}(n, 𝔽_{q}), or by SO^{±}(n, 𝔽_{q}) to denote either class of group simultaneously.

The second-named author [14, Section 4] proved the following, using results on the centralizers of conjugacy classes in the finite special orthogonal groups.

Proposition 4. Let q be the power of an odd prime. If G = SO^{±}(2m, 𝔽_{q}), then the number of elements in G whose sequare is the identity is I_{m}(q^{2}). If G = SO(2m + 1, 𝔽_{q}), then the number of elements in G whose square is the identity is

∑_{k=0}^{m} q^{2k(m−k+1)}\binom{m}{k}_{q^{2}}.

Proposition 4 prompts the following definition generalizing I_{n}(q). For any integer j, define I_{n}^{(j)}(q) by

I_{n}^{(j)}(q) = ∑_{k=0}^{n} q^{k(n−k+j)}\binom{n}{k}_{q}.

So, I_{n}^{(0)}(q) = I_{n}(q), and the number of elements in SO(2m + 1, 𝔽_{q}) whose square is the identity is I_{m}^{(1)}(q^{2}). The numbers I_{n}^{(j)}(q) have the following property. Theorem 5. The numbers I_{n}^{(j)}(q) satisfy the formula

I_{n+1}^{(j)}(q) = I_{n}^{(j)}(q) + q^{nj}(q^{n} − 1)I_{n−1}^{(1−j)}(q) + q^{(n+1)j}I_{n}^{(2−j)}(q).

Proof. First, by Proposition 1, we have

I_{n+1}^{(j)}(q) = ∑_{k=0}^{n+1} q^{k(n+1−k+j)}\binom{n + 1}{k}_{q} = 1 + ∑_{k=1}^{n+1} q^{k(n+1−k+j)} (\binom{n}{k}_{q} + q^{n+1−k}\binom{n}{k − 1}_{q}) .

We may rewrite this as

∑_{k=0}^{n} q^{k(n−k+j)}\binom{n}{k}_{q} + ∑_{k=0}^{n}(q^{k(n+1−k+j)} − q^{k(n−k+j)})\binom{n}{k}_{q} + ∑_{k=1}^{n+1} q^{(k+1)(n+1−k)+kj}\binom{n}{k − 1}_{q}

= I_{n}^{(j)}(q) + ∑_{k=0}^{n} q^{k(n−k+j)}(q^{k} − 1)\binom{n}{k}_{q} + ∑_{k=0}^{n} q^{(k+2)(n−k)+(k+1)j}\binom{n}{k}_{q}.

Now, by applying Proposition 2 with d = 1, and then reindexing the first summation, we have

I_{n+1}^{(j)}(q) = I_{n}^{(j)}(q) + (q^{n} − 1) ∑_{k=1}^{n} q^{k(n−k+j)}\binom{n − 1}{k − 1}_{q} + ∑_{k=0}^{n} q^{(k+2)(n−k)+(k+1)j}\binom{n}{k}_{q}

= I_{n}^{(j)}(q) + (q^{n} − 1) ∑_{k=0}^{n−1} q^{(k+1)(n−k−1+j)}\binom{n − 1}{k}_{q} + ∑_{k=0}^{n} q^{(k+2)(n−k)+(k+1)j}\binom{n}{k}_{q}.

Finally, by (3), we may switch k with n − 1 − k in the first summation, and k with n − k in the second summation above to obtain

I_{n+1}^{(j)}(q) = I_{n}^{(j)}(q) + (q^{n} − 1) ∑_{k=0}^{n−1} q^{(n−k)(k+j)}\binom{n − 1}{k}_{q} + ∑_{k=0}^{n} q^{k(n−k+2)+(n−k+1)j}\binom{n}{k}_{q}

= I_{n}^{(j)}(q) + (q^{n} − 1) ∑_{k=0}^{n−1} q^{nj}q^{k(n−k−j)}\binom{n − 1}{k}_{q} + ∑_{k=0}^{n} q^{(n+1)j}q^{k(n−k+2−j)}\binom{n}{k}_{q}

= I_{n}^{(j)}(q) + q^{nj}(q^{n} − 1)I_{n−1}^{(1−j)}(q) + q^{(n+1)j}I_{n}^{(2−j)}(q),

as desired.

If we let j = 0 in Theorem 5, then we have the following relationship between the number of elements in GL(n + 1, 𝔽_{q}) and in GL(n, 𝔽_{q}) whose square is the identity, when q is the power of an odd prime:

I_{n+1}(q) = I_{n}(q) + (q^{n} − 1)I_{n−1}^{(1)}(q) + I_{n}^{(2)}(q).

This is reminiscent of the recursion of the numbers G_{n}(q) = ∑_{k=0}^{n} \binom{n}{k}_{q}, which satisfy G_{n+1}(q) = 2G_{n}(q) + (q^{n} − 1)G_{n−1}(q), a result due to Goldman and Rota [6].

If we let j = 1 in Theorem 5, and replace q with q^{2}, where q is the power of an odd prime, then we get the following particularly nice result, which follows from Proposition 4.

Corollary 6. Let q be the power of an odd prime, and let n > 1. The number of elements whose square is the identity in SO(2n + 3, 𝔽_{q}) (which is I_{n+1}^{(1)}(q^{2})), in SO(2n + 1, 𝔽_{q}) (which is I_{n}^{(1)}(q^{2})), and in SO(2n − 2, 𝔽_{q}) (which is I_{n−1}^{(0)}(q^{2})) are related in the following way:

I_{n+1}^{(1)}(q^{2}) = (q^{2n+2} + 1)I_{n}^{(1)}(q^{2}) + q^{2n}(q^{2n} − 1)I_{n−1}^{(0)}(q^{2}).

It would be interesting to have a purely combinatorial proof of Corollary 6, by directly counting elements whose square is the identity in these groups, but we have not been able to find such a proof.

4 A q-analog of the number of prime order elements in S_{n}

4.1 Counting prime order elements in S_{n}

Let p be prime, and let T_{n}^{(p)} be the number of elements g in S_{n} such that g^{p} is the identity. In the Introduction, we gave some properties of the numbers T_{n} = T_{n}^{(2)}, and here we give the analogous properties of T_{n}^{(p)} due to Jacobsthal [8].

An element g in S_{n+1} which satisfies g^{p} = 1 either fixes the point n + 1, or it does not. There are T_{n}^{(p)} such elements in S_{n+1} which fix the point n + 1. If such an element does not fix the point n + 1, then it contains a p-cycle permuting n + 1. The number of such p-cycles can be seen to be n(n − 1) ⋯ (n − p + 2) by assuming that, in cycle notation, n + 1 appears in the first position, and then choosing the remaining p − 1 points in the cycle from the set {1, 2, …, n}. To construct the rest of the element, we may permute the remaining n − p + 1 points in such a way that our element still satisfies g^{p} = 1, and the number of ways in which to do this is exactly T_{n−p+1}^{(p)}. This implies that we have the following recursion:

T_{n+1}^{(p)} = T_{n}^{(p)} + n(n − 1) ⋯ (n − p + 2)T_{n−p+1}^{(p)}.  (4)

We may also enumerate T_{n}^{(p)} directly. An element g in S_{n} satisfying g^{p} = 1 may consist of anywhere from 0 (the identity element) to ⌊n/p⌋ disjoint p-cycles. If g consists of exactly k disjoint p-cycles, then we may choose the points permuted in these p-cycles in \binom{n}{pk} ways. We then order these points in one of (pk)! ways, where each block of p points form a p-cycle.

But each of these p-cycles, written in cycle notation, may be written in p ways, and the k different p-cycles may be ordered in any of k! ways to obtain the same element. Putting all of this together, we obtain the formula

T_{n}^{(p)} = ∑_{k=0}^{⌊n/p⌋} \frac{(pk)!}{p^{k}k!}\binom{n}{pk}.  (5)

We may rewrite (5) in a few different useful ways. For any integer m ≥ 2, we define the m-fold multifactorial of an integer r ≥ 0, denoted r!^{(m)} as the product

r!^{(m)} = r(r − m)(r − 2m) ⋯ (r − tm), where t ≥ 0 is maximum such that r > tm.

So, for example, r!^{(2)}, which is also written r!!, is the product of every other decreasing positive integer, starting with r. Using this notation, and by rewriting the binomial coefficients as factorials and reindexing, we may write T_{n}^{(p)} as

T_{n}^{(p)} = ∑_{k=0}^{⌊n/p⌋} \frac{(pk)!}{(pk)!^{(p)}} \binom{n}{pk} = ∑_{i,j≥0,pi+j=n} \frac{n!}{p^{i}i!j!}.  (6)

It follows from the second formula for T_{n}^{(p)} in (6) above, that e^{x+x^{p}/p} is the exponential generating function for T_{n}^{(p)}.

4.2 A q-analog

For any integer m ≥ 2, and a parameter q, define the m-fold q-multifactorial of an integer r ≥ 0, denoted [r]!^{(m)}, by

[r]!^{(m)} = [r][r − m][r − 2m] ⋯ [r − tm], where t ≥ 0 is maximum such that r > tm.

Continue to let p be a prime, and let n ≥ 0. Define T_{n}^{(p)}(q) to be the following:

T_{n}^{(p)}(q) = ∑_{k=0}^{⌊n/p⌋} \frac{[pk]!}{[pk]!^{(p)}} \binom{n}{pk}_{q}.  (7)

It is immediate from the first formula for T_{n}^{(p)} in (6) that we have lim_{q→1} T_{n}^{(p)}(q) = T_{n}^{(p)}, so that T_{n}^{(p)}(q) is a q-analog of T_{n}^{(p)}. In the case that q is the power of a prime (independent of the prime p), there is a combinatorial interpretation of T_{n}^{(p)}(q). Before that, we need a definition.

If V is any vector space of dimension n, define a complete flag of V to be a chain of subspaces of V,

{0} = V_{0} ⊂ V_{1} ⊂ ⋯ ⊂ V_{n−1} ⊂ V_{n} = V,

such that dim(V_{i}) = i for each i. For example, if we have a basis {v_{1}, v_{2}, …, v_{n}} of V, then a complete flag of V may be obtained by taking V_{i} = span{v_{1}, …, v_{i}}. Henceforth, we will let a line in a vector space V mean a one-dimensional subspace of V.

Proposition 7. Let p be prime, q the power of a prime (independent of p), n ≥ 0, and V an n-dimensional 𝔽_{q}-vector space. Then T_{n}^{(p)}(q) is the number of ways to choose a subspace W of V with dimension divisible by p, together with, for some complete flag of W, a sequence of lines, one in each subspace of the complete flag with dimension not divisible by p.

Proof. First, to choose a subspace of V with dimension divisible by p, we must take some non-negative integer k ≤ ⌊n/p⌋, and choose a subspace W of V of dimension pk, the number of which is \binom{n}{pk}_{q}. Now, given a complete flag of W, if W_{i} is a subspace in the flag with

dim(W_{i}) = i, then the number of lines in W_{i} is \binom{i}{1}_{q} = [i]. So, the number of ways to choose a sequence of lines, one in each subspace of dimension not divisible by p in a given flag of W, is exactly

[pk − 1][pk − 2] ⋯ [pk − p + 1][pk − p − 1][pk − p − 2] ⋯ [p + 1][p − 1] ⋯ [2][1] = \frac{[pk]!}{[pk]!^{(p)}} .

Putting all of this together, we get exactly the formula for T_{n}^{(p)}(q) in (7).

We can also describe T_{n}^{(p)}(q) in terms of an Eulerian generating function, as follows.

Proposition 8. The Eulerian generating function for T_{n}^{(p)}(q) is given by

(∑_{i=0}^{∞} \frac{x^{pi}}{[pi]!^{(p)}} ) e_{q}^{x}.

Proof. We have

(∑_{i=0}^{∞} \frac{x^{pi}}{[pi]!^{(p)}} ) e_{q}^{x} = ∑_{i=0}^{∞} \frac{x^{pi}}{[pi]!^{(p)}} ∑_{j=0}^{∞} \frac{x^{j}}{[j]!} = ∑_{n=0}^{∞} ( ∑_{k=0}^{⌊n/p⌋} \frac{1}{[pk]!^{(p)}[n − pk]!}) x^{n}

= ∑_{n=0}^{∞} ( ∑_{k=0}^{⌊n/p⌋} \frac{[pk]!}{[pk]!^{(p)}} \frac{[n]!}{[pk]![n − pk]!}) \frac{x^{n}}{[n]!} = ∑_{n=0}^{∞} \frac{T_{n}^{(p)}(q)}{[n]!}x^{n},

as desired.

Next, we see that the T_{n}^{(p)}(q) have a property similar to the recursion in (4) of the T_{n}^{(p)}.

Theorem 9. For p a prime, and n ≥ 0, define R_{n}^{(p)}(q) to be the following polynomial:

R_{n}^{(p)}(q) = ∑_{k=0}^{⌊n/p⌋} q^{n−pk} \frac{[pk]!}{[pk]!^{(p)}} \binom{n}{pk}_{q}.

Then for all n ≥ p − 1, the T_{n}^{(p)}(q) satisfy

T_{n+1}^{(p)}(q) = T_{n}^{(p)}(q) + [n][n − 1] ⋯ [n − p + 2]R_{n−p+1}^{(p)}(q),

and T_{n}^{(p)}(q) = 1 for 0 ≤ n ≤ p − 2.

Note that if we let q → 1, the identity for the T_{n}^{(p)}(q) in Theorem 9 turns into the recursion (4), since we have lim_{q→1} R_{n}^{(p)}(q) = T_{n}^{(p)}. We now give a combinatorial proof of Theorem 9 using Proposition 7.

Proof of Theorem 9. Let V be an (n+1)-dimensional 𝔽_{q}-vector space, and let {v_{1}, …, v_{n+1}} be a basis for V. By Proposition 7, T_{n+1}^{(p)}(q) is the number of ways to choose a subspace W of V with dimension divisible by p, together with a line in each of the subspaces in some complete flag of W with dimension not divisible by p. We now count this quantity another way.

Define V_{0} = {0} and V_{i} = span{v_{1}, …, v_{i}} for 1 ≤ i ≤ n + 1. For any subspace W of V of dimension divisible by p, say dim(W) = pk, we take a complete flag of W as follows. Let W_{0} = W ∩ V_{0} = {0}, and for each j such that 1 ≤ j ≤ pk, define W_{j} = W ∩ V_{i}, where i is minimal so that dim(W_{j}) = j. Now, W_{0} ⊂ W_{1} ⊂ ⋯ ⊂ W_{pk} = W is a complete flag of W.

First suppose that the subspace W is contained in V_{n}. The number of ways to choose a subspace W of V_{n} of dimension divisible by p, along with a sequence of lines in each space of dimension not divisible by p in the complete flag of W defined above, is equal to T_{n}^{(p)}(q) by Proposition 7.

Now consider the case that our subspace W with dimension divisible by p is not a subspace of V_{n}. Suppose that dim(W) = pk, where k satisfies 1 ≤ k ≤ ⌊\frac{n}{p}⌋. Since W is not completely contained in V_{n}, we must have dim(W ∩ V_{n}) = pk − 1, and so W ∩ V_{n} = W_{pk−1}. By the remarks given before Proposition 1, the number of ways to choose our subspace W is q^{n+1−pk}\binom{n}{pk−1}_{q}.

Now that we have chosen our subspace W, we now choose lines from the subspaces W_{i}, where pk − p + 1 ≤ i ≤ pk − 1. The number of ways to do this is exactly [pk − p + 1][pk − p + 2] ⋯ [pk − 1]. So now, the number of ways to select W, together with these lines, is

q^{n+1−pk}[pk − 1] ⋯ [pk − p + 2][pk − p + 1]\binom{n}{pk − 1}_{q},

where [pk − 1] ⋯ [pk − p + 2][pk − p + 1]\binom{n}{pk−1}_{q} counts the number of ways to select our W′ = W_{pk−1}, together with these lines. By Proposition 2 with d = p − 1, we know that this is also counted by [n][n − 1] ⋯ [n − p + 2]\binom{n−p+1}{pk−p}_{q}, by first choosing lines from V_{i}, for n − p + 2 ≤ i ≤ n. So, the total number of ways to select our space W, together with these p − 1 lines, is

q^{n+1−pk}[n][n − 1] ⋯ [n − p + 2]\binom{n − p + 1}{pk − p}_{q}.

Now, consider the complete flag {0} = W_{0} ⊂ ⋯ ⊂ W_{pk} = W of W, where {0} = W_{0} ⊂ ⋯ ⊂ W_{pk−p} is a complete flag of W_{pk−p}. We have already selected lines from the subspaces W_{pk−p+1}, …, W_{pk−1}, so we need only choose lines from the remaining W_{i} with dimension not divisible by p. By the argument in the proof of Proposition 7, the number of ways to do this is \frac{[pk−p]!}{[pk−p]!^{(p)}} . Putting all of this together, the number of ways to choose a dimension pk subspace W of V which is not contained in V_{n}, together with a sequence of lines, one each from the subspaces of dimension not divisible by p in our complete flag of W, is

[n][n − 1] ⋯ [n − p + 2]q^{n+1−pk} \frac{[pk − p]!}{[pk − p]!^{(p)}} \binom{n − p + 1}{pk − p}_{q}.

Summing over all possible k and reindexing, gives a total of [n][n−1] ⋯ [n−p+2]R_{n−p+1}^{(p)}(q). We note that it follows from this argument that R_{n−p+1}^{(p)}(q) is the number of ways, after choosing lines from V_{i} for n − p + 2 ≤ i ≤ n, to choose our subspace and the remaining lines appropriately. Adding [n][n − 1] ⋯ [n − p + 2]R_{n−p+1}^{(p)}(q) to T_{n}^{(p)}(q), the count for the case where W is contained in V_{n}, gives the desired result.

4.3 The case p = 2

We began in the Introduction with a discussion of the number of elements whose square is the identity, or involutions, in the symmetric group. The set of involutions of the symmetric group is of particular interest, because, for example, the centralizer of a fixed point free involution is a Weyl group of type B, and plays an important role in Lie theory. There are various statistics on involutions which are useful to keep track of using generating functions [4, 5]. Such generating functions can provide for more examples of q-analogs of the number T_{n}^{(2)} of involutions in S_{n}.

Deodhar and Srinivasan [4], for example, define the weight of an involution δ ∈ S_{n}, denoted wt(δ), as follows. If δ is written in cycle notation, and (i j) is one of the disjoint transpositions of δ, then write (i j) ∈ δ with the assumption i < j, and define sp(i j) = j −i−1. If we draw an arc diagram for δ, where an arc from i to j denotes (i j) ∈ δ, then let c(δ) denote the number of crossings of arcs in the diagram (see [4, Section 1]). Now define the weight of δ as

wt(δ) = ( ∑_{(i j)∈δ} sp(i j)) − c(δ).

Let Inv(n, k) denote the set of involutions in S_{n} which are a product of exactly k disjoint transpositions, and define i_{q}(n, k) to be the generating function

i_{q}(n, k) = ∑_{δ∈Inv(n,k)} q^{wt(δ)}.

Deodhar and Srinivasan [4, Proposition 2.1] proved that the i_{q}(n, k) satisfy the recursion

i_{q}(n + 1, k) = i_{q}(n, k) + [n]i_{q}(n − 1, k − 1).  (8)

If we define I_{n}(q) = ∑_{k=0}^{⌊n/2⌋} i_{q}(n, k), then it follows from (8) that

I_{n+1}(q) = I_{n}(q) + [n]I_{n−1}(q),  (9)

which is a q-analog of (1). Indeed, it follows from the definition of i_{q}(n, k) as a generating function that lim_{q→1} I_{n}(q) = T_{n}^{(2)}.

It is unclear what is exactly the connection between I_{n}(q) and T_{n}^{(2)}(q), or whether I_{n}(q) has an interpretation in terms of 𝔽_{q}-vector spaces. Such an interpretation seems possible, since i_{q}(2n, n) = [2n]!/[2n]!! = [2n − 1]!! for n ≥ 1 [4, Corollary 2.2], while

T_{n}^{(2)}(q) = ∑_{k=0}^{⌊n/2⌋} \frac{[2k]!}{[2k]!!}\binom{n}{2k}_{q} = 1 + ∑_{k=1}^{⌊n/2⌋}[2k − 1]!!\binom{n}{2k}_{q}.

We might expect a convenient Eulerian generating function f(x) for I_{n}(q). Based on Proposition 8, we make the guess that f(x) has the form f(x) = F (x)e_{q}^{x} for some power series F (x) = ∑_{m=0}^{∞} a_{n}x^{n}. We may in fact solve for the a_{n} from equations obtained from f(x) = F (x)e_{q}^{x}, starting with a_{0} = I_{0}(q) = 1, by computing the values of I_{n}(q). Calculating the first few values of a_{n}, we find

F (x) = 1 + \frac{1}{[2]!}x^{2} + \frac{1 − q^{2}}{[3]!} x^{3} + \frac{q^{5} + q^{3} + 2q^{2} + 3q + 1}{[4]!}x^{4} + ⋯

Unfortunately, this does not seem to shed any light on the meaning of I_{n}(q) in terms of 𝔽_{q}- vector spaces. Likewise, we also do not know if T_{n}^{(2)}(q) has an interpretation as a generating function for involutions in S_{n} with respect to some statistic. It would be satisfying to understand any connections amongst these points of view.

We conclude by remarking that it would be of interest to have a statistic on order p elements of S_{n} to generalize the work of Deodhar and Srinivasan [4], and to understand the general connection between T_{n}^{(p)}(q) and statistics on order p elements in symmetric groups.

5 Acknowledgments

The first-named author was supported by NSF grant DMS-0751964, at the College of William and Mary REU. The second-named author was supported by a summer research grant from the College of William and Mary. Both authors thank Shahla Nasserasr for several helpful discussions, and the anonymous referee for suggestions to improve this paper.

References

[1] N. Chigira, The solutions of x^{d} = 1 in finite groups, J. Algebra 180 (1996), 653–661.

[2] S. Chowla, I. N. Herstein, and W. K. Moore, On recursions connected with symmetric groups. I, Canad. J. Math. 3 (1951), 328–334.

[3] S. Chowla, I. N. Herstein, and W. R. Scott, The solutions of x^{d} = 1 in symmetric groups, Norske Vid. Selsk. Forh., Trondheim 25 (1952), 29–31.

[4] R. S. Deodhar and M. K. Srinivasan, A statistic on involutions, J. Algebraic Combin. 13 (2001), 187–198.

[5] W. M. B. Dukes, Permutation statistics on involutions, European J. Combin. 28 (2007), 186–198.

[6] J. Goldman, G.-C. Rota, The number of subspaces of a vector space, in Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968), Academic Press, 1969, pp. 75–83.

[7] L. C. Grove, Classical Groups and Geometric Algebra, Graduate Studies in Mathematics, 39, American Mathematical Society, 2002.

[8] E. Jacobsthal, Sur le nombre d’éléments du groupe symétrique S_{n} dont l’ordre est un nombre premier, Norske Vid. Selsk. Forh., Trondheim 21 (1949), 49–51.

[9] K. Morrison, Integer sequences and matrices over finite fields, J. Integer Seq. 9 (2006), Article 06.2.1.

[10] L. Moser and M. Wyman, On the solutions of x^{d} = 1 in symmetric groups, Canad. J. Math. 7 (1955), 159–168.

[11] T. Müller, Enumerating representations in finite wreath products, Adv. Math. 153 (2000), 118–154.

[12] M. K. Srinivasan, The Eulerian generating function of q-derangements, Discrete Math. 306 (2006), 2134–2140.

[13] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, 1997.

[14] C. R. Vinroot, Character degree sums and real representations of finite classical groups of odd characteristic, to appear in J. Algebra Appl.,

http://arxiv.org/abs/0908.2398.

2000 Mathematics Subject Classification: Primary 05A10; Secondary 05A15. Keywords: q-analogs, q-binomial coefficients, vector spaces over finite fields, recursions, symmetric group, Eulerian generating functions.

(Concerned with sequences \underline{A000085} and \underline{A052501}.)

Received August 31 2009; revised versions received December 4 2009; March 9 2010. Published in Journal of Integer Sequences, March 12 2010.

Return to Journal of Integer Sequences home page.