A006171 Number of factorization patterns of polynomials of degree n over integers.
1, 1, 3, 5, 11, 17, 34, 52, 94, 145, 244, 370, 603, 899, 1410, 2087, 3186, 4650, 6959, 10040, 14750, 21077, 30479, 43120, 61574, 86308, 121785, 169336, 236475, 326201, 451402, 618135, 848209, 1153733, 1571063, 2123325, 2871419, 3857569, 5182999, 6924303
Offset: 0
Examples
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. 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
References
- 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.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
- A. K. Agarwal and G. L. Mullen, Partitions with "d(a) copies of a", J. Combin. Theory Ser. A, 48(1)(1988), 120-135.
- N. A. Brigham, A General Asymptotic Formula for Partition Functions, Proc. Amer. Math. Soc., vol. 1 (1950), pp. 182-191.
- William Q. Erickson, The Demazure product extended to biwords, arXiv:2407.13165 [math.CO], 2024. See p. 16.
- MathOverflow, Number of representations of an integer as an (arbitrary) sum of products, 2014.
- N. J. A. Sloane, Transforms
Crossrefs
Programs
-
Maple
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
-
Mathematica
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 *) 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 *) 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 *) -
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 */ -
PARI
N=66; x='x+O('x^N); gf=1/prod(j=1,N, eta(x^j)); Vec(gf) \\ Joerg Arndt, May 03 2008 -
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 */ -
PARI
{A060640(n)=sumdiv(n, d, d*sigma(n/d))} {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 */
Formula
From Vladeta Jovovic, Apr 21 2001: (Start)
Euler transform of tau(n), tau(n) = the number of divisors of n, cf. A000005.
G.f.: Product_{k>=1} (1 - x^k)^(-tau(k)).
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)
a(n) = Sum_{ 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
G.f.: A(x) = exp( Sum_{n>=1} sigma(n)*x^n/(1-x^n)/n ). - Paul D. Hanna, Mar 28 2009
From Paul D. Hanna, Oct 19 2011: (Start)
Logarithmic derivative yields A060640.
G.f.: 1/Product_{n>=1} E(q^n) where E(q) = Product_{n>=1} (1-q^n). - Joerg Arndt, Feb 27 2014
log(a(n)) ~ Pi * sqrt(n*log(n)/3) [Brigham, 1950]. - Vaclav Kotesovec, Jan 04 2017
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
Comments