A053763 -id:A053763 - cp's OEIS frontend

A309980 Number of binary relations on n unlabeled nodes that are neither reflexive nor antireflexive.

0, 4, 72, 2608, 272752, 93847104, 110518842048, 454710381676032, 6640565658505128832, 348708024629593894001152, 66538376166308068986316241408, 46534722991725338264882258863095808, 120139253095727581744381043433138973706240, 1151909524447243687554850690730124812494959992832

Offset: 1

Peter Dolland, Nov 02 2019

nonn

Also the number of colored digraphs on n unlabeled nodes with nodes of exactly two colors. (Understand "(x,x) in the relation" for several nodes x as a special color!)

			n=2: We label node 1 with (1,1) in the relation and node 2 with (2,2) not in the relation, and we have two differently labeled nodes and so a(2) = A053763(2) = 4.
n=3: We have exactly either one or two nodes x with (x,x) in the relation. In A328773 this labelings correspond to the color schemes [2,1] and [1,2], both represented by the column index 2. So we have a(3) = 2 * A328773(3,2) = 72.

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

Cf. A000595 (arbitrary binary relations), A000273 (digraphs, i.e. reflexive resp. antireflexive binary relations), A053763 (digraphs with distinguishing labeled nodes), A328773 (digraphs with given color scheme).

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];
a[n_] := Module[{s = 0}, Do[t = 2^edges[p]; s += t*(1 - 2^(1 - Length[p]))* permcount[p], {p, IntegerPartitions[n]}]; s/n!];
Array[a, 14] (* Jean-François Alcover, Jan 08 2021, after Andrew Howroyd *)

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])}
a(n) = {my(s=0); forpart(p=n, my(t=2^edges(p)); s+=t*(1 - 2^(1-#p))*permcount(p)); s/n!} \\ Andrew Howroyd, Nov 02 2019

a(n) = A000595(n) - 2 * A000273(n) for n >= 1.

A319016 Decimal expansion of Sum_{k>=0} 1/2^(k*(k+1)).

Original entry on oeis.org

1, 2, 6, 5, 8, 7, 0, 0, 9, 5, 2, 3, 0, 8, 6, 6, 3, 6, 8, 4, 1, 8, 9, 2, 1, 3, 1, 4, 5, 4, 3, 5, 4, 3, 4, 2, 7, 4, 6, 4, 2, 6, 5, 4, 4, 6, 3, 9, 9, 6, 3, 8, 7, 1, 6, 8, 2, 0, 0, 5, 3, 3, 4, 1, 8, 1, 4, 8, 9, 3, 4, 9, 2, 5, 1, 1, 2, 7, 4, 8, 9, 4, 4, 3, 7, 0, 6, 4, 5, 9, 7, 4, 8, 3, 5, 3, 0, 5, 6, 7, 3, 9, 0, 8, 4, 2, 7, 1, 1, 4

Offset: 1

Ilya Gutkovskiy, Sep 07 2018

The binary expansion is the characteristic function of the oblong numbers (A005369).

The Engel expansion of this constant are the powers of 4 (A000302). - Amiram Eldar, Dec 07 2020

			1.2658700952308663684189... = (1.010001000001000000010000000001...)_2.
                               |  |   |     |       |         |
                               0  2   6    12      20        30

Cf. A000302, A002378, A005369, A053763, A190405, A299998, A319015.

RealDigits[EllipticTheta[2, 0, 1/2]/2^(3/4), 10, 110] [[1]]

suminf(k=0, 1/2^(k*(k+1))) \\ Michel Marcus, Sep 08 2018

Equals theta_2(1/2)/2^(3/4), where theta_2 is the Jacobi theta function.

Equals Product_{k>=1} (1 - 1/4^k)^((-1)^k). - Antonio Graciá Llorente, Oct 01 2024

A329541 Triangle read by rows: T(n,k) is the number of colored digraphs on n nodes with exactly k colors assigned in a fix order according the node count (1 <= k <= n).

Original entry on oeis.org

1, 3, 4, 16, 36, 64, 218, 1856, 2112, 4096, 9608, 136376, 445440, 528384, 1048576, 1540944, 62020640, 270506880, 449511424, 537919488, 1073741824, 882033440, 55259421024, 435010671104, 1101584588800, 1834672455680, 2200096997376, 4398046511104

Offset: 1

Peter Dolland, Nov 16 2019

The values are just subtotals of the rows of the irregular triangle A328773.
Colors C_1,...,C_k are assigned to n nodes in the way that a_i >= a_(i+1) >= 1 for 1 <= i < k, where a_i denotes the number of nodes colored with C_i.
T(n,k) gives the number of digraphs (see A000273) without restrictions, where nodes of the same color are not differentiated.
The order of the colors effects, that only one color scheme has to be considered for a given color count. If such an order may not be presupposed, you should note A329546.

			Partitions for n=4, k=2: [3,1] and [2,2] with indices 2 and 3: T(4,2) = Sum_{i=2,3} A328773(4,i) = 752 + 1104 = 1856.
Partitions for n=6, k=3: [4,1,1], [3,2,1], [2,2,2] with indices 4, 6, 8: T(6,3) = Sum_{i=4,6,8} A328773(6,i) = 45277312 + 90196736 + 135032832 = 270506880.
Triangle T(n,k) begins:
        1
        3        4
       16       36        64
      218     1856      2112      4096
     9608   136376    445440    528384   1048576
  1540944 62020640 270506880 449511424 537919488 1073741824
  ...

Cf. A000273 (digraphs with one color), A053763 (digraphs with n colors), A328773 (digraphs to a given color scheme). A329546 (digraphs with unordered colors).

\\ here C(p) computes A328773 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)={[vecsum(apply(C, vecsort([Vecrev(p) | p<-partitions(n),#p==m], , 4))) | m<-[1..n]]}
{ for(n=0, 10, print(Row(n))) }

T(n,1) = A000273(n) = A328773(n,1).
T(n,n) = 2^(n^2-n) = A053763(n) = A328773(n,A000041(n)).
T(n,n-1) = A328773(n,A000041(n)-1).
T(n,k) = Sum_{i=1..A000041(n), A063008(n,i) encodes a partition p with k=#p} A328773(n,i).

A329546 Triangle read by rows: T(n,k) is the number of colored digraphs on n nodes with exactly k colors arbitrarily assigned (1 <= k <= n).

Original entry on oeis.org

1, 3, 4, 16, 72, 64, 218, 2608, 6336, 4096, 9608, 272752, 1336320, 2113536, 1048576, 1540944, 93847104, 812045184, 2337046528, 2689597440, 1073741824, 882033440, 110518842048, 1580861402112, 7344135176192, 14676310097920, 13200581984256, 4398046511104

Offset: 1

Peter Dolland, Nov 16 2019

The values are weighted subtotals of the rows of the irregular triangle A328773.
The weight of a color scheme is the multiplicity A072811(n,k) with k as the index of the induced partition.
T(n,k) gives the number of digraphs (see A000273) without restrictions, where nodes of the same color are not differentiated.
If we do not consider the exchange of colors with different sizes to be different digraphs, we can impose an order on the colors, which leads to A329541.

			First six rows:
      1
      3        4
     16       72        64
    218     2608      6336       4096
   9608   272752   1336320    2113536    1048576
1540944 93847104 812045184 2337046528 2689597440 1073741824
n=4, k=2: Partitions: [3,1] and [2,2] with indices 2 and 3 and multiplicities 2 and 1: T(4,2) = Sum_{i=2,3} A072811(4,i)*A328773(4,i) = 2*752 + 1104 = 2608.
n=6, k=3: Partitions: [4,1,1], [3,2,1], [2,2,2] with indexes 4, 6, 8 and multiplicities 3, 6, 1: T(6,3) = Sum_{i=4,6,8} A072811(6,i)*A328773(6,i) = 3*45277312 + 6*90196736 + 1*135032832 = 812045184.

Cf. A000273 (digraphs with one color), A053763 (digraphs with n colors), A328773 (digraphs to a given color scheme).
Cf. A072811 (multiplicity of color schemes).
Cf. A329541 (ordered colors).
Cf. A309980 (reflexive/anti-reflexive: just two colors).

\\ here C(p) computes A328773 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, [])}
\\ here mulp(v) computes the multiplicity of the given partition. (see A072811)
mulp(v) = {my(p=(#v)!, k=1); for(i=2, #v, k=if(v[i]==v[i-1], k+1, p/=k!; 1)); p/k!}
wC(p)=mulp(p)*C(p)
Row(n)={[vecsum(apply(wC, vecsort([Vecrev(p) | p<-partitions(n),#p==m], , 4))) | m<-[1..n]]}
{ for(n=0, 10, print(Row(n))) }

T(n,1) = A000273(n) = A328773(n,1).
T(n,n) = A053763(n) = A328773(n,A000041(n)).
T(n,n-1) = (n-1)*A328773(n,A000041(n)-1).
T(n,k) = Sum_{i=1..A000041(n), A063008(n,i) encodes a partition with k elements} A072811(n,i)*A328773(n,i).

A343592 Number of symmetry types of digraphs with n nodes.

Original entry on oeis.org

1, 2, 4, 9, 14, 36

Offset: 1

Peter Dolland, Apr 21 2021

The symmetry type of a digraph is determined by its automorphism group. It is a permutation group on the nodes set, and therefore a subgroup of the symmetric group Sn. The total number of these is determined by A000638. But not all of them occur as an automorphism group of a digraph.

			The four symmetry types of the digraphs with 3 nodes are represented by:
1.) {}, the empty graph, has together with the full graph the automorphism group S_3 (as subgroup of S_3) as symmetry type.
2.) {(1,2)} has together with 6 other digraphs the trivial automorphism group {id} as symmetry type. This digraph class is called asymmetric. Their values are given by A051504.
3.) {(1,2),(2,1)} has together with 5 other digraphs the automorphism group containing id and a transposition (so it is C_2 as the subgroup of S_3) as symmetry type.
4.) {(1,2),(2,3),(3,1)} has as the only digraph with three nodes the automorphism group C_3 as symmetry type. As a consequence it has to be self-complementary.
The total of the sizes of the symmetry type classes yields the number of digraphs A000273. Here: 2+7+6+1 = 16 = A000273(3).
Note, that for n > 3 there may be different symmetry types with isomorphic automorphism groups. For n=4 both {(1,2)} and {(1,2),(3,4)} have C_2 as automorphism group, but they are different as permutation group.

Peter Dolland, Digraph Symmetry Tables for n = 3..6
Götz Pfeiffer, Subgroups. [broken link]

Cf. A000273, A000638, A051504, A053763, A000595.

A346210 Number of n X n matrices over GF(2) whose characteristic polynomial is a product of (not necessarily distinct) linear factors, i.e., the characteristic polynomial has the form x^k(1+x)^(n-k) for some 0 <= k <= n.

Original entry on oeis.org

1, 2, 14, 352, 32512, 11239424, 14761852928, 74524125036544, 1459094811012235264, 111539381955990155952128, 33460660604316425324211470336, 39542320578630779599776165929156608, 184615341335916919478531491782548361576448

Offset: 0

Geoffrey Critzer, Jul 10 2021

nonn

			a(2) = 14 because there are 16 2 X 2 matrices over GF(2) and all except {{0,1},{1,1}} and {{1,1},{1,0}} have characteristic polynomials of the desired form.

L. Kaylor and D. Offner, Counting matrices over a finite field with all eigenvalues in the field, Involve, a Journal of Mathematics, Vol. 7 (2014), No. 5, 627-645.

Cf. A002884, A053763.

nn = 12; q = 2; Table[Product[q^n - q^i, {i, 0, n - 1}], {n, 0, nn}] CoefficientList[Series[Product[1/(1 - u/q^r), {r, 1, \[Infinity]}]^2, {u, 0, nn}], u]

Sum_{n>=0} a(n)*x^n/A002884(n) = (Sum_{n>=0} A053763(n)x^n/A002884(n))^2 = (Product_{n>=1} 1/(1-x/2^n))^2.

A053766 a(n) = 5^(n^2 - n).

Original entry on oeis.org

1, 1, 25, 15625, 244140625, 95367431640625, 931322574615478515625, 227373675443232059478759765625, 1387778780781445675529539585113525390625

Offset: 0

Stephen G Penrice, Mar 29 2000

Number of nilpotent n X n matrices over GF(5).

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.

Cf. A053763, A053764, A053765.

A053766:=n->5^(n^2 - n); seq(A053766(n), n=0..10); # Wesley Ivan Hurt, Jan 28 2014

Table[5^(n^2 - n), {n, 0, 10}] (* Wesley Ivan Hurt, Jan 28 2014 *)

a(n) = A000351(n^2 - n). - Wesley Ivan Hurt, Jan 28 2014

More terms from James Sellers, Apr 08 2000

A054914 Number of labeled connected digraphs with n nodes such that complement is also connected.

Original entry on oeis.org

1, 2, 44, 3572, 1005584, 1060875152, 4382913876704, 71987098738435232, 4721068803628864289024, 1237845578934919489219757312, 1298046978912816702510086132201984, 5444486716626952189940499391640815580672, 91343710775311761525117954724021374685703481344

Offset: 1

N. J. A. Sloane, May 23 2000

Alois P. Heinz, Table of n, a(n) for n = 1..50
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A003027, A053763.

m:=30;
f:= func< x | (&+[2^(n*(n-1))*x^n/Factorial(n): n in [0..m+3]]) >;
R:=PowerSeriesRing(Rationals(), m);
Coefficients(R!(Laplace( 1 + 2*Log(f(x)) - f(x) ))); // G. C. Greubel, Apr 28 2023

b:= n-> 2^(n^2-n):
g:= proc(n) option remember; local k; `if`(n=0, 1,
      b(n)- add(k*binomial(n,k) *b(n-k)*g(k), k=1..n-1)/n)
    end:
a:= n-> 2*g(n)-b(n):
seq (a(n), n=1..20);  # Alois P. Heinz, Oct 21 2012

nn=20; g=Sum[2^(2Binomial[n,2])x^n/n!,{n,0,nn}];
Drop[Range[0,nn]!CoefficientList[Series[2(Log[g]+1)-g,{x,0,nn}],x],1]  (* Geoffrey Critzer, Oct 21 2012 *)

m=30
def f(x): return sum(2^(n*(n-1))*x^n/factorial(n) for n in range(m+4))
def A054914_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( 2 + 2*log(f(x)) - f(x) ).egf_to_ogf().list()
a=A054914_list(40); a[1:] # G. C. Greubel, Apr 28 2023

a(n) = 2*A003027(n) - A053763(n).

More terms from Vladeta Jovovic, Jul 17 2000

A110195 a(n) = 11^((n^2-n)/2).

Original entry on oeis.org

1, 1, 11, 1331, 1771561, 25937424601, 4177248169415651, 7400249944258160101211, 144209936106499234037676064081, 30912680532870672635673352936887453361, 72890483685103052142902866787761839379440139451, 1890591424712781041871514584574319778449301246603238034051

Offset: 0

Philippe Deléham, Sep 07 2005

Sequence given by the Hankel transform (see A001906 for definition) of A082173 = {1, 1, 12, 155, 2124, 30482, 453432, 6936799, ...}; example : det([1, 1, 12, 155; 1, 12, 155, 2124; 12, 155, 2124, 30482; 155, 2124, 30482, 453432]) = 11^6 = 1771561.

Cf. A001020, A006125, A047656, A053763, A053764, A109345, A109354, A109493, A109966, A110147, A161680.

Table[11^((n^2-n)/2),{n,0,20}] (* Harvey P. Dale, Feb 02 2012 *)
Join[{1,1},Table[Det[Table[Binomial[11i,j],{i,n},{j,n}]],{n,10}]] (* Harvey P. Dale, Apr 01 2019 *)

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

a(n) = A001020(A161680(n)).

a(11) from Harvey P. Dale, Feb 02 2012

a(12) from Jason Yuen, Aug 29 2025

A129148 Expansion of (1-x-sqrt(1-6x-7x^2))/(2(1+2x)).

Original entry on oeis.org

1, 2, 8, 36, 180, 956, 5300, 30316, 177604, 1060284, 6427092, 39452364, 244748196, 1532044572, 9664688436, 61380865452, 392148430212, 2518518772604, 16250624534420, 105297028489612, 684865176181348

Offset: 1

Paul Barry, Apr 01 2007

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

Hankel transform is 4^C(n+1,2)=A053763(n+1).

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

Rest[CoefficientList[Series[(1-x-Sqrt[1-6*x-7*x^2])/(2*(1+2*x)), {x, 0, 20}], x]] (* Vaclav Kotesovec, Oct 20 2012 *)
Table[(1/(2*Pi))*Integrate[x^n*Sqrt[7+6*x-x^2]/(2+x),{x,-1,7}],{n,0,10}] (* Vaclav Kotesovec, Oct 20 2012 *)

a(n)=sum{k=0..n, sum{j=0..n, C(n,j)*C(n-k,j+k-n)*C(n-k)*3^(j+k-n)}}, C(n)=A000108(n); a(n)=(1/(2*pi))*int(x^n*sqrt(7+6*x-x^2)/(2+x),x,-1,7);
D-finite with recurrence: n*a(n) = (4*n-9)*a(n-1) + (19*n-39)*a(n-2) + 14*(n-3)*a(n-3) . - Vaclav Kotesovec, Oct 20 2012
a(n) ~ 7^(n+1/2)/(9*sqrt(2*Pi)*n^(3/2)) . - Vaclav Kotesovec, Oct 20 2012

Offset corrected to 1, Vaclav Kotesovec, Oct 20 2012

cp's OEIS Frontend

A309980 Number of binary relations on n unlabeled nodes that are neither reflexive nor antireflexive.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A319016 Decimal expansion of Sum_{k>=0} 1/2^(k*(k+1)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A329541 Triangle read by rows: T(n,k) is the number of colored digraphs on n nodes with exactly k colors assigned in a fix order according the node count (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A329546 Triangle read by rows: T(n,k) is the number of colored digraphs on n nodes with exactly k colors arbitrarily assigned (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A343592 Number of symmetry types of digraphs with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A346210 Number of n X n matrices over GF(2) whose characteristic polynomial is a product of (not necessarily distinct) linear factors, i.e., the characteristic polynomial has the form x^k(1+x)^(n-k) for some 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A053766 a(n) = 5^(n^2 - n).

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A054914 Number of labeled connected digraphs with n nodes such that complement is also connected.

Views

Author

Keywords

Links

Crossrefs

A129148 Expansion of (1-x-sqrt(1-6x-7x^2))/(2(1+2x)).