The Sixth Moment of Random Determinants

Dominik Beck Charles University Prague 11636 Czech Republic

                   beckd@karlin.mff.cuni.cz

Zelin Lv and Aaron Potechin The University of Chicago Chicago, IL 60637 USA

                       zlv@uchicago.edu
                     potechin@uchicago.edu

Abstract In this paper, we determine the sixth moment of the determinant of an asymmetric n × n random matrix where the entries are drawn independently from an arbitrary distribution Ω over ℝ with mean 0. Furthermore, we derive the asymptotic behavior of the sixth moment of the determinant as the size of the matrix tends to infinity.

1 Introduction

The behavior of the determinant of a random matrix has been extensively studied. One line of work analyzed the kth moment of a random determinant, i.e., the expected value of the kth power of the determinant of a random matrix. Turán observed that the second moment of the determinant of an n × n matrix (where the entries have mean 0 and variance 1) is n!. The fourth moment of the determinant was determined by Nyquist, Rice, and Riordan [?]. For the special case when the entries of the random matrix are Gaussian, several works [?, ?] showed that the kth moment of the determinant is ∏_{j=0}^{\frac{k}{2} −1} \frac{(n+2j)!}{(2j)!} for even k.

Several variations of this question have also been analyzed. Dembo [?] generalized these results for p × n matrices (where we consider E[det(MM^{⊤})^{\frac{k}{2}} ] rather than E[det(M)^{k}]). Very recently, Beck [?] determined the fourth moment of the determinant of an n × n random matrix with independent entries from an arbitrary distribution (which may not have mean 0). For symmetric random matrices, the second moment of the determinant was analyzed by Zhurbenko [?].

A second line of work analyzed the distribution of the determinant of a random matrix. Girko [?, ?] showed that under some assumptions on the entries of the random matrix, the logarithm of the determinant obeys a central limit theorem, but his proofs are quite difficult. Nguyen and Vu [?] gave a simpler proof of a stronger version of this central limit theorem.

A third line of work analyzed the probability that a random n × n matrix with ±1 entries is singular. Komlós [?, ?] was the first to prove that this probability is o(1). Kahn, Komlós, and Szemerédi [?] proved that this probability is at most .999^{n}, which was the first exponential upper bound. A series of works [?, ?, ?] improved this upper bound culminating in the work of Tikhomirov [?] who proved an upper bound of (\frac{1}{2} + o(1))^{n}, which is tight. For the symmetric case, Costello, Tao, and Vu [?] showed that the probability that a random symmetric matrix with ±1 entries is singular is o(1) and further work has improved this bound.

For a recent survey of results on random matrices, see [?]. In this paper, we extend the first line of work by analyzing the sixth moment of the determinant of a random matrix.

1.1 The fourth moment of random determinants

Before stating our main result, we describe the results of Nyquist, Rice, and Riordan [?] on the fourth moment of the determinant of a random matrix.

Definition 1. Given a distribution Ω over ℝ, we define M_{n×n}(Ω) to be the distribution of n × n matrices where each entry is drawn independently from Ω.

Definition 2. Given a distribution Ω over ℝ, we define m_{k} to be the kth moment of Ω, i.e.,

m_{k} = E_{x∼Ω}[x^{k}].

Definition 3. We define f_{k}(n) = E_{M∼M_{n×n}(Ω)}[det(M)^{k}] to be the expected value of the k-th power of the determinant of a random n × n matrix. Similarly, we define p_{k}(n) to be the expected value of the k-th power of the permanent of a random n × n matrix.

Remark 4. Both f_{k}(n) and p_{k}(n) depend on the moments of Ω, but we write f_{k}(n) and p_{k}(n) rather than f_{k,Ω}(n) and p_{k,Ω}(n) for brevity.

Nyquist, Rice, and Riordan [?] showed that f_{4}(n) = n! y_{n} where y_{n} obeys the recurrence relation

y_{n} = (n + m_{4} − 1)y_{n−1} + (3 − m_{4})(n − 1)y_{n−2}.

where y_{0} = 1 and y_{1} = m_{4}. They further observed that if we take the generating function Y (t) = ∑_{t=0}^{∞} \frac{y_{n}t^{n}}{n!} then Y (t) = (1 − t)^{−3}e^{(m_{4}−3)t}. From this generating function, they found the equation

f_{4}(n) = n! y_{n} = \frac{(n! )^{2}}{2} ∑_{k=0}^{n} \frac{(n − k + 1)(n − k + 2)}{k!}(m_{4} − 3)^{k}.

To prove their results, Nyquist, Rice, and Riordan [?] counted 4 × n tables with certain properties. As we describe in Section 2, we use the same general approach though our analysis is considerably more intricate.

1.2 Our results

Our main results are as follows.

Theorem 5. For any distribution Ω over ℝ such that m_{1} = m_{3} = 0 and m_{2} = 1, the formal generating function F_{6}(t) = ∑_{n=0}^{∞} \frac{t^{n}}{(n!)^{2}} f_{6}(n) for f_{6}(n) is

F_{6}(t) = \frac{e^{t(m_{6}−15m_{4}+30)}}{48(1 + 3t − m_{4}t)^{15}} ∑_{i=0}^{∞} \frac{(1 + i)(2 + i)(4 + i)! t^{i}}{(1 + 3t − m_{4}t)^{3i}} .

Performing Taylor expansion on this generating function, we get a formula for computing the sixth moment of random determinants, namely:

Corollary 6. For any distribution Ω over ℝ such that m_{1} = m_{3} = 0 and m_{2} = 1, we have that f_{6}(n) equals

n!^{2} ∑_{j=0}^{n} ∑_{i=0}^{j} \frac{(1+i)(2+i)(4+i)!}{48(n − j)!}\binom{14 + j + 2i}{j − i}(m_{6}−15m_{4}+30)^{n−j}(m_{4}−3)^{j−i}.

Remark 7. If m_{2} ≠ 1 then we can scale the distribution Ω by \frac{1}{\sqrt{m_{2}}} (which changes the determinant of matrices in M_{n×n}(Ω) by a factor of (\frac{1}{\sqrt{m_{2}}} )^{n}) and then apply the result in Corollary 6.

Remark 8. If Ω = N(0, 1) then m_{4} = 3 and m_{6} = 15 so f_{6}(n) = P_{n} = \frac{n!(n+2)!(n+4)!}{48}, which is

a special case of the result that f_{k}(n) = ∏_{j=0}^{\frac{k}{2} −1} \frac{(n+2j)!}{(2j)!} when Ω = N(0, 1) and k is even.

Another generalization is when m_{3} ≠ 0.

Theorem 9. For any distribution Ω over ℝ such that m_{1} = 0 and m_{2} = 1, the formal generating function F_{6}(t) = ∑_{n=0}^{∞} \frac{t^{n}}{(n!)^{2}} f_{6}(n) for f_{6}(n) is

F_{6}(t) = (1 + m_{3}^{2}t)^{10} \frac{e^{t(m_{6}−10m_{3}^{2}−15m_{4}+30)}}{48(1 + 3t − m_{4}t)^{15}} ∑_{i=0}^{∞} \frac{(1 + i)(2 + i)(4 + i)! t^{i}}{(1 + 3t − m_{4}t)^{3i}} .

Corollary 10. For any distribution Ω over ℝ such that m_{1} = 0 and m_{2} = 1,

f_{6}(n) = n!^{2} ∑_{j=0}^{n} ∑_{i=0}^{j} ∑_{k=0}^{n−j} \frac{(1+i)(2+i)(4+i)!}{48(n − j − k)!}\binom{10}{k}\binom{14 + j + 2i}{j − i}q_{6}^{n−j−k}q_{4}^{j−i}q_{3}^{k},

where q_{6} = m_{6} − 10m_{3}^{2} − 15m_{4} + 30, q_{4} = m_{4} − 3, and q_{3} = m_{3}^{2}.

Below, we show the values of f_{k}(n) and p_{k}(n) when Ω = {−1, 1} for small values of k and n. When Ω = {−1, 1}, we note that f_{4}(n) is the integer sequence A052127 in the On-Line Encyclopedia of Integer Sequences [?, \underline{A052127}]. In the entry for this integer sequence, it is noted that f_{4}(n) ∼ (n! )^{2} \frac{(n^{2}+7n+10)}{(2e^{2})} as n → ∞.

\begin{matrix}n & f_{2}(n), \underline{A000142} & f_{4}(n), \underline{A052127} & f_{6}(n), \underline{A357571} & p_{2}(n) & p_{4}(n) & p_{6}(n) \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 8 & 32 & 2 & 8 & 32 \\ 3 & 6 & 96 & 1536 & 6 & 96 & 2976 \\ 4 & 24 & 2112 & 282624 & 24 & 2112 & 513024 \\ 5 & 120 & 68160 & 66846720 & 120 & 68160 & 157854720 \end{matrix}

Table 1: Values of f_{k}(n) and p_{k}(n) for Ω = {−1, 1}, k ≤ 6, and n ≤ 5.

Remark 11. Note that for all n ∈ ℕ, p_{2}(n) = f_{2}(n) and p_{4}(n) = f_{4}(n). However, for n ≥ 3, p_{6}(n) > f_{6}(n).

We can describe the asymptotic behavior of f_{6} using the following asymptotic expansion.

Theorem 12. For all R ∈ ℕ ∪ {0},

f_{6}(n) = \frac{e^{3q_{4}}(n! )^{2}}{48} ( ∑_{k=0}^{R} c_{k}(n + 6 − k)! )±O((n! )^{2}(n + 6 − R − 1)! ),

where the coefficients c_{k} are the Taylor expansion coefficients of the function C(t) = ∑_{k≥0} c_{k}t^{k},

C(t) = e^{(q_{6}−3q_{4}^{2})t+q_{4}^{3}t^{2}}(1 + q_{3}t)^{10}(1 − 2(3q_{4} + 4)t + 3(5q_{4}^{2} + 8q_{4} + 4)t^{2}
− 4(q_{4}^{2}(5q_{4} + 6))t^{3} + q_{4}^{3}(15q_{4} + 8)t^{4} − 6q_{4}^{5}t^{5} + q_{4}^{6}t^{6}).

Remark 13. For the first terms in the expansion, we have

f_{6}(n) ∼ \frac{e^{3m_{4}−9}}{48} n!^{3} (n^{6} + (m_{6} − 3m_{4}^{2} − 3m_{4} + 34)n^{5} + \frac{1}{2} (m_{6}^{2} − 10m_{3}^{4} + 9m_{4}^{4}

+20m_{4}^{3} − 183m_{4}^{2} − 126m_{4} − 6m_{4}^{2}m_{6} − 6m_{4}m_{6} + 56m_{6} + 905) n^{4} + ⋯).

Remark 14. Note that when Ω = {−1, 1}, as n → ∞,

f_{6}(n) ∼ \frac{(n! )^{3}}{48e^{6}} (n^{6} + 29n^{5} + 335n^{4} + \frac{5861n^{3}}{3} + \frac{17944n^{2}}{3} + \frac{44036n}{5}

+\frac{167536}{45} − \frac{210176}{63n}) .

2 Preliminaries

To prove Theorem 5, we need a few definitions and a key lemma. For this section and the next section, we assume that m_{1} = m_{3} = 0.

Definition 15. Given natural numbers k and n where k is even, we define an even k × n table to be a k × n table where each row is a permutation of [n] and each column contains each number that appears in the column an even number of times. We define T_{k,n} to be the set of all even k × n tables.

Definition 16. Given an even table t of size k×n, we define its sign sgn(t) to be the product of the signs of its rows, which are permutations of [n].

Definition 17. Given a column c where each element is in [n], we define its weight w(c) to be

