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

Author

N. J. A. Sloane, Aug 13 2008

Keywords

• nonn

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

Examples

			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.
		

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

• 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.

Crossrefs

Cf. A115457, A203011.

Row sums of powers of two triangles A000079.

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

Programs

Magma

[2^((n+1)*(n+2) div 2) - 2^(n*(n+1) div 2): n in [0..30]]; // Vincenzo Librandi, Oct 01 2015

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

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

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)

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