Date: Sat, 07 Oct 2006 10:37:57 +0200
From: Thomas Wieder <wieder.thomas(AT)t-online.de>
Subject: Further comments on A000262 (latex document)

\documentclass[11pt]{article}

\parskip1.0ex
\thispagestyle{empty}
\begin{document}

Consider all $n!$ permutations of the integer sequence $[n] = 
1,2,3,...,n$. The $i$-th permutation, $i=1,2,\ldots,n!$, consists of 
$Z(i)$ permutation cycles. Such a cycle has the length $lc(i,j)$, 
$j=1,...,Z(i)$. For a given permutation we form the product of all its 
cycle lengthes $\prod_{j=1}^{Z(i)} lc(i,j)$. Furthermore, we sum up all 
such products for all permutations of $[n]$ which gives

\begin{equation} \label{LS}
\sum_{i=1}^{n!} \prod_{j=1}^{Z(i)} lc(i,j) = A000262(n).
\end{equation}

For $n=4$ we have $\sum_{i=1}^{n!} \prod_{j=1}^{Z(i)} lc(i,j) = 1*1*1*1 
+ 2*1*1 + 3*1 + 2*1*1 + 3*1 + 2*1 + 3*1 + 4 + 3*1 + 4 + 2*2 + 2*1*1 + 
3*1 + 4 + 3*1 + 2*1*1 + 2*2 + 4 + 2*2 + 4 + 3*1 + 2*1*1 + 3*1 + 4 = 73 = 
A000262(4)$.

We will indicate the set of lengths $L(i)$ of the $i$-th permutation by 
$\{|lc(i,j=1),...,lc(i,j=Z(i))|\}$ . E.g. $\{|3,1|\}$ corresponds to a 
permutation with two cycles, one of length 3 the other of length 1. Here 
we are interested in the multiplicities $mc(s)$ of the $L(s)$, where $s= 
1,\ldots,S$ counts the different $L(s)$ and we have $S$ of them. For 
$n=4$ one finds that there are $mc(s=1)=8$ permutations with $\{|3,1|\}$ 
and $mc(s=1)=3$ permutations with $\{|2,2|\}$. Thus there are $S=2$ 
different sets of lengths and it comes clear later that generally 
$S=P(n,k)$, that is the number of integer partitions of $n$ into $k$ 
parts. We observe that $8 + 3 = 11 = s(n=4,k=2)$ where $s(n,k)$ is the 
Stirling number of the first kind, see A008275, and $k$ gives the number 
of cycles.

Now we take into account Wilf's formula (Wilf, OEIS, Comment to A000262, 
2005) $A000262(n) = n! \sum_{k=0}^{n-1} C(n-1,k) /(k+1)!$ for $n= 
1,2,3,...$ (where C(n,k) denotes the usual binomial coefficient). For 
$n=4$ this sum is $24+36+12+1=73$. Each term in Wilf's sum consists of 
$s(n,k)$ summands. Let the index $i$ now run from $i=1$ to $R(n,k)$ with 
$R(n,k)$ the number of permutations of $[n]$ with $k$ cycles. Then we 
can write a formula which is Wilf's formula term by term. For our 
example permutations we have $8*(3*1) + 3*(2*2) = 24*C(3,1)/2! = 36$. 
The formula is

\begin{equation} \label{RS}
\sum_{i=1}^{R(n,k)} \prod_{j}^{k} lc(i,j) = \frac{n! \; C(n-1,k-1)}{k!}.
\end{equation}

As the last step we include integer partitions into our considerations. 
There are $P(n,k)$ partitions of $n$ into $k$ parts. The index $p= 
1,...,P(n,k)$ designates the partitions. We will write the $p$-th 
partition with $k$ parts in the usual manner as $[t(1),t(2),...,t(k)[$ 
with $t(1)$ the first part and so on. E.g. there are 2 partitions 
$P(n=2,k=2)$, namely $[1,3[$ and $[2,2[$. Furthermore, we need the 
multiplicities $mp(p,q)$ of the different parts in the $p$-th partition. 
The different parts are counted by the index $q=1,...D(p)$ and by 
definition $t(q=1) <> t(q=2) <> ... <> t(q=D(p))$ where we have $D(p)$ 
different parts. E.g. in the partition $p=5$ [1115] of $n=8$ two 
different parts occur, namely $t(q=1)=p(1)=p(2)= p(3)=1$ and 
$t(q=2)=p(4)=5$. Therefore $mp(p=5,q=1)=3$ and $mp(p=5,q=2)=1$. As has 
been described earlier (Wieder, OEIS, Comment to A000262, 2005), we can 
write A000262(n) as a sum over all $P(n)$ partitions of $n$. This sum 
can be split up into $n$ sums over the partitions into $k$ parts. Again 
we meet Wilf's formula term by term and have

\begin{equation}
\sum_{p=1}^{P(n,k)} \frac{n!}{\prod_{q=1}^{D(p)} mp(p,q)!} = \frac{n! \; 
C(n-1,k-1)}{k!}.
\end{equation}

For our example partitions $[1,3]$, $[2,2]$ we have $24/(1!*1!) + 
24/(2!) = 24 * C(3,1)/2! = 36$. Equating the left sides of the last both 
equations gives

\begin{equation} \label{BS}
\sum_{i=1}^{R(n,k)} \prod_{j}^{k} lc(i,j) = \sum_{p=1}^{P(n,k)} 
\frac{n!}{\prod_{q=1}^{D(p)} mp(p,q)!}.
\end{equation}

We finally get for our example $8*(3*1) + 3*(2*2) = 24/(1!*1!) + 
24/(2!)$. On the left hand side we deal with permutations of $[n]$ with 
$Z(i)=k$ permutation cycles. The length sets $L(i)$ are identical with 
the integer partitions of $n$ into $k$ parts. On the right hand side we 
deal with the corresponding multiplicities $mp(p,q)$ of the integer 
partitions. Collecting the contributions of likewise sets $L(i)$ on the 
left hand side, results in an equivalent writing of the left hand side, 
namely

\begin{equation} \label{LS2}
\sum_{s=1}^{S} mc(s) \prod_{j=1}^{k} lc(s,j).
\end{equation}

This form outlines the connection to the Stirling numbers of the first 
kind, since for the involved multiplicities $mc(s)$ it is 
$\sum_{s=1}^{S} mc(s) = s(n,k)$.

\end{document}