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,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

Table of n, a(n) for n=0..63.

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

Cf. A035098, A035310.

Sequence in context: A261771 A015743 A015755 * A126442 A129306 A322077

Adjacent sequences: A096440 A096441 A096442 * A096444 A096445 A096446

Keyword

nonn

Author

Jon Wild, Aug 11 2004

Extensions

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

Status

approved