|
%I M2479 #97 Oct 29 2023 21:15:43
%S 1,1,3,5,11,17,34,52,94,145,244,370,603,899,1410,2087,3186,4650,6959,
%T 10040,14750,21077,30479,43120,61574,86308,121785,169336,236475,
%U 326201,451402,618135,848209,1153733,1571063,2123325,2871419,3857569,5182999,6924303
%N Number of factorization patterns of polynomials of degree n over integers.
%C Number of partitions of n where there are unlimited distinguishable but unlabeled objects of each size. E.g., in splitting 2 into two parts of size 1, we distinguish whether the same object is used for each part. Also number of factorization patterns over rationals, or many other UFDs (but not over real or complex numbers). - _Franklin T. Adams-Watters_, Jun 19 2006
%C Equals the "aerate and convolve" convergent of A000041: (1, 1, 2, 3, 5, 7, 11, ...) * (1, 0, 1, 0, 2, 0, 3, 0, 5, ...) * (1, 0, 0, 1, 0, 0, 2, 0, 0, 3, ...). - _Gary W. Adamson_, Jun 16 2009
%C Also equals the number of distinct (up to unitary similarity) unital *-subalgebras of the n X n complex matrices. A unital *-subalgebra is a subspace that is closed under multiplication and the conjugate transpose, and which contains the identity matrix (see A215905 and A215925). - _Nathaniel Johnston_, Aug 27 2012
%C Also equals the number of partitions having parts consisting of runs of equal parts. - _Gregory L. Simay_, May 25 2017
%C Also equals the number of generalized partitions of n when there are d(a) different types of a, (a = 1,2,3,...), where d(n) is the number of divisors of n. a(3)=5 because there are 5 partitions of 3 with "d(a) copies of a", namely (3_1), (3_2), (2_1, 1_1), (2_2, 1_1), (1_1, 1_1, 1_1). - _Augustine O. Munagi_, Jun 13 2022
%D R. A. Hultquist, G. L. Mullen and H. Niederreiter, Association schemes and derived PBIB designs of prime power order, Ars. Combin., 25 (1988), 65-82.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A006171/b006171.txt">Table of n, a(n) for n = 0..10000</a> (first 1001 terms from T. D. Noe)
%H A. K. Agarwal and G. L. Mullen, <a href="https://doi.org/10.1016/0097-3165(88)90079-9">Partitions with "d(a) copies of a"</a>, J. Combin. Theory Ser. A, 48(1)(1988), 120-135.
%H N. A. Brigham, <a href="https://doi.org/10.1090/S0002-9939-1950-0034409-3">A General Asymptotic Formula for Partition Functions</a>, Proc. Amer. Math. Soc., vol. 1 (1950), pp. 182-191.
%H MathOverflow, <a href="http://mathoverflow.net/questions/159955/number-of-representations-of-an-integer-as-an-arbitrary-sum-of-products/160752">Number of representations of an integer as an (arbitrary) sum of products</a>, 2014.
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%F From _Vladeta Jovovic_, Apr 21 2001: (Start)
%F Euler transform of tau(n), tau(n) = the number of divisors of n, cf. A000005.
%F G.f.: Product_{k>=1} (1 - x^k)^(-tau(k)).
%F a(n) = 1/n*Sum_{k=1..n} a(n-k)*b(k), n>1, a(0)=1, b(k) = Sum_{d|k} d*tau(d), cf. A060640. (End)
%F a(n) = Sum_{<b(i)^k(i)> partition of n} product p(k(i)), where p(n) is the partition function A000041. E.g., for the partition [4,2^3,1^4], the product is p(1)*p(3)*p(4) = 1*3*5 = 15. - _Franklin T. Adams-Watters_, Jun 19 2006
%F G.f.: A(x) = exp( Sum_{n>=1} sigma(n)*x^n/(1-x^n)/n ). - _Paul D. Hanna_, Mar 28 2009
%F From _Paul D. Hanna_, Oct 19 2011: (Start)
%F Logarithmic derivative yields A060640.
%F G.f.: A(x) = exp( Sum_{n>=1} A060640(n)*x^n/n ), where A060640(n) = Sum_{d|n} d*sigma(n/d). (End)
%F G.f.: 1/Product_{n>=1} E(q^n) where E(q) = Product_{n>=1} (1-q^n). - _Joerg Arndt_, Feb 27 2014
%F log(a(n)) ~ Pi * sqrt(n*log(n)/3) [Brigham, 1950]. - _Vaclav Kotesovec_, Jan 04 2017
%F a(n) ~ exp(Pi*sqrt(n/(3*log(n))) * (log(n) - log(log(n))/2 + gamma + 6*Zeta'(2)/Pi^2 + log(2/Pi) + log(3)/2)) * Pi^(1/4) * (log(n))^(1/8) / (2^(3/4) * 3^(1/8) * n^(5/8)), where gamma is the Euler-Mascheroni constant (A001620) and Zeta'(2) = -0.9375482543158437537... (see A073002) [user Lucia, MathOverflow, 2014]. - _Vaclav Kotesovec_, Jan 05 2017
%e For n=3 we have 3 = (3*1) = (1*3) = (2*1) + (1*1) = (1*2) + (1*1) = (1*1) + (1*1) + (1*1) so a(3)=5.
%e For n=4 we have the following 11 partitions, with the additive runs indicated by "[]": [4], [3]+[1], [2+2], [2]+[2], [2]+[1+1], [2]+[1]+[1], [1+1+1+1], [1+1+1]+[1], [1+1]+[1+1], [1+1]+[1]+[1], [1]+[1]+[1]+[1]. - _Gregory L. Simay_, May 25 2017
%p with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d,j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: a:=etr(tau): seq(a(n), n=0..40); # _Alois P. Heinz_, Sep 08 2008
%t max = 50; gf[x_] := Product[(1 - x^k)^-DivisorSigma[0, k], {k, 1, max}]; CoefficientList[ Series[gf[x], {x, 0, max}], x] (* _Jean-François Alcover_, Nov 23 2011 *)
%t nmax = 50; s = 1 - x; Do[s *= Sum[Binomial[DivisorSigma[0, k], j]*(-1)^j*x^(j*k), {j, 0, nmax/k}]; s = Expand[s]; s = Take[s, Min[nmax + 1, Exponent[s, x] + 1, Length[s]]];, {k, 2, nmax}]; CoefficientList[Series[1/s, {x, 0, nmax}], x] (* _Vaclav Kotesovec_, Aug 28 2018, the fastest *)
%t nmax = 50; CoefficientList[Series[Product[Sum[PartitionsP[k]*x^(j*k), {k, 0, nmax/j}], {j, 1, nmax}], {x, 0, nmax}], x] (* _Vaclav Kotesovec_, Dec 26 2020 *)
%o (PARI) {a(n) = if(n<0, 0, polcoeff( 1 / prod(k=1, n, (1 - x^k + x * O(x^n))^numdiv(k)), n))}; /* _Michael Somos_, Apr 01 2003 */
%o (PARI) N=66; x='x+O('x^N); gf=1/prod(j=1,N, eta(x^j)); Vec(gf) \\ _Joerg Arndt_, May 03 2008
%o (PARI) {a(n)=if(n==0,1,polcoeff(exp(sum(m=1,n,sigma(m)*x^m/(1-x^m+x*O(x^n))/m)),n))} /* _Paul D. Hanna_, Mar 28 2009 */
%o (PARI) {A060640(n)=sumdiv(n, d, d*sigma(n/d))}
%o {a(n)=polcoeff(exp(sum(m=1,n+1,A060640(m)*x^m/m)+x*O(x^n)),n)} /* _Paul D. Hanna_, Oct 19 2011 */
%Y Cf. A000005, A060640, A061255, A061256, A001970, A061257.
%Y Cf. A006167-A006170, A006171 (log).
%Y Cf. A000041, A115621, A215905, A215909, A215914, A215925, A288098.
%Y Cf. A000219.
%K nonn,nice
%O 0,3
%A _N. J. A. Sloane_
|
