OFFSET
0,3
COMMENTS
The signature of a multiset is the partition consisting of the multiplicities of its elements; e.g., {a,a,a,b,c} is represented by [3,1,1]. The Mathematica order for partitions orders by ascending number of total elements, then by descending numerical order of its representation. The list begins:
n.....#elements.....n-th partition
0.....0 elements:....[]
1.....1 element:.....[1]
2.....2 elements:....[2]
3....................[1,1]
4.....3 elements:....[3]
5....................[2,1]
6....................[1,1,1]
7.....4 elements:....[4]
8....................[3,1]
9....................[2,2]
10...................[2,1,1]
11...................[1,1,1,1]
12....5 elements:....[5]
13...................[4,1]
A000041 and A000110 are subsequences for conjugate partitions. A000070 and A035098 are also subsequences for conjugate partitions. - Alford Arnold, Dec 31 2005
A002774 and A020555 is another pair of subsequences for conjugate partitions. - Franklin T. Adams-Watters, May 16 2006
LINKS
Jun Kyo Kim and Sang Guen Hahn, Recursive Formulae for the Multiplicative Partition Function, Internat. J. Math. & Math. Sci., 22(1) (1999), 213-216.
A. Knopfmacher, M. E. Mays, A survey of factorization counting functions, International Journal of Number Theory, 1(4):563-581,(2005). See P(n) page 3.
EXAMPLE
The 10th partition is [2,1,1]. The partitions of a multiset whose elements have multiplicities 2,1,1 - for example, {a,a,b,c} - are:
{{a,a,b,c}}
{{a,a,b},{c}}
{{a,a,c},{b}}
{{a,b,c},{a}}
{{a,a},{b,c}}
{{a,b},{a,c}}
{{a,a},{b},{c}}
{{a,b},{a},{c}}
{{a,c},{a},{b}}
{{b,c},{a},{a}}
{{a},{a},{b},{c}}
We see there are 11 partitions of this multiset, so a(10)=11.
MATHEMATICA
MultiPartiteP[n : {___Integer?NonNegative}] :=
Block[{p, $RecursionLimit = 1024, firstPositive},
firstPositive =
Compile[{{vv, _Integer, 1}},
Module[{k = 1}, Do[If[el == 0, k++, Break[]], {el, vv}]; k]];
p[{0 ...}] := 1;
p[v_] :=
p[v] = Module[{len = Length[v], it, k, zeros, sum, pos, gcd},
it = Array[k, len];
pos = firstPositive[v];
zeros = ConstantArray[0, len];
sum = 0;
Do[If[it == zeros, Continue[]];
gcd = GCD @@ it;
sum += it[[pos]] DivisorSigma[-1, gcd] p[v - it]; ,
Evaluate[Sequence @@ Thread[{it, 0, v}]]];
sum/v[[pos]]];
p[n]];
ParallelMap[MultiPartiteP,
Flatten[Table[IntegerPartitions[k], {k, 0, 8}], 1]]
(* Oleksandr Pavlyk, Jan 23 2011 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Jon Wild, Aug 11 2004
EXTENSIONS
Edited by Franklin T. Adams-Watters, May 16 2006
STATUS
approved