w(c) = ∏_{j=1}^{n} m_{# of times j appears in column c}.

For even 6 × n tables, we say that a column is a 6-column if it contains some number 6 times, a 4-column if it contains one number four times and another number two times, and a 2-column if it contains three different numbers two times. Observe that the weight of a 6-column is m_{6}, the weight of a 4-column is m_{4}m_{2}, and the weight of a 2-column is m_{2}^{3}.

Definition 18. Given an even k × n table t, we define its weight w(t) to be the product of the weights of its columns.

We can use the following proposition to reduce the problem of finding the sixth moment of a random determinant to a combinatorial problem.

Proposition 19. For all even k ∈ ℕ, f_{k}(n) = ∑_{t∈T_{k,n}} sgn(t)w(t) and p_{k}(n) = ∑_{t∈T_{k,n}} w(t).

Proof. We observe that

f_{k}(n) = E_{A∼M_{n×n}(Ω)} [ ∑_{π_{1},π_{2},...,π_{k}∈S_{n}} (∏_{i=1}^{k} sgn(π_{i})) ∏_{p=1}^{n} (∏_{q=1}^{k} A_{p,π_{q}(p)})]

and

p_{k}(n) = E_{A∼M_{n×n}(Ω)} [ ∑_{π_{1},π_{2},...,π_{k}∈S_{n}} ∏_{p=1}^{n} (∏_{q=1}^{k} A_{p,π_{q}(p)})] .

For each p ∈ [n], we have that E_{A∼M_{n×n}(Ω)}[∏_{q=1}^{k} A_{p,π_{q}(p)}] = w(p) (i.e., the weight of column p), so f_{k}(n) = ∑_{t∈T_{k,n}} sgn(t)w(t) and p_{k}(n) = ∑_{t∈T_{k,n}} w(t), as needed.

Thus, computing the kth moment of a random determinant is equivalent to summing the signed weights of all even tables of size k × n.

Corollary 20. If Ω is the uniform Bernoulli distribution (i.e., the uniform distribution on {−1, 1}) then f_{k}(n) = ∑_{t∈T_{k,n}} sgn(t) and p_{k}(n) = |T_{k,n}|.

Corollary 21. If k = 2, k = 4, or n ≤ 2 then p_{k}(n) = f_{k}(n). If n ≥ 3, k ≥ 6, and k is even then p_{k}(n) > f_{k}(n).

To analyze f_{6}(n), it is useful to consider tables together with pairings of identical elements in each column.

Definition 22. Given an even k × n table t, we define a pairing P on t to be a set of matchings {M_{i} : i ∈ [n]}, one for each column, where each matching M_{i} pairs up identical elements of column i. We define P(t) to be the set of all pairings on t.

Example 23. The table on the left below is an even 6 × 4 table with 27 possible pairings. The table on the right shows one of the 27 possible pairings.

1 2 4 3 1 2 4 3 1 3 4 2 1 3 4 2 2 4 1 3 2 4 1 3  1 2 4 3 1 2 4 3 1 3 4 2 1 3 4 2 2 4 1 3 2 4 1 3

Proposition 24. For each even 6 × n table t,

|P(t)|= 15^{# of 6−columns in t}3^{# of 4−columns in t}.

Definition 25. We define P_{n} = ∑_{t∈T_{k,n}} sgn(t)|P(t)|.

It turns out that P_{n} can be easily computed and this is crucial for our results.

Lemma 26. For all n ∈ ℕ, P_{n} = n(n + 2)(n + 4)P_{n−1} where P_{0} = 1.

This lemma follows from the fact that when Ω = N(0, 1) and k is even, the kth moment of the determinant is ∏_{j=0}^{\frac{k}{2} −1} \frac{(n+2j)!}{(2j)!}. We give a direct proof of this lemma in Appendix ??.

Note that P_{n} = ∑_{t∈T_{k,n}} sgn(t)15^{# of 6-columns in t}3^{# of 4-columns in t} while f_{6}(n) = ∑_{t∈T_{k,n}} sgn(t)m_{6}^{# of 6-columns in t}m_{4}^{# of 4-columns in t}. If Ω = N(0, 1) (or we at least have that m_{1} = m_{3} = 0, m_{2} = 1, m_{4} = 3, and m_{6} = 15) then f_{6}(n) = P_{n}.

In the next section, we show how to handle other distributions Ω using inclusion/exclusion.

We finish our preliminaries section with the following generation function result on derangements:

Lemma 27. Let S_{n} be the set of all permutations of order n on [n] = {1, 2, 3, …, n} and let D_{n} be the set of all derangements of the same order on [n], i.e., the permutations in S_{n} which have no fixed points. If we let C(π) denote the number of cycles in a permutation π and take C_{n}(u) = ∑_{π∈D_{n}} u^{C(π)}, then

C_{n}(u) = (n − 1)(C_{n−1}(u) + u C_{n−2}(u))

and

∑_{n=0}^{∞} \frac{x^{n}}{n!} C_{n}(u) = \frac{e^{−ux}}{(1 − x)^{u}} .

Proof. See the chapter on Bivariate generating functions in the textbook “Analytic Combinatorics” by Flajolet and Sedgewick [?]. For completeness, we present our own derivation. We proceed recursively based on the position of the node n. We can create a derangement π ∈ D_{n} by either:

1. Adding the node n to one of the cycles of a derangement π′ ∈ D_{n−1}. That is, if i → π(i), then we insert n as i → n → π(i). Since there are n−1 nodes in π′, there are n − 1 different π ∈ D_{n} we can create. In this case, the number of cycles is unchanged, i.e., C(π) = C(π′).

2. Adding a cycle (n, n − 1) of length two to π′′ ∈ D_{n−2}. We can then replace n − 1 by any i ∈ π′′. This gives n − 1 new derangements π ∈ D_{n} created from π′′, all of them having C(π) = C(π′′) + 1.

We can obtain all derangements D_{n} in this way. These two possibilities are shown in the figures below.

\begin{matrix}D_{n−1} \\ n \end{matrix} ; Figure 1: D_{n−1} → D_{n}.  \begin{matrix}D_{n−2} \\ n \\ i \end{matrix} ; Figure 2: D_{n−2} → D_{n}.

In terms of C_{n}(u), we get the desired recurrence relation

C_{n}(u) = ∑_{π∈D_{n}} u^{C(π)} = (n − 1) ∑_{π′∈D_{n}} u^{C(π′)} + (n − 1) ∑_{π′′∈D_{n−2}} u^{C(π′′)+1}
= (n − 1)(C_{n−1}(u) + u C_{n−2}(u)),

from which one can deduce its generating function easily.

3 Proof of Theorem 5

Before preceding to the proof of Theorem 5, we first prove the following result on the sixth moment of random determinants.

Lemma 28. For any distribution Ω over ℝ such that m_{1} = m_{3} = 0 and m_{2} = 1,

f_{6}(n) = ∑_{j=0}^{n} ∑_{a=0}^{j} \binom{n}{j}\binom{j}{a}(m_{6} − 15)^{a}(m_{4} − 3)^{(j−a)}D_{n,a,j−a},

where

1. We have that P_{n} = n(n+2)(n+4)P_{n−1} where P_{0} = 1. Equivalently, P_{n} = \frac{n!(n+2)!(n+4)!}{2!4!}.

2. We take C_{n} = (n − 1)(C_{n−1} + 15C_{n−2}) where C_{0} = 1 and C_{1} = 0.

3. We take H_{n,j,a,b} = ∑_{x=1}^{j} \frac{j!}{x!} \binom{j−1}{x−1} ∏_{y=0}^{x−1}(3(n − a − b) − y).

4. We take D_{n,a,b} = ( ∏_{j=0}^{a+b−1} (n − j))( ∑_{i=0}^{b} \binom{b}{i}C_{i}H_{n,b−i,a,b})P_{n−a−b}.

Proof. The idea behind the proof is as follows. We consider the tables where we know that some set A ⊆ [n] of elements appear six times in a 6-column and another set B ⊆ [n] \ A of elements appear four times in a 4-column and two times in a different column. We do not know whether the elements in [n] \ (A ∪ B) appear six times in a 6-column, appear four times in a 4-column and two times in a different column, or appear two times in three different columns. We consider these tables together with pairings for the columns which are unaccounted for by A and B (i.e., the columns which don’t contain six of the same element in A or four of the same element in B), which we call the center columns.

To obtain f_{6}(n), we compute the contribution from each A and B and then take an appropriate linear combination of these contributions so that the contribution from each individual table t is sgn(t)w(t).

Definition 29. Given A ⊆ [n] and B ⊆ [n] \ A, we define D_{n,A,B} to be the set of tables in T_{6,n} such that the elements in A appear six times in a 6-column and the elements in B appear four times in a 4-column and two times in a different column.

Definition 30. Given t ∈ T_{6,n}, A ⊆ [n], and B ⊆ [n] \ A such that t ∈ D_{n,A,B}, we define the center columns of t to be the columns which do not contain six of the same element of A and which do not contain four of the same element of B. We define P_{center}(t) to be the set of pairings on the center columns of t.

Example 31. The following table is a 6 × 9 table t ∈ D_{9,{7},{1,5,6,8,9}} together with a pairing P ∈ P_{center}(t) on the center columns.

7 8 5 2 4 3 6 1 9
7 9 5 2 4 3 6 1 8
7 8 3 5 4 2 6 1 9
7 8 3 5 4 2 6 1 9
7 9 5 2 6 3 1 4 8
7 8 5 2 6 3 1 4 9

By symmetry, the contribution from each D_{n,A,B} only depends on |A| and |B|.

Definition 32. Given n, a, b ∈ ℕ ∪ {0} such that a + b ≤ n, we define D_{n,a,b} to be

D_{n,a,b} = ∑_{t∈D_{n,A,B}} sgn(t)|P_{center}(t)|

where A ⊆ [n], B ⊆ [n] \ A, |A|= a, and |B|= b.

Lemma 33. For all n ∈ ℕ ∪ {0},

f_{6}(n) = ∑_{j=0}^{n} ∑_{a=0}^{j} \binom{n}{j}\binom{j}{a}(m_{6} − 15)^{a}(m_{4} − 3)^{(j−a)}D_{n,a,j−a}.

Proof. Observe that

∑_{j=0}^{n} ∑_{a=0}^{j} \binom{n}{j}\binom{j}{a}(m_{6} − 15)^{a}(m_{4} − 3)^{(j−a)}D_{n,a,j−a}

= ∑_{A⊆[n]} ∑_{B⊆[n]\A} ∑_{t∈D_{n,A,B}} (m_{6} − 15)^{|A|}(m_{4} − 3)^{|B|} sgn(t)|P_{center}(t)|.

Given a table t ∈ T_{6,n}, let A′ be the set of elements in [n] which appear six times in a 6-column of t and let B′ be the set of elements which appear four times in a 4-column of t. Now consider the contribution from t in

∑_{A⊆[n]} ∑_{B⊆[n]\A} ∑_{t∈D_{n,A,B}} (m_{6} − 15)^{|A|}(m_{4} − 3)^{|B|} sgn(t)|P_{center}(t)|.

We have that whenever A ⊆ A′ and B ⊆ B′, t ∈ D_{n,A,B} and |P_{center}(t)|= 15^{|A′\A|}3^{|B′\B|}. Thus, the contribution from t is

∑_{A⊆A′} ∑_{B⊆B′}(m_{6} − 15)^{|A|}(m_{4} − 3)^{|B|}15^{|A′\A|}3^{|B′\B|} sgn(t)
= m_{6}^{|A′|}m_{4}^{|B′|} sgn(t) = sgn(t)w(t).

This implies that

∑_{j=0}^{n} ∑_{a=0}^{j} \binom{n}{j}\binom{j}{a}(m_{6} − 15)^{a}(m_{4} − 3)^{(j−a)}D_{n,a,j−a} = ∑_{t∈T_{6,n}} sgn(t)w(t) = f_{6}(n),

as needed.

We now compute D_{n,a,b}.

Lemma 34. For all n, a, b ∈ ℕ ∪ {0} such that a + b ≤ n,

D_{n,a,b} = ( ∏_{j=0}^{a+b−1} (n − j))( ∑_{i=0}^{b} \binom{b}{i}C_{i}H_{n,b−i,a,b})P_{n−a−b}

where C_{n} is given by the recurrence relation C_{n} = (n − 1)(C_{n−1} + 15C_{n−2}), C_{0} = 1, C_{1} = 0 and

H_{n,j,a,b} = ∑_{x=1}^{j} \frac{j!}{x!}\binom{j − 1}{x − 1} ∏_{y=0}^{x−1}(3(n − a − b) − y).

Proof. To prove this lemma, we group the tables in D_{n,A,B} based on the structure of the 4-columns containing four of the same element of B.

Definition 35. Given a table t ∈ D_{n,A,B}, we define the directed graph G(t) to be the graph with vertices V (G(t)) = B ∪ {v_{center}} and the following edges. For each j ∈ B,

1. If there is a j′ ∈ B \ {b} such that there are two j in the 4-column containing four j′ then we add an edge from j to j′.

2. If there is no such j′ then we add an edge from j to v_{center}.

For each vertex v ∈ V (G(t)), we define the outdegree deg^{+}(v) of v to be the number of edges going from v to another vertex and we define the indegree deg^{−}(v) of v to be the number of edges going from another vertex to v.

Proposition 36. For all t ∈ D_{n,A,B}, G(t) has the following properties.

1. For all j ∈ B, deg^{+}(j) = 1 and deg^{−}(j) ≤ 1.

2. deg^{+}(v_{center}) = 0.

Corollary 37. For all t ∈ D_{n,A,B}, G(t) consists of directed cycles and paths which end at v_{center}, all of which are disjoint except for their common endpoint.

Example 38. The figure on the left below shows a table t together with a pairing P ∈ P_{center}(t) on the center columns of t. The figure on the right shows the resulting graph G(t).

7 8 5 2 4 3 6 1 9
7 9 5 2 4 3 6 1 8
7 8 3 5 4 2 6 1 9
7 8 3 5 4 2 6 1 9
7 9 5 2 6 3 1 4 8
7 8 5 2 6 3 1 4 9
Figure 3: A 6 × 9 table t ∈ D_{9,{7},{1,5,6,8,9}}.

\begin{matrix}v_{center} \\ 5 \\ 6 \\ 8 \\ 9 \\ 1 \end{matrix}

Figure 4: The associated G(t).

Note that as the cycles and paths are disjoint, we can split any table t ∈ D_{n,A,B} into 6-columns corresponding to A, 4-columns corresponding to B_{cycles}, 4-columns corresponding to B_{paths}, and center columns, respectively.

Example 39. The figures below show the split of table t ∈ D_{9,{7},{1,5,6,8,9}} from Example 31.

7 7 7 7 7 7 Figure 5: A. 8 9 9 8 8 9 8 9 9 8 8 9

Figure 6: B_{cycles}.

5 6 1 5 6 1 3 6 1 3 6 1 5 1 4 5 1 4
Figure 7: B_{paths}.

2 4 3 2 4 3 5 4 2 5 4 2 2 6 3 2 6 3

Figure 8: center.

We now consider how many ways there are to start with a table t_{center} ∈ T_{6,n−a−b} together with a pairing P ∈ P(t_{center}) and construct a table t ∈ D_{n,A,B} (we will automatically have that sgn(t) = sgn(t_{center}) and P_{center}(t) = P). Before giving the entire analysis, we describe the parts of the analysis corresponding to the cycles and paths of G(t) as these are the trickiest parts of the analysis.

To handle the cycles of G(t), we observe that the columns of t corresponding to these cycles are independent from the rest of t. This means that once the locations and elements of these columns are chosen, it is sufficient to count the number of possible tables for these columns. This can be done as follows.

Definition 40. Define C_{n} to be the number of tables t_{cycles} ∈ D_{n,∅,[n]} such that G(t_{cycles}) consists of directed cycles and for each i ∈ [n], column i contains four i.

Lemma 41. For all n ≥ 2, C_{n} = (n − 1)(C_{n−1} + 15C_{n−2}) where C_{0} = 1 and C_{1} = 0 and as a consequence,

∑_{n=0}^{∞} \frac{t^{n}}{n!}C_{n} = \frac{e^{−15x}}{(1 − x)^{15}} .

Proof. Notice that G(t_{cycles}) is a derangement of order n. On the other hand, given a derangement π ∈ D_{n}, we determine the number of tables t_{cycles} ∈ D_{n,∅,[n]} with the property that G(t_{cycles}) = π and for each i ∈ [n], column i contains four i. Note that for each i and j in a given cycle of π, the four rows of column i which contain i are the same as the four rows of column j which contain j. Thus, for each cycle C, to determine the entries of the part of t_{cycles} corresponding to C, it is sufficient to take an arbitrary i in C and choose which four rows of column i contain i. There are \binom{6}{4} = 15 choices for this, so there are 15^{C(π)} distinct tables t_{cycles} which we can construct from π. Thus,

C_{n} = ∑_{π∈D_{n}} 15^{C(π)} = C_{n}(15).

By Lemma 27, we get the recurrence relation and the generating function.

Example 42. The figures below show a table t_{cycles} and the corresponding derangement G(t_{cycles}).

1 2 3 4 5
1 2 3 4 5
1 2 5 3 4
1 2 5 3 4
2 1 3 4 5
2 1 3 4 5

Figure 9: A 6 × 5 table t_{cylces} ∈ D_{5,∅,[5]}.

1 2 3 4 5

Figure 10: The associated G(t_{cycles}).

To handle the paths of G(t), we observe that if we want to construct t so that G(t) has a path b_{1} → b_{2} → ⋯ → b_{l} → v_{center}, we can do this as follows:

1. We start with a table t_{center} for the center columns and a pairing P ∈ P(t_{center}).

2. For each j ∈ [l], we add a column containing six b_{j}.

3. We choose a pair of entries of t_{center} which are paired together by P. Let z ∈ [n] be the element in these entries and let r_{1} and r_{2} be the two rows of these entries.

4. For each j ∈ {0, 1, …, l − 1}, we swap this pair of z with the two b_{l−j} in rows r_{1} and r_{2} and then move on to the next j. When we are done,

1. The column which started with six b_{1} now has two z in rows r_{1} and r_{2}.

2. For each j ∈ [l − 1], the column which started with six b_{j+1} now has two b_{j} in rows r_{1} and r_{2}.

3. The original pair of z are replaced by a pair of b_{l}.

Example 43. The figures below show how to extend a table t_{center} and a pairing P ∈ P(t_{center}) based on a path to v_{center} and an endpoint for this path in t_{center} (i.e., a pair of entries in t_{center} which are paired up by P).

3 2 6 4 1 5
3 2 5 6 1 4
3 4 2 6 1 5
3 4 6 2 1 5
3 1 5 2 6 4
3 1 2 4 6 5

Figure 11: A table t_{center} with a pairing P.

\begin{matrix}v_{center} \\ 9 \\ 8 \\ 7 \end{matrix}

Figure 12: A path to v_{center}.

9 8 7 3 2 6 4 1 5
9 8 7 3 2 5 6 1 4
5 9 8 3 4 2 6 1 7
9 8 7 3 4 6 2 1 5
9 8 7 3 1 5 2 6 4
5 9 8 3 1 2 4 6 7

Figure 13: A 6×9 table t where G(t) has the given path to v_{center}.

Following this logic, we can handle the paths in G(t) as follows:

1. Choose the paths in G(t).

2. For each path in G(t), choose a pair of entries in t_{center} which are paired up by P to act as an endpoint for the path. Note that no two paths can have the same pair of entries as an endpoint.

Remark 44. This argument for analyzing the paths of G(t) is the reason why it is important to consider the table t_{center} for the center columns together with a pairing P ∈ P(t_{center}). To count the number of ways to choose the paths in G(t′) and their endpoints, we use the following lemma which counts the number of possible graphs G_{paths} with a given number of paths to v_{center} and no cycles.

Lemma 45. Let B′ ⊆ [n] and take j = |B′|. For all x ∈ [j], there are \frac{j!}{x!} \binom{j−1}{x−1} possible graphs G_{paths} on the vertices B′ ∪ {v_{center}} which consist of x disjoint paths to v_{center} and no cycles.

Proof. We can specify each such graph as follows:

1. Choose an ordering for the elements of B′. There are j! possibilities for this ordering.

2. Choose the x paths by putting x − 1 dividing lines among the elements of B′. Between each neighbouring elements of B′, there must be at most one dividing line, since each path must have at least one vertex in B′. Hence, there are \binom{j−1}{x−1} possibilities for this.

However, if we do this, each graph G_{paths} is counted x! times, one for each possible ordering of the x paths. Thus, the number of possible graphs G_{paths} on the vertices B′ ∪ {v_{center}} which consist of x disjoint paths to v_{center} and no cycles is \frac{j!}{x!} \binom{j−1}{x−1}, as needed.

Proposition 46. Letting x be the number of paths in G_{paths}, there are ∏_{y=0}^{x−1} (3(n − a − b) − y) ways to choose the endpoints for these paths.

We now give the entire analysis for D_{n,a,b}. Given A ⊆ [n] and B ⊆ [n] \ A such that |A|= a and |B|= b, we can compute our D_{n,a,b} = ∑_{t∈D_{n,A,B}} sgn(t)|P_{center}(t)| as follows.

1. For each i ∈ A, we choose which column contains six copies of i. Similarly, for each j ∈ B, we choose which column contains four j. The number of choices for this is ∏_{j=0}^{a+b−1} (n − j).

2. After choosing these columns, we choose a table t_{center} ∈ T_{6,n−a−b} and a pairing P ∈ P(t_{center}) to fill in the remaining columns. The number of choices for this is P_{n−a−b}.

3. We split into cases based on the number of vertices i in G(t) which are contained in cycles. For each i, we choose which \binom{b}{i} of the elements in B are contained in cycles. By Lemma 41, once these elements are chosen there are C_{i} possibilities for the columns containing these elements.

4. There are now j = b − i elements of B which are contained in paths. We further split into cases based on the number x of paths in G(t). By Lemma 45, there are \frac{j!}{x!} \binom{j−1}{x−1} possibilities for what these paths are in G(t).

As discussed above, for each of the x paths, we need to choose a different pair of entries which are paired up by P to be an endpoint for the path and the number of choices for these pairs is ∏_{y=0}^{x−1} (3(n − a − b) − y). Summing all of these possibilities up gives a factor of

H_{n,j,a,b} = ∑_{x=1}^{j} \frac{j!}{x!}\binom{j − 1}{x − 1} ∏_{y=0}^{x−1}(3(n − a − b) − y).

Putting everything together, we have that

D_{n,a,b} = ( ∏_{j=0}^{a+b−1} (n − j))( ∑_{i=0}^{b} \binom{b}{i}C_{i}H_{n,b−i,a,b})P_{n−a−b},

as needed.

Since this argument is intricate and is a central argument for our results, we make this argument formal with the following bijection.

Lemma 47. Given A = {i_{1}, …, i_{a}} ⊆ [n] and B = {j_{1}, …, j_{b}} ⊆ [n] \ A, there is a bijection between the following sets of data:

1. A table t ∈ D_{n,A,B} together with a pairing P ∈ P_{center}(t) on the center columns.

2. A tuple (C_{A}, C_{B}, t_{center}, P, i, B_{cycles}, t_{cycles}, x, G_{paths}, E) where

(a) The indices C_{A} specify the locations of the 6-columns corresponding to the elements in A. More precisely, C_{A} = (c_{i_{1}}, c_{i_{2}}, …, c_{i_{a}}) where for each k ∈ [a], column c_{i_{k}} contains six i_{k}.

(b) The indices C_{B} specify the locations of the 4-columns corresponding to the elements in B. More precisely, C_{B} = (c_{j_{1}}, c_{j_{2}}, …, c_{j_{b}}) where for each k ∈ [b], column c_{j_{k}} contains four j_{k}.

(c) We let t_{center} ∈ T_{6,n−|A|−|B|} and P ∈ P(t_{center}) denote a table for the center columns and a pairing on this table.

(d) We let i ∈ [0, |B|] denote the number of elements of B which are contained in cycles in G(t).

(e) We let B_{cycles} ⊆ B denote the i elements of B which are contained in cycles in G(t).

(f) We let t_{cycles} ∈ D_{i,∅,[i]} denote a table such that G(t_{cycles}) contains only cycles.

(g) We let x ∈ [0, |B|−i] denote the number of paths in G(t).

(h) Letting B_{paths} = B \ B_{cycles}, we let G_{paths} denote a graph on the vertices B_{paths} ∪ v_{center} which consists of x disjoint paths to v_{center}.

(i) We let E = (p_{1}, …, p_{x}) denote the pairs in P which are the endpoints for the x paths in G_{paths}.

Proof. Given a table t ∈ D_{n,A,B} together with a pairing P ∈ P_{center}(t) on the center columns, it is easy to find C_{A}, C_{B}, i, B_{cycles}, x, and G_{paths}. We obtain t_{center}, t_{cycles}, and E as follows.

1. We obtain t_{cycles} from the entries of the columns containing the elements in B_{cycles}. More precisely, let c′_{1}, …, c′_{i} be the columns containing the elements of B_{cycles} and let j′_{k} be the element which appears four times in column c′_{k} (note that j′_{1}, …, j′_{i} are not necessarily in increasing order). If the entry in row r and column c′_{k} is j′_{y} then we take the entry in row r and column k of t_{cycles} to be y.

2. In order to obtain t_{center} and E, we first modify t as follows. We order the paths in G_{paths} based on the order of their starting vertices. Let j_{k1} → j_{k2} → ⋯ → j_{kl_{k}} → v_{center} be the kth path in G_{paths}. Let r_{k1} and r_{k2} be the rows of column c_{j_{k1}} which contain an element z_{k} ∉ A ∪ B rather than j_{k1}. Finally, let c_{k}^{∗} be the center column containing two j_{kl_{k}}. We now make the following modifications to t.

1. We replace the two z_{k} in rows r_{k1} and r_{k2} of column c_{j_{k1}} with j_{k1}.

2. For all i ∈ [l_{k} − 1], the two j_{ki} in column c_{j_{k(i+1)}} must be in rows r_{k1} and r_{k2}. We replace these two j_{ki} with j_{k(i+1)}.

3. The two j_{kl_{k}} in column c_{k}^{∗} must be in rows r_{k1} and r_{k2}. We replace these j_{kl_{k}} with z_{k}. We take p_{k} to be this pair of elements.

Let t′ be the table we obtain after making these modifications for each of the k paths. The center columns of t′ only contain elements in [n] \ (A ∪ B), so we can obtain t_{center} from t′. More precisely, letting c′′_{1}, …, c′′_{n−a−b} be the center columns of t′ and letting i′_{1}, …, i′_{n−a−b} be the elements of [n] \ (A ∪ B), if t′ has an element i′_{y} in row r and column c′_{j} for some r ∈ [6] and j, y ∈ [n − a − b] then we put the element y in row r and column j of t_{center}. We translate P ∈ P_{center}(t′) and E = (p_{1}, …, p_{k}) from the center columns of t′ to t_{center} accordingly.

Conversely, given a tuple (C_{A}, C_{B}, t_{center}, P, i, B_{cycles}, t_{cycles}, x, G_{paths}, E), we construct t ∈ D_{n,A,B} as follows.

1. For each i_{k} ∈ A, We start by putting six i_{k} in column c_{i_{k}}. Similarly, for each j_{k} ∈ B, we start by putting six j_{k} in column c_{j_{k}}.

2. We use t_{center} to fill in the center columns. More precisely, letting c′′_{1}, …, c′′_{n−a−b} be the center columns and letting i′_{1}, …, i′_{n−a−b} be the elements of [n] \ (A ∪ B), if t_{center} has an element y ∈ [n − a − b] in row r and column j then we put the element i′_{y} in row r and column c′′_{j} of t.

We translate the pairing P ∈ P(t_{center}) and the endpoints E = (p_{1}, …, p_{x}) to the center columns accordingly.

3. We use t_{cycles} to replace the columns of t containing the i elements of B_{cycles}. More precisely, if c′′_{1}, …, c′′_{i} are the columns containing the elements of B_{cycles} and j′_{k} is the element in column c′′_{k} (note that j′_{1}, …, j′_{i} are not necessarily in increasing order) then if t_{cylces} has an element y ∈ [i] in row r and column k then we put the element j′_{y} in row r and column c′′_{k}.

We let t′ be the table which we obtain after this replacement.

4. We order the paths in G_{paths} based on their starting vertex. For each k ∈ [x], let j_{k1} → j_{k2} → ⋯ → j_{kl_{k}} → v_{center} be the kth path in G_{paths}. After translating E to the center columns, p_{k} is a pair of elements z_{k} in rows r_{k1} and r_{k2} of column c_{k}^{∗} for some z_{k} ∈ [n] \ (A ∪ B), c_{k}^{∗} ∈ {c′′_{1}, …, c′′_{n−a−b}}, and r_{k1}, r_{k2} ∈ [6]. We obtain t by performing the following modifications to t′ for each of the k paths.

1. We replace the two z_{k} in rows r_{k1} and r_{k2} of column c_{k}^{∗} with j_{kl_{k}}.

2. For all i ∈ [l_{k} − 1], we replace the two j_{k(i+1)} in rows r_{k1} and r_{k2} of column c_{j_{k(i+1)}} with j_{ki}.

3. We replace the two j_{k1} in rows r_{k1} and r_{k2} of column c_{j_{k1}} with z_{k}.

Example 48. The figures below illustrate the bijection when A = {7}, B = {1, 5, 6, 8, 9}, C_{A} = (1), C_{B} = (8, 4, 7, 2, 9) (as these are the 4-columns for 1, 5, 6, 8, 9 respectively), i = 2, B_{cycles} = {8, 9}, x = 2, and t_{center} t_{cycles}, G_{paths}, and E are as shown below.

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

Figure 14: t_{center} and t_{cycles}.

\begin{matrix}v_{center} \\ 5 \\ 6 \\ 8 \\ 9 \\ 1 \end{matrix}

Figure 15: G(t).

7 8 2 5 4 3 6 1 9
7 9 2 5 6 3 1 4 8
7 8 5 3 6 2 1 4 9
7 8 5 3 4 2 6 1 9
7 9 2 5 4 3 6 1 8
7 8 2 5 4 3 6 1 9

Figure 16: The resulting table t.

It is not hard to check that these maps are inverses of each other.

This completes the proof of Lemma 34. Combining Lemmas 33 and 34 completes the proof of Lemma 28.

We now simplify the terms in Lemma 28. Proposition 49.

H_{n,j,a,b} = \frac{(3(n − a − b) + j − 1)!}{(3(n − a − b) − 1)!}.

Proof. Originally,

H_{n,j,a,b} = ∑_{x=1}^{j} \frac{j!}{x!}\binom{j − 1}{x − 1} ∏_{y=0}^{x−1}(3(n − a − b) − y).

Let z = 3(n − a − b). For the inner product, we can write

∏_{y=0}^{x−1}(3(n − a − b) − y) = \frac{z!}{(z − x)!},

so

H_{n,j,a,b} = ∑_{x=1}^{j} \frac{j!}{x!}\binom{j − 1}{x − 1}\frac{z!}{(z − x)!} = j! ∑_{x=1}^{j} \binom{j − 1}{x − 1}\binom{z}{x} = j! \binom{z + j − 1}{j}.

The last equality is a special case of the Chu-Vandermonde Identity. With these simplifications, we can derive an expression for the generating function

F_{6}(t) = ∑_{n=0}^{∞} \frac{t^{n}}{(n! )^{2}} f_{6}(n).

By Lemma 28,

F_{6}(t) = ∑_{0≤a≤j≤n} \frac{t^{n}}{(n! )^{2}} \binom{n}{j}\binom{j}{a}(m_{6} − 15)^{a}(m_{4} − 3)^{(j−a)}D_{n,a,j−a}.

Summing with respect to b = j − a instead of a and observing that

D_{n,a,b} = ( ∏_{k=0}^{a+b−1} (n − k))( ∑_{i=0}^{b} \binom{b}{i}C_{i}H_{n,b−i,a,b})P_{n−a−b}

= \frac{n!}{(n − j)!}( ∑_{i=0}^{b} \binom{b}{i}C_{i}H_{n,b−i,j−b,b})P_{n−j}

= n! ( ∑_{i=0}^{b} \binom{b}{i}C_{i}H_{n,b−i,j−b,b})\frac{(n−j+2)! (n−j+4)!}{48},

we have that

F_{6}(t) = ∑_{0≤i≤b≤j≤n} \frac{t^{n}}{n!}\binom{n}{j}\binom{j}{b}\binom{b}{i}(m_{6} − 15)^{(j−b)}(m_{4} − 3)^{b}

\frac{(n − j + 2)! (n − j + 4)!}{48}H_{n,b−i,j−b,b}C_{i}.

By Proposition 49, H_{n,b−i,j−b,b} = (3n−3j+b−i−1)! /(3n−3j−1)!. Using the reparametrization b = i + s, j = b + r, n = j + q, where s, r, q goes from 0 to ∞, we get

F_{6}(t) = ∑_{q=0}^{∞} ∑_{r=0}^{∞} ∑_{s=0}^{∞} ∑_{i=0}^{∞} \frac{t^{i+s+r+q}}{q! r! s! i!}(m_{6} − 15)^{r}(m_{4} − 3)^{(i+s)}

\frac{(q + 2)! (q + 4)!}{48} \frac{(3q + s − 1)!}{(3q − 1)!}C_{i}.

Grouping the terms to separate the dependence on r, s, and i, we have that F_{6}(t) equals

(∑_{q=0}^{∞} \frac{t^{q}}{q!} \frac{(q + 2)! (q + 4)!}{48}) (∑_{r=0}^{∞} \frac{t^{r}(m_{6} − 15)^{r}}{r!} )

(∑_{s=0}^{∞} \frac{t^{s}}{s!} \frac{(3q + s − 1)!}{(3q − 1)!}(m_{4} − 3)^{s}) (∑_{i=0}^{∞} \frac{t^{i}}{i!}(m_{4} − 3)^{i}C_{i}) .

Summing all the inner sums (the rightmost using Lemma 41),

F_{6}(t) = ∑_{q=0}^{∞} \frac{t^{q}}{q!} \frac{(q + 2)! (q + 4)!}{48}e^{t(m_{6}−15)} \frac{1}{(1 − t(m_{4} − 3))^{3q}} \frac{e^{−15t(m_{4}−3)}}{(1 − t(m_{4} − 3))^{15}} .

4 Generalization for an arbitrary third moment

Restating Proposition 19, we can write

f_{6}(n) = ∑_{t∈T_{6,n}} sgn(t)w(t),

where T_{6,n} is the set of all permutation tables of length n with six rows whose columns fall in one of the following categories:

• 6-columns: six copies of a single number (weight m_{6})

• 4-columns: four copies of one number and two copies of a distinct number (weight m_{4})

• 2-columns: three pairs of distinct numbers (weight 1)

The weight w(t) of a table t is simply the product of the weights of its columns.

When m_{3} ≠ 0, we can have the following type of column in addition to 2-columns, 4-columns, and 6-columns:

• 3-columns: three copies of one number and three copies of a distinct number (weight m_{3}^{2})

To handle this, we make the following definitions.

Definition 50. We define f_{6}^{∗}(n) = E_{M∼M_{n×n}(Ω)}[det(M)^{6}] to be the expected value of the sixth power of the determinant of a matrix M ∼ M_{n×n}(Ω) (i.e., an n × n random matrix with entries drawn from Ω) where Ω is a distribution such that m_{1} = 0.

We define the formal generating function F_{6}^{∗}(t) for f_{6}^{∗}(n) to be F_{6}^{∗}(t) = ∑_{n=0}^{∞} \frac{t^{n}}{(n!)^{2}} f_{6}^{∗}(n).

Remark 51. We write f_{6}^{∗}(n) instead of f_{6}(n) to distinguish this case from the case we previously analyzed where m_{1} = m_{3} = 0.

Definition 52. We define T_{6,n}^{∗} to be the set of all 6 × n tables whose rows are permutations of [n] and whose columns are 2-columns, 3-columns, 4-columns, or 6-columns.

Similar to before, we can write f_{6}^{∗}(n) as the sum over tables in T_{6,n}^{∗} of the contribution from each table.

Proposition 53. For all n ∈ ℕ, f_{6}^{∗}(n) = ∑_{t∈T_{6,n}^{∗}} sgn(t)w(t).

We can evaluate f_{6}^{∗}(n) using our expression for f_{6}(n).

Definition 54. We define f_{6}(n) = ∑_{t∈T_{6,n}} sgn(t)w(t) = E_{M∼M_{n×n}(Ω′)}[det(M)^{6}] where Ω′ is the distribution where we first sample x from Ω and then randomly choose x or −x (so Ω and Ω′ have the same even moments but the odd moments of Ω′ are 0).

Lemma 55. For all n ∈ ℕ,

f_{6}^{∗}(n) = ∑_{j=0}^{n} \binom{n}{j}^{2}f_{6}(n − j) j! m_{3}^{2j}(−1)^{j} ∑_{π∈D_{j}}(−10)^{C(π)}.

Proof. We first break each table t ∈ T_{6,n}^{∗} into tables s and t′, where s contains all of the 3-columns of t. The signs of these tables are related as

sgn(t) = sgn(s) sgn(t′).

Definition 56. Given J ⊂ [n], letting j = |J|, we define T_{6,J} to be the set of all 6 × |J| tables whose rows are permutations of J and whose columns are all 2-columns, 4-columns, or 6-columns. We define Q_{6,J} to be the set of all 6 × |J| tables whose rows are permutations of J and whose columns are all 3-columns.

Since the selection of the subset J ⊆ [n] does not depend on the positions of the columns containing the elements of J in table t, we can write our sum as

f_{6}^{∗}(n) = ∑_{J⊂[n]} \binom{n}{j} ∑_{t′∈T_{6,[n]/J}} sgn(t′)w(t′) ∑_{s∈Q_{6,J}} sgn(s)w(s).

No matter which numbers J are selected, as long as we select the same amount of them, the contribution is the same. Hence,

f_{6}^{∗}(n) = ∑_{j=0}^{n} \binom{n}{j}^{2} ∑_{t′∈T_{6,n−j}} sgn(t′)w(t′) ∑_{s∈Q_{6,j}} sgn(s)w(s),

where Q_{6,j} = Q_{6,[j]}. The first inner sum is simply f_{6}(n − j). For the second inner sum, by symmetry, we can fix the first permutation in s to be the identity. Since w(s) = m_{3}^{2j}, we get

∑_{s∈Q_{6,j}} w(s) sgn(s) = j! m_{3}^{2j} ∑_{\begin{matrix}s∈Q_{6,j} \\ s_{1}=id \end{matrix}} sgn(s).

Similarly as before, we construct a graph G(s) from the numbers in table s and then show G(s) is a derangement. Let c be a number in the first row of a given column of table s. Since it is a 3-column, we denote the other number in the column as c′. We construct a graph G(s) for a given table s whose edges are all of these pairs c → c′.

Example 57. Example showing the correspondence between a table s where s_{1} = id and the corresponding derangement G(s).

1 2 3 4 5 6 7 8 9
3 6 1 4 5 7 2 8 9
1 2 3 9 4 6 7 5 8
1 6 3 9 4 7 2 5 8
3 2 1 9 4 6 7 5 8
3 6 1 4 5 7 2 8 9

Figure 17: A 6 × 9 table s ∈ Q_{6,9}.

1 3 2 6 7 4 9 8 5

Figure 18: The associated G(s).

For the signs, letting π = G(s), we have

sgn(s) = sgn(π) = (−1)^{j−C(π)}.

Note that since c and c′ are always different, the set of all G(s) corresponds to the set D_{j} of all derangements. Since there are \binom{5}{2} = 10 possibilities how to arrange the leftover 5 numbers c and c′ in each of the 3-columns corresponding to a given cycle of π, we get

∑_{s∈Q_{6,j}} w(s) sgn(s) = j! m_{3}^{2j}(−1)^{j} ∑_{π∈D_{j}}(−1)^{C(π)}10^{C(π)}.

Putting everything together, we obtain that

f_{6}^{∗}(n) = ∑_{j=0}^{n} \binom{n}{j}^{2}f_{6}(n − j) j! m_{3}^{2j}(−1)^{j} ∑_{π∈D_{j}}(−10)^{C(π)}.

Corollary 58.

F_{6}^{∗}(t) = (1 + m_{3}^{2}t)^{10}e^{−10m_{3}^{2}t} F_{6}(t).

Proof. In terms of generating functions,

\begin{aligned}F_{6}^{∗}(t) & = ∑_{n=0}^{∞} \frac{t^{n}}{n!^{2}} f_{6}^{∗}(n) = ∑_{n=0}^{∞} ∑_{j=0}^{n} \frac{t^{n−j}}{(n − j)!^{2}} f_{6}(n − j)\frac{(−m_{3}^{2}t)^{j}}{j!} ∑_{π∈D_{j}}(−10)^{C(π)} \\ & = F_{6}(t) ∑_{j=0}^{∞} \frac{(−m_{3}^{2}t)^{j}}{j!} ∑_{π∈D_{j}}(−10)^{C(π)} = F_{6}(t)\frac{e^{−10m_{3}^{2}t}}{(1 + m_{3}^{2}t)^{−10}} . \end{aligned}

The final equality is a special case of Lemma 27. Theorem 9 follows.

5 Asymptotics

The proof relies directly on the calculus developed by Borinsky [?], enabling us to extract the asymptotic behaviour of coefficients from their factorially divergent generating function. We use the following result from Borinsky [?]: