A053763 -id:A053763 - cp's OEIS frontend

A326222 Number of non-Hamiltonian unlabeled n-vertex digraphs (without loops).

1, 0, 2, 12, 157, 5883, 696803, 255954536

Offset: 0

Gus Wiseman, Jun 15 2019

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

Gus Wiseman, Non-isomorphic representatives of the a(3) = 12 non-Hamiltonian digraphs.

The labeled case is A326218 (without loops) or A326220 (with loops).
The undirected case (without loops) is A246446.
The case with loops is A326223.
Hamiltonian unlabeled digraphs are A326225 (without loops) or A003216 (with loops).
Cf. A000273, A000595, A002416, A003087, A053763, A326216, A326217, A326224, A326226.

a(n) = A000273(n) - A326225(n). - Pontus von Brömssen, Mar 17 2024

a(5)-a(7) (using A000273 and A326225) from Pontus von Brömssen, Mar 17 2024

A053773 Number of n X n binary matrices of order dividing 8 (i.e., number of solutions of X^8=I in GL(n,2)).

Original entry on oeis.org

1, 1, 4, 64, 4096, 1048576, 1073741824, 4398046511104, 72057594037927936, 1989505896802466922496, 164384949539438492410445824, 47902612878717208996830483841024

Offset: 0

Vladeta Jovovic, Mar 24 2000

V. Jovovic, The cycle index polynomials of some classical groups, Belgrade, 1995, unpublished.

Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Cf. A053722, A053725, A053718, A053763.

A107254 a(n) = SF(2n-1)/SF(n-1)^2 where SF = A000178.

Original entry on oeis.org

1, 1, 12, 8640, 870912000, 22122558259200000, 222531556847250309120000000, 1280394777025250130271722799104000000000, 5746332926632566442385615219551212618645504000000000000

Offset: 0

Henry Bottomley, May 14 2005

nonn

Inverse product of all matrix elements of n X n Hilbert matrix M(i,j) = 1/(i+j-1) (i,j = 1..n). - Alexander Adamchuk, Apr 12 2006

The n X n matrix with A(i,j) = 1/(i+j-1)! (i,j = 1..n) has determinant (-1)^floor(n/2)/a(n). - Mikhail Lavrov, Nov 01 2022

			a(3) = 1!*2!*3!*4!*5!/(1!*2!*1!*2!) = 34560/4 = 8640.
n = 2: HilbertMatrix[n,n]
  1/1 1/2
  1/2 1/3
so a(2) = 1 / (1 * 1/2 * 1/2 * 1/3) = 12.
The n X n Hilbert matrix begins:
  1/1 1/2 1/3 1/4  1/5  1/6  1/7  1/8 ...
  1/2 1/3 1/4 1/5  1/6  1/7  1/8  1/9 ...
  1/3 1/4 1/5 1/6  1/7  1/8  1/9 1/10 ...
  1/4 1/5 1/6 1/7  1/8  1/9 1/10 1/11 ...
  1/5 1/6 1/7 1/8  1/9 1/10 1/11 1/12 ...
  1/6 1/7 1/8 1/9 1/10 1/11 1/12 1/13 ...

Alois P. Heinz, Table of n, a(n) for n = 0..20
Mathematics Stack Exchange, Determinant of a matrix involving factorials.
Eric Weisstein's World of Mathematics, Hilbert Matrix.

Cf. A000178, A002457, A005249, A098118.

A107254:= func< n | n eq 0 select 1 else (&*[Factorial(n+j)/Factorial(j): j in [0..n-1]]) >;
[A107254(n): n in [0..12]]; // G. C. Greubel, Apr 21 2021

a:= n-> mul((n+i)!/i!, i=0..n-1):
seq(a(n), n=0..10);  # Alois P. Heinz, Jul 23 2012

Table[Product[(i+j-1),{i,1,n},{j,1,n}], {n,1,10}] (* Alexander Adamchuk, Apr 12 2006 *)
Table[n!*BarnesG[2n+1]/(BarnesG[n+2]*BarnesG[n+1]), {n,0,12}] (* G. C. Greubel, Apr 21 2021 *)

a = lambda n: prod(rising_factorial(k,n) for k in (1..n))
print([a(n) for n in (0..10)]) # Peter Luschny, Nov 29 2015

a(n) = n!*(n+1)!*(n+2)!*...*(2n-1)!/(0!*1!*2!*3!*...*(n-1)!) = A000178(2n-1)/A000178(n-1)^2 = A079478(n)/A000984(n) = A079478(n-1)*A009445(n-1) = A107252(n)*A000142(n) = A088020(n)/A039622(n).
a(n) = 1/Product_{j=1..n} ( Product_{i=1..n} 1/(i+j-1) ). - Alexander Adamchuk, Apr 12 2006
a(n) = 2^(n*(n-1)) * A136411(n) for n > 0 . - Robert Coquereaux, Apr 06 2013
a(n) = A136411(n) * A053763(n) for n > 0. [Following remark from Robert Coquereaux] - M. F. Hasler, Apr 06 2013
a(n) ~ A * 2^(2*n^2-1/12) * n^(n^2+1/12) / exp(3*n^2/2+1/12), where A = 1.28242712910062263687534256886979... is the Glaisher-Kinkelin constant (see A074962). - Vaclav Kotesovec, Feb 10 2015
a(n) = Product_{k=1..n} rf(k,n) where rf denotes the rising factorial. - Peter Luschny, Nov 29 2015
a(n) = (n! * G(2*n+1))/(G(n+1)*G(n+2)), where G(n) is the Barnes G - function. - G. C. Greubel, Apr 21 2021

A123554 Triangle read by rows: T(n,k) = number of labeled loopless digraphs with n nodes and k arcs (n >= 1, 0 <= k <= n*(n-1)).

Original entry on oeis.org

1, 1, 2, 1, 1, 6, 15, 20, 15, 6, 1, 1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1, 1, 20, 190, 1140, 4845, 15504, 38760, 77520, 125970, 167960, 184756, 167960, 125970, 77520, 38760, 15504, 4845, 1140, 190, 20, 1, 1, 30, 435, 4060, 27405, 142506, 593775

Offset: 1

N. J. A. Sloane, Nov 15 2006

			Triangle begins:
1
1 2 1
1 6 15 20 15 6 1
1 12 66 220 495 792 924 792 495 220 66 12 1

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 521.

G. C. Greubel, Table of n, a(n) for the first 25 rows, flattened

Row sums are A053763.

Cf. A052283 (unlabeled analog).

Table[CoefficientList[Series[(1+x)^(2*Binomial[n,2]), {x,0,2*Binomial[n,2]}], x], {n,6}] (* Geoffrey Critzer, Nov 12 2011 *)

T(n,k)={binomial(n*(n-1), k)}
{for(n=1, 5, for(k=0, n*(n-1), print1(T(n,k), ", ")); print)} \\ Andrew Howroyd, Apr 19 2020

T(n,k) = binomial(n*(n-1), k). - Andrew Howroyd, Apr 19 2020

More terms from Vladeta Jovovic, Nov 15 2006

A109493 a(n) = 7^((n^2 - n)/2).

Original entry on oeis.org

1, 1, 7, 343, 117649, 282475249, 4747561509943, 558545864083284007, 459986536544739960976801, 2651730845859653471779023381601, 107006904423598033356356300384937784807

Offset: 0

Philippe Deléham, Aug 29 2005

Sequence given by the Hankel transform (see A001906 for definition) of A081178 = {1, 1, 8, 71, 680, 6882, 72528, 788019, ...}; example: det([1, 1, 8, 71; 1, 8, 71, 680; 8, 71, 680, 6882; 71, 680, 6882, 72528]) = 7^6 = 117649.

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 7 types of edge. - Mark Stander, Apr 11 2019

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

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

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

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

A189898 Triangular array read by rows. T(n,k) is the number of digraphs with n labeled nodes having exactly k undirected (or weak) components, n >= 1, 1 <= k <= n.

Original entry on oeis.org

1, 3, 1, 54, 9, 1, 3834, 243, 18, 1, 1027080, 20790, 675, 30, 1, 1067308488, 6364170, 67635, 1485, 45, 1, 4390480193904, 7543111716, 23031540, 171045, 2835, 63, 1, 72022346388181584, 35217115838604, 30469951764, 63580545, 370440, 4914, 84, 1

Offset: 1

Geoffrey Critzer, May 01 2011

