A053763 -id:A053763 - cp's OEIS frontend

A361455 Triangle read by rows: T(n,k) is the number of simple digraphs on labeled n nodes with k strongly connected components.

1, 0, 1, 0, 1, 3, 0, 18, 21, 25, 0, 1606, 1173, 774, 543, 0, 565080, 271790, 122595, 59830, 29281, 0, 734774776, 229224750, 70500705, 25349355, 10110735, 3781503, 0, 3523091615568, 685793359804, 138122171880, 35130437825, 11002159455, 3767987307, 1138779265

Offset: 0

Andrew Howroyd, Mar 16 2023

			Triangle begins:
  1;
  0,         1;
  0,         1,         3;
  0,        18,        21,       25;
  0,      1606,      1173,      774,      543;
  0,    565080,    271790,   122595,    59830,    29281;
  0, 734774776, 229224750, 70500705, 25349355, 10110735, 3781503;
  ...

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

Column k=1 is A003030.
Main diagonal is A003024.
Row sums are A053763.
The unlabeled version is A361582.
Cf. A189898 (weak components), A361269 (loops allowed), A361591.

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) )}
T(n)={my(e=2); [Vecrev(p) | p<-Vec(serlaplace(U(e, 1/G(e, exp(y*log(U(e, 1/G(e, DigraphEgf(n, e)))))))))]}
{ my(A=T(6)); for(i=1, #A, print(A[i])) }

T(n,k) = A361269(n,k)/2^n.

A361579 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] with exactly k source-like components, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 3, 1, 0, 51, 12, 1, 0, 3614, 447, 34, 1, 0, 991930, 53675, 2885, 85, 1, 0, 1051469032, 21514470, 741455, 16665, 201, 1, 0, 4366988803688, 30405612790, 642187105, 9816380, 90678, 462, 1, 0, 71895397383029040, 160152273169644, 2024633081100, 19625842425, 122330544, 474138, 1044, 1

Offset: 0

Geoffrey Critzer, Mar 16 2023

Here, a source-like component of a digraph D is a strongly connected component of D that corresponds to a node of in-degree 0 in the condensation of D.

			Triangle begins:
  1;
  0,      1;
  0,      3,     1;
  0,     51,    12,    1;
  0,   3614,   447,   34,  1;
  0, 991930, 53675, 2885, 85, 1;
  ...

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. A003028 (column k=1), A053763 (row sums).

nn = 6; B[n_] := n! 2^Binomial[n, 2]; 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}]];
ggfz[egfx_] := Normal[Series[egfx, {x, 0, nn}]] /.Table[x^i -> z^i/2^Binomial[i, 2], {i, 0, nn}];Table[B[n], {n, 0, nn}] CoefficientList[Series[ggfz[Exp[(u - 1) s[x]]]/ggfz[Exp[- s[x]]], {z, 0, nn}], {z u}] // Grid

A361592 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] with exactly k strongly connected components of size 1, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 0, 1, 1, 0, 3, 18, 21, 0, 25, 1699, 1080, 774, 0, 543, 587940, 267665, 103860, 59830, 0, 29281, 750744901, 225144360, 64169325, 19791000, 10110735, 0, 3781503, 3556390155318, 672637205149, 126726655860, 29445913175, 7939815030, 3767987307, 0, 1138779265

Offset: 0

Geoffrey Critzer, Mar 16 2023

			Triangle begins:
       1;
       0,      1;
       1,      0,      3;
      18,     21,      0,    25;
    1699,   1080,    774,     0, 543;
  587940, 267665, 103860, 59830,   0, 29281;
  ...

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. A086366 (column k=0), A003024 (main diagonal), A053763 (row sums), A361590 (unlabeled version).

nn = 7; B[n_] := n! 2^Binomial[n, 2]; 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}]]; ggfz[egfx_] := Normal[Series[egfx, {x, 0, nn}]] /.Table[x^i -> z^i/2^Binomial[i, 2], {i, 0, nn}];Table[Take[(Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggfz[Exp[-(s[x] - x + u x)]], {z, 0, nn}], {z,u}])[[i]], i], {i, 1, nn + 1}] // Grid

A363919 a(n) = n^excess(n), where excess(n) = A046660(n).

Original entry on oeis.org

1, 1, 1, 4, 1, 1, 1, 64, 9, 1, 1, 12, 1, 1, 1, 4096, 1, 18, 1, 20, 1, 1, 1, 576, 25, 1, 729, 28, 1, 1, 1, 1048576, 1, 1, 1, 1296, 1, 1, 1, 1600, 1, 1, 1, 44, 45, 1, 1, 110592, 49, 50, 1, 52, 1, 2916, 1, 3136, 1, 1, 1, 60, 1, 1, 63, 1073741824, 1, 1, 1, 68

Offset: 1

Peter Luschny and Michael De Vlieger, Jul 14 2023

nonn

			108 = 2^2 * 3^3 => excess(108) = 5 - 2 => a(108) = 108^3 = 1259712.

Plot2 A363923 vs A205959.
Michael De Vlieger, Plot p(k)^e(k) at (x,y) = (n,k) for n = 1..2^11, with a color function representing e(k) where black represents e(k) = 1, red e(k) = 2, through magenta. The bar at bottom represents a(n) = 1 in black, a(n) a composite prime power in gold, a(n) neither squarefree nor semiprime in blue, and a(n) such that all e(k) > 1 in purple.
Michael De Vlieger, Notes on certain sequences relating BigOmega(n), omega(n), and rad(n), 2023.

Cf. A001221, A001222, A005117, A046660, A053763, A056170, A060687, A013929, A205959, A337945, A363923.

using Nemo
exc(n::fmpz) = sum(e - 1 for (p, e) in factor(n))
A363919(n::fmpz) = n < 2 ? fmpz(1) : n^exc(n)
println([A363919(fmpz(n)) for n in 1:68])

with(NumberTheory):
A363919 := n -> n^(NumberOfPrimeFactors(n) - NumberOfPrimeFactors(n, 'distinct')):
# Alternative:
a := n -> local i: n^add(i[2] - 1, i in ifactors(n)[2]): seq(a(n), n = 1..68);

Array[#^(PrimeOmega[#] - PrimeNu[#]) &, 120]

a(n) = my(f=factor(n)[, 2]); n^(vecsum(f)-#f); \\ Michel Marcus, Jul 16 2023

from sympy import factorint
def A363919(n): return n**sum(map(lambda e:e-1,factorint(n).values())) # Chai Wah Wu, Jul 18 2023

def A363919(n):
    if n < 2: return 1
    return n^sum(p[1] - 1 for p in list(factor(n)))
print([A363919(n) for n in srange(1, 69)])

a(n) = n^(Sum_{p in Factors(n)} (mult(p) - 1)), where Factors(n) is the integer factorization of n and mult(p) the multiplicity of the prime factor p.
a(n) = A363923(n) / A205959(n).
a(n) = n^A046660(n) = n^(A001222(n) - A001221(n)).
a(n) = 1 or divisible by at least one squared prime.
a(n) = 1 <=> n is squarefree (A005117).
a(n) != 1 <=> A056170(n) != 0.
a(n) = n <=> n = A060687(n - 1) for n >= 2.
a(2^n) = 2^(n*(n - 1)) = A053763(n).
a(n) <= 2^(lb(n)*(lb(n)-1)), where lb(n) = floor(log_{2}(n)).
a(n) is even <=> n = 2*A337945(n).
a(n) > 1 is odd <=> n = A053850(n).
n is prime => a(n) = 1. ('prime' means term of A000040).
n is prime product => a(n) = 1. ('prime product' means term of A144338).
n is proper prime power => a(n) is proper prime power. ('proper prime power' means term of A246547).
Moebius(a(n)) = [a(n) = 1], where [ ] denotes the Iverson bracket.

A054593 Number of disconnected labeled digraphs with n nodes.

Original entry on oeis.org

0, 1, 10, 262, 21496, 6433336, 7566317200, 35247649746352, 648839620390462336, 47230175230392839683456, 13617860445102311268975051520, 15577054031612736747163633737901312

Offset: 1

Vladeta Jovovic, Apr 15 2000

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

The unlabeled case is A054590.

Cf. A003027, A053763 (not necessarily connected), A054592.

a(n) = 2^(n*(n-1)) - A003027(n).

A087615 Number of labeled cyclic preferences/voting outcomes, indifference and undecidedness/incompleteness permitted (Social Choice Theory).

Original entry on oeis.org

0, 0, 2, 488, 282912, 496045008

Offset: 1

Detlef Pauly (dettodet(AT)yahoo.de), Sep 12 2003

Jobst Heitzig, Social Choice Under Incomplete, Cyclic Preferences, arXiv:math/0201285 [math.CO], 2002.

Cf. A087616 for the unlabeled analog, A003024, A087613, A053763.

a(n) = A053763(n) - A087613(n).

A110147 10^((n^2-n)/2).

Original entry on oeis.org

1, 1, 10, 1000, 1000000, 10000000000, 1000000000000000, 1000000000000000000000, 10000000000000000000000000000, 1000000000000000000000000000000000000

Offset: 0

Philippe Deléham, Sep 04 2005

Sequence given by the Hankel transform (see A001906 for definition) of A082148 = {1, 1, 11, 131, 1661, 22101, 305151, 4335711, ...}; example: det([1, 1, 11, 131; 1, 11, 131, 1661; 11, 131, 1661, 22101; 131, 1661, 22101, 305151]) = 10^6 = 1000000.

Also the Hankel transform of A379103. - Nathaniel Johnston, Dec 16 2024

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

a(n)=10^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(10i, j).

a(n)=10a(n-1)^2/a(n-2), a(0)=a(1)=1. - Michael Somos, Sep 12 2005

A138240 Expansion of (1/4)(1-sqrt(1-12x)/sqrt(1-4x)).

Original entry on oeis.org

0, 1, 6, 40, 296, 2400, 20928, 192768, 1848960, 18277888, 184890368, 1904259072, 19898765312, 210424545280, 2247494172672, 24209586782208, 262696649785344, 2868744309571584, 31504024885002240, 347697247933169664

Offset: 0

Paul Barry, Mar 07 2008

Hankel transform of a(n) is -4^comb(n,2)*A099156(n)=-4^comb(n,2)*[x^n](x/(1-8x+4x^2)).
Hankel transform of a(n+1) is 4^comb(n+1,2)=A053763(n+1).
Hankel transform of a(n+2) is 4^comb(n+1,2)*A102591(n+1)=4^comb(n+1,2)*[x^n](6-4x)/(1-8x+4x^2).

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

Cf. A104498.

CoefficientList[Series[1/4*(1-Sqrt[1-12*x]/Sqrt[1-4*x]), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 20 2012 *)

Recurrence: n*a(n) = 4*(4*n-5)*a(n-1) - 48*(n-2)*a(n-2) . - Vaclav Kotesovec, Oct 20 2012

a(n) ~ 2^(2*n-7/2)*3^(n+1/2)/(sqrt(Pi)*n^(3/2)) . - Vaclav Kotesovec, Oct 20 2012

A197927 The number of isolated nodes in all labeled directed graphs (with self loops allowed) on n nodes.

Original entry on oeis.org

0, 1, 4, 48, 2048, 327680, 201326592, 481036337152, 4503599627370496, 166020696663385964544, 24178516392292583494123520, 13944156602510523416463735259136, 31901471898837980949691369446728269824, 289909687580898100839964337544428699577745408

Offset: 0

Geoffrey Critzer, Oct 19 2011

nonn

Here, isolated means indegree = outdegree = 0.

a(n) is also the number of directed graphs on [n] (no self loops allowed, A053763) with a distinguished vertex of indegree 0. - Geoffrey Critzer, Apr 01 2023

Cf. A011266, A053763, A002416.

a = Sum[2^(n^2)x^n/n!, {n,0,20}]; Range[0,12]! CoefficientList[Series[x a, {x,0,12}], x]

E.g.f.: x*A(x) where A(x) = Sum_{n>=0} 2^(n^2)*x^n/n!.
a(n) = n * 2^((n-1)^2) = n*A002416(n-1).
Sum_{n>=0} a(n)*z^n/B(n) = z*Sum_{n>=0} A053763(n)*z^n/B(n) where B(n) = n!*2^binomial(n,2). - Geoffrey Critzer, Apr 01 2023

A217652 Number of isolated nodes over all labeled directed graphs on n nodes.

Original entry on oeis.org

0, 1, 2, 12, 256, 20480, 6291456, 7516192768, 35184372088832, 648518346341351424, 47223664828696452136960, 13617340432139183023890366464, 15576890575604482885591488987660288, 70778732319555200400381918345807787982848

Offset: 0

Geoffrey Critzer, Oct 09 2012

nonn

a(n) = Sum_{k=1..n} A217580(n,k) * k.

a(n) is also the number of labeled directed graphs on n nodes with an "Emperor". - Rémy-Robert Joseph, Nov 12 2012

Alois P. Heinz, Table of n, a(n) for n = 0..40

See also A123903 (case of tournaments) and A219116 (case of semicomplete digraphs) Rémy-Robert Joseph, Nov 12 2012

a:= n-> 2^(n^2-3*n+2)*n:
seq (a(n), n=0..15);  # Alois P. Heinz, Oct 09 2012

nn=15; s=Sum[2^(n^2-n)x^n/n!,{n,0,nn}]; Range[0,nn]! CoefficientList[Series[x s, {x,0,nn}], x]

A217652(n):=2^(n^2-3*n+2)*n$ makelist(A217652(n),n,0,10); /* Martin Ettl, Nov 13 2012 */

E.g.f.: x * A(x) where A(x) is the e.g.f. for A053763.

a(n) = 2^(n^2-3*n+2)*n. - Alois P. Heinz, Oct 09 2012

cp's OEIS Frontend

A361455 Triangle read by rows: T(n,k) is the number of simple digraphs on labeled n nodes with k strongly connected components.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A361579 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] with exactly k source-like components, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A361592 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] with exactly k strongly connected components of size 1, n>=0, 0<=k<=n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A363919 a(n) = n^excess(n), where excess(n) = A046660(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Julia

Maple

Mathematica

PARI

Python

SageMath

Formula

A054593 Number of disconnected labeled digraphs with n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

A087615 Number of labeled cyclic preferences/voting outcomes, indifference and undecidedness/incompleteness permitted (Social Choice Theory).

Views

Author

Keywords

Links

Crossrefs

Formula

A110147 10^((n^2-n)/2).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

A138240 Expansion of (1/4)(1-sqrt(1-12x)/sqrt(1-4x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A197927 The number of isolated nodes in all labeled directed graphs (with self loops allowed) on n nodes.

Views