Skip to main content
included text of the quote exercise and added Google Books link
Source Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

For some further results of this nature, see Exercise 5.64Exercise 5.64 of Enumerative Combinatorics, vol. 2Enumerative Combinatorics, vol. 2. This exercise deals with the uniform distribution on (0,1)-matrices or $(-1,1)$-matrices, but the arguments can be carried over to other distributions where the matrix entries are i.i.d. The proofs are similar to the argument in David Speyer's comment.

5.64. a. [2+] Let $\mathcal D_n$ be the set of all $n\times n$ matrices of $+1$'s and $-1$'s. For $k\in\mathbb P$ let \begin{align*} f_k(n)&= 2^{-n^2} \sum_{M\in\mathcal D_n} (\det M)^k \\ g_k(n)&= 2^{-n^2} \sum_{M\in\mathcal D_n} (\operatorname{per} M)^k, \end{align*} where $\operatorname{per}$ denotes the permanent function defined by $$\operatorname{per}(m_{ij})= \sum_{n\in\mathfrak{S}_n} m_{1,\pi(1)} m_{2,\pi(2)} \dots m_{n,\pi(n)}.$$ Find $f_k(n)$ and $g_k(n)$ explicitly when $k$ is odd or $k=2$.
b. [3-] Show that $f_4(n)=g_4(n)$, and show that $$\sum_{n\ge 0} f_4(n) \frac{x^n}{n!} = (1-x)^{-3} e^{-2x}. \tag{5.120}$$ HINT. We have $$\sum_m (\det M)^4 = \sum_M \left(\sum_{\pi\in\mathfrak S_n} \pm m_{1,\pi(1)}\dots m_{n,\pi(n)}\right)^4.$$ Interchange the order of summation and use Exercise 5.63.
c. [2+] Show that $f_{2k}(n)<g_{2k}(n)$ if $k\ge 3$ and $n\ge 3$.
d. [3-] Let $\mathcal D'_n$ be the set of all $n\times n$ 0-1 matrices. Let $f'_k(n)$ and $g'_k(n)$ be defined analogously to $f_k(n)$ and $g_k(n)$. Show that $f'_k(n)=2^{-kn} f_k(n+1)$. Show also that \begin{align*} g'_1(n) &= 2^{-n} n!\\ g'_2(n) &= 4^n n!^2 \left(1+\frac1{1!}+\frac1{2!}+\dots+\frac1{n!}\right) \end{align*}

For some further results of this nature, see Exercise 5.64 of Enumerative Combinatorics, vol. 2. This exercise deals with the uniform distribution on (0,1)-matrices or $(-1,1)$-matrices, but the arguments can be carried over to other distributions where the matrix entries are i.i.d. The proofs are similar to the argument in David Speyer's comment.

For some further results of this nature, see Exercise 5.64 of Enumerative Combinatorics, vol. 2. This exercise deals with the uniform distribution on (0,1)-matrices or $(-1,1)$-matrices, but the arguments can be carried over to other distributions where the matrix entries are i.i.d. The proofs are similar to the argument in David Speyer's comment.

5.64. a. [2+] Let $\mathcal D_n$ be the set of all $n\times n$ matrices of $+1$'s and $-1$'s. For $k\in\mathbb P$ let \begin{align*} f_k(n)&= 2^{-n^2} \sum_{M\in\mathcal D_n} (\det M)^k \\ g_k(n)&= 2^{-n^2} \sum_{M\in\mathcal D_n} (\operatorname{per} M)^k, \end{align*} where $\operatorname{per}$ denotes the permanent function defined by $$\operatorname{per}(m_{ij})= \sum_{n\in\mathfrak{S}_n} m_{1,\pi(1)} m_{2,\pi(2)} \dots m_{n,\pi(n)}.$$ Find $f_k(n)$ and $g_k(n)$ explicitly when $k$ is odd or $k=2$.
b. [3-] Show that $f_4(n)=g_4(n)$, and show that $$\sum_{n\ge 0} f_4(n) \frac{x^n}{n!} = (1-x)^{-3} e^{-2x}. \tag{5.120}$$ HINT. We have $$\sum_m (\det M)^4 = \sum_M \left(\sum_{\pi\in\mathfrak S_n} \pm m_{1,\pi(1)}\dots m_{n,\pi(n)}\right)^4.$$ Interchange the order of summation and use Exercise 5.63.
c. [2+] Show that $f_{2k}(n)<g_{2k}(n)$ if $k\ge 3$ and $n\ge 3$.
d. [3-] Let $\mathcal D'_n$ be the set of all $n\times n$ 0-1 matrices. Let $f'_k(n)$ and $g'_k(n)$ be defined analogously to $f_k(n)$ and $g_k(n)$. Show that $f'_k(n)=2^{-kn} f_k(n+1)$. Show also that \begin{align*} g'_1(n) &= 2^{-n} n!\\ g'_2(n) &= 4^n n!^2 \left(1+\frac1{1!}+\frac1{2!}+\dots+\frac1{n!}\right) \end{align*}

Source Link
Richard Stanley
  • 50.8k
  • 14
  • 155
  • 279

For some further results of this nature, see Exercise 5.64 of Enumerative Combinatorics, vol. 2. This exercise deals with the uniform distribution on (0,1)-matrices or $(-1,1)$-matrices, but the arguments can be carried over to other distributions where the matrix entries are i.i.d. The proofs are similar to the argument in David Speyer's comment.