A002416 -id:A002416 - cp's OEIS frontend

A355440 Expansion of e.g.f. Sum_{k>=0} exp(4^k * x) * x^k/k!.

1, 2, 10, 98, 2050, 84482, 7221250, 1218502658, 421846581250, 288641130823682, 403002184457781250, 1112950376623239069698, 6251793960501383945781250, 69503063309910921346390425602, 1568447691296998939150390025781250

Offset: 0

Seiichi Manyama, Jul 02 2022

nonn

a(n) is the number of labeled digraphs on [n] with self loops allowed (A002416) such that reflexive nodes are only adjacent to irreflexive nodes and vice versa. A reflexive node is a node with a self loop. An irreflexive node is a node without a self loop. - Geoffrey Critzer, Aug 21 2023

Column k=4 of A355395.

Cf. A193199.

nn = 6; B[n_] := n! 4^Binomial[n, 2]; e[x_] := Sum[x^n/B[n], {n, 0, nn}];
Table[B[n], {n, 0, nn}] CoefficientList[Series[e[x]^2, {x, 0, nn}], x]

my(N=20, x='x+O('x^N)); Vec(serlaplace(sum(k=0, N, exp(4^k*x)*x^k/k!)))

my(N=20, x='x+O('x^N)); Vec(sum(k=0, N, x^k/(1-4^k*x)^(k+1)))

a(n) = sum(k=0, n, 4^(k*(n-k))*binomial(n, k));

G.f.: Sum_{k>=0} x^k/(1 - 4^k * x)^(k+1).
a(n) = Sum_{k=0..n} 4^(k*(n-k)) * binomial(n,k).
E(x)^2 = Sum_{k>=0} a(n)*x^n/B(n) where B(n) = n!*4^binomial(n,2) and E(x) = Sum_{n>=0} x^n/B(n). - Geoffrey Critzer, Aug 21 2023

A361269 Triangular array read by rows. T(n,k) is the number of binary relations on [n] containing exactly k strongly connected components, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 2, 0, 4, 12, 0, 144, 168, 200, 0, 25696, 18768, 12384, 8688, 0, 18082560, 8697280, 3923040, 1914560, 936992, 0, 47025585664, 14670384000, 4512045120, 1622358720, 647087040, 242016192, 0, 450955726792704, 87781550054912, 17679638000640, 4496696041600, 1408276410240, 482302375296, 145763745920

Offset: 0

Geoffrey Critzer, Mar 06 2023

			  1;
  0,     2;
  0,     4,    12;
  0,   144,   168,   200;
  0, 25696, 18768, 12384, 8688;
  ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.
Wikipedia, Strongly connected component

Cf. A003030, A003024, A002416 (row sums).

nn =15; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
   Length@# == 2 &][[All, 2]]; s[x_] := Total[strong Table[x^i/i!, {i, 1, 58}]]; begf = Total[CoefficientList[ Series[1/(Total[CoefficientList[Series[ Exp[-u *s[x]], {x, 0, nn}], x]* Table[z^n/(2^Binomial[n, 2]), {n, 0, nn}]]), {z, 0, nn}],z]*Table[z^n 2^Binomial[n, 2], {n, 0, nn}]] /. z -> 2 z;
Range[0, nn]! CoefficientList[begf, {z, u}] // Grid (* Geoffrey Critzer, Mar 14 2023 after Andrew Howroyd *)

Z(p, f)={my(n=serprec(p, x)); serconvol(p, sum(k=0, n-1, x^k*f(k), O(x^n)))}
G(e, p)={Z(p, k->1/e^(k*(k-1)/2))}
U(e, p)={Z(p, k->e^(k*(k-1)/2))}
RelEgf(n, e)={sum(k=0, n, e^(k^2)*x^k/k!, O(x*x^n) )}
T(n)={my(e=2); [Vecrev(p) | p<-Vec(serlaplace(U(e, 1/G(e, exp(y*log(U(e, 1/G(e, RelEgf(n, e)))))))))]}
{ my(A=T(6)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Mar 06 2023

E.g.f. for column 1: A(2*x) where A(x) is the e.g.f. for A003030.

E.g.f. for main diagonal: B(2*x) where B(x) is the e.g.f. for A003024.

Terms a(15) and beyond from Andrew Howroyd, Mar 06 2023

A365590 Number of n X n Boolean relation matrices such that each of the diagonal blocks of its Frobenius normal form is either a 1 block or a 0 block.

Original entry on oeis.org

1, 2, 13, 243, 11998, 1477763, 436610299, 300960642300, 474171878424571, 1680899431189662775, 13241419272545722904788, 229482664065433754849099977, 8677282817864146616211588609715, 710901968198799834001047038898570250

Offset: 0

Geoffrey Critzer, Sep 10 2023

nonn

A 1(0) block is such that every entry in the block is 1(0). See Gregory, Kirkland, Pullman for a description of Frobenius normal form.

a(n) is also the number of labeled digraphs (with loops allowed A002416) on [n] such that every strongly connected component is either complete or a single vertex without a loop.

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.

Cf. A355612, A365593, A365534.

nn = 13; B[n_] := n! 2^Binomial[n, 2]; ggf[egf_] := Normal[Series[egf, {x, 0, nn}]] /. Table[x^i -> x^i/2^Binomial[i, 2], {i, 0, nn}]; Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggf[Exp[-(Exp[x] - 1 + x)]], {x, 0, nn}], x]

Sum_{n>=0} a(n)*x^n/(n!*2^binomial(n,2)) = 1/(E(x) @ exp(-(exp(x)-1+x))) where E(x)=Sum_{n>=0} x^n/(n!*2^binomial(n,2)) and @ is the exponential Hadamard product (see Panafieu and Dovgal).

A374525 T(n,k) is the number of distinct n X n {0,1}-matrices that reach a fixed point after k alternately applied sorts by rows and columns, where T(n,k), k>=0 is an irregular triangle read by rows.

Original entry on oeis.org

2, 7, 7, 2, 45, 219, 243, 5, 650, 13599, 46385, 4512, 344, 46, 24520, 2542012, 23807149, 6258387, 781647, 132869, 7134, 714, 2625117, 1649029775, 39954292931, 22532640821, 3839779352, 685879134, 49418375, 5578311, 215664, 17256, 836488618

Offset: 1

Hugo Pfoertner at the suggestion of Markus Sigg, Jul 19 2024

It is conjectured that for n>=3 the last term > 0 in row n is T(n,2*n-3). This is consistent with the result of random draws, where T(7,11) is the last term in row 7.

Approximate values of the terms in the next row 7 from random drawings are as follows: 8.4E8, 3.79E12, 2.38E14, 2.54E14, 5.61E13, 1.02E13, 8.22E11, 9.0E10, 4.2E9, 3E8, 9E6, 1E6.

			The triangle begins
   \ k    0        1         2        3       4       5     6    7
  n  -------------------------------------------------------------
  1 |     2,
  2 |     7,       7,        2,
  3 |    45,     219,      243,       5,
  4 |   650,   13599,    46385,    4512,    344,     46,
  5 | 24520, 2542012, 23807149, 6258387, 781647, 132869, 7134, 714
.
  T(2,0) = 7;
  matrices that are already stably sorted, i.e., neither affected
  by sorting by rows nor by sorting by columns:
  [0, 0; 0, 0], [0, 0; 0, 1], [0, 0; 1, 1], [0, 1; 0, 1],
  [0, 1; 1, 0], [0, 1; 1, 1], [1, 1; 1, 1]
.
  T(2,1) = 7; matrices that become stable after one sort:
               sorting by     stable
  [0, 0; 1, 0] columns ->  [0, 0; 0, 1]
  [0, 1; 0, 0] rows    ->  [0, 0; 0, 1]
  [1, 0; 0, 1] rows or ->  [0, 1; 1, 0]
               columns
  [1, 0; 1, 0] columns ->  [0, 1; 0, 1]
  [1, 0; 1, 1] columns ->  [0, 1; 1, 1]
  [1, 1; 0, 0] rows    ->  [0, 0; 1, 1]
  [1, 1; 0, 1] rows    ->  [0, 1; 1, 1]
.
  T(2,2) = 2; matrices needing two sorts to become stable:
         sorting            by     stable
  [1, 0]            [0, 1]         [0, 0]
  [0, 0]            [0, 0]         [0, 1]
         columns ->        rows ->
  [1, 1]            [1, 1]         [0, 1]
  [1, 0]            [0, 1]         [1, 1]

Hugo Pfoertner, PARI program, computes row n.
Markus Sigg, C program, computes row n for A374525 or A374526.

Cf. A002416 (row sums), A089006 (column 0), A374526.

PARI
```
\\ See link.
```

For each n: Sum_{k>=0} T(n,k) = 2^(n^2).

T(n,0) = A089006(n).

a(24)-a(33) (row 6 of triangle) from Markus Sigg, Jul 25 2024

A060704 Singular n X n matrices over GF(2).

Original entry on oeis.org

1, 10, 344, 45376, 23555072, 48560766976, 399099960492032, 13098680304497852416, 1718239329196060706865152, 901210462928281273073900978176, 1890350559451566075272982533664407552

Offset: 1

Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 20 2001

nonn

Also (apparently) number of n X n matrices over GF(2) having permanent = 0. - Hugo Pfoertner, Nov 14 2003

Harry J. Smith, Table of n, a(n) for n = 1..57
Index entries for sequences related to binary matrices

Cf. A002884, A002416.

for n from 1 to 20 do printf(`%d,`,2^(n^2) - product(2^n - 2^j, j=0..n-1)) od:

a(n)={2^(n^2) - prod(i=0, n-1, 2^n - 2^i)} \\ Harry J. Smith, Jul 09 2009

For n >= 1 a(n) = 2^(n^2) - A002884(n) = A002416(n) - A002884(n) = 2^(n^2) - Product_{i=0..n-1} (2^n - 2^i).

More terms from James Sellers, Apr 23 2001

A099704 Consider the family of multigraphs enriched by the species of directed graphs. Sequence gives number of those multigraphs with n labeled edges.

Original entry on oeis.org

1, 2, 24, 776, 79840, 35397440, 69619053504, 564929183555840, 18464894708236907776, 2418517115222622481308160, 1267747370909677813160722947072, 2658511777246500251150215101758228480, 22300872810108738542496498718468714032205824

Offset: 0

N. J. A. Sloane, Oct 26 2004

nonn

G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.

Andrew Howroyd, Table of n, a(n) for n = 0..50
G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004. [Cached copy, with permission]

Cf. A002416, A014500, A098620, A099705, A099706, A099707.

\\ R(n) is A002416 as e.g.f.; EnrichedGnSeq defined in A098620.
R(n)={sum(k=0, n, 2^(k^2)*x^k/k!) + O(x*x^n)}
EnrichedGnSeq(R(15)) \\ Andrew Howroyd, Jan 12 2021

E.g.f.: B(R(x)) where B(x) is the e.g.f. of A014500 and 1 + R(x) is the e.g.f. of A002416. - Andrew Howroyd, Jan 12 2021

Terms a(10) and beyond from Andrew Howroyd, Jan 12 2021

A099706 Consider the family of directed multigraphs enriched by the species of directed graphs. Sequence gives number of those multigraphs with n labeled loops and arcs.

Original entry on oeis.org

1, 4, 84, 3568, 305712, 87782720, 144600947392, 1139235294403328, 37012349010095737088, 4840037457225169875031040, 2535930555678883610642223895552, 5317274645187046706095607711946092544, 44602319906972740832371696997145322907873280

Offset: 0

N. J. A. Sloane, Oct 26 2004

nonn

G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.

Andrew Howroyd, Table of n, a(n) for n = 0..50
G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004. [Cached copy, with permission]

Cf. A002416, A014507, A098622, A099704, A099705, A099707.

\\ R(n) is A002416 as e.g.f.; EnrichedGdlSeq defined in A098622.
R(n)={sum(k=0, n, 2^(k^2)*x^k/k!) + O(x*x^n)}
EnrichedGdlSeq(R(15)) \\ Andrew Howroyd, Jan 12 2021

E.g.f.: B(R(x)) where B(x) is the e.g.f. of A014507 and 1 + R(x) is the e.g.f. of A002416. - Andrew Howroyd, Jan 12 2021

Terms a(10) and beyond from Andrew Howroyd, Jan 12 2021

