login
A096443
Number of partitions of a multiset whose signature is the n-th partition (in Mathematica order).
14
1, 1, 2, 2, 3, 4, 5, 5, 7, 9, 11, 15, 7, 12, 16, 21, 26, 36, 52, 11, 19, 29, 38, 31, 52, 74, 66, 92, 135, 203, 15, 30, 47, 64, 57, 98, 141, 109, 137, 198, 296, 249, 371, 566, 877, 22, 45, 77, 105, 97, 171, 250, 109, 212, 269, 392, 592, 300, 444, 560, 850, 1315, 712, 1075
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.
Also, a(n) is the number of distinct factorizations of A063008(n). For example, A063008(10) = 60 and 60 has 11 factorizations: 60, 30*2, 20*3, 15*4, 15*2*2, 12*5, 10*6, 10*3*2, 6*5*2, 5*4*3, 5*3*2*2 which confirms that 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
Sequence in context: A261771 A015743 A015755 * A126442 A129306 A322077
KEYWORD
nonn
AUTHOR
Jon Wild, Aug 11 2004
EXTENSIONS
Edited by Franklin T. Adams-Watters, May 16 2006
STATUS
approved