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

[Michele Dondi]

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 adjoin;
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;
    }

}

sub adjoin {
    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"