A126603 Number of real {0,1}-matrices of size n X n which are not robust (cf. A125587).

Original entry on oeis.org

1, 12, 444, 60528, 31951200, 66495244096

Offset: 1

Artur Jasinski, Jan 06 2007

a(n) = 2^(n^2) - A125587(n) = A002416(n) - A125587(n). - Klaus Brockhaus, Jan 08 2007

Cf. A125587, A002416.

a(5) and a(6) (from A125587) from Klaus Brockhaus, Jan 08 2007

A133460 3^n*2^(n^2).

Original entry on oeis.org

1, 6, 144, 13824, 5308416, 8153726976, 50096498540544, 1231171548132409344, 121029087867608368152576, 47590573814949492091483324416, 74853500292876717928978827574247424

Offset: 0

Philippe Deléham, Nov 28 2007

Hankel transform of A089022.

Table[3^n 2^n^2,{n,0,10}] (* Harvey P. Dale, Jul 28 2013 *)

a(n)=3^n*2^(n^2)=A000244(n)*A002416(n).

A186081 Number of binary relations R on {1,2,...,n} such that the transitive closure of R is the trivial relation.

Original entry on oeis.org

1, 1, 4, 144, 25696, 18082560, 47025585664, 450955726792704, 16260917603754029056, 2253010420928564535951360, 1219004114245442237742488879104, 2601909995433633381004133738019815424, 22040854392120341022554569447470527813779456

Offset: 0

Geoffrey Critzer, Feb 12 2011

For n >= 2, a(n) is the number of strongly connected binary relations on [n]. - Geoffrey Critzer, Dec 04 2023

			a(2)=4 because there are four relations on {1,2} whose transitive closure is {(1,1), (1,2), (2,1), (2,2)}. They are the three nontransitive relations,{(1,2), (2,1)}, {(1,2), (2,1), (2,2)}, {(1,1), (1,2), (2,1)} and the trivial relation itself.

Cf. A002416, A003030, A070322, A361269.

Needs["Combinatorica`"];
f[list_] := Apply[Plus, Table[MatrixPower[list,n], {n,1,Length[list]}]];
Join[{1}, Table[Length[Select[Map[Flatten, Map[f, Tuples[Strings[{0, 1}, n], n]]], FreeQ[#, 0] &]], {n, 1, 4}]]
(* Second program: *)
a[ n_] := If[ n < 1, Boole[n == 0], With[{triv = matnk[n, 2^n^2 - 1]}, Sum[ Boole[triv === transitiveClosure[ matnk[n, k]]], {k, 0, 2^n^2 - 1}]]]; matnk[n_, k_] := Partition[ IntegerDigits[ k, 2, n^2], n]; transitiveClosure[x_] := FixedPoint[ Sign@(# + Dot[#, x]) &, x, Length@x]; (* Michael Somos, Mar 08 2012 *)

From Geoffrey Critzer, Dec 04 2023: (Start)
For n >= 2, a(n) = A003030(n)*2^n = A361269(n,1).
E.g.f.: 1 + s(2*x) - x where s(x) is the e.g.f. for A003030. (End)

a(0)=1 prepended by Alois P. Heinz, Aug 31 2015
a(6) from Bert Dobbelaere, Feb 16 2019
a(7)-a(12) from Geoffrey Critzer, Dec 04 2023

cp's OEIS Frontend

A355440 Expansion of e.g.f. Sum_{k>=0} exp(4^k * x) * x^k/k!.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A361269 Triangular array read by rows. T(n,k) is the number of binary relations on [n] containing exactly k strongly connected components, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A365590 Number of n X n Boolean relation matrices such that each of the diagonal blocks of its Frobenius normal form is either a 1 block or a 0 block.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A374525 T(n,k) is the number of distinct n X n {0,1}-matrices that reach a fixed point after k alternately applied sorts by rows and columns, where T(n,k), k>=0 is an irregular triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A060704 Singular n X n matrices over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A099704 Consider the family of multigraphs enriched by the species of directed graphs. Sequence gives number of those multigraphs with n labeled edges.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A099706 Consider the family of directed multigraphs enriched by the species of directed graphs. Sequence gives number of those multigraphs with n labeled loops and arcs.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula