A053763 -id:A053763 - cp's OEIS frontend

A109345 a(n) = 5^((n^2 - n)/2).

1, 1, 5, 125, 15625, 9765625, 30517578125, 476837158203125, 37252902984619140625, 14551915228366851806640625, 28421709430404007434844970703125

Offset: 0

Philippe Deléham, Aug 21 2005

Sequence given by the Hankel transform (see A001906 for definition) of A078009 = {1, 1, 6, 41, 306, 2426, 20076, 171481, ...}; example: det([1, 1, 6, 41; 1, 6, 41, 306; 6, 41, 306, 2426; 41, 306, 2426, 20076]) = 5^6 = 15625.

a(n) is the number of simple labeled graphs, with bi-directional and non-directed edges allowed and not regarded as equivalent, on n labeled nodes. - Mark Stander, Feb 07 2019

G. C. Greubel, Table of n, a(n) for n = 0..50

Cf. A006125 (number of graphs on n labeled nodes), A047656 (number of semi-complete digraphs on n labeled nodes), A053763 (number of simple digraphs on n labeled nodes), A053764.

List([0..12], n -> 5^Binomial(n,2)); # G. C. Greubel, Feb 09 2019

[5^Binomial(n,2): n in [0..12]]; // G. C. Greubel, Feb 09 2019

seq(5^(binomial(2+n,n)), n=-2..8); # Zerinvary Lajos, Jun 12 2007

5^Binomial[Range[0, 12], 2] (* G. C. Greubel, Feb 09 2019 *)

a(n)=5^binomial(n,2) \\ Charles R Greathouse IV, Jan 11 2012

[5^binomial(n,2) for n in (0..12)] # G. C. Greubel, Feb 09 2019

a(n+1) is the determinant of n X n matrix M_(i, j) = binomial(5i, j).

G.f. A(x) satisfies: A(x) = 1 + x * A(5*x). - Ilya Gutkovskiy, Jun 04 2020

A053765 a(n) = 4^(n^2 - n).

Original entry on oeis.org

1, 1, 16, 4096, 16777216, 1099511627776, 1152921504606846976, 19342813113834066795298816, 5192296858534827628530496329220096, 22300745198530623141535718272648361505980416

Offset: 0

Stephen G Penrice, Mar 29 2000

Number of nilpotent n X n matrices over GF(4).
(-1)^n * resultant of the Chebyshev polynomial of first kind of degree n and Chebyshev polynomial of first kind of degree 2n (cf. A039991). - Benoit Cloitre, Jan 26 2003
a(n) is the number of spanning subgraphs (or equivalently sets of edges) in the n X n grid graph. - Andrew Howroyd, Jan 29 2023

N. J. Fine and I. N. Herstein, The probability that a matrix be nilpotent, Illinois J. Math., 2 (1958), 499-504.
M. Gerstenhaber, On the number of nilpotent matrices with coefficients in a finite field. Illinois J. Math., Vol. 5 (1961), 330-333.

Andrew Howroyd, Table of n, a(n) for n = 0..40

Cf. A053763, A053764.

a(n) = 4^(n^2 - n) \\ Andrew Howroyd, Jan 29 2023

More terms from James Sellers, Apr 08 2000

A125587 Call an n X n matrix robust if the top left i X i submatrix is invertible for all i = 1..n. Sequence gives number of n X n robust real {0,1}-matrices.

Original entry on oeis.org

1, 4, 68, 5008, 1603232, 2224232640

Offset: 1

N. J. A. Sloane and Vinay Vaishampayan, Jan 05 2007

An upper bound is the total number of {0,1}-matrices, 2^(n^2).
Comment from Michael Kleber, Jan 05 2006: A lower bound is 2^(n^2-n), A053763. For given the principal n-1 X n-1 submatrix A, the 2n-2 further entries (excluding the bottom right corner) can be filled in arbitrarily and then there is always at least one choice for the last entry which makes the matrix invertible.
Comment from N. J. A. Sloane, Jan 06 2006: Let the matrix be [A b; c d], where A is n-1 X n-1, b is n-1 X 1, c is 1 X n-1, d is 0 or 1. The matrix is singular iff d = c A^(-1) b, which for given A, b, c has at most one solution d.
Suppose A = identity, as in A125586. Then if d=0 there are 3^(n-1) choices for b and c, while if d=1 there are (n-1)*3^(n-2) choices for b and c. This proves the formula in A125586.

			a(2) = 4 from:
10 10 11 11
01 11 01 10

Cf. A125586, A126603, A125593.

a(5) and a(6) from Brendan McKay, Jan 06 2007

A326217 Number of labeled n-vertex digraphs (without loops) containing a Hamiltonian path.

Original entry on oeis.org

0, 0, 3, 48, 3324, 929005, 1014750550, 4305572108670

Offset: 0

Gus Wiseman, Jun 15 2019

			The a(3) = 48 edge-sets:
  {12,23}  {12,13,21}  {12,13,21,23}  {12,13,21,23,31}  {12,13,21,23,31,32}
  {12,31}  {12,13,23}  {12,13,21,31}  {12,13,21,23,32}
  {13,21}  {12,13,31}  {12,13,21,32}  {12,13,21,31,32}
  {13,32}  {12,13,32}  {12,13,23,31}  {12,13,23,31,32}
  {21,32}  {12,21,23}  {12,13,23,32}  {12,21,23,31,32}
  {23,31}  {12,21,31}  {12,13,31,32}  {13,21,23,31,32}
           {12,21,32}  {12,21,23,31}
           {12,23,31}  {12,21,23,32}
           {12,23,32}  {12,21,31,32}
           {12,31,32}  {12,23,31,32}
           {13,21,23}  {13,21,23,31}
           {13,21,31}  {13,21,23,32}
           {13,21,32}  {13,21,31,32}
           {13,23,31}  {13,23,31,32}
           {13,23,32}  {21,23,31,32}
           {13,31,32}
           {21,23,31}
           {21,23,32}
           {21,31,32}
           {23,31,32}

Wikipedia, Hamiltonian path
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

The undirected case is A326206.
The unlabeled undirected case is A057864.
The case with loops is A326214.
Unlabeled digraphs with a Hamiltonian path are A326221.
Digraphs (without loops) not containing a Hamiltonian path are A326216.
Digraphs (without loops) containing a Hamiltonian cycle are A326219.
Cf. A000595, A002416, A003024, A003216, A283420, A326204, A326208, A326213, A326225.

Table[Length[Select[Subsets[Select[Tuples[Range[n],2],UnsameQ@@#&]],FindHamiltonianPath[Graph[Range[n],DirectedEdge@@@#]]!={}&]],{n,4}] (* Mathematica 10.2+ *)

A053763(n) = a(n) + A326216(n).

a(5)-a(7) from Bert Dobbelaere, Feb 21 2023

A326218 Number of non-Hamiltonian labeled n-vertex digraphs (without loops).

Original entry on oeis.org

1, 0, 3, 49, 2902

Offset: 0

Gus Wiseman, Jun 15 2019

A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.

			The a(3) = 49 edge-sets:
  {}  {12}  {12,13}  {12,13,21}  {12,13,21,23}
      {13}  {12,21}  {12,13,23}  {12,13,21,31}
      {21}  {12,23}  {12,13,31}  {12,13,23,32}
      {23}  {12,31}  {12,13,32}  {12,13,31,32}
      {31}  {12,32}  {12,21,23}  {12,21,23,32}
      {32}  {13,21}  {12,21,31}  {12,21,31,32}
            {13,23}  {12,21,32}  {13,21,23,31}
            {13,31}  {12,23,32}  {13,23,31,32}
            {13,32}  {12,31,32}  {21,23,31,32}
            {21,23}  {13,21,23}
            {21,31}  {13,21,31}
            {21,32}  {13,23,31}
            {23,31}  {13,23,32}
            {23,32}  {13,31,32}
            {31,32}  {21,23,31}
                     {21,23,32}
                     {21,31,32}
                     {23,31,32}

Wikipedia, Hamiltonian path

The unlabeled case is A326222.
The undirected case is A326207.
The case with loops is A326220.
Digraphs (without loops) containing a Hamiltonian cycle are A326219.
Digraphs (without loops) not containing a Hamiltonian path are A326216.
Cf. A000595, A002416, A003024, A003216, A246446, A326204, A326213, A326223, A326225.

Table[Length[Select[Subsets[Select[Tuples[Range[n],2],UnsameQ@@#&]],FindHamiltonianCycle[Graph[Range[n],DirectedEdge@@@#]]=={}&]],{n,4}] (* Mathematica 8.0+. Warning: Using HamiltonianGraphQ instead of FindHamiltonianCycle returns a(4) = 2896 which is incorrect *)

A053763(n) = a(n) + A326219(n).

A326219 Number of labeled n-vertex Hamiltonian digraphs (without loops).

Original entry on oeis.org

0, 1, 1, 15, 1194

Offset: 0

Gus Wiseman, Jun 15 2019

A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.

			The a(3) = 15 edge-sets:
  {12,23,31}  {12,13,21,32}  {12,13,21,23,31}  {12,13,21,23,31,32}
  {13,21,32}  {12,13,23,31}  {12,13,21,23,32}
              {12,21,23,31}  {12,13,21,31,32}
              {12,23,31,32}  {12,13,23,31,32}
              {13,21,23,32}  {12,21,23,31,32}
              {13,21,31,32}  {13,21,23,31,32}

Wikipedia, Hamiltonian path

The unlabeled case is A326225.
The undirected case is A326208 (without loops) or A326240 (with loops).
The case with loops is A326204.
Digraphs (without loops) not containing a Hamiltonian cycle are A326218.
Digraphs (without loops) containing a Hamiltonian path are A326217.
Cf. A000595, A002416, A003024, A003216, A053763, A246446, A326220, A326226.

Table[Length[Select[Subsets[Select[Tuples[Range[n],2],UnsameQ@@#&]],FindHamiltonianCycle[Graph[Range[n],DirectedEdge@@@#]]!={}&]],{n,0,4}] (* Mathematica 8.0+. Warning: Using HamiltonianGraphQ instead of FindHamiltonianCycle returns a(4) = 1200 which is incorrect *)

A053763(n) = a(n) + A326218(n).

A328773 Irregular triangle read by rows: T(n,k) is the number of colored digraphs on n nodes with color scheme given by the partitions of n in canonical ordering.

Original entry on oeis.org

1, 1, 3, 4, 16, 36, 64, 218, 752, 1104, 2112, 4096, 9608, 45960, 90416, 178944, 266496, 528384, 1048576, 1540944, 9133760, 22692704, 45277312, 30194176, 90196736, 180011008, 135032832, 269500416, 537919488, 1073741824

Offset: 0

Peter Dolland, Oct 27 2019

Colors are not interchangeable. Adjacent nodes may have the same color.
A partition [b_1, ..., b_m] with b_i > 0 and Sum_{i=1..m} b_i = n corresponds to a color scheme on n nodes having m colors. To find out which digraphs are equivalent with respect to a color scheme, consider the automorphism group on the partition. This group is the m-fold product of the symmetric groups on the b_i nodes, and therefore contains Product_{i=1..m} b_i! elements (i.e. the permutations).
Calculate the number of equivalence classes by determining the cycle index of the group induced by the automorphism group in the set of the edges [(i,j)|i,j in [1..n]; i != j] and set, with Pólya, the variable values to 2.
The left column of the triangle gives the number of unlabeled digraphs, while the right flank of the triangle gives the number of labeled digraphs.
Canonical ordering is also known as graded reverse lexicographic ordering, see A080577, A063008, or link below. Partitions here have the property b_i >= b_j for i < j.

			The sequence begins:
      1;
      1;
      3,       4;
     16,      36,       64;
    218,     752,     1104,     2112,     4096;
   9608,   45960,    90416,   178944,   266496,   528384,   1048576;
   ...
For n = 3, the three partitions of n are [3], [2, 1] and [1, 1, 1]. T(n,1) = 16 gives the number of colored digraphs with all nodes having the same color; T(n, 2) = 36 gives the number of colored digraphs with two nodes having the first color and one node having the second color; T(n, 3) gives the number of colored digraphs with each node having its own color.
For n = 5, k = 4 the required partition is [3,1,1]. T(5,4) = 178944 is then the number of colored digraphs with 5 nodes, where 3 nodes have the first color and the other two nodes each has its own color.

N. G. de Bruijn, Pólyas Abzähl-Theorie: Muster für Graphen und chemische Verbindungen, Selecta Mathematica III, Springer-Verlag (1971), 1-55.

Peter Dolland, Table of n, a(n) for n = 0..138 (rows 0..10)
OEIS Wiki, Orderings of partitions (a comparison).

Cf. A000041 equals the row length, A080577 lists the partitions in the used order, A063008 instantiates the index sequences encoding the partitions. A000273 and A053763 represent the flanks of the triangle.

\\ here C(p) computes sequence value for given partition.
permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i]-1)}
C(p)={((i,v)->if(i>#p, 2^edges(v), my(s=0); forpart(q=p[i], s+=permcount(q)*self()(i+1, concat(v,Vec(q)))); s/p[i]!))(1, [])}
Row(n)={apply(C, vecsort([Vecrev(p) | p<-partitions(n)], ,4))}
{ for(n=0, 6, print(Row(n))) } \\ Andrew Howroyd, Nov 02 2019

T(n, 1) = A000273(n).
T(n, A000041(n)) = A053763(n) = 2^(n^2 - n).
T(n, A000041(n)-1) = 2^(n^2 - 3*n - 1) * (2^(2*n) + 8) for n > 1.

A109354 a(n) = 6^((n^2 - n)/2).

Original entry on oeis.org

1, 1, 6, 216, 46656, 60466176, 470184984576, 21936950640377856, 6140942214464815497216, 10314424798490535546171949056, 103945637534048876111514866313854976, 6285195213566005335561053533150026217291776, 2280250319867037997421842330085227917956272625811456

Offset: 0

Philippe Deléham, Aug 25 2005

nonn

Sequence given by the Hankel transform (see A001906 for definition) of A078018 = {1, 1, 7, 55, 469, 4237, 39907, 387739, ...}; example: det([1, 1, 7, 55; 1, 7, 55, 469; 7, 55, 469, 4237; 55, 469, 4237, 39907]) = 6^6 = 46656.

In general, sequences of the form m^((n^2 - n)/2) enumerate the graphs with n labeled nodes with m types of edge. a(n) therefore is the number of labeled graphs with n nodes with 6 types of edge. - Mark Stander, Apr 11 2019

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A000400, A006125, A047656, A053763, A053764, A109345.

Table[6^((n^2-n)/2),{n,0,10}] (* Harvey P. Dale, May 28 2013 *)

a(n) = 6^((n^2 - n)/2); \\ Michel Marcus, Apr 12 2019

a(n+1) is the determinant of n X n matrix M_(i, j) = binomial(6i, j).

G.f. A(x) satisfies: A(x) = 1 + x * A(6*x). - Ilya Gutkovskiy, Jun 04 2020

Terms a(11) and beyond from Andrew Howroyd, Jan 02 2020

A121724 Generalized central binomial coefficients for k=2.

Original entry on oeis.org

1, 1, 5, 9, 45, 97, 485, 1145, 5725, 14289, 71445, 185193, 925965, 2467137, 12335685, 33563481, 167817405, 464221105, 2321105525, 6507351113, 32536755565, 92236247841, 461181239205, 1319640776249, 6598203881245, 19031570387857, 95157851939285

Offset: 0

Paul Barry, Aug 17 2006, Feb 28 2007

Hankel transform is 4^binomial(n+1,2) = A053763(n+1). Case k=2 of T(n,k) = (1/Pi)*2*k^2*(2*k)^n*Integral_{x=-1..1} x^n*sqrt(1-x^2)/(1+k^2-2*k*x) dx. T(n,k) has Hankel transform (k^2)^binomial(n+1,2). k=1 corresponds to C(n,floor(n/2)).

Series reversion of x*(1+x)/(1+2*x+5*x^2).

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

Cf. A000108, A009766, A053763, A120730.

R:=PowerSeriesRing(Rationals(), 40); Coefficients(R!( (Sqrt(1-16*x^2)+2*x-1)/(2*x*(1-5*x)) )); // G. C. Greubel, Nov 07 2022

CoefficientList[Series[(Sqrt[1-16*x^2]+2*x-1)/(2*x*(1-5*x)), {x,0,40}], x] (* Vaclav Kotesovec, Feb 13 2014 *)

def A120730(n, k): return 0 if (n>2*k) else binomial(n, k)*(2*k-n+1)/(k+1)
def A121724(n): return sum(4^(n-k)*A120730(n,k) for k in range(n+1))
[A121724(n) for n in range(51)] # G. C. Greubel, Nov 07 2022

G.f.: (sqrt(1-16*x^2) + 2*x - 1)/(2*x*(1-5*x)) = c(4*x^2)/(1-x*c(4*x^2)), c(x) the g.f. of A000108.
a(n) = (1/(n+1))*Sum_{k=0..n+1} Sum_{j=0..k} C(n,k)*C(k,j)*C(2*n-2*k+j, n-2*k+j)*(-1)^(n-2*k+j)*2^j*5^(k-j).
a(n) = (1/Pi)*8*4^n*Integral_{x=-1..1} x^n*sqrt(1-x^2)/(5-4*x) dx.
a(n) = Sum_{k=0..floor(n/2)} A009766(n-k,k)*2^2k. - Philippe Deléham, Aug 18 2006
a(n) = Sum_{k=0..n} 4^(n-k)*A120730(n,k). - Philippe Deléham, Oct 16 2008
Conjecture: (n+1)*a(n) = 5*(n+1)*a(n-1) + 16*(n-2)*a(n-2) - 80*(n-2)*a(n-3). - R. J. Mathar, Nov 26 2012
a(n) ~ (9+(-1)^n) * 2^(2*n+5/2) / (9 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 13 2014

More terms from Vincenzo Librandi, Feb 15 2014

A326216 Number of labeled n-vertex digraphs (without loops) not containing a (directed) Hamiltonian path.

Original entry on oeis.org

1, 1, 1, 16, 772

Offset: 0

Gus Wiseman, Jun 15 2019

A path is Hamiltonian if it passes through every vertex exactly once.

			The a(3) = 16 edge-sets:
  {}  {12}  {12,13}
      {13}  {12,21}
      {21}  {12,32}
      {23}  {13,23}
      {31}  {13,31}
      {32}  {21,23}
            {21,31}
            {23,32}
            {31,32}

Wikipedia, Hamiltonian path
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

Unlabeled digraphs not containing a Hamiltonian path are A326224.
The undirected case is A326205.
The unlabeled undirected case is A283420.
The case with loops is A326213.
Digraphs (without loops) containing a Hamiltonian path are A326217.
Digraphs (without loops) not containing a Hamiltonian cycle are A326218.
Cf. A000595, A002416, A003024, A003216, A057864, A326206, A326214, A326220, A326221, A326225.

Table[Length[Select[Subsets[Select[Tuples[Range[n],2],UnsameQ@@#&]],FindHamiltonianPath[Graph[Range[n],DirectedEdge@@@#]]=={}&]],{n,4}] (* Mathematica 10.2+ *)

A053763(n) = a(n) + A326217(n).

cp's OEIS Frontend

A109345 a(n) = 5^((n^2 - n)/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A053765 a(n) = 4^(n^2 - n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A125587 Call an n X n matrix robust if the top left i X i submatrix is invertible for all i = 1..n. Sequence gives number of n X n robust real {0,1}-matrices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A326217 Number of labeled n-vertex digraphs (without loops) containing a Hamiltonian path.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326218 Number of non-Hamiltonian labeled n-vertex digraphs (without loops).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A326219 Number of labeled n-vertex Hamiltonian digraphs (without loops).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A328773 Irregular triangle read by rows: T(n,k) is the number of colored digraphs on n nodes with color scheme given by the partitions of n in canonical ordering.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula