cp's OEIS Frontend

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

%I A096443 #30 Aug 06 2024 09:35:15
%S A096443 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,
%T A096443 66,92,135,203,15,30,47,64,57,98,141,109,137,198,296,249,371,566,877,
%U A096443 22,45,77,105,97,171,250,109,212,269,392,592,300,444,560,850,1315,712,1075
%N A096443 Number of partitions of a multiset whose signature is the n-th partition (in Mathematica order).
%C A096443 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:
%C A096443 n.....#elements.....n-th partition
%C A096443 0.....0 elements:....[]
%C A096443 1.....1 element:.....[1]
%C A096443 2.....2 elements:....[2]
%C A096443 3....................[1,1]
%C A096443 4.....3 elements:....[3]
%C A096443 5....................[2,1]
%C A096443 6....................[1,1,1]
%C A096443 7.....4 elements:....[4]
%C A096443 8....................[3,1]
%C A096443 9....................[2,2]
%C A096443 10...................[2,1,1]
%C A096443 11...................[1,1,1,1]
%C A096443 12....5 elements:....[5]
%C A096443 13...................[4,1]
%C A096443 A000041 and A000110 are subsequences for conjugate partitions. A000070 and A035098 are also subsequences for conjugate partitions. - _Alford Arnold_, Dec 31 2005
%C A096443 A002774 and A020555 is another pair of subsequences for conjugate partitions. - _Franklin T. Adams-Watters_, May 16 2006
%H A096443 Jun Kyo Kim and Sang Guen Hahn, <a href="http://www.emis.de/journals/HOA/IJMMS/22/1213.pdf">Recursive Formulae for the Multiplicative Partition Function</a>, Internat. J. Math. & Math. Sci., 22(1) (1999), 213-216.
%H A096443 A. Knopfmacher, M. E. Mays, <a href="https://citeseerx.ist.psu.edu/pdf/d7ed31ad7c11cad37442838d6614f658af539ef5">A survey of factorization counting functions</a>, International Journal of Number Theory, 1(4):563-581,(2005). See P(n) page 3.
%e A096443 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:
%e A096443 {{a,a,b,c}}
%e A096443 {{a,a,b},{c}}
%e A096443 {{a,a,c},{b}}
%e A096443 {{a,b,c},{a}}
%e A096443 {{a,a},{b,c}}
%e A096443 {{a,b},{a,c}}
%e A096443 {{a,a},{b},{c}}
%e A096443 {{a,b},{a},{c}}
%e A096443 {{a,c},{a},{b}}
%e A096443 {{b,c},{a},{a}}
%e A096443 {{a},{a},{b},{c}}
%e A096443 We see there are 11 partitions of this multiset, so a(10)=11.
%e A096443 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.
%t A096443 MultiPartiteP[n : {___Integer?NonNegative}] :=
%t A096443 Block[{p, $RecursionLimit = 1024, firstPositive},
%t A096443   firstPositive =
%t A096443    Compile[{{vv, _Integer, 1}},
%t A096443     Module[{k = 1}, Do[If[el == 0, k++, Break[]], {el, vv}]; k]];
%t A096443   p[{0 ...}] := 1;
%t A096443   p[v_] :=
%t A096443    p[v] = Module[{len = Length[v], it, k, zeros, sum, pos, gcd},
%t A096443      it = Array[k, len];
%t A096443      pos = firstPositive[v];
%t A096443      zeros = ConstantArray[0, len];
%t A096443      sum = 0;
%t A096443      Do[If[it == zeros, Continue[]];
%t A096443       gcd = GCD @@ it;
%t A096443       sum += it[[pos]] DivisorSigma[-1, gcd] p[v - it];,
%t A096443       Evaluate[Sequence @@ Thread[{it, 0, v}]]];
%t A096443      sum/v[[pos]]];
%t A096443   p[n]];
%t A096443 ParallelMap[MultiPartiteP,
%t A096443 Flatten[Table[IntegerPartitions[k], {k, 0, 8}], 1]]
%t A096443 (* Oleksandr Pavlyk, Jan 23 2011 *)
%Y A096443 Cf. A035098, A035310.
%K A096443 nonn
%O A096443 0,3
%A A096443 _Jon Wild_, Aug 11 2004
%E A096443 Edited by _Franklin T. Adams-Watters_, May 16 2006