login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006171 Number of factorization patterns of polynomials of degree n over integers.
(Formerly M2479)
67
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

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

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

Also equals the number of partitions having parts consisting of runs of equal parts. - 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

T. D. Noe and Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)

N. A. Brigham, A General Asymptotic Formula for Partition Functions, Proc. Amer. Math. Soc., vol. 1 (1950), pp. 182-191.

MathOverflow, Number of representations of an integer as an (arbitrary) sum of products, 2014.

N. J. A. Sloane, Transforms

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_{<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

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.: A(x) = exp( Sum_{n>=1} A060640(n)*x^n/n ), where A060640(n) = Sum_{d|n} d*sigma(n/d). (End)

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

EXAMPLE

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

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 *)

PROG

(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 */

CROSSREFS

Cf. A000005, A060640, A061255, A061256, A001970, A061257.

Cf. A006167-A006170, A006171 (log).

Cf. A000041, A115621, A215905, A215909, A215914, A215925, A288098.

Sequence in context: A091610 A006170 A147071 * A261674 A319632 A060647

Adjacent sequences:  A006168 A006169 A006170 * A006172 A006173 A006174

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 17 02:33 EST 2019. Contains 320200 sequences. (Running on oeis4.)