A122743 Number of normalized polynomials of degree n in GF(2)[x,y].

1, 6, 56, 960, 31744, 2064384, 266338304, 68451041280, 35115652612096, 35993612646875136, 73750947497819242496, 302157667927362455470080, 2475577847115856892504571904, 40562343327224770087344704323584, 1329187430965708569562959165777772544

Offset

0,2

Comments

a(n) = n-th elementary symmetric function in n+1 variables evaluated at {2,4,8,16,...,2^(n+1)}; see Mathematica program.

a(n) is the number of simple labeled graphs on {1,2,...,n+2} such that the vertex 1 is not isolated. - Geoffrey Critzer, Sep 12 2013

a(n) is the HANKEL transform of the large Schröder numbers A006318(n+2). - Emanuele Munarini, Sep 14 2017

References

Joachim von zur Gathen, Alfredo Viola, and Konstantin Ziegler, Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields, in: A. López-Ortiz (Ed.), LATIN 2010: Theoretical Informatics, Proceedings of the 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010, in: Lecture Notes in Comput. Sci., vol. 6034, Springer, Berlin, Heidelberg, 2010, pp. 243-254 (Extended Abstract). Final version to appear in SIAM J. Discrete Math.

Links

Table of n, a(n) for n=0..14.

Arnaud Bodin, Number of irreducible polynomials in several variables over finite fields, arXiv:0706.0157 [math.AC], 2007; Amer. Math. Monthly, 115 (2008), 653-660.

Joachim von zur Gathen, Alfredo Viola, and Konstantin Ziegler, Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields, arXiv:0912.3312 [math.AC], 2009-2013.

Formula

a(n) = 2^((n+1)(n+2)/2) - 2^(n(n+1)/2). - Paul D. Hanna, Apr 08 2009

E.g.f.: d(G(2x)-G(x))/dx where G(x) is the e.g.f. for A006125. - Geoffrey Critzer, Sep 12 2013

From Emanuele Munarini, Sep 14 2017: (Start)

(2^(n+1)-1)*a(n+1) - 2^(n+1)*(2^(n+2)-1)*a(n) = 0.

a(n+1) - (2^(n+2)+1)*a(n) = 2^(binomial(n+1,2)).

a(n+2) - (5*2^(n+1)+1)*a(n+1) + 2^(n+1)*(2^(n+2)+1)*a(n) = 0. (End)

Example

Let esp abbreviate "elementary symmetric polynomial".  Then
0th esp of {2} is 1.
1st esp of {2,4} is 2+4 = 6.
2nd esp of {2,4,8} is 2*4 + 2*8 + 4*8 = 56.

Maple

seq(2^((n*(1+n))/2)*(2^(1+n)-1), n=0..14); # Peter Luschny, Sep 19 2017

Mathematica

f[k_] := 2^k; t[n_] := Table[f[k], {k, 1, n}]
a[n_] := SymmetricPolynomial[n - 1, t[n]]
Table[a[n], {n, 1, 16}] (* A122743 *)
(* Clark Kimberling, Dec 29 2011 *)

Prog

(PARI) a(n) = 2^((n+1)*(n+2)/2) - 2^(n*(n+1)/2);
vector (100, n, a(n-1)) \\ Altug Alkan, Sep 30 2015
(Magma) [2^((n+1)*(n+2) div 2) - 2^(n*(n+1) div 2): n in [0..30]]; // Vincenzo Librandi, Oct 01 2015

Crossrefs

Cf. A115457, A203011.

Row sums of powers of two triangles A000079.

Equals A000225(n+1)*2^A000217(n).

Sequence in context: A303921 A052317 A185524 * A241031 A268760 A137032

Adjacent sequences: A122740 A122741 A122742 * A122744 A122745 A122746

Keyword

nonn

Author

N. J. A. Sloane, Aug 13 2008

Extensions

Edited, terms and links added by Johannes W. Meijer, Oct 10 2010

Comments corrected, reference added, and example edited by Konstantin Ziegler, Dec 04 2012

a(14) from Vincenzo Librandi, Oct 01 2015

Status

approved