4
$\begingroup$

The number of partitions of $2n$ into partitions with no element greater than $n$ (copied and slightly adapted from http://mathworld.wolfram.com/PartitionFunctionq.html), so I'm looking for a nice formula of $q(2n,n)$.

By asking http://www.wolframalpha.com/input/?i=integer+partitions+of+12 and counting the ones of interest I get results from 2 to 12, that look the following: $ 1,3,7,15,30,58 $ which matches the data from http://oeis.org/A026820/table when you start from the $1$ in the 2.row and go straight down. My question is now, if there is closed formula or at least an asymptotic for $q(2n,n)$?

  • 0
    @joriki: yes, thx, I'll change that. Any idea of a solution? Approximations/asymptotics welcome...2012-01-03

3 Answers 3

4

For large $n$, these are almost all the partitions there are. There can be at most one part $m$ larger than $n$, and the remaining parts form a partition of $2n-m$, so we have

$q(2n,n)=p(2n)-\sum_{k=0}^{n-1}\;p(k)\;.$

For large $n$, the terms in the sum are exponentially smaller than $p(2n)$, so asymptotically

$q(2n,n)\sim p(2n) \sim \frac {1} {8n\sqrt{3}} e^{\pi \sqrt {\frac{4n}{3}}}\;.$

1

The first $36$ values are:

1, 3, 7, 15, 30, 58, 105, 186, 318, 530, 863, 1380, 2164, 3345, 5096, 7665, 11395, 16765, 24418, 35251, 50460, 71669, 101050, 141510, 196888, 272293, 374423, 512081, 696760, 943442, 1271527, 1706159, 2279700, 3033772, 4021695, 5311627

Here’s a (lin-log) graph, also showing the curve for Joriki’s asymptotic expression $\frac{1}{8 n \sqrt{3}} e^{\pi \sqrt{\frac{4 n}{3}}}$.

$\hspace{1in}$ graph

The list was generated using

Length@IntegerPartitions[2n, All, Range[n]] 

in Mathematica.

0

Using the following result for restricted partition generating functions, what I need can be calculated like $ \left(\frac{d^{2n}}{dx^{2n}}\prod_{k=1}^n (1-x^k)^{-1} \right) \Biggr|_{x=0} =\left(\frac{d^{2n}}{dx^{2n}}\sum_{k=0}^\infty h_{nk}x^k\right) \Biggr|_{x=0}, $ where $h_{nk}$ is the number of ways, that $k$ can be written with $n$ as largest value.