cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 10 results.

A003027 Number of weakly connected digraphs with n labeled nodes.

Original entry on oeis.org

1, 3, 54, 3834, 1027080, 1067308488, 4390480193904, 72022346388181584, 4721717643249254751360, 1237892809110149882059440768, 1298060596773261804821355107253504, 5444502293680983802677246555274553481984, 91343781554246596956424128384394531707099632640
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

References

  • R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

The unlabeled case is A003085.
Row sums of A062735.
Cf. A053763 (not necessarily connected), A003030 (strongly connected).

Programs

  • Maple
    b:= n-> 2^(n^2-n):
a:= proc(n) option remember; local k; `if`(n=0, 1,
      b(n)- add(k*binomial(n,k) *b(n-k)*a(k), k=1..n-1)/n)
    end:
seq(a(n), n=1..20);  # Alois P. Heinz, Oct 21 2012
  • Mathematica
    Range[0, 20]! CoefficientList[Series[D[1 + Log[Sum[2^(n^2 - n) x^n/n!, {n, 0, 20}]], x], {x, 0,20}], x]
c[n_]:=2^(n(n-1))-Sum[k Binomial[n,k]c[k] 2^((n-k)(n-k-1)),{k,1,n-1}]/n;c[0]=1;Table[c[i],{i,0,20}]  (* Geoffrey Critzer, Oct 24 2012 *)
  • PARI
    v=Vec(log(sum(n=0, default(seriesprecision), 2^(n^2-n)*x^n/n!))); for(i=1, #v, v[i]*=(i-1)!); v \\ Charles R Greathouse IV, Feb 14 2011
  • Sage
    b = lambda n: 2^(n^2-n)
@cached_function
def A003027(n):
    return b(n) - sum(k*binomial(n, k)*b(n-k)*A003027(k) for k in (1..n-1)) / n
[A003027(n) for n in (1..13)] # Peter Luschny, Jan 18 2016

Formula

a(n) = A062738(n)/2^n, since binary relations = digraphs with loops. - Ralf Stephan and Vladeta Jovovic, Mar 24 2004
E.g.f.: log(sum n>=0, 2^(n^2-n)*x^n/n!).
a(n) = A053763(n) - (1/n) * Sum_{k=1..n-1} k*C(n,k)*a(k)*A053763(n-k). - Geoffrey Critzer, Oct 24 2012

Extensions

Corrected and extended by Vladeta Jovovic, Goran Kilibarda

A057273 Triangle T(n,k) of the number of strongly connected digraphs on n labeled nodes and with k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 2, 9, 6, 1, 0, 0, 0, 0, 6, 84, 316, 492, 417, 212, 66, 12, 1, 0, 0, 0, 0, 0, 24, 720, 6440, 26875, 65280, 105566, 122580, 106825, 71700, 37540, 15344, 4835, 1140, 190, 20, 1, 0, 0, 0, 0, 0, 0, 120, 6480, 107850, 868830, 4188696, 13715940
Offset: 1

Views

Author

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

Keywords

Examples

			Triangle begins:
  [1] 1;
  [2] 0,0,1;
  [3] 0,0,0,2,9,6,1;
  [4] 0,0,0,0,6,84,316,492,417,212,66,12,1;
  ...
Number of strongly connected digraphs on 3 labeled nodes is 18 = 2+9+6+1.

References

  • Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041. See Table 2.

Links

Crossrefs

Row sums give A003030.
The unlabeled version is A057276.
Cf. A057271, A057272, A057274, A057275, A062735.
Cf. A123554, A339590, A339807.

Programs

  • PARI
    B(nn, e=2)={my(v=vector(nn)); for(n=1, nn, v[n] = e^(n*(n-1)) - sum(k=1, n-1, binomial(n,k)*e^((n-1)*(n-k))*v[k])); v}
Strong(n, e=2)={my(u=B(n, e), v=vector(n)); v[1]=1; for(n=2, #v, v[n] = u[n] + sum(j=1, n-1, binomial(n-1, j-1)*u[n-j]*v[j])); v}
row(n)={ Vecrev(Strong(n, 1+'y)[n]) }
{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 10 2022

Extensions

Terms a(46) and beyond from Andrew Howroyd, Jan 10 2022

A054733 Triangle of number of (weakly) connected unlabeled digraphs with n nodes and k arcs (n >=2, k >= 1).

Original entry on oeis.org

1, 1, 0, 3, 4, 4, 1, 1, 0, 0, 8, 22, 37, 47, 38, 27, 13, 5, 1, 1, 0, 0, 0, 27, 108, 326, 667, 1127, 1477, 1665, 1489, 1154, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 91, 582, 2432, 7694, 19646, 42148, 77305, 122953, 170315, 206982, 220768, 207301, 171008
Offset: 2

Views

Author

Vladeta Jovovic, Apr 21 2000

Keywords

Examples

			1,1;
0,3,4,4,1,1;
0,0,8,22,37,47,38,27,13,5,1,1;
the last batch giving the numbers of connected digraphs with 4 nodes and from 1 to 12 arcs.

References

  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.

Links

Crossrefs

Cf. A000238 (leading diagonal), A003085 (row sums), A053454 (column sums), A062735 (labeled).
Cf. A052283 (not necessarily connected), A283753 (another version), A057276 (strongly connected), A350789 (transpose).

Programs

  • PARI
    InvEulerMTS(p)={my(n=serprec(p,x)-1, q=log(p), vars=variables(p)); sum(i=1, n, moebius(i)*substvec(q + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i)}
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, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^(2*g) )) * prod(i=1, #v, my(c=v[i]); t(c)^(c-1))}
G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i)); s/n!}
row(n)={Vecrev(polcoef(InvEulerMTS(sum(i=0, n, G(i, y)*x^i, O(x*x^n))), n)/y)}
{ for(n=2, 6, print(row(n))) } \\ Andrew Howroyd, Jan 28 2022

A057271 Triangle T(n,k) of number of digraphs with a source and a sink on n labeled nodes and k arcs, k=0,1,..,n*(n-1).

Original entry on oeis.org

1, 0, 2, 1, 0, 0, 6, 20, 15, 6, 1, 0, 0, 0, 24, 234, 672, 908, 792, 495, 220, 66, 12, 1, 0, 0, 0, 0, 120, 2544, 16880, 55000, 111225, 161660, 183006, 167660, 125945, 77520, 38760, 15504, 4845, 1140, 190, 20, 1
Offset: 1

Views

Author

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

Keywords

Examples

			Triangle starts:
[1] 1;
[2] 0,2,1;
[3] 0,0,6,20,15,6,1;
[4] 0,0,0,24,234,672,908,792,495,220,66,12,1;
  ...
The number of digraphs with a source and a sink on 3 labeled nodes is 48 = 6+20+15+6+1.

References

  • V. Jovovic, G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996), p. 245.

Links

Crossrefs

Row sums give A049524.
The unlabeled version is A057278.
Cf. A057272, A057273, A057274, A057275, A062735, A350791.

Programs

  • PARI
    \\ Following Eqn 20 in the Robinson reference.
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))}
DigraphEgf(n,e)={sum(k=0, n, e^(k*(k-1))*x^k/k!, O(x*x^n) )}
StrongD(n,e=2)={-log(U(e, 1/G(e, DigraphEgf(n, e))))}
InitFinally(n, e=2)={my(S=StrongD(n, e)); Vec(serlaplace( S - S^2 + exp(S) * U(e, G(e, S*exp(-S))^2*G(e, DigraphEgf(n,e))) ))}
row(n)={Vecrev(InitFinally(n, 1+'y)[n]) }
{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 16 2022

A057274 Triangle T(n,k) of the number of digraphs with a source on n labeled nodes with k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 0, 2, 1, 0, 0, 9, 20, 15, 6, 1, 0, 0, 0, 64, 330, 720, 914, 792, 495, 220, 66, 12, 1, 0, 0, 0, 0, 625, 5804, 24560, 63940, 117310, 164260, 183716, 167780, 125955, 77520, 38760, 15504, 4845, 1140, 190, 20, 1
Offset: 1

Views

Author

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

Keywords

Examples

			Triangle begins:
  1;
  0, 2, 1;
  0, 0, 9, 20,  15,   6,   1;
  0, 0, 0, 64, 330, 720, 914, 792, 495, 220, 66, 12, 1;
  ...
The number of digraphs with a source on 3 labeled nodes is the sum of the terms in row 3, i.e., 0+0+9+20+15+6+1 = 51 = A003028(3).

Links

Crossrefs

Row sums give A003028.
The unlabeled version is A057277.
Cf. A057271, A057272, A057273, A057275, A062735.

Programs

  • PARI
    \\ See A057273 for Strong.
Lambda(t, nn, e=2)={my(v=vector(1+nn)); for(n=0, nn, v[1+n] = e^(n*(n+t-1)) - sum(k=0, n-1, binomial(n,k)*e^((n-1)*(n-k))*v[1+k])); v}
Initially(n, e=2)={my(s=Strong(n, e), v=vector(n)); for(k=1, n, my(u=Lambda(k, n-k, e)); for(i=k, n, v[i] += binomial(i,k)*u[1+i-k]*s[k])); v }
row(n)={ Vecrev(Initially(n, 1+'y)[n]) }
{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 11 2022

A054547 Triangular array giving number of labeled digraphs on n unisolated nodes and k=0..n*(n-1) arcs.

Original entry on oeis.org

0, 0, 2, 1, 0, 0, 12, 20, 15, 6, 1, 0, 0, 12, 140, 435, 768, 920, 792, 495, 220, 66, 12, 1, 0, 0, 0, 240, 2520, 11604, 34150, 73560, 123495, 166860, 184426, 167900, 125965, 77520, 38760, 15504, 4845, 1140, 190, 20, 1
Offset: 1

Views

Author

Vladeta Jovovic, Apr 09 2000

Keywords

Examples

			Triangle T(n,k) begins:
  [0],
  [0,2,1],
  [0,0,12,20,15,6,1],
  [0,0,12,140,435,768,920,792,495,220,66,12,1],
  ...

Links

Crossrefs

Row sums are A054545.
Column sums are A121252.
The unlabeled version is A350908.
Cf. A054548 (graphs), A062735, A123554.

Programs

  • PARI
    row(n) = {Vecrev(sum(i=0, n, (-1)^(n-i)*binomial(n,i)*(1 + 'y)^(i*(i-1))), n*(n-1)+1)}
{ for(n=1, 6, print(row(n))) } \\ Andrew Howroyd, Jan 28 2022

Formula

T(n, k) = Sum_{i=0..n} (-1)^(n-i)*binomial(n, i)*binomial(i*(i-1), k).

A057275 Triangle T(n,k) of number of unilaterally connected digraphs on n labeled nodes and with k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 0, 2, 1, 0, 0, 6, 20, 15, 6, 1, 0, 0, 0, 24, 222, 660, 908, 792, 495, 220, 66, 12, 1, 0, 0, 0, 0, 120, 2304, 15540, 52700, 109545, 161120, 182946, 167660, 125945, 77520, 38760, 15504, 4845, 1140, 190, 20, 1
Offset: 1

Views

Author

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

Keywords

Examples

			Triangle begins:
  [1],
  [0,2,1],
  [0,0,6,20,15,6,1],
  [0,0,0,0,24,222,660,908,792,495,220,66,12,1],
  ...
The number of unilaterally connected digraphs on 3 labeled nodes is 48 = 6+20+15+6+1.

Links

Crossrefs

Row sums give A003029.
The unlabeled version is A057270.
Cf. A057271, A057272, A057273, A057274, A062735.

Programs

  • PARI
    \\ See A057273 for Strong.
Unilaterally(n, e=2)={my(u=vector(n), s=Strong(n,e)); for(n=1, #u, u[n]=vector(n, k, binomial(n,k)*s[k]*if(k==n, 1, sum(j=1, n-k, e^(k*(n-k-j))*(e^(k*j)-1)*u[n-k][j])))); vector(#u, n, vecsum(u[n]))}
row(n)={Vecrev(Unilaterally(n, 1+'y)[n])}
{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 19 2022

A350732 Triangle read by rows: T(n,k) is the number of weakly connected oriented graphs on n labeled nodes with k arcs, n >= 0, k=0..n*(n-1)/2.

Original entry on oeis.org

1, 0, 2, 0, 0, 12, 8, 0, 0, 0, 128, 240, 192, 64, 0, 0, 0, 0, 2000, 7104, 13120, 15360, 11520, 5120, 1024, 0, 0, 0, 0, 0, 41472, 234240, 729600, 1578240, 2531840, 3068928, 2795520, 1863680, 860160, 245760, 32768
Offset: 1

Views

Author

Andrew Howroyd, Jan 11 2022

Keywords

Examples

			Triangle begins:
  [1] 1;
  [2] 0, 2;
  [3] 0, 0, 12,   8;
  [4] 0, 0,  0, 128,  240,  192,    64;
  [5] 0, 0,  0,   0, 2000, 7104, 13120, 15360, 11520, 5120, 1024;
  ...

Links

Crossrefs

Row sums are A054941.
The leading diagonal is A097629.
The unlabeled version is A350734.
Cf. A062735 (digraphs), A350731 (strongly connected).

Programs

  • PARI
    row(n)={Vecrev(n!*polcoef(1 + log(sum(k=0, n, (1+2*y)^(k*(k-1)/2)*x^k/k!, O(x*x^n))), n))}
{ for(n=1, 5, print(row(n))) }

A350909 Triangle read by rows: T(n,k) is the number of weakly connected acyclic digraphs on n labeled nodes with k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 0, 2, 0, 0, 12, 6, 0, 0, 0, 128, 186, 108, 24, 0, 0, 0, 0, 2000, 5640, 7840, 6540, 3330, 960, 120, 0, 0, 0, 0, 0, 41472, 189480, 456720, 730830, 832370, 690300, 416160, 178230, 51480, 9000, 720, 0, 0, 0, 0, 0, 0, 1075648, 7178640, 26035800, 65339820
Offset: 1

Views

Author

Andrew Howroyd, Jan 29 2022

Keywords

Examples

			Triangle begins:
  [1] 1;
  [2] 0, 2;
  [3] 0, 0, 12,   6;
  [4] 0, 0,  0, 128,  186,  108,   24;
  [5] 0, 0,  0,   0, 2000, 5640, 7840, 6540, 3330, 960, 120;
  ...

Links

Crossrefs

Row sums are A082402.
Leading diagonal is A097629.
The unlabeled version is A350449.
Cf. A057273, A062735, A081064.

Programs

  • PARI
    G(n)={my(v=vector(n+1)); v[1]=1; for(n=1, n, v[n+1]=sum(k=1, n, -(-1)^k*(1+y)^(k*(n-k))*v[n-k+1]/k!))/n!; Ser(v)}
row(n)={Vecrev(n!*polcoef(log(G(n)), n))}
{ for(n=1, 6, print(row(n))) }

A217563 Irregular triangular array read by rows. T(n,k) is the number of weakly connected relations on n labeled nodes with k arcs. (n>=0, 0<=k<=n^2).

Original entry on oeis.org

1, 1, 1, 0, 2, 5, 4, 1, 0, 0, 12, 56, 111, 123, 84, 36, 9, 1, 0, 0, 0, 128, 944, 3264, 7096, 10936, 12687, 11400, 8004, 4368, 1820, 560, 120, 16, 1, 0, 0, 0, 0, 2000, 21104, 109400, 373920, 950725, 1915405, 3168880, 4394760, 5169230, 5188390, 4454000
Offset: 0

Views

Author

Geoffrey Critzer, Oct 07 2012

Keywords

Comments

Row sums = A062738.

Examples

			1,
1, 1,
0, 2, 5, 4, 1,
0, 0, 12, 56, 111, 123, 84, 36, 9, 1,
0, 0, 0, 128, 944, 3264, 7096, 10936, 12687, 11400, 8004, 4368, 1820, 560, 120, 16, 1

Crossrefs

Cf. A062735.

Programs

  • Mathematica
    nn=6; s=Sum[(1+y)^(n^2) x^n/n!, {n,0,nn}]; Range[0,nn]! CoefficientList[Series[ Log[s]+1, {x,0,nn}], {x,y}] //Grid

Formula

E.g.f.: Log[Sum_{n>=0} (1+y)^(n^2) x^n/n!] + 1
Showing 1-10 of 10 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.