7
$\begingroup$

Let be $ p(n,4)$ number of partitions of $ n $ in parts no greater than $4$ then

$p(13n,4)-p(n,4)={61\over4}n^3 + {35\over2}n^2 + \frac{45+3(-1)^n}{8}n$

I can prove this identity that seems to me very interesting (In my work, still unpublished, I need 3 or 4 pages to explain it at all). If someone has any reference where is mentioned above formula lets me know, or a short proof if it is possible. See [A191698] in OEIS

3 Answers 3

6

For fixed $k$, the sequence $p(n, k)$ has generating function

$F_k(x) = \sum_{n \ge 0} p(n, k) x^n = \frac{1}{(1 - x)(1 - x^2)...(1 - x^k)}.$

This generating function is rational, so partial fraction decomposition gives an explicit formula for its coefficients. If this isn't covered in Wilf's generatingfunctionology, it should be covered in Flajolet and Sedgewick's Analytic Combinatorics.

A very general approach to automatically proving certain types of combinatorial identities, which I am reasonably sure handles this special case correctly, is described in Petkovsek, Wilf, and Zeilberger's A=B.

  • 0
    @Adi: I only suggested $k = 2$ as an exercise, not as a necessary step in proving this identity. Again, the details are messy, but algorithmic. There are probably computer algebra packages (perhaps they are described in A=B) that can automatically do this for you.2011-07-21
3

With regard to Qiaochu's answer, the partial fraction decomposition is messy (compared, say, to anything you'd put on a calculus exam), having 8 terms, and coefficients like 59/288. It's worked out in detail in the lovely book by Andrews and Eriksson, Integer Partitions, in Section 6.3, A formula for $p(n,4)$, pages 58-60. They give several formulas for $p(n,4)$, perhaps the simplest is $p(n,4)={\rm\ nearest\ integer\ to\ }{(n+5)(n^2+n+22+18\left[{n\over2}\right])\over144}$

I suppose one could use this to have a go at $q(n)=p(13n,4)-p(n,4)$. But it might be better to work directly with a generating function for $q(n)$.

1

To add to Qiaochu's answer, there is a large body of work in existence on the Partition Function. Let $P(n,k)$ denote the number of ways to write $n$ as a sum of exactly $k$ positive integers. (Similar to your $p(n,k)$ above) Then we have the recurrence relation $P(n,k)=P(n-1,k-1)+P(n-k,k).$ This can be solved exactly, see equations $(61)$ to $(66)$ of the Wolfram link.