A203011 -id:A203011 - cp's OEIS frontend

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

N. J. A. Sloane, Aug 13 2008

nonn

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

			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.

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.

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.

Cf. A115457, A203011.
Row sums of powers of two triangles A000079.
Equals A000225(n+1)*2^A000217(n).

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

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

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

a(n) = 2^((n+1)*(n+2)/2) - 2^(n*(n+1)/2);
vector (100, n, a(n-1)) \\ Altug Alkan, Sep 30 2015

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)

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

A127850 a(n)=(2^n-1)*2^(n(n-1)/2)/(2^(n-1)).

Original entry on oeis.org

0, 1, 3, 14, 120, 1984, 64512, 4161536, 534773760, 137170518016, 70300024700928, 72022409665839104, 147537923792657448960, 604389122831019749146624, 4951457925686617442302820352

Offset: 0

Paul Barry, Feb 02 2007

To base 2, this is given by A127851.
a(n)=(n-1)-st elementary symmetric function of {1,2,4,6,16,...,2^(n-1)}; see Mathematica program. - Clark Kimberling, Dec 29 2011
With offset = 1: the number of simple labeled graphs on n vertices in which vertex 1 or vertex 2 is isolated (or both). - Geoffrey Critzer, Dec 27 2012
HANKEL transform of A001003(n+2) (= [3, 11, 45, ...]) is a(n+2) (= [3, 14, 120, ...]). - Michael Somos, May 19 2013

			G.f. = x + 3*x^2 + 14*x^3 + 120*x^4 + 1984*x^5 + 64512*x^6 + 4161536*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..80

Cf. A001003, A122743, A203011.

[2^Binomial( n-1, 2) * (2^n - 1):n in [0..30]]; // Vincenzo Librandi, Aug 31 2014

f[k_] := 2^(k - 1); t[n_] := Table[f[k], {k, 1, n}]
a[n_] := SymmetricPolynomial[n - 1, t[n]]
Table[a[n], {n, 1, 16}]  (* A127850 *)
(* Clark Kimberling, Dec 29 2011 *)
a[ n_] := 2^Binomial[ n - 1, 2] (2^n - 1); (* Michael Somos, Aug 30 2014 *)
Table[2^Binomial[n - 1, 2] (2^n - 1), {n, 0, 30}] (* Vincenzo Librandi, Aug 31 2014 *)
Table[(2^n-1) (2^((n(n-1))/2))/2^(n-1),{n,0,20}] (* Harvey P. Dale, Sep 02 2025 *)

{a(n) = 2^binomial( n-1, 2) * (2^n - 1)}; /* Michael Somos, Aug 30 2014 */

a(n) = 2^C(n,2)*(2^n-1)/2^(n-1).
a(-n) = -(4^n) * a(n) for all n in Z. - Michael Somos, Aug 30 2014
0 = +a(n)*(-a(n+2) + a(n+3)) + a(n+1)*(2*a(n+1) - 6*a(n+2) - 4*a(n+3)) + a(n+2)*(+8*a(n+2)) for all n in Z. - Michael Somos, Aug 30 2014
0 = +a(n)*a(n+2)*(-a(n) - 4*a(n+2)) + a(n)*a(n+1)*(+2*a(n+1) + 10*a(n+2)) + a(n+1)^2*(-24*a(n+1) + 8*a(n+2)) for all n in Z. - Michael Somos, Aug 30 2014

A204243 Determinant of the n-th principal submatrix of A204242.

Original entry on oeis.org

1, 2, 11, 144, 4149, 251622, 31340799, 7913773980, 4024015413705, 4106387069191890, 8395359475529822355, 34357677843892688699400, 281336437060919094044274525, 4608419756389534634440592965950, 150992374805715685629827976712244775

Offset: 1

Clark Kimberling, Jan 13 2012

nonn

Colin Barker, Table of n, a(n) for n = 1..80
Wikipedia, Matrix determinant lemma

Cf. A005329, A203011, A204238, A204242.

f:= n -> (1 - add(1/(2^i-1),i=2..n))*mul(2^i-1,i=2..n):
seq(f(n),n=1..30); # Robert Israel, Nov 30 2015

f[i_, j_] := 0; f[1, j_] := 1; f[i_, 1] := 1; f[i_, i_] := 2^i - 1;
m[n_] := Table[f[i, j], {i, 1, n}, {j, 1, n}]
TableForm[m[8]] (* 8x8 principal submatrix *)
Flatten[Table[f[i, n + 1 - i],
  {n, 1, 12}, {i, 1, n}]]     (* A204242 *)
Table[Det[m[n]], {n, 1, 15}]  (* A204243 *)
Permanent[m_] :=
  With[{a = Array[x, Length[m]]},
   Coefficient[Times @@ (m.a), Times @@ a]];
Table[Permanent[m[n]], {n, 1, 15}]   (* A203011 *)

vector(20, n, matdet(matrix(n, n, i, j, if(i==1, 1, if(j==1, 1, if(i==j, 2^i-1)))))) \\ Colin Barker, Nov 27 2015

a(n) = (1 - Sum_{k=2..n} 1/(2^k-1)) * Product_{k=2..n} (2^k-1) = 2*A005329(n) - A203011(n). - Robert Israel, Nov 30 2015

A204242 Infinite symmetric matrix given by f(i,1)=1, f(1,j)=1, f(i,i)=2^i-1 and f(i,j)=0 otherwise, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 0, 0, 1, 1, 0, 7, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 15, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 31, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 63, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 127, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0