The Bell transform of A003027(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016

			1
3       1
54      9     1
3834    243   18   1
1027080 20790 675  30  1

Alois P. Heinz, Rows n = 1..32, flattened

Column 1 = A003027, row sums = A053763, lower diagonal = A045943.

T:= (n, k)-> coeff(series(log(add(2^(i^2-i) *x^i/i!, i=0..n))^k /k!,
                   x, n+1), x, n) *n!:
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, May 01 2011

a= Sum[4^Binomial[n,2]x^n/n!,{n,0,10}];
Transpose[Map[Drop[#, 1] &,Table[Range[0, 10]! CoefficientList[Series[Log[a]^n/n!, {x, 0, 10}], x], {n, 1, 10}]]] // Grid

# uses[bell_matrix from A264428, A003027]
# Adds a column 1,0,0,0, ... at the left side of the triangle.
bell_matrix(lambda n: A003027(n+1), 10) # Peter Luschny, Jan 18 2016

E.g.f. for column k: log(A(x))^k/k! where A(x) is the e.g.f. for A053763.

Name clarified by Andrew Howroyd, Jan 11 2022

A109966 a(n) = 8^((n^2-n)/2).

Original entry on oeis.org

1, 1, 8, 512, 262144, 1073741824, 35184372088832, 9223372036854775808, 19342813113834066795298816, 324518553658426726783156020576256, 43556142965880123323311949751266331066368, 46768052394588893382517914646921056628989841375232, 401734511064747568885490523085290650630550748445698208825344

Offset: 0

Philippe Deléham, Sep 01 2005

Sequence given by the Hankel transform (see A001906 for definition) of A082147 = {1, 1, 9, 89, 945, 10577, 123129, 1476841, ...}; example: det([1, 1, 9, 89; 1, 9, 89, 945; 9, 89, 945, 10577; 89, 945, 10577, 123129]) = 8^6 = 262144.

The number of labeled multigraphs on n vertices such that (i) no self loops are allowed; (ii) all edges are painted in one of 3 colors; (iii) edges between any pair of vertices are painted in distinct colors. Note, this implies that there are at most 3 edges between any vertex pair. Also note there is no restriction on the color of edges incident to a common vertex. - Geoffrey Critzer, Jan 14 2020

Cf. A006125, A047656, A053763, A053764, A059435, A082147, A109345, A109354, A109493.

[2^(3*Binomial(n,2)): n in [0..10]]; // G. C. Greubel, Feb 05 2018

Table[2^(3*Binomial[n,2]),{n,0,10}] (* Geoffrey Critzer, Nov 10 2011 *)

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

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

Hankel transform of A059435. - Philippe Deléham, Sep 03 2006

a(10) corrected and a(11), a(12) from Georg Fischer, Apr 01 2022

A269576 a(n) = Product_{i=1..n} (4^i - 3^i).

Original entry on oeis.org

1, 7, 259, 45325, 35398825, 119187843775, 1692109818073675, 99792176520894983125, 24195710911432718503470625, 23942309231057283642583777144375, 96180015123706384385790918441966041875

Offset: 1

Bob Selcoe, Mar 02 2016

nonn

In general, for sequences of the form a(n) = Product_{i=1..n} j^i-k^i, where j>k>=1 and n>=1: given probability p=(k/j)^n that an outcome will occur at the n-th stage of an infinite process, then r = 1 - a(n)/j^((n^2+n)/2) is the probability that the outcome has occurred at or before the n-th iteration. Here j=4 and k=3, so p=(3/4)^n and r = 1-a(n)/A053763(n+1). The limiting ratio of r is ~ 0.9844550.

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

Cf. A005061, A053763.
Cf. sequences of the form Product_{i=1..n}(j^i - 1): A005329 (j=2), A027871 (j=3), A027637 (j=4), A027872 (j=5), A027873 (j=6), A027875 (j=7),A027876 (j=8), A027877 (j=9), A027878 (j=10), A027879 (j=11), A027880 (j=12).
Cf. sequences of the form Product_{i=1..n}(j^i - k^1), k>1: A263394 (j=3, k=2), A269661 (j=5, k=4).

seq(mul(4^i-3^i,i=1..n),n=0..20); # Robert Israel, Jun 01 2023

Table[Product[4^i - 3^i, {i, n}], {n, 11}] (* Michael De Vlieger, Mar 07 2016 *)
FoldList[Times,Table[4^n-3^n,{n,20}]] (* Harvey P. Dale, Jul 30 2018 *)

a(n) = prod(k=1, n, 4^k-3^k); \\ Michel Marcus, Mar 05 2016

a(n) = Product_{i=1..n} A005061(i).
a(n) ~ c * 2^(n*(n+1)), where c = QPochhammer(3/4) = 0.015545038845451847... . - Vaclav Kotesovec, Oct 10 2016
a(n+3)/a(n+2) - 7 * a(n+2)/a(n+1) + 12 * a(n+1)/a(n) = 0. - Robert Israel, Jun 01 2023

A309327 a(n) = Product_{k=1..n-1} (4^k + 1).

Original entry on oeis.org

1, 1, 5, 85, 5525, 1419925, 1455423125, 5962868543125, 97701601079103125, 6403069829921181503125, 1678532740564688125136703125, 1760070825503098980191468752703125, 7382273863761775568111978346806480703125, 123854010565759745011512941023673583762640703125

Offset: 0

Ilya Gutkovskiy, Jun 06 2020

nonn

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

Cf. A027637, A052539, A053763.

Sequences of the form Product_{j=1..n-1} (m^j + 1): A000012 (m=0), A011782 (m=1), A028362 (m=2), A290000 (m=3), this sequence (m=4).

[n lt 2 select 1 else (&*[4^j +1: j in [1..n-1]]): n in [0..15]]; // G. C. Greubel, Feb 21 2021

Table[Product[4^k + 1, {k, 1, n - 1}], {n, 0, 13}]
Join[{1}, Table[4^(Binomial[n,2])*QPochhammer[-1/4, 1/4, n-1], {n,15}]] (* G. C. Greubel, Feb 21 2021 *)

a(n) = prod(k=1, n-1, 4^k + 1); \\ Michel Marcus, Jun 06 2020

from sage.combinat.q_analogues import q_pochhammer
[1]+[4^(binomial(n,2))*q_pochhammer(n-1, -1/4, 1/4) for n in (1..15)] # G. C. Greubel, Feb 21 2021

G.f. A(x) satisfies: A(x) = 1 + x * A(4*x) / (1 - x).
G.f.: Sum_{k>=0} 2^(k*(k - 1)) * x^k / Product_{j=0..k-1} (1 - 4^j*x).
a(0) = 1; a(n) = Sum_{k=0..n-1} 4^k * a(k).
a(n) ~ c * 2^(n*(n - 1)), where c = Product_{k>=1} (1 + 1/4^k) = 1.355909673863479380345544...
a(n) = 4^(binomial(n+1,2))*(-1/4; 1/4){n}, where (a;q){n} is the q-Pochhammer symbol. - G. C. Greubel, Feb 21 2021

A346214 Triangular array read by rows. T(n,k) is the number of nilpotent n X n matrices over GF(2) with index k, 1 <= k <= n, n >= 1.

Original entry on oeis.org

1, 1, 3, 1, 21, 42, 1, 315, 1260, 2520, 1, 6975, 104160, 312480, 624960, 1, 373023, 23436000, 104993280, 314979840, 629959680, 1, 32252031, 9175162752, 121912197120, 426692689920, 1280078069760, 2560156139520, 1, 6619979775, 9978120069120, 421755245936640, 1989607056998400, 6963624699494400, 20890874098483200, 41781748196966400

Offset: 1

Geoffrey Critzer, Jul 10 2021

The index of a nilpotent matrix A is the smallest positive integer k such that A^k = 0.

Define the co-index of an n X n matrix A to be n - index(A). Let X_n be the random variable that assigns to each nilpotent n X n matrix over GF(2) the value j in {0,1,...,n-1} of its co-index. Conjecture: lim_{n->inf} P(X_n = j) = Product_{i>=1}1-1/2^i * 2^((j-1)^2)/A002884(j). Moreover, for j < 2n, T(n,n-j) = A002884(n)/(A002884(j)*2^(n - (j-1)^2)). - Geoffrey Critzer, Jun 10 2025

			  1,
  1,    3,
  1,   21,     42,
  1,  315,   1260,   2520,
  1, 6975, 104160, 312480, 624960

Cf. A083402 (main diagonal), A053763 (row sums), A002884, A048651.

nn = 8;  q = 2;
b[p_, i_] := Count[p, i];
d[p_, i_] :=  Sum[j b[p, j], {j, 1, i}] + i Sum[b[p, j], {j, i + 1, Total[p]}];
aut[deg_, p_] := Product[Product[ q^(d[p, i] deg) - q^((d[p, i] - k) deg), {k, 1, b[p, i]}], {i, 1, Total[p]}];
l = Level[Table[IntegerPartitions[n],  {n,  0,  nn}],  {2}];
\[Gamma][n_, q_] := Product[q^n - q^i, {i, 0, n - 1}];
g[u_,  v_,  deg_,  partitions_] := Total[Map[v^If[# == {},  0,  Max[#]] u^(deg Total[#])/aut[deg,  #] &, partitions]];
Map[Select[#,  # > 0 &] &, Drop[Table[\[Gamma][n,  q],  {n,  0,  nn}] CoefficientList[     Series[g[u,  v,  1,  l],  {u,  0,  nn}],  {u,  v}],  1]] // Grid

More terms from Geoffrey Critzer, Jun 10 2025

cp's OEIS Frontend

A326222 Number of non-Hamiltonian unlabeled n-vertex digraphs (without loops).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A053773 Number of n X n binary matrices of order dividing 8 (i.e., number of solutions of X^8=I in GL(n,2)).

Views

Author

Keywords

References

Links

Crossrefs

A107254 a(n) = SF(2n-1)/SF(n-1)^2 where SF = A000178.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

A123554 Triangle read by rows: T(n,k) = number of labeled loopless digraphs with n nodes and k arcs (n >= 1, 0 <= k <= n*(n-1)).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A109493 a(n) = 7^((n^2 - n)/2).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

A189898 Triangular array read by rows. T(n,k) is the number of digraphs with n labeled nodes having exactly k undirected (or weak) components, n >= 1, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions

A109966 a(n) = 8^((n^2-n)/2).

Views

Author

Keywords

Comments

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A269576 a(n) = Product_{i=1..n} (4^i - 3^i).