MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

On the seqfan mailing list RGWv gave short algorithm for computing A000041 number of partitions of n the partition numbers:

f[1, 1] = 1; f[n_, k_] := f[n, k] = If[n < 0, 0, If[k > n, 0, If[k == n, 1, f[n, k + 1] + f[n - k, k]]]]

So number of partitions of $n$ is $f(n,1)$ where $f(n,k)$ is the recurrence:

$$f(1,1)=1$$ $$f(n,k)=1, k=n$$ $$f(n,k)=0 \text{ if } k>n \text{ or } n<0$$ $$f(n,k)=f(n,{k+1}) + f(n-k,k)$$

Blindly changing $k+1$ to next_prime(k) (see sage implementation) appears to give A034891 Number of different products of partitions of n; partitions of n into prime parts (1 included); number of distinct orders of Abelian subgroups of symmetric group S_n.

This was verfied for the first 1000 terms, the last term being > $10^{19}$.

Number of partitions of $n$ into prime parts (1 included) seems $f(n,1)$ where $f(n,k)$ is the recurrence:

$$f(1,1)=1$$ $$f(n,k)=1, k=n$$ $$f(n,k)=0 \text{ if } k>n \text{ or } n<0$$ $$f(n,k)=f(n,nextprime(k)) + f(n-k,k)$$

Is this a correct way to compute A034891?

$k+1$ in the original formula seems a successor relation.

Other changes of $k+1$:

$2k$ seems A018819 Binary partition function: number of partitions of n into powers of 2

$3k$ seems A062051 Number of partitions of n into parts which are powers of 3

|next_non_prime(k)| A002095 Number of partitions of n into nonprime parts.

|next_fibonacci(k)| A003107 Number of partitions of n into Fibonacci parts with a single type of 1

Update: According to this code Number of partitions of n into nonzero triangular numbers number of partitions of $n$ into increasing sequence $g(k)$ seems $f(n,1)$ where $f(n,k)$ is the recurrence:

$$f(n,k)=f(n-g(k),k) + f(n,k+1), \ \ n>g(k)$$ $$f(n,k)=1, \ n=g(k)$$ $$f(n,k)=0 \text{ otherwise }$$

#sage implementation for A034891
#usage: [partf(i) for i in xrange(1,100)]
def partf_(n,k,cac={}):
    if n==1 and k==1:
        return 1,cac
    if nn:  return 0,cac
    if k==n:  return 1,cac
    if (n,k) in cac:  return cac[(n,k)],cac
    #next_prime(k) can be changed to 2*k,3*k,next_non_prime(k),next_fibonacci(k)
    a,cac=partf_(n,next_prime(k),cac) #partf_(n,k+1,cac)
    b,cac = partf_(n-k,k,cac) # partf_(n-k,k,cac)
    a += b
    return a,cac
def partf(n,k=1):
    return a
share|cite|improve this question
The algorithm you have given is based on f[n, k] being the number of partitions of n into parts of size at least k. It uses k+1 to iterate, because it wants parts which include all natural numbers. Using a different successor function, the "partial function" f[n,k] might measure the number of partitions of n into primes no smaller than k - you just have to think through the interpretation a little. The treatment of 1 as a part is significant too. f[1, 1] = 1 implies 1 is a part. If not, more care is needed over defining a base case. – Mark Bennet Jan 25 '11 at 9:39
And care over the case of equality too. – Mark Bennet Jan 25 '11 at 9:41
@Mark without caring about the equality the first 1000 terms coincide. – joro Jan 25 '11 at 9:57
@joro I think you just have to work through some small cases to see what the equality case is doing here - which partition is it picking up that isn't included in the other case? It can't be the partition into 1 part (as in the general partitions case) because n is not always prime. – Mark Bennet Jan 25 '11 at 11:36
k runs in 1 union the primes and the equality adds 1. n changes as n-k. does this mean this is just hidden enumeration of all partitions? (i am somewhat puzzled because on the seqfan list was claimed that the number of partitions of 10^9 was computed in 40 seconds probably using memoization and this would seem to require a lot of RAM IMO). – joro Jan 25 '11 at 11:58

Your Answer


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

Browse other questions tagged or ask your own question.