Offset: 1

Clark Kimberling, Jan 13 2012

			Northwest corner:
1 1 1 1
1 3 0 0
1 0 7 0
1 0 0 15

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A204243, A203011.

N:= 1000: # to get a(1) to a(N)
V:= Vector(N):
V[[seq(k*(k+1)/2, k= 1..floor((sqrt(8*N+1)-1)/2))]]:= 1:
V[[seq(1+k*(k+1)/2, k=1..floor((sqrt(8*N-7)-1)/2))]]:= 1:
V[[seq(1+2*k+2*k^2, k=0..floor((sqrt(2*N-1)-1)/2))]]:=
    :
convert(V,list); # Robert Israel, Nov 30 2015

f[i_, j_] := 0; f[1, j_] := 1; f[i_, 1] := 1; f[i_, i_] := 2^i - 1;
m[n_] := Table[f[i, j], {i, 1, n}, {j, 1, n}]
TableForm[m[8]] (* 8x8 principal submatrix *)
Flatten[Table[f[i, n + 1 - i],
  {n, 1, 12}, {i, 1, n}]]     (* A204242 *)
Table[Det[m[n]], {n, 1, 15}]  (* A204243 *)
Permanent[m_] :=
  With[{a = Array[x, Length[m]]},
   Coefficient[Times @@ (m.a), Times @@ a]];
Table[Permanent[m[n]], {n, 1, 15}]   (* A203011 *)

From Robert Israel, Nov 30 2015: (Start)
a(k*(k+1)/2) = a(1 + k*(k+1)/2) = 1.
a(2*k^2 + 2*k + 1) = 2^(k+1) - 1.
a(n) = 0 otherwise. (End)

Name edited by Robert Israel, Nov 30 2015

A342186 Triangle read by rows, matrix inverse of A139382.

Original entry on oeis.org

1, -1, 1, 3, -4, 1, -21, 31, -11, 1, 315, -486, 196, -26, 1, -9765, 15381, -6562, 1002, -57, 1, 615195, -978768, 428787, -69688, 4593, -120, 1, -78129765, 124918731, -55434717, 9279163, -652999, 19833, -247, 1

Offset: 1

John Keith, Mar 04 2021

This triangle appears to be the q-analog of A008275 (Stirling numbers of the first kind) for q=2. However, A333142 has a similar definition.
Row sums of unsigned triangle are A006125 with offset 1.
|T(n,k)| is the number of descent free digraphs on [n] containing exactly k source nodes.  A descent in a digraph is a pair of vertices s->t such that s>t.  A descent free digraph is necessarily acyclic.  A source in an acyclic digraph is a node with indegree 0. - Geoffrey Critzer, Mar 05 2025

			The triangle begins:
           1;
          -1,         1;
           3,        -4,         1;
         -21,        31,       -11,       1;
         315,      -486,       196,     -26,       1;
       -9765,     15381,     -6562,    1002,     -57,     1;
      615195,   -978768,    428787,  -69688,    4593,  -120,    1;
   -78129765, 124918731, -55434717, 9279163, -652999, 19833, -247, 1;
  ...

John Keith, Rows n = 1..20 of triangle, flattened
Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020.

Cf. A008275, A139382, A333142, A333143, A006125 (row sums).

Columns of unsigned triangle: A005329, A203011, A000295, A203242.

A342186 := proc(n, k) if n = 1 and k = 1 then 1 elif k > n or k < 1 then 0 else
A342186(n-1, k-1) - (2^(n-1) - 1) * A342186(n-1, k) fi end:
for n from 1 to 8 do seq(A342186(n, k), k = 1..n) od; # Peter Luschny, Jun 28 2022

T[1, 1] := 1; T[n_, k_] := T[n, k] = If[k > n || k < 1, 0, T[n - 1, k - 1] - (2^(n - 1) - 1)*T[n - 1, k]]; Table[T[n, k], {n, 1, 8}, {k, 1, n}] (* after G. C. Greubel's program for A139382 *)

mat(nn) = my(m = matrix(nn, nn)); for (n=1, nn, for(k=1, nn, m[n,k] = if (n==1, if (k==1, 1, 0), if (k==1, 1, (2^k-1)*m[n-1, k] + m[n-1, k-1])););); m; \\ A139382
tabl(nn) = 1/mat(nn); \\ Michel Marcus, Mar 18 2021

T(n,k) = T(n-1,k-1) - (2^(n-1)-1) * T(n-1,k), n, k >= 1, T(1, 1) = 1, T(n, 0) = 0.
For unsigned triangle, T(n, 1) = A005329(n-1); T(n, 2) = A203011(n-1); T(n, n-1) = A000295(n+1); T(n, n-2) = A203242(n-1).
T(n,k) = Sum_{j=k..n} (-1)^(n-j)*2^binomial(n-j,2)*qBinomial(n,j,2)*binomial(j,k), where qBinomial(n,k,2) is A022166(n,k). - Fabian Pereyra, Feb 08 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A127850 a(n)=(2^n-1)*2^(n(n-1)/2)/(2^(n-1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A204243 Determinant of the n-th principal submatrix of A204242.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A204242 Infinite symmetric matrix given by f(i,1)=1, f(1,j)=1, f(i,i)=2^i-1 and f(i,j)=0 otherwise, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A342186 Triangle read by rows, matrix inverse of A139382.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula