Again on the number of partitions of n into parts of -k different kinds (k>0)

Michele Dondi blazar at
Thu Jun 24 18:16:20 CEST 2004

I thought some more on the subject and I realized that the obvious 

  p_k(n)=sum_{m=0}^n p_{k-1}(m) p(m-n),

holding for for the number of partitions of n into parts of k different 
kinds, holds for all k in Z as of my last post, so that the "number of 
different partitions of -1 different kinds" has a generating function that 
is the inverse of that of the number of partitions of n, i.e:

  f(x)=prod (1-x^k).

This makes it easy to write a naive program that gives (some more of) the
terms of the sequence:

#!/usr/bin/perl -l

use strict;
use warnings;

my @p=1;

for (1..500) {
    my $i;
    no warnings 'uninitialized';
    @p = map $p[$i++]-$_, (0) x $_, @p;
    print "$_:\t $p[$_]";


However this is still not terribly efficient, since to find the n-th terms 
you must compute n*(n+1)/2 of them, although the involved operations are 

Alternatively, the sequence of the number of different partitions of n 
into parts of -1 kinds is the Euler transform of [-1,-1,-1,...]

More for (coding) fun than for real need I'll try to write a program 
explicitly exploiting the Euler transform to see if more terms can be 
calculated like that.

Also, the product above seem to exhibit certain regularities that are less 
obvious and harder to prove something about than one could expect. But 
then I suppose it is well known and there are references available: can 
you suggest any?!?

> I understand that it is possible to express the number of ways of
> having k bishops on an n*n board such that they are not attacking each
> other as a combinatorial formula [...]
Why would bishops attack one another?  Oh--over homosexuality perhaps?
- George Cox on sci.math [edited]

More information about the SeqFan mailing list