Again on the number of partitions of n into parts of -k different kinds (k>0)
Michele Dondi
blazar at pcteor1.mi.infn.it
Thu Jun 24 18:16:20 CEST 2004
I thought some more on the subject and I realized that the obvious
relationship
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[$_]";
}
__END__
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
lightweight.
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?!?
Michele
--
> 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