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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A269456 Triangular array T(n,k) read by rows: T(n,k) is the number of degree n monic polynomials in GF(2)[x] with exactly k factors in its unique factorization into irreducible polynomials. 0
2, 1, 3, 2, 2, 4, 3, 5, 3, 5, 6, 8, 8, 4, 6, 9, 18, 14, 11, 5, 7, 18, 30, 32, 20, 14, 6, 8, 30, 63, 57, 47, 26, 17, 7, 9, 56, 114, 124, 86, 62, 32, 20, 8, 10, 99, 226, 234, 191, 116, 77, 38, 23, 9, 11, 186, 422, 480, 370, 260, 146, 92, 44, 26, 10, 12, 335, 826, 932, 775, 512, 330, 176, 107, 50, 29, 11, 13 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Column 1 is A001037.

Row sums are 2^n.

T(n,k) is the number of length-n binary words having k factors in their standard (Chen, Fox, Lyndon)-factorization. [Joerg Arndt, Nov 05 2017]

LINKS

Table of n, a(n) for n=1..78.

Daniel Panario, Random Polynomials over Finite Fields: Statistics and Algorithms, 2013.

FORMULA

G.f.: Product_{k>0} 1/(1 - y*x^k)^A001037(k).

EXAMPLE

2,

1, 3,

2, 2, 4,

3, 5, 3, 5,

6, 8, 8, 4, 6,

9, 18, 14, 11, 5, 7,

18, 30, 32, 20, 14, 6, 8,

30, 63, 57, 47, 26, 17, 7, 9,

56, 114, 124, 86, 62, 32, 20, 8, 10,

T(3,1) = 2 because there are 2 monic irreducible polynomials of degree 3 in F_2[x]: 1 + x^2 + x^3, 1 + x + x^3.

T(3,2) = 2 because there are 2 such polynomials that can be factored into exactly 2 irreducible factors: (1 + x) (1 + x + x^2), x (1 + x + x^2).

T(3,3) = 4 because there are 4 such polynomials that can be factored into exactly 3 irreducible factors: x^3, x^2 (1 + x), x (1 + x)^2, (1 + x)^3.

MATHEMATICA

nn = 12; b =Table[1/n Sum[MoebiusMu[n/d] 2^d, {d, Divisors[n]}], {n, 1, nn}]; Map[Select[#, # > 0 &] &, Drop[CoefficientList[Series[Product[Sum[y^i x^(k*i), {i, 0, nn}]^b[[k]], {k, 1, nn}], {x, 0, nn}], {x, y}], 1]] // Grid

CROSSREFS

Sequence in context: A141157 A137948 A210553 * A208906 A120933 A064134

Adjacent sequences:  A269453 A269454 A269455 * A269457 A269458 A269459

KEYWORD

nonn,tabl

AUTHOR

Geoffrey Critzer, Feb 27 2016

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 17:22 EST 2018. Contains 299624 sequences. (Running on oeis4.)