\documentclass[12pt]{article} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \usepackage{amsthm} \usepackage{amssymb} \usepackage{latexsym} \usepackage{longtable} \usepackage{epsfig} \usepackage{amsmath} \usepackage{hhline} \newtheorem{thm}{Theorem}[section] \newtheorem{example}{Example}[section] \newtheorem{Corollary}{Corollary}[section] \newtheorem{prop}{Proposition}[section] \newtheorem{remarks}{Remarks}[section] \def\B{\hfill $\Box$} \begin{document} \begin{center} {\bf ON ELEMENTARY LOWER BOUNDS FOR THE PARTITION FUNCTION} \vskip 20pt {\bf Attila Mar\'oti\footnote{Research partially supported by the Hungarian National Foundation for Scientific Research Grant T034878.}}\\ {\smallit School of Mathematics and Statistics, University of Birmingham, Birmingham B15 2TT, United Kingdom}\\ {\tt marotia@maths.bham.ac.uk}\\ \vskip 10pt \end{center} \vskip 30pt \centerline{\smallit Received:1/8/03, Revised: 7/22/03, Accepted:7/30/03, Published: 7/31/03} \vskip 30pt \centerline{\bf Abstract} \noindent We present two analogues of two well-known elementary arguments for a lower bound for $p(n)$, the number of partitions of the integer $n$. One of these is character-theoretic, and the other relies on partition combinatorics developed and used in the theory of representations of the symmetric group. We show that these arguments provide better lower estimates. We also give an application. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 3 (2003), \#A10\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \section*{\normalsize 1. Introduction} Although the asymptotic $$\frac{e^{2\sqrt{\pi^{2}/6}\sqrt{n}}}{4n\sqrt{3}},$$ or even an exact formula for $p(n)$, the number of partitions of the integer $n$, is long known, good, explicit estimates for the partition function are not at all straightforward (for non-specialists) from the works of Hardy, Ramanujan, Uspensky and Rademacher. Elementary and analytic proofs for the asymptotic formula (see \cite{E}, (\cite{N}), \cite{V}, \cite{K}, \cite{A}) indicate that sharp universal {\it upper} bounds for $p(n)$ (holding for all $n$) are more natural than {\it lower} ones. Indeed, the partition function is relatively small compared to its asymptotic formula (above) at small integer values. There are two elementary arguments to estimate $p(n)$ from below: counting partitions by parts, and counting partitions with parts of bounded lengths. In this note, we present two analogues of these arguments. In particular, motivated by a group-theoretic application, to prove that the number of conjugacy classes of a primitive permutation group of degree $n$ is at most $p(n)$ (see \cite{M}), we state explicit lower bounds for $p(n)$ (holding for all $n$) which - we believe - are sharper than any other lower estimate available in the literature (see Corollary 2.1 with Remark (ii), Corollary 3.1 and Theorem 4.2). We note here that though the papers of Erd\H os \cite{E} and Newman \cite{N} give an elementary proof of the aymptotic expression for $p(n)$ starting from a simple, well-known recursion formula, their (accurate) lower bounds are quite implicit and valid only for sufficiently large $n$. On the other hand, in the case of our second method, it is not known whether the asymptotic formula for $p(n)$ is a direct consequence - in the spirit of Erd\H os and Newman - of Osima's recursion formula (see Theorem 4.1). Finally, as an application of our second method, we give a lower bound for the number of certain partitions of $n$ which are interesting in the modular representation theory of the symmetric group. \vskip 30pt \section*{\normalsize 2. Counting involutions} Let $G$ be any finite group of even order, and let ${\cal I}(G)$ denote the set of elements of order 2 (that is, involutions), of $G$. It is well known that we have $$1 + |{\cal I}(G)| = \sum_{ \chi \in Irr(G)} \nu(\chi)\chi(1),$$ where $Irr(G)$ denotes the set of complex irreducible characters of $G,$ and for $\chi \in Irr(G),$ $\nu(\chi)$ denotes the \emph{Frobenius-Schur indicator} of $\chi,$ which is $0$ if $\chi$ is not real-valued, $1$ if $\chi$ may be afforded by a \emph{real} representation, $-1$ if $\chi$ may not be afforded by a real representation. Using the Cauchy-Schwarz inequality, we deduce that $|{\cal I}(G)| < \sqrt{r(G)}\sqrt{|G|}$, where $r(G)$ is the number of irreducible characters of $G$ which may be afforded by real representations. In particular, $\frac{|{\cal I}(G)|^{2}}{|G|} < k(G)$, where $k(G)$ is the number of conjugacy classes of $G$ (and $k(G)$ is also the number of complex irreducible characters of $G$). We summarize this in the following. \noindent {\bf Theorem 2.1.} Let $G$ be a finite group and $t \in G$ be an arbitrary element of order $2$. We have $$\frac{|G|}{{|C_{G}(t)|}^2} < k(G),$$ where $C_{G}(t)$ is the centralizer of $t$ in $G$ and $k(G)$ is the number of conjugacy classes of $G$. Note that the dihedral groups show that the above estimate for $k(G)$ is sharp apart from a constant factor, and that the symmetric groups show that the involution, $t$ in the Theorem may not be replaced in general by any other element of order different than $2$. So what kind of lower bound does this argument give us for $k(S_{n}) = p(n)$ in the special case of the symmetric group? \noindent {\bf Corollary 2.1.} We have $$\frac{e^{2 \sqrt{n}}}{c n} < p(n)$$ for some constant $c$. \noindent {\it Proof.} We have $$p(n) = k(S_{n}) > \frac{|{\cal I}(S_{n})|^{2}}{n!} = \frac{( \sum_{t=1}^{[n/2]} f(n,t) )^{2}}{n!} > \sum_{t=1}^{[n/2]} \frac{f(n,t)^{2}}{n!},$$ where $f(n,t) = \frac{n!}{2^{t}t!(n-2t)!}$ is the number of involutions in $S_{n}$ which are products of $t$ disjoint transpositions. Now $$\frac{f(n,t)}{f(n,t+1)} = \frac{2(t+1)}{(n-2t)(n-2t-1)},$$ so we see easily that for a fixed $n$, we have $f(n,t) \leq f(n,t+1)$ precisely when $(n-2t)^{2} \geq n+2$. Hence the largest value of $f(n,t)$ for $n$ fixed and $t$ in the range of $[1,[n/2]]$ is taken by $t_{0}= \lfloor \frac{(n+2)- \sqrt{n+2}}{2} \rfloor$. Finally, by an elementary argument using Stirling's formula it may be shown that $\frac{f(n,t_{0})^{2}}{n!}$ is of the desired form. \B \noindent {\bf Remarks.} \rm (i) The fact that we concentrated on just a single contribution does not significantly affect the general nature of the lower bound (even if all the $f(n,t)$ were roughly equal, we would multiply by a factor of around $\frac{n^2}{4}$, but the $f(n,t)$'s decrease quickly as $t$ moves away from $t_0$). (ii) A more careful argument shows that the constant, $c$ in Corollary 2.1 may be taken to be $e^{3} \sqrt{2\pi^3}$. (iii) There is a combinatorial interpretation of the idea of the proof of Corollary 2.1 by means of the Robinson - Schensted algorithm. Indeed, the algorithm (see Chapter 3 of \cite{S}) provides a bijection between elements of $S_n$ and pairs of standard tableaux of the same shape. In particular, it gives $n! = \sum_{\lambda \vdash n } {a_{\lambda}}^2$ where $a_{\lambda}$ denotes the number of standard tableaux of shape $\lambda \vdash n$. A closer look at the algorithm shows that elements of order dividing $2$ are in correspondence with pairs of tableaux with identical entries. Hence we also have $1+ |\mathcal{I}(S_{n})| = \sum_{\lambda \vdash n} a_{\lambda}$. Now apply the inequality between the arithmetic and the quadratic means for the $a_{\lambda}$'s. (iv) One might wonder why this estimate is close to the general nature of $p(n)$? A possible answer is that ``almost all" irreducible character degrees of the symmetric group are ``roughly" equal. \medskip The above argument is similar to that of counting partitions by parts, however the character theory provides an even better lower estimate for the partition function. This will be shown in the rest of this section. There are at least $g(n,k) = {\frac{1}{k!}} \binom{n-1}{k-1}$ partitions of $n$ with exactly $k$ parts, so we have $\sum_{k=1}^{n}g(n,k) \leq p(n)$. Notice that for fixed $n$, the g(n,k)'s increase in the interval $[1,\sqrt{1+n}-1)$ and decrease in the interval $[\sqrt{1+n}-1,n]$. By Wallis's formula we see that $$\frac{{f(n,t)}^2}{n!} \sim \frac{1}{\sqrt{(\frac{\pi}{2})(2t+1)}} \cdot \frac{1}{(n-2t)!} \binom{n}{n-2t}$$ as both $t$ and $(t <<) n$ tend to infinity. For $k \equiv n \ mod \ (2)$ define the function $$G(n,k) = \frac{n! \cdot (g(k-1)+g(k))}{{f(n,(n-k)/2)}^2}.$$ There exists an irrational number $0 < c < 1$ and an integer $N_1$ such that if $n > N_{1}$, then $G(n,k) < \sqrt[3]{7/6} \sqrt{2\pi}$ for all $k$ in the interval $((1-c)\sqrt{n}-1,(1+c)\sqrt{n}+1)$ and that $[(1-c)\sqrt{n}] \equiv n \ mod \ (2)$. Now choose $\epsilon$ to be $0$ or $1$ such that $[(1+c)\sqrt{n} + \epsilon] \equiv n \ mod \ (2)$. Put $c_{1} = [(1-c)\sqrt{n}+1]$ and $c_{2} = [(1+c)\sqrt{n}+\epsilon]$ for convenience. Now choose an integer, $N_2$ such that if $n > N_2$, then $$\sum_{k=1}^{n} g(n,k) < \sqrt[3]{7/6} \sum_{k=c_{1}}^{c_{2}} g(n,k).$$ There are $l= \frac{c_{2}-c_{1}+1}{2}$ number of integers $k$ in the interval $[c_{1},c_{2}]$ congruent to $n$ modulo $2$. For each such $k$ we have an integer $t= \frac{n-k}{2}$. Label these $l$ number of $t$'s with subscripts $1$ through $l$ such that $f(n,t_{1}) < \ldots < f(n,t_{l})$. (Note that the $t_{i}$'s implicitly depend on $n$. When we write $f(n,t_{i})$, we really mean $f(n,t_{i}(n)$.) Choose an integer $N_3$ such that whenever $n > N_3$, then $l > 3$ and $f(n,t_{l}) < \sqrt[3]{7/6} \cdot f(n,t_{l-3})$ follow. Put $N = \ max \ \{ N_{1}, N_{2}, N_{3} \}$. If $n > N$, we have $$\sqrt[3]{7/6} \sum_{k=c_{1}}^{c_{2}} g(n,k) < {(\sqrt[3]{7/6})}^{2} \sqrt{2\pi} \sum_{i=1}^{l} \frac{{f(n,t_{i})}^2}{n!} < $$ $$ < \frac{(7/6)\sqrt{2\pi}}{3} \frac{{ ( {\sum_{i=1}^{l} f(n,t_{i})} ) }^{2}}{n!} < \frac{ {( \sum_{t=1}^{[n/2]} f(n,t) ) }^{2}}{n!}.$$ So indeed, the above argument produces a better lower bound for $p(n)$. \vskip 30pt \section*{\normalsize 3. Counting characters in the principal block} It is well-known that the (complex) irreducible characters of the symmetric group, $S_n$ are labelled canonically by partitions of $n$. So if $\lambda$ is a partition of $n$, denote the corresponding (complex) irreducible character of $S_n$ by $\chi_{\lambda}$. Now fix an integer $d>1$. For each partition $\lambda$ of $n$ we may define a $d$-core, $\gamma_{\lambda}$ and a $d$-quotient, $\beta_{\lambda}$ as in section 2.7 of \cite{JK}. The $d$-core is obtained from $\lambda$ by removing all $d$-hooks from $\lambda$. The number of $d$-hooks to be removed from $\lambda$ to go to the core is called the $d$-weight of $\lambda$ and is denoted by $w_{\lambda}$. The quotient $\beta_{\lambda}$ is a $d$-tuple of partitions whose cardinalities add up to $w_{\lambda}$. It is known that $\beta_{\lambda}$ and $\gamma_{\lambda}$ determine $\lambda$ uniquely. A combinatorial $d$-block is a non-empty subset, $B$ of $Irr(S_{n})$ with the property that the set of all partitions labelling the characters in $B$ is precisely the set of partitions having a fixed $d$-core. The principal combinatorial $d$-block is the block which contains the trivial character of $S_n$, the one labelled by the partition $(1^n)$, that is the partition with all parts being $1$. Nakayama's conjecture (which is already a theorem) states that for any prime $p$, the combinatorial $p$-blocks of $S_n$ are precisely the usual $p$-blocks of modular representation theory. Recently, it was proved in \cite{KOR} that for each integer $d>1$ the combinatorial $d$-blocks coincide with the block-theoretic $\mathcal{C}$-blocks where $\mathcal{C}$ is a certain union of (naturally defined) conjugacy classes of $S_n$. Loosly speaking, Nakayama's conjecture is generalized for arbitrary integers, $d>1$. This allows us to talk about just $d$-blocks rather than combinatorial $d$-blocks. In this present work we will only need (and use) the basic combinatorics associated with partitions described above. (This is why our method will be elementary.) However, it is important to note that everything may be set in a wider and more natural block-theoretic context. Let us continue with an observation. \noindent {\bf Theorem 3.1.} For all positive integers $d \leq n$ we have $p([n/d^{2}])^{d} \leq p(n)$. \noindent {\it Proof.} This is obvious for $d=1$. So suppose that $d>1$. The principal $d$-block has $$\sum_{w_{1},w_{2},...,w_{d}} p(w_{1})p(w_{2})...p(w_{d})$$ number of irreducible characters with different $d$-quotients of partitions labelling them where the $w_{i}$'s are nonnegative integers satisfying $w_{1}+w_{2}+...+w_{d}= [n/d]$. This number is at least $p([n/d^{2}])^{d}$. \B If $d=[\sqrt{n/2}]$, then Theorem 3.1 gives the estimate $2^{[ \sqrt{n/2} ]} \leq p(n)$, which is similar to saying that there are at least $2^{[ \sqrt{n/2} ]}$ partitions of $n$ with parts not exceeding $[ \sqrt{n/2} ]$. By counting partitions with parts of bounded lengths one can not easily do better than $2^{\sqrt{2n}}/c < p(n)$ where $c$ is a constant. However Theorem 3.1 suggests more. \noindent {\bf Corollary 3.1.} For all integers $n$ we have $$\frac{e^{2 \sqrt{n}}}{14} < p(n).$$ \noindent {\it Proof.} For integers $n < 190$ this may be checked by computer. Similarly, if $190 \leq n < 760$, then it is checked that $e^{2(\sqrt{n}+0.25)} < p(n)$ holds. Finally, if $n \geq 760$, then by Theorem 3.1 and by induction, we have $$p(n) > p([[n/2]/2])^{2} > e^{4(\sqrt{[[n/2]/2]}+0.25)} > e^{2(\sqrt{n}+0.25)}.$$ \B \noindent {\bf Remark.} \rm The estimate of Corollary 3.1 is better than the one noted in remark (ii) of Corollary 2.1. However, in the previous proof we had to check all values of $p(n)$ for $n$ no greater than $760$ to start the induction, while in our other method we only have to know the values of $p(n)$ for integers less than $110$. \medskip Notice that this lower bound may considerably be sharpened provided that we have a good computer. Theoretically, Theorems 3.1 with the idea in the proof of Corollary 3.1 gives a method to set an $\frac{e^{(c_{0}- \epsilon) \sqrt{n}}} {A(\epsilon)} < p(n)$-type lower bound for any given $\epsilon$ where $A(\epsilon)$ is some constant depending on $\epsilon$ and where $c_{0} = 2\sqrt{\pi^{2}/6} \sim 2.56...$. We demonstrate this in the following example. \medskip \noindent {\bf Example. \rm} Since $e^{2.5 \cdot 10^3} < p(10^6)$, applying Theorem 3.1 for $d=10$, we see that there exists a computable constant $c$, such that $\frac{e^{2.5 \sqrt{n}}}{c} < p(n)$ for all $10$-powers, $n$. \vskip 30pt \section*{\normalsize 4. A sharp lower bound} The example above shows that it is hard to set a universal $\frac{e^{2.5 \cdot \sqrt{n}}}{cn}$ -type lower bound for $p(n)$ by only relying on Theorem 3.1. In this section we present a recursion formula (see Theorem 3 of \cite{O}) for $p(n)$ with which we are able to give such a lower estimate. \noindent {\bf Theorem 4.1.} For all integers $n$ we have $$ p(n) = \sum_{t=0}^{n} \overset{n}{\underset{4w+t(t+1) = 2n} {\underset{w=0}{\sum}}} \sum_{l=0}^{w} p(l) p(w-l).$$ Note that all $l$ and $m-l$ appearing in the above Theorem are at most $[n/2]$. \noindent {\it Proof.} Recall that each $2$-block of $S_n$ is uniquely determined by a certain $2$-core. Moreover, by section 2.7 of \cite{JK}, a partition of $n$ is uniquely determined by its $2$-core and its $2$-quotient, and each ``possible" pair consisting of a $2$-core and a $2$-quotient determines a partition. So we may label each $2$-block, $B$ of the symmetric group, $S_n$ by some integer, $t$ congruent to $n$ modulo $2$ with $t(t+1)/2 \leq n$ such that the $2$-core corresponding to the block $B$ is a partition of the integer $t(t+1)/2$. It is easy to see that this correspondence is one to one between the set of $2$-blocks of $S_n$ and the set of integers $t$ congruent to $n$ modulo $2$ with $t(t+1)/2 \leq n$. Finally, for a given $t$, the expression on the right hand side of the equality without the first sum is exactly the number of irreducible characters in the $2$-block of $S_n$ corresponding to the integer $t$. \B Before we state the main theorem of this section, observe that the function $f(x) = \frac{e^{2.5 \cdot \sqrt{x}}}{\sqrt{x}}$ defined for all real numbers $x>1$ is monotone increasing. Moreover define the function $p'(x)$ on all real numbers $x>1$ by putting $p'(x) := p(x)$ whenever $x$ is an integer and by $p'(x) := f(x)$ otherwise. \noindent {\bf Theorem 4.2.} For all integers $n$ we have $$\frac{e^{2.5 \cdot \sqrt{n}}}{13 n} < p(n).$$ \noindent {\it Proof.} This is true for integers $n < 11000$. One can also check by computer that if $11000 \leq n < 45000$, then $f(x) < p(n)$. So let us suppose that $n \geq 45000$. Count all ordered pairs of integers $(l,w-l)$ in the recursion formula in Theorem 4.1 for which $\frac{n}{2} - \frac{1}{4}\sqrt{n} \leq w \leq \frac{n}{2}$ and for which both $l$ and $w-l$ is not less than $\frac{n-\sqrt{n}}{4}$. There are less than $$g(n) := 2 \cdot (\frac{1}{8}\sqrt{n}-2) \cdot \frac{\sqrt{2}}{4} \cdot n^{0.25}$$ such ordered pairs. So by Theorem 4.1, we have $p(n) > g(n) \cdot {p'((n-\sqrt{n})/4)}^2$. To finish the proof, it is sufficient to show that $g(n) \cdot {p'((n-\sqrt{n})/4)}^2 > f(n)$, that is, to show $$\frac{n - 16\sqrt{n}}{n-\sqrt{n}} \cdot \frac{\sqrt{2}}{4} \cdot n^{0.25} > e^{2.5 (\sqrt{n} - \sqrt{n-\sqrt{n}})}.$$ Since the right-hand side of the previous inequality is less than $e^{1.25}$, it is sufficient to see $$\frac{n - 16\sqrt{n}}{n-\sqrt{n}} \cdot \frac{\sqrt{2}}{4} \cdot n^{0.25} > e^{1.25}.$$ But this is clearly true for $n \geq 45000$. \B \vskip 30pt \section*{\normalsize 5. An application} Euler showed that the number of partitions of $n$ with different parts is equal to the number of partitions of $n$ with odd parts. This was generalized in $1883$ by Glaisher. \noindent {\bf Proposition 5.1.} Fix any positive integer $d$. The number of partitions of $n$ not containing $d$ equal parts is equal to the number of partitions of $n$ with no part divisible by $d$. Denote this common number by $p_{d}^{*}(n)$. By Proposition 5.2 of \cite{KOR} and by Theorem 4.2 we are able to give good lower bounds for the $p_{d}^{*}(n)$'s. \noindent {\bf Theorem 5.1.} For all integers $d>1$ and $n \geq d^2$, we have $${\Big(\frac{d(d-1)}{160n}\Big)}^{\sqrt{d}} \cdot e^{2.5 \cdot \sqrt{(1-1/d)n}} < p_{d}^{*}(n).$$ \noindent {\it Proof.} By Theorem 6.2.2 of \cite{JK} and by the proof of Theorem 3.1, we see that $p([[n/d]/(d-1)])^{d-1} \leq p_{d}^{*}(n)$. Using Theorem 4.2 to estimate the left hand side of the previous inequality we get $$p_{d}^{*}(n) \cdot {(d(d-1))}^{-d} > \frac{e^{2.5 \cdot (d-1) \sqrt{(n-d)/(d(d-1))-1}}}{{(13n)}^{d}} = \frac{e^{2.5 \cdot \sqrt{(1-1/d)n -{(d-1/2)}^2}}}{{(13 n)}^{d}}.$$ Since $n \geq d^2$, we conclude that $$\frac{e^{2.5 \cdot \sqrt{(1-1/d)n - {(d-1/2)}^2}}}{{(13 n)}^{d}} > \frac{e^{2.5 \cdot \sqrt{(1-1/d)n}-(d-1/2)}}{{(13 n)}^{d}} > \frac{e^{2.5 \cdot \sqrt{(1-1/d)n}}}{{(160n)}^{d}}.$$ \B By Theorem 6.2.2 of \cite{JK} and by Theorem 4.1, we find a recursion formula for $p_{2}^{*}(n)$. \noindent {\bf Theorem 5.2.} The number of partitions of $n$ with different parts, and the number of partitions of $n$ with odd parts is equal to $$\sum_{t=0}^{n} \overset{n}{\underset{4m+t(t+1) = 2n}{\underset{m=0}{\sum}}} p(m).$$ The number of partitions of $n$ with different odd parts is equal to the number of self-conjugated partitions of $n$. Denote this number by $u(n)$. Theorem 4 of \cite{O} is the following. \noindent {\bf Theorem 5.3.} For a given integer $n$, let $s_i$ $(i = 1, \ldots ,q)$ be all of the non-negative integer solutions of the equations $n-4s = \frac{1}{2}k(k+1)$ $(k=0, 1, \ldots)$. Then $$u(n) = \sum_{i=1}^{q} p(s_{i}).$$ In particular, we have $p(s_{j}) < u(n)$ where $s_j$ is the largest number among the $s_i$'s. Bt the use of Theorem 4.2, this observation allows us to give an even sharper bound than the one in Theorem 5.1 in the special case of $d=2$. \noindent {\bf Theorem 5.4.} If $n>10$, then we have $$\frac{e^{1.25 \sqrt{n-6}}}{4(n-6)} < u(n) < p_{2}^{*}(n).$$ \vskip 30pt \section*{\normalsize Acknowledgements} The use of character theory in Section 2 was suggested to me by G. R. Robinson, who I thank most heartily. \vskip 30pt \begin{thebibliography}{30} \footnotesize \bibitem{A} Apostol, T. M. Introduction to analytic number theory. \emph{Undergraduate Texts in Mathematics. Springer-Verlag}, New York-Heidelberg, (1976). \bibitem{E} Erd\H{o}s, P. On an elementary proof of some asymptotic formulas in the theory of partitions. \emph{Ann. of Math.} (2) \textbf{43} (1942), 437--450. \bibitem{K} Knopp, M. I. Modular functions in analytic number theory. \emph{Markham Publishing Co.}, Chicago, Ill. (1970). \bibitem{KOR} K\"ulshammer, B; Olsson, J. B; Robinson, G. R. Generalized blocks for symmetric groups, \emph{Invent. Math.} \textbf{151} (2003), no. 3, 513--552. \bibitem{JK} James, G; Kerber, A. The representation theory of the symmetric group. \emph{Encyclopedia of Mathematics and its Applications} \textbf{16} (1981). \bibitem{M} Mar\'oti, A. Bounding the number of conjugacy classes of a permutation group, submitted. \bibitem{N} Newman, D. J. The evaluation of the constant in the formula for the number of partitions of $n$. \emph{Amer. J. Math.} \textbf{73}, (1951). 599-601. \bibitem{O} Osima, M. On the irreducible representations of the symmetric group. \emph{Canadian J. Math.} \textbf{4} (1952). 381--384. \bibitem{S} Sagan, B. E. The symmetric group. Representations, combinatorial algorithms, and symmetric functions. Second edition. Graduate Texts in Mathematics, \textbf{203}, \emph{Springer-Verlag}, New York, 2001. \bibitem{V} van Lint, J. H. Combinatorial Theory Seminar, \emph{Lecture Notes in Mathematics}, Vol. \textbf{382.} \emph{Springer-Verlag}, Berlin-New York, (1974). \end{thebibliography} \end{document}