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

%I #44 Sep 08 2022 08:45:28

%S 1,6,56,960,31744,2064384,266338304,68451041280,35115652612096,

%T 35993612646875136,73750947497819242496,302157667927362455470080,

%U 2475577847115856892504571904,40562343327224770087344704323584,1329187430965708569562959165777772544

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

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

%C 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

%C a(n) is the HANKEL transform of the large Schröder numbers A006318(n+2). - _Emanuele Munarini_, Sep 14 2017

%D 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.

%H Arnaud Bodin, <a href="https://arxiv.org/abs/0706.0157">Number of irreducible polynomials in several variables over finite fields</a>, arXiv:0706.0157 [math.AC], 2007; Amer. Math. Monthly, 115 (2008), 653-660.

%H Joachim von zur Gathen, Alfredo Viola, and Konstantin Ziegler, <a href="https://arxiv.org/abs/0912.3312">Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields</a>, arXiv:0912.3312 [math.AC], 2009-2013.

%F a(n) = 2^((n+1)(n+2)/2) - 2^(n(n+1)/2). - _Paul D. Hanna_, Apr 08 2009

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

%F From _Emanuele Munarini_, Sep 14 2017: (Start)

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

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

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

%e Let esp abbreviate "elementary symmetric polynomial". Then

%e 0th esp of {2} is 1.

%e 1st esp of {2,4} is 2+4 = 6.

%e 2nd esp of {2,4,8} is 2*4 + 2*8 + 4*8 = 56.

%p seq(2^((n*(1+n))/2)*(2^(1+n)-1), n=0..14); # _Peter Luschny_, Sep 19 2017

%t f[k_] := 2^k; t[n_] := Table[f[k], {k, 1, n}]

%t a[n_] := SymmetricPolynomial[n - 1, t[n]]

%t Table[a[n], {n, 1, 16}] (* A122743 *)

%t (* _Clark Kimberling_, Dec 29 2011 *)

%o (PARI) a(n) = 2^((n+1)*(n+2)/2) - 2^(n*(n+1)/2);

%o vector (100, n, a(n-1)) \\ _Altug Alkan_, Sep 30 2015

%o (Magma) [2^((n+1)*(n+2) div 2) - 2^(n*(n+1) div 2): n in [0..30]]; // _Vincenzo Librandi_, Oct 01 2015

%Y Cf. A115457, A203011.

%Y Row sums of powers of two triangles A000079.

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

%K nonn

%O 0,2

%A _N. J. A. Sloane_, Aug 13 2008

%E Edited, terms and links added by _Johannes W. Meijer_, Oct 10 2010

%E Comments corrected, reference added, and example edited by _Konstantin Ziegler_, Dec 04 2012

%E a(14) from _Vincenzo Librandi_, Oct 01 2015