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)$?

  • 1
    Maybe I am wrong, but shouldn't you expect something like $$ q(2n,n) = p(2n) - p(n) $$ where $p(n)$ is the number of partitions of $n$? In other words, I am counting the number of partitions of $2n$ and removing those partitions who already have one integer greater or equal to $n$ in it, and I think there are $p(n)$ such partitions of $2n$ which have this property.2012-01-03
  • 0
    @PatrickDaSilva: No I don't. That's why I was wondering that the numbers matched that good. Any idea what they (WIKI) are talking about?2012-01-03
  • 0
    $p(k,n)$ is defined as number of partitions of $n$ where the summands are all $\ge k$. By splitting this into two cases, i.e. when one of the summands is $k$ and when one of the summands isn't, they achieve this identity. $p(k+1,n)$ accounts for the number of partitions with no summands equal to $k$, and if there is one summand equal to $k$, you subtract it from $n$ and count partitions of the rest with summands $\ge k$. This gives you $p(k,n) = p(k+1,n) + p(k,n-k)$. Note that $p(a,b) \neq p(b,a)$ so be careful when you're quoting.2012-01-03
  • 0
    Dahhhhh crap. I wrote an answer which is total junk. I thought I had it and stumbled across something, then noticed what was the problem.2012-01-03
  • 0
    I think you mean $p(1,2n)-p(2,2n)$ (with $2n$ instead of $n$)? This holds only up to $n=5$ and seems to be coincidental. Using generating functions, you can show that $p(1,n)-p(2,n)=p(n-1)$, so this is just $p(2n-1)$, and $p(11)=56$, not 58.2012-01-03
  • 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.