Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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. –  Patrick Da Silva Jan 3 '12 at 15:29
    
@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? –  draks ... Jan 3 '12 at 15:34
    
$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. –  Patrick Da Silva Jan 3 '12 at 15:53
    
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. –  Patrick Da Silva Jan 3 '12 at 16:13
    
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. –  joriki Jan 3 '12 at 17:49
show 1 more comment

3 Answers

up vote 4 down vote accepted

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}}}\;.$$

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.