cp's OEIS Frontend

A006171 Number of factorization patterns of polynomials of degree n over integers.

%I A006171 M2479 #101 Jul 26 2024 11:39:37
%S A006171 1,1,3,5,11,17,34,52,94,145,244,370,603,899,1410,2087,3186,4650,6959,
%T A006171 10040,14750,21077,30479,43120,61574,86308,121785,169336,236475,
%U A006171 326201,451402,618135,848209,1153733,1571063,2123325,2871419,3857569,5182999,6924303
%N A006171 Number of factorization patterns of polynomials of degree n over integers.
%C A006171 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 A006171 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 A006171 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 A006171 Also equals the number of partitions having parts consisting of runs of equal parts. - _Gregory L. Simay_, May 25 2017
%C A006171 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 A006171 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 A006171 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006171 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 A006171 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 A006171 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 A006171 William Q. Erickson, <a href="https://arxiv.org/abs/2407.13165">The Demazure product extended to biwords</a>, arXiv:2407.13165 [math.CO], 2024. See p. 16.
%H A006171 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 A006171 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%F A006171 From _Vladeta Jovovic_, Apr 21 2001: (Start)
%F A006171 Euler transform of tau(n), tau(n) = the number of divisors of n, cf. A000005.
%F A006171 G.f.: Product_{k>=1} (1 - x^k)^(-tau(k)).
%F A006171 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 A006171 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 A006171 G.f.: A(x) = exp( Sum_{n>=1} sigma(n)*x^n/(1-x^n)/n ). - _Paul D. Hanna_, Mar 28 2009
%F A006171 From _Paul D. Hanna_, Oct 19 2011: (Start)
%F A006171 Logarithmic derivative yields A060640.
%F A006171 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 A006171 G.f.: 1/Product_{n>=1} E(q^n) where E(q) = Product_{n>=1} (1-q^n). - _Joerg Arndt_, Feb 27 2014
%F A006171 log(a(n)) ~ Pi * sqrt(n*log(n)/3) [Brigham, 1950]. - _Vaclav Kotesovec_, Jan 04 2017
%F A006171 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 A006171 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 A006171 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 A006171 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 A006171 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 A006171 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 A006171 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 A006171 (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 A006171 (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 A006171 (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 A006171 (PARI) {A060640(n)=sumdiv(n, d, d*sigma(n/d))}
%o A006171 {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 A006171 Cf. A000005, A060640, A061255, A061256, A001970, A061257.
%Y A006171 Cf. A006167-A006170, A006171 (log).
%Y A006171 Cf. A000041, A115621, A215905, A215909, A215914, A215925, A288098.
%Y A006171 Cf. A000219.
%K A006171 nonn,nice
%O A006171 0,3
%A A006171 _N. J. A. Sloane_