A096443 Number of partitions of a multiset whose signature is the n-th partition (in Mathematica order).

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

Author

Jon Wild, Aug 11 2004

Keywords

• nonn

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

Examples

			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.
		

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.

Crossrefs

Cf. A035098, A035310.

Programs

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 *)

Extensions

Edited by Franklin T. Adams-Watters, May 16 2006