% version soumise au journal Loth de Comb. automne 2001
% version finale: 11 janv. 02
\input epsf 
\documentclass[a4paper,12pt]{amsart}

\begin{document}

\title{Hooks and powers of parts in partitions}
\author{Roland Bacher and Laurent Manivel}
\date{}
\newcommand\E{{\mathbb E}}
\newcommand\vol{\operatorname{vol}}




\begin{abstract}
This paper shows that the number of hooks
of length $k$ contained in all partitions of $n$ equals $k$ times the 
number of parts of length $k$ in partitions of $n$. It contains also 
formulas for the moments (under uniform distribution) of
$k$-th parts in partitions of $n$.
\end{abstract}

\subjclass[2000]{05A17}
\keywords{Partition}
\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 47 \rms (2002), Article~B47d\hfill}
\def\thepage{}
%
%

\section{Introduction and Main Results}     

Many textbooks contain material on partitions. Two standard references are
{\bf [A]} and {\bf  [S]}.

A {\it partition} of a natural integer $n$ with {\it parts}
$\lambda_1,\dots,\lambda_k$ is a finite decreasing
sequence $\lambda=(\lambda_1\geq \lambda_2\geq \dots\geq \lambda_k>0)$
of natural integers $\lambda_1,\dots ,\lambda_k>0$ such that $n=\sum_{i=1}^k
\lambda_i$. We denote by $\vert \lambda \vert$ the 
{\it content} $n$ of $\lambda$.
Partitions are also written as sums: $n=\lambda_1+\dots+\lambda_k$
and one uses also the (abusive) multiplicative notation
$$\lambda=1^{\nu_1}\cdot 2^{\nu_2}\cdots n^{\nu_n}$$
where $\nu_i$ denotes the number of parts equal to $i$ in the
partition $\lambda$. 

A partition is graphically represented by its {\it Young diagram} obtained
by drawing $\lambda_1$ adjacent boxes of identical size
on a first row, followed by $\lambda_2$ adjacent boxes of identical size
on a second row and so on with all first boxes (of different rows)
aligned along a common first column. In the sequel we identify a 
partition with its Young diagram. A {\it hook} in a partition is a choice
of a box $H$ in the corresponding Young diagram together with all boxes
at the right of the same row and all boxes below of the same column.
The total number of boxes in a hook is its {\it hooklength}, the number
of boxes in a hook to the right of $H$ is its {\it armlength}
and the number of boxes of a hook below $H$ is the {\it leglength}.
The Figure below displays the Young diagram of the partition $(5,4,3,1)$
of $13$ together with a hook of length $4$ having armlength $2$ and
leglength $1$. We call the couple $(\hbox{armlength,leglength})$
of a hook its {\it hooktype} and denote it by $\tau=\tau(\alpha,k-1-\alpha)$
if its armlength is $\alpha$ and its leglength $k-1-\alpha$. Such a hook has
hence total length $k$ and there are exactly $k$ different hooktypes
for hooks of length $k$. 

\medskip
\centerline{\epsfysize2cm\epsfbox{exple1.eps}}
\centerline{\Small The partition $(5,4,3,1)$ of $13$ together with a 
hook of type $\tau(2,1)$ and length $4$.}
\bigskip
Let $k$ be a natural integer and let $\tau=\tau(\alpha,k-1-\alpha)$ be the
hooktype of a hook of length $k$
with armlength $\alpha$ and leglength $k-1-\alpha$.
Given a partition $\lambda$ of $n$, set
$$\tau(\lambda)=\sharp\{\hbox{hooks of type }\tau\hbox{ in 
(the Young diagram of) }\lambda\}$$
and
$$\tau(n)=\sum_{\lambda,\ \vert \lambda\vert=n} \tau(\lambda)$$
where the sum is over all partitions of $n$.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL ROLAND BACHER AND LAURENT MANIVEL}{\SMALL HOOKS AND POWERS OF PARTS IN PARTITIONS}
%
%

\medskip
{\bf Theorem 1.1.} {\sl One has
$$\begin{array}{lcl}
\displaystyle \sum_{n=1}^\infty\tau(n)z^n&\displaystyle =&\displaystyle
\frac{z^k}{1-z^k}\prod_{i=1}^\infty\frac{1}{
1-z^i}\cr&\displaystyle
=&\displaystyle
\sum_{\lambda=1^{\nu_1}2^{\nu_2}\cdots} \nu_k\ z^{\vert\lambda\vert}
\end{array}$$
where the last sum is over all partitions of integers.}

In other terms, the number of hooks of given type and length $k$
appearing in all partitions of $n$ equals the number of parts of length $k$ in
all partitions of $n$.

This result implies in particular that the total number of hooks of given
type $\tau=\tau(\alpha,k-1-\alpha)$
occuring in all partitions of $n$ depends only on the length $k$ 
and not on the particular hooktype $\tau(\alpha,k-1-\alpha)$ itself. Since there
are exactly $k$ distinct hooktypes for hooks of length $k$, the total
number of hooks of length $k$ in partitions of $n$ is given by
the coefficient of $z^n$ of the series 
$$k\frac{z^k}{1-z^k}\prod_{i=1}^\infty\frac{1}{1-z^i}\ .$$

C. Bessenrodt pointed out to us that this Theorem follows directly 
from Theorem~1.1 in {\bf [B]}. Indeed, Theorem~1.1 of {\bf [B]}
states that the number of $k$-hooks of given leglength which can
be added to a Young diagram always exceeds by 1 the
number of $k$-hooks of the same leglength which can
be removed from the same Young diagram. This implies the
identity 
$$\sum_{n=1}^\infty\tau(n)z^n=z^k\left(\sum_{n=1}^\infty\tau(n)z^n
+\prod_{i=1}^\infty\frac{1}{1-z^i}\right)$$
on the generating series appearing in Theorem~1.1. The obvious 
initial conditions $\tau(n)=0$ for $n<k$ determine now the generating
series which is easily checked to be
$$\frac{z^k}{1-z^k}\prod_{i=1}^\infty\frac{1}{
1-z^i}\ .$$
 
Our initial proof of Theorem~1.1 was based on the $q-$binomial theorem.

As remarked previously, partitions of a natural integer $n$ can 
be written in (at least) two different ways: either by considering
the finite decreasing sequence
$$\lambda=(\lambda_1\geq \lambda_2\geq \dots \geq \lambda_k)$$
of its parts or by considering the vector 
$$\nu=(\nu_1,\nu_2,\dots,\nu_n)$$
where $\nu_i$ counts the multiplicity of parts with length $i$ in $\lambda$.
We still denote by $\lambda$ the vector 
$$(\lambda_1,\lambda_2,\dots\lambda_k,0,\dots,0)\in {\bf Z}^n$$
of length $n$ obtained by appending $n-k$ zero-coordinates at the end of 
the vector $(\lambda_1,\dots,\lambda_k)$ defining a partition $\lambda$.

We consider moreover the vector $\gamma=(\gamma_1,\dots,\gamma_n)$
where $\gamma_i$ equals the number of coordinates equal to $i$ among
$\nu_1,\dots,\nu_n$. The vector $\gamma$ of a partition encodes
\lq\lq multiplicities of multiplicities (of parts)'' and does no longer
encode the partition since for instance
the $\gamma$-vectors of the two partitions
$5=3+2$ and $5=4+1$ give both rise to $\gamma=(2,0,0,0,0)$. 

We introduce also the vectors 
$$\begin{array}{l}
\lambda(n)=(\lambda_1(n),\lambda_2(n),\dots,\lambda_n(n))=\sum_{\vert\lambda\vert=n}
\lambda\ ,\cr
\nu(n)=(\nu_1(n),\nu_2(n),\dots,\nu_n(n))=\sum_{\vert\lambda\vert=n}
\nu\ ,\cr
\gamma(n)=(\gamma_1(n),\gamma_2(n),\dots,\gamma_n(n))=\sum_{\vert\lambda\vert=n}
\gamma\end{array}$$
of ${\bf Z}^n$ obtained by summing up the vectors $\lambda,\nu$  or $\gamma$
over all partitions of $n$. The coordinates of the vector $\lambda(n)$ are
of course related to the mean length (under uniform distribution) of the 
$k$-th part in partitions of $n$. Similarly, coordinates of $\nu(n)$ 
relate to the mean multiplicity of parts equal to $k$ and coordinates of 
$\gamma(n)$ measure the mean number of distinct part-lengths appearing with 
common multiplicity $k$.

The following Table displays all five partitions of $4$ together with
the corresponding $\lambda$-, $\nu$- and $\gamma$-vectors.

$$\begin{array}{lccccc}
\hbox{Partition}&(1,1,1,1)&(2,1,1)&(2,2)&(3,1)&(4)\cr
\lambda\hbox{-vector}&(1,1,1,1)&(2,1,1,0)&(2,2,0,0)&(3,1,0,0)&(4,0,0,0)\cr
\nu\hbox{-vector}&(4,0,0,0)&(2,1,0,0)&(0,2,0,0)&(1,0,1,0)&(0,0,0,1)\cr
\gamma\hbox{-vector}&(0,0,0,1)&(1,1,0,0)&(0,1,0,0)&(2,0,0,0)&(1,0,0,0)
\end{array}$$

Summing up all $\lambda$-, $\nu$- and $\gamma$-vectors associated to
the five partitions of $4$ we get hence
$$\begin{array}{l}
\lambda(4)=(12,5,2,1),\cr
\nu(4)=(7,3,1,1),\cr
\gamma(4)=(4,2,0,1)\ .\end{array}$$

One has the following result.

\medskip
{\bf Theorem 1.2.} {\sl For all $n\geq 1$ we have $\lambda_n(n)=
\nu_n(n)=\gamma_n(n)=1$ and
$$\begin{array}{l}
\lambda_k(n)=\nu_k(n)+\lambda_{k+1}(n)\ ,\cr
\nu_k(n)=\gamma_k(n)+\nu_{k+1}(n)\end{array}$$
for $k=1,\dots,n-1.$}

These equalities can be restated as
$$\lambda_k(n)=\sum_{i=k}^n\nu_i(n)\hbox{ and }\nu_k(n)=\sum_{i=k}^n \gamma_i(n)\ .$$
This last equality states for instance that the sum over all partitions of $n$ 
of the number
of distinct parts arising with multiplicity at least $k$ equals the number of parts
equal to $k$ in all partitions of $n$. Our proof of this fact uses generating 
series. C. Bessenrodt ({\bf [B1]}) communicated to us a beautiful 
bijective proof which we reproduce with her permission.

The coordinates of the vectors $\nu(n)$ are of course given by the 
generating series mentioned in Theorem~1.1, i.e., the $k$-th 
coordinate $\nu_k(n)$ of $\nu(n)$ equals the coefficient of $z^n$
in the generating series
$$\frac{z^k}{1-z^k}\prod_{i=1}\frac{1}{1-z^i}\ .$$

The coordinates of the vectors $\lambda(n)$ and $\nu(n)$ are then easily computed
using Theorem~1.2. More precisely, one has the following result:

\medskip
{\bf Corollary 1.3.} {\sl (i) The $k$-th coordinate of the vector 
$\lambda(n)$ is the coefficient of $z^n$ in the generating series
$$\prod_{i=1}^\infty\frac{1}{1-z^i}\ \sum_{j=k}^\infty 
\frac{z^j}{1-z^j}\ .$$

\ \ (ii) The $k$-th coordinate of the vector 
$\gamma(n)$ is the coefficient of $z^n$ in the generating series
$$\frac{(1-z)\ z^k}{(1-z^k)(1-z^{k+1})}\prod_{i=1}^\infty\frac{1}{1-z^i}\ .$$
}

Given a partition 
$$\lambda=(\lambda_1,\dots,\lambda_n)=(1^{\nu_1}\cdots n^{\nu_n})$$
and an integer $d\geq 0$ we introduce the vectors ${\binom\lambda d}$
and ${\binom\nu d}\in{\bf Z}^n$ by setting
$${\binom\lambda d}=\left({\binom{\lambda_1} d},\dots,
{\binom{\lambda_n} d}\right)
\hbox{ and }{\binom\nu d}=\left({\binom{\nu_1} d},\dots,
{\binom{\nu_n} d}\right)$$
and define
$${\binom{\lambda(n)} d}=\sum_{\vert\lambda\vert=n}{\binom\lambda d}\ ,\quad
{\binom{\nu(n)} d}=\sum_{\vert 1^{\nu_1}\ 2^{\nu_2}\cdots\vert=n}{\binom\nu d}$$
with coordinates
$${\binom{\lambda_k(n)} d}=\sum_{\vert\lambda\vert=n}{\binom{\lambda_k} d}\ ,\quad
{\binom{\nu_k(n)} d}=\sum_{\vert 1^{\nu_1}\ 2^{\nu_2}\cdots\vert=n}{\binom{\nu_k} d}
\ .$$

The following example shows the vectors  ${\binom\lambda 1}=\lambda,
{\binom\lambda 2},{\binom\lambda 3}$ and ${\binom\nu 1}=\nu,{\binom\nu 2},
{\binom\nu 3}$ associated to all five partitions of $4$.

\medskip

{\bf Example:}
$$\kern-5pt\begin{array}{lcccccc}
\hbox{Partition}&&(1,1,1,1)&(2,1,1)&(2,2)&(3,1)&(4)\cr
{\binom\lambda 1}& =&(1,1,1,1)&(2,1,1,0)&(2,2,0,0)&(3,1,0,0)&(4,0,0,0)\cr
{\binom\lambda 2}& =&(0,0,0,0)&(1,0,0,0)&(1,1,0,0)&(3,0,0,0)&(6,0,0,0)\cr
{\binom\lambda 3}& =&(0,0,0,0)&(0,0,0,0)&(0,0,0,0)&(1,0,0,0)&(4,0,0,0)\cr
\end{array}$$
$$\kern-5pt\begin{array}{lcccccc}
\hbox{Partition}&&(1,1,1,1)&(2,1,1)&(2,2)&(3,1)&(4)\cr
{\binom\nu 1}& =&(4,0,0,0)&(2,1,0,0)&(0,2,0,0)&(1,0,1,0)&(0,0,0,1)\cr
{\binom\nu 2}& =&(6,0,0,0)&(1,0,0,0)&(0,1,0,0)&(0,0,0,0)&(0,0,0,0)\cr
{\binom\nu 3}& =&(4,0,0,0)&(0,0,0,0)&(0,0,0,0)&(0,0,0,0)&(0,0,0,0)\cr
\end{array}$$

We have thus
$$\begin{array}{lll}
{\binom{\lambda(4)} 1}=(12,5,2,1),\quad&
{\binom{\lambda(4)} 2}=(11,1,0,0),\quad& 
{\binom{\lambda(4)} 3}=(5,0,0,0)\cr
{\binom{\nu(4)} 1}=(7,3,1,1),\quad&
{\binom{\nu(4)} 2}=(7,1,0,0),\quad& 
{\binom{\nu(4)} 3}=(4,0,0,0)\end{array}$$

The following probably well-known result allows easy computations of the
vectors ${\binom{\lambda(n)} d}$ and ${\binom{\nu(n)} d}$.

\medskip
{\bf Proposition 1.4.} {\it For any natural integer $d\geq 0$, the
$k$-th coefficients ${\binom{\lambda_k(n)} d}$, respectively
${\binom{\nu_k(n)} d}$ (extended by ${\binom0 d}$ for $k>n$) have 
generating series
$$\sum_{n}^\infty {\binom{\lambda_k(n)} d}\ z^n=
\left(\prod_{j=1}^{k-1}\frac{1}{1-z^j}\right)\left(\sum_{i=0}^\infty
{\binom i d}\ z^{ik}\ \left(\prod_{j=1}^i\frac{1}{1-z^j}\right)\right)$$
and 
$$\sum_{n}^\infty {\binom{\nu_k(n)} d}\ z^n=\left(\frac{z^k}{1-z^k}\right)^d
\left(\prod_{j=1}^{\infty}\frac{1}{1-z^j}\right)\ .$$
}

{\bf Remark 1.5.} One has
$$\sum_{\vert\lambda\vert=n} \lambda_k^d=\sum_i i!\ \hbox{Stirling}_2(d,i)\
{\binom{\lambda_k(n)} i}$$
and
$$\sum_{\vert 1^{\nu_1}\ 2^{\nu_2}\cdots\vert=n} \nu_k^d=
\sum_i i!\ \hbox{Stirling}_2(d,i)\
{\binom{\nu_k(n)} i}$$
where $\hbox{Stirling}_2(d,i)$ denote Stirling numbers of the second kind, 
defined by
$x^d=\sum_i\hbox{Stirling}_2(d,i)\ x(x-1)\cdots(x-i+1)$.

Asymptotics are not so easy to work out from 
the formula for ${\binom{\lambda(n)} d}$. 
Our last result is an equivalent expression
for the above series on which asymptotics are easier to see.

We introduce the generating series $\sigma_r(k)$ defined as
$$\sigma_r(k)=\sum_{i=k}^\infty \left(\frac{z^i}{1-z^i}\right)^r$$
for $r\geq 1$ and $k\geq 1$ natural integers. We consider the series
$\sigma_r(k)$ as beeing graded of degree $r$ and define the homogeneous series
$S_d(k)$ of degree $d$ by
$$\begin{array}{rcl}
\displaystyle S_d(k)&\displaystyle =&
\displaystyle \sum_{\vert(1^{\nu_1}\ 2^{\nu_2}\cdots)\vert=d}
\frac{d!}{\left(\sum_i \nu_i\right)!}{\binom{\left(\sum_i \nu_i\right)}
{ \nu_1\ \nu_2\dots}}\prod_{i=1}^d \left(\frac{\sigma_i(k)}{i}
\right)^{\nu_i}\cr
&\displaystyle =&\displaystyle d!\quad\sum_{\vert 1^{\nu_1}2^{\nu_2}\cdots
t^{\nu_t}\vert=d}\qquad
\prod_{j=1}^d \frac{(\sigma_j(k))^{\nu_j}}{j^{\nu_j}\ \nu_j!}\end{array}$$
(i.e., the coefficient of the homogeneous \lq\lq monomial'' series
$\sigma_\lambda(k)=\sigma_{\lambda_1}(k)
\dots \sigma_{\lambda_s}(k)$ equals the number of elements in the symmetric group
on $\vert \lambda \vert$ elements of the conjugacy class with $s$ cycles
of length $\lambda_1,\lambda_2,\dots,\break \lambda_s$).

We have then the following result.

\medskip
{\bf Theorem 1.6.} {\it For any natural integers $d\geq 1$ and $k\geq 1$,
we have
$$\sum_{n}^\infty {\binom{\lambda_k(n)} d}\ z^n=
\frac{S_d(k)}{d!}\ \left(\prod_{j=1}^{\infty}\frac{1}{1-z^j}\right)\ .$$}

The first series $S_i=S_i(k)$ are given in terms of $\sigma_j=\sigma_j(k)$ as follows
$$\begin{array}{l}
S_0=1,\cr
S_1=\sigma_1,\cr
S_2=\sigma_1^2+\sigma_2,\cr
S_3=\sigma_1^3+3\sigma_1\sigma_2+2\sigma_3\cr
S_4=\sigma_1^4+6\sigma_1^2\sigma_2+3\sigma_2^2+8\sigma_1\sigma_3+6\sigma_4\cr
S_5=\sigma_1^5+10\sigma_1^3\sigma_2+20\sigma_1^2\sigma_3+15\sigma_1\sigma_2^2+
30\sigma_1\sigma_4+20\sigma_2\sigma_3+24\sigma_5\cr\end{array}$$

Let us remark that the analogous statement of Theorem~1.6
for the generating series $\sum_n {\binom{\nu_k} d} z^n$ boils down to 
a trivial identity.

The formulas of Theorem~1.6 ease the computations of asymptotics (in $n$) for 
$\lambda_k(n)$ and its moments and allow a rederivation of the results
contained in {\bf [EL]} and {\bf [VK]}: Indeed, the asymptotics of the 
coefficients in $\sum_n^\infty {\binom{\lambda_k(n)} d}z^n$
are essentially given by the asymptotics of 
$$\frac{\sigma_1^d(k)}{d!}\left(\prod_{j=1}^\infty\frac{1}{1-z^j}\right)$$
which can be worked out.


\section{Proofs}


{\bf Proof of Theorem 1.2.} The partition $1^n$ yields the unique non-zero 
contribution to $\lambda_n(n)$ and $\gamma_n(n)$ and this contribution equals 
$1$ in both cases. The partition $n$ consisting of a unique part of
length $n$ yields the unique non-zero contribution to $\nu_n(n)$ and
this contribution equals again $1$.

Given a partition 
$\lambda=(\lambda_1,\dots,\lambda_k)$ of $n$, the {\it conjugate
partition} $\lambda^t=(\lambda^t_1,\dots,\lambda^t_{k'})$ of $\lambda$
is defined by
$$\lambda^t_j=\sharp\{i\ \vert\ \lambda_i\geq j\}$$
(this corresponds to a reflection of the Young diagramm of $\lambda$
through the main diagonal $y=-x$). The difference $\lambda_k-\lambda_{k+1}$
(where non-existing parts are considered as parts of length $0$)
equals hence the number $\nu^t_k$ of parts having length $k$
in the transposed partition $\lambda^t=(1^{\nu_1^t}\ 2^{\nu_2^t}\cdots)$
of $\lambda$. Summing over all partitions of $n$ yields then the recursion
relation $\lambda_k(n)=\nu_k(n)+\lambda_{k+1}(n)$.

The proof of the equality $\nu_k(n)=\gamma_k(n)+\nu_{k+1}(n)$ uses
generating series.
Introducing the numbers 
$$\begin{array}{l}
\displaystyle m_k(\lambda)=\sharp\{i\ \vert\ \nu_i\geq k\}\ ,\cr
\displaystyle m_k(n)=\sum_{\vert\lambda\vert=n}m_k(\lambda)\end{array}$$
one has obviously $\gamma_k(n)=m_k(n)-m_{k+1}(n)$.
We have hence to show the equality $m_k(n)=\nu_k(n)$ for $1\leq k<n$
(the equalities $m_n(n)=\nu_n(n)=1$ are easy).

We introduce the generating function 
$$\psi_k(y,z)=\sum_\lambda y^{m_k(\lambda)} z^{\vert \lambda\vert}\ .$$
One has
$$\begin{array}{l}
\displaystyle \psi_k(y,z)=\sum_{I\subset\{1,2,3,\dots\},\ \sharp(I)<\infty}
\left(\prod_{i\in I}\frac{yz^{ki}}{1-z^i}\right)\left(\prod_{1\leq j\not\in I}
\frac{1-z^{kj}}{1-z^j}\right)\cr
\displaystyle \qquad =\prod_{j=1}^\infty\left(\frac{yz^{kj}}{1-z^j}+
\frac{1-z^{kj}}{1-z^j}\right)=
\prod_{j=1}^\infty\left(\frac{1}{1-z^j}-(1-y)
\frac{z^{kj}}{1-z^j}\right)\ .
\end{array}$$
A small computation yields
$$\frac{\partial \psi_k(y,z)}{\partial y}=\psi_k(y,z)
\sum_{j=1}^\infty\frac{z^{kj}}{1-(1-y)z^{kj}}$$
and we have hence
$$\sum_{n=0}^\infty m_k(n)\ z^n=\frac{\partial \psi_k}{\partial y}(1,z)=
\left(\prod_{j=1}^\infty\frac{1}{1-z^j}\right)\ \frac{z^k}{1-z^k}=
\sum_{n=0}^\infty \nu_k(n)\ z^n$$
(cf.\ Theorem~1.1 for the last equality) which finishes the proof.\hfill QED

 
\medskip
{\bf C. Bessenrodt's bijective Proof of Theorem 1.2.} 
We establish first the equality
$$\nu_k(n)=\sum_{i=k}^n \gamma_i(n)$$
which corresponds to the second statement of Theorem~1.2.

Define the sets
$$P_k(n)=\{(i,\lambda)\ \vert\ \vert\lambda\vert=n,\ 1\leq i\leq 
\nu_k(\lambda)\}$$
and 
$$Q_k(n)=\{(j,\lambda)\ \vert \ \vert \lambda\vert=n,\ \nu_j(\lambda)
\geq k\}$$
(recall that $\nu_i(\lambda)$ counts the number of parts with length $i$ in 
the partition $\lambda$). 
The cardinality $\sharp (P_k(n))$ equals obviously $\nu_k(n)$ and one 
has si\-mi\-larly $\sharp(Q_k(n))=\sum_{i=k}^n \gamma_i(n)$ (recall that 
$\gamma_i(\lambda)$ counts the number of distinct partlengths whose parts
appear with multiplicity $i$ in $\lambda$). An element
$(i,\lambda)\in P_k(n)$ stems from a partition $\lambda$ having at least
$i$ parts equal to $k$. Erasing $i$ such parts and adding $k$ parts
of length $i$ yields a partition $\mu$ of $n$ such that $\mu$ contains
at least $k$ parts of length $i$. This shows that $(i,\mu)\in
Q_k(n)$ and the application $(i,\lambda)\longmapsto (i,\mu)$
is clearly a bijection.

The first statement of Theorem~1.2 can be proven similarly by
considering the sets
$$R_k=\{(i,\lambda)\ \vert\ \vert\lambda\vert=n,\ 1\leq i\leq 
\lambda_k(\lambda)\}$$
and 
$$S_k(n)=\{(j,\lambda)\ \vert \ \vert \lambda\vert=n,\ j\leq \sum_{i=k}^n
\nu_i(\lambda)\}$$
and the bijection $R_k(n)\longrightarrow S_k(n)$ defined by
$(i,\lambda)\longmapsto (i,\lambda^t)$ (this is more or less the proof
given above).\hfill QED

Corollary 1.3 results immediately from Theorem~1.2 and from
the last equality in Theorem~1.1.

\medskip
{\bf Proof of Proposition 1.4.} A partition
$$\lambda=(\lambda_1\geq \lambda_2\geq\dots\geq \lambda_k=i\geq \lambda_{k+1}\geq\dots)$$
with $\lambda_k=i$ of $n=\sum_{j=1}\lambda_j$ can be written as
$$\lambda=(i+(\lambda_1-i)\geq i+(\lambda_2-i)\geq\dots\geq i+(\lambda_{k-1}-i)\geq i
\geq\lambda_{k+1}\geq\dots)\ .$$
Such partitions are hence in bijection with pairs of partitions
$$\begin{array}{l}
\alpha=(\alpha_1=(\lambda_1-i)\geq \alpha_2=(\lambda_2-i)\geq\dots\geq 
\alpha_{k-1}=(\lambda_{k-1}-i)
\geq 0)\ ,\cr
\omega=(\omega_1=\lambda_{k+1}\geq\omega_2=\lambda_{k+2}\geq\dots)
\end{array}$$
with $\alpha$ having at most $k-1$ non-zero parts and $\omega$ having all 
parts $\leq i$. The conjugate partition $\alpha^t$ of $\alpha$ has 
hence only parts 
$\leq k-1$. Such a pair $\alpha^t,\omega$ of partitions yields hence a unique
partition with $\lambda_k=i$ of the integer $n=ki+\sum_{j=1}^{k-1}\alpha^t_j+
\sum_{j=k+1} \omega_j$ and contributes hence with ${\binom i d}$ 
to the $k$-th
coordinate ${\binom{\lambda_k(n)} d}$ of ${\binom{\lambda(n)} d}$. 
Summing up over $i\in{\bf N}$ yields easily the generating series for
${\binom{\lambda_k(n)} d}$.

Considering the generating series for ${\binom{\nu_k(n)} d}$ one has
$$\sum_n{\binom{\nu_k(n)} d}z^n=\left(\sum_j{\binom j d}z^{jk}\right)
\prod_{i\not=k}\frac{1}{1-z^i}$$
and the (easy) equality
$$\sum_j{\binom j d}Z^j=\frac{1}{Z}\left(\frac{Z}{1-Z}\right)^{d+1}$$
implies the result.
\hfill QED

\medskip
{\bf Proof of Theorem 1.6.} Given a partition $\lambda=(\lambda_1,\lambda_2,\dots)$
the definition 
$$\lambda^t_k=\sharp\{i\ \vert \ \lambda_i\geq k\}$$
for the $k$-th part of its transposed partition 
$\lambda^t=(\lambda^t_1,\lambda^t_2,\dots)$ shows the equalities
$$\sum_\lambda y^{\lambda_k}\ z^{\vert\lambda\vert}=
\sum_\lambda y^{(\lambda^t)_k}\ z^{\vert\lambda\vert}=
\left(\prod_{i=1}^{k-1}
\frac{1}{1-z^i}\right)\left(\prod_{j=k}^\infty
\frac{1}{1-yz^j}\right)\ .$$
Denote this series by $\varphi_k(y,z)$. An easy computation yields
$$\varphi_k(y,z)=\left(\prod_{i=1}^\infty
\frac{1}{1-z^i}\right)\prod_{j\geq k}\left(1-(y-1)\frac{z^j}{1-z^j}\right)^{-1}\ .$$
Applying the identity
$$\prod_{i}\left(1-x_i\right)^{-1}=\hbox{exp}\left(
\sum_{l=1}^\infty\frac{\sum_i x_i^l}{l}\right)$$
of formal power series to the last factor we get
$$\begin{array}{l}
\displaystyle 
\prod_{j\geq k}\left(1-(y-1)\frac{z^j}{1-z^j}\right)^{-1}
=\hbox{exp}\left(\sum_{l=1}^\infty\frac{(y-1)^l}{l}\sigma_l(k)\right)\cr
\displaystyle \quad =\sum_{n=0}^\infty \frac{(y-1)^n}{n!}\sum_{\vert(
1^{\nu_1}\cdot 2^{\nu_2}\cdots)\vert=n}\frac{n!}{\left(\sum_i \nu_i\right)!}
{\binom{\sum_i\nu_i}{
\nu_1\ \nu_2\dots}}\prod_i\left(\frac{\sigma_i(k)}{i}\right)^{\nu_i}\cr
\displaystyle \quad =\sum_{n=0}^\infty \frac{(y-1)^n}{n!}\ S_n(k)\ .\end{array}$$
We have thus
$$d!\sum_\lambda {\binom{\lambda_k} d}z^{\vert \lambda\vert}=
\frac{\partial^d \varphi_k}{\partial y^d}(1,z)=
\left(\prod_{i=1}^\infty \frac{1}{1-z^i}\right)
S_d(k)$$
which finishes the proof by comparison with Proposition 1.4.\hfill QED

\vskip0.5cm
We thank S. Attal, M-L. Chabanol and C. Krattenthaler
for comments and for their interest in this work. 
We also thank C. Bessenrodt for comments 
on a preliminary version.  

\vskip10pt

{\bf References}

\vskip6pt
\small

{\bf [A]} G.E. Andrews, {\it The Theory of Partitions, Encyclopedia of 
Mathematics and its Applications}, Addison--Wesley (1976).
 
{\bf [B]} C. Bessenrodt, {\it On hooks of Young diagrams}, Ann.\ of Comb.\ 
{\bf 2}, 103--110 (1998).

{\bf [B1]} C. Bessenrodt, Electronic letter to the authors, 18 sept.\ 2001.

{\bf [EL]} P. Erd\"os, J. Lehner, {\it The distribution of the number of
summands in the partition of a positive integer}, Duke Math.\ Journal
{\bf 8}, 335--345 (1941).

{\bf [GR]} G. Gasper, M. Rahman, {\it Basic hypergeometric series}, 
Cambridge University Press (Encycl.\ of Math.\ and its Appl.), 1990.

{\bf [S]} Stanley, {\it Enumerative Combinatorics 2}, Cambridge 
University Press (1999).

{\bf [ST]} M. Szalay, P. Tur\'an, {\it On some problems of the statistical
theory of partitions with application to characters of the symmetric
group I}, Acta Math.\ Sci.\ Hung.\ {\bf 29}, 361--379 (1977).

{\bf [VK]} A. Vershik, S. Kerov, {\it Asymptotics of the Plancherel 
measure of the symmetric group and the limit form of Young 
tableaux}, Soviet Math.\ Dokl.\ {\bf 18}, 1977, 527--531.

\vskip1cm

Roland Bacher
 
INSTITUT FOURIER
 
Laboratoire de Math\'ematiques
 
UMR 5582 (UJF--CNRS)
 
BP 74
 
38402 St MARTIN D'H\`ERES Cedex (France)
 
e-mail: Roland.Bacher@ujf-grenoble.fr  

\vskip0.5cm

Laurent Manivel
 
INSTITUT FOURIER
 
Laboratoire de Math\'ematiques
 
UMR 5582 (UJF--CNRS)
 
BP 74
 
38402 St MARTIN D'H\`ERES Cedex (France)
 
e-mail: Laurent.Manivel@ujf-grenoble.fr 

\end{document}

