# Number of partitions of -k different kinds! (k>0)

Michele Dondi blazar at pcteor1.mi.infn.it
Wed Jun 16 16:52:50 CEST 2004

```Although of course there can't be such a thing as a "partition of n of -1,
-2, etc. different kinds", for all k>=1 each partition of n contributes to
the number of partitions of k different kinds

prod_i P_k(m(i)),

where the product is extended to all i in the partition, m(i) is the
number of times i appears in the partition itself, and

P_1(n)=1 for all n>=0,
P_k(n)=sum_{j=0}^n P_{k-1}(j) for all k>=1, n>=0

is the number of different ways to assign k labels to n identical objects.
(Consistently P_k(0)=1 for all k.)

But the functions P_k can be generalized to all k in Z, precisely

p_{-k}(n)=(-1)^n C(k,n) for all k>=0,

where C(k,n) is the binomial coefficient. Thus we can use the same
algorithm as above, summing over all partitions of n, with P_(-k), k>=1.
(k=0 yields the "trivial" sequence 1,0,0,...). The resulting sequences are
tabulated hereafter for k=1,2,3 and 0<=n<=50.

k=1

0:	1
1:	-1
2:	-1
3:	0
4:	0
5:	1
6:	0
7:	1
8:	0
9:	0
10:	0
11:	0
12:	-1
13:	0
14:	0
15:	-1
16:	0
17:	0
18:	0
19:	0
20:	0
21:	0
22:	1
23:	0
24:	0
25:	0
26:	1
27:	0
28:	0
29:	0
30:	0
31:	0
32:	0
33:	0
34:	0
35:	-1
36:	0
37:	0
38:	0
39:	0
40:	-1
41:	0
42:	0
43:	0
44:	0
45:	0
46:	0
47:	0
48:	0
49:	0
50:	0

k=2

0:	1
1:	-2
2:	-1
3:	2
4:	1
5:	2
6:	-2
7:	0
8:	-2
9:	-2
10:	1
11:	0
12:	0
13:	2
14:	3
15:	-2
16:	2
17:	0
18:	0
19:	-2
20:	-2
21:	0
22:	0
23:	-2
24:	-1
25:	0
26:	2
27:	2
28:	-2
29:	2
30:	1
31:	2
32:	0
33:	2
34:	-2
35:	-2
36:	2
37:	0
38:	-2
39:	0
40:	-4
41:	0
42:	0
43:	0
44:	1
45:	-2
46:	0
47:	0
48:	2
49:	0
50:	2

k=3

0:	1
1:	-3
2:	0
3:	5
4:	0
5:	0
6:	-7
7:	0
8:	0
9:	0
10:	9
11:	0
12:	0
13:	0
14:	0
15:	-11
16:	0
17:	0
18:	0
19:	0
20:	0
21:	13
22:	0
23:	0
24:	0
25:	0
26:	0
27:	0
28:	-15
29:	0
30:	0
31:	0
32:	0
33:	0
34:	0
35:	0
36:	17
37:	0
38:	0
39:	0
40:	0
41:	0
42:	0
43:	0
44:	0
45:	-19
46:	0
47:	0
48:	0
49:	0
50:	0

The sequences were generated by brute force with the following Perl
program (not particularly smart, only slightly optimized):

#!/usr/bin/perl -l

use strict;
use warnings;

sub part;
sub wkpart;
sub wkind;
sub kfunc;

{
my @mem = [[]];

sub part {
my \$n=shift;
my %seen;
@{ \$mem[\$n] ||= [grep !\$seen{"@\$_"}++,
map { adjoin \$_, part \$n-\$_ } 1..\$n] };
}

sub wkind {
my (\$n,\$t)=shift;
my @ok=grep \$_->[1],
map [\$_, wkpart \$_], part \$n;
\$mem[\$n]=[ map \$_->[0], @ok ];
\$t+=\$_->[1] for @ok;
\$t;
}

}

my \$n=shift;
map [ sort {\$a <=> \$b} @\$_, \$n], @_;
}

sub wkpart {
my (\$k,%b)=1;
\$b{\$_}++ for @{shift()};
\$k*=kfunc \$b{\$_} ||
return 0 for keys %b;
\$k;
}

sub kfunc {
(1,-1)[shift] || 0;
}

print \$_, ":\t", wkind \$_ for 0..50;

__END__

This program generates the sequence for k=1; substituting the line

(1,-1)[shift] || 0;

with

(1,-2,1)[shift] || 0;

and

(1,-3,3,-1)[shift] || 0;

will give the programs to generate the sequence for k=2 and 3
respectively.

I wanted to contribute these sequences to OEIS, but I was uncertain about
the exact phrasing of some fields. Any comment?!?

TIA,
Michele
--
MANIOS MED FHEFHAKED NUMASIOI
- "Fibula Praenestina"

```