Skip to main content
deleted 61 characters in body
Source Link
Qiaochu Yuan
  • 124.2k
  • 42
  • 468
  • 765

Here is a more informative version of this identity. Let $Z_n$ denote the cycle index polynomial of the symmetric group $S_n$, namely

$$Z_n = \frac{1}{n!} \sum_{\sigma \in S_n} z_1^{c_1(\sigma)} z_2^{c_2(\sigma)} \dots $$

where $c_i(\sigma)$ denotes the number of $i$-cycles of $\sigma$. The observations in the comments boil down to the observation that

$$Z_n = \sum_{\lambda \vdash n} \frac{z_1^{\lambda_1} z_2^{\lambda_2} \dots}{1^{\lambda_1} \lambda_1! 2^{\lambda_2} \lambda_2! \dots }$$$$Z_n = \sum_{\sum ic_i = n} \prod_{i=1}^n \frac{z_i^{c_i}}{i^{c_i} c_i!}$$

and setting all $z_i = 1$ gives your identity, but without doing this, it is possible to arrange the $Z_n$ into a beautiful generating function, namely

$$\sum_{n \ge 0} Z_n t^n = \exp \left( \sum_{n \ge 1} \frac{z_i t^i}{i} \right).$$

This is the "permutation form" of the exponential formula, which has many applications in combinatorics. See, for example, Stanley's Enumerative Combinatorics: Volume 2 for an exposition, or this blog post.

Here is a more informative version of this identity. Let $Z_n$ denote the cycle index polynomial of the symmetric group $S_n$, namely

$$Z_n = \frac{1}{n!} \sum_{\sigma \in S_n} z_1^{c_1(\sigma)} z_2^{c_2(\sigma)} \dots $$

where $c_i(\sigma)$ denotes the number of $i$-cycles of $\sigma$. The observations in the comments boil down to the observation that

$$Z_n = \sum_{\lambda \vdash n} \frac{z_1^{\lambda_1} z_2^{\lambda_2} \dots}{1^{\lambda_1} \lambda_1! 2^{\lambda_2} \lambda_2! \dots }$$

and setting all $z_i = 1$ gives your identity, but without doing this, it is possible to arrange the $Z_n$ into a beautiful generating function, namely

$$\sum_{n \ge 0} Z_n t^n = \exp \left( \sum_{n \ge 1} \frac{z_i t^i}{i} \right).$$

This is the "permutation form" of the exponential formula, which has many applications in combinatorics. See, for example, Stanley's Enumerative Combinatorics: Volume 2 for an exposition, or this blog post.

Here is a more informative version of this identity. Let $Z_n$ denote the cycle index polynomial of the symmetric group $S_n$, namely

$$Z_n = \frac{1}{n!} \sum_{\sigma \in S_n} z_1^{c_1(\sigma)} z_2^{c_2(\sigma)} \dots $$

where $c_i(\sigma)$ denotes the number of $i$-cycles of $\sigma$. The observations in the comments boil down to the observation that

$$Z_n = \sum_{\sum ic_i = n} \prod_{i=1}^n \frac{z_i^{c_i}}{i^{c_i} c_i!}$$

and setting all $z_i = 1$ gives your identity, but without doing this, it is possible to arrange the $Z_n$ into a beautiful generating function, namely

$$\sum_{n \ge 0} Z_n t^n = \exp \left( \sum_{n \ge 1} \frac{z_i t^i}{i} \right).$$

This is the "permutation form" of the exponential formula, which has many applications in combinatorics. See, for example, Stanley's Enumerative Combinatorics: Volume 2 for an exposition, or this blog post.

Source Link
Qiaochu Yuan
  • 124.2k
  • 42
  • 468
  • 765

Here is a more informative version of this identity. Let $Z_n$ denote the cycle index polynomial of the symmetric group $S_n$, namely

$$Z_n = \frac{1}{n!} \sum_{\sigma \in S_n} z_1^{c_1(\sigma)} z_2^{c_2(\sigma)} \dots $$

where $c_i(\sigma)$ denotes the number of $i$-cycles of $\sigma$. The observations in the comments boil down to the observation that

$$Z_n = \sum_{\lambda \vdash n} \frac{z_1^{\lambda_1} z_2^{\lambda_2} \dots}{1^{\lambda_1} \lambda_1! 2^{\lambda_2} \lambda_2! \dots }$$

and setting all $z_i = 1$ gives your identity, but without doing this, it is possible to arrange the $Z_n$ into a beautiful generating function, namely

$$\sum_{n \ge 0} Z_n t^n = \exp \left( \sum_{n \ge 1} \frac{z_i t^i}{i} \right).$$

This is the "permutation form" of the exponential formula, which has many applications in combinatorics. See, for example, Stanley's Enumerative Combinatorics: Volume 2 for an exposition, or this blog post.