A062738 -id:A062738 - cp's OEIS frontend

A003027 Number of weakly connected digraphs with n labeled nodes.

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

Offset: 1

N. J. A. Sloane

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).

T. D. Noe, Table of n, a(n) for n=1..30
A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.

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

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

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 *)

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

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

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

Corrected and extended by Vladeta Jovovic, Goran Kilibarda

A274805 The logarithmic transform of sigma(n).

Original entry on oeis.org

1, 2, -3, -6, 45, 11, -1372, 4298, 59244, -573463, -2432023, 75984243, -136498141, -10881169822, 100704750342, 1514280063802, -36086469752977, -102642110690866, 11883894518252419, -77863424962770751, -3705485804176583500, 71306510264347489177

Offset: 1

Johannes W. Meijer, Jul 27 2016

sign

The logarithmic transform [LOG] transforms an input sequence b(n) into the output sequence a(n). The LOG transform is the inverse of the exponential transform [EXP], see the Weisstein link and the Sloane and Plouffe reference. This relation goes by the name of Riddell’s formula. For information about the EXP transform see A274804. The logarithmic transform is related to the inverse multinomial transform, see A274844 and the first formula.
The definition of the LOG transform, see the second formula, shows that n >= 1. To preserve the identity EXP[LOG[b(n)]] = b(n) for n >= 0 for a sequence b(n) with offset 0 the shifted sequence b(n-1) with offset 1 has to be used as input for the LOG transform, otherwise information about b(0) will be lost in transformation.
In the a(n) formulas, see the examples, the cumulant expansion numbers A127671 appear.
We observe that the logarithmic transform leaves the value of a(0) undefined.
The Maple programs can be used to generate the logarithmic transform of a sequence. The first program uses a formula found by Alois P. Heinz, see A001187 and the first formula. The second program uses the definition of the logarithmic transform, see the Weisstein link and the second formula. The third program uses information about the inverse of the logarithmic transform, see A274804.

			Some a(n) formulas, see A127671:
a(0) = undefined
a(1) = 1*x(1)
a(2) = 1*x(2) - x(1)^2
a(3) = 1*x(3) - 3*x(1)*x(2) + 2*x(1)^3
a(4) = 1*x(4) - 4*x(1)*x(3) - 3*x(2)^2 + 12*x(1)^2*x(2) - 6*x(1)^4
a(5) = 1*x(5) - 5*x(1)*x(4) - 10*x(2)*x(3) + 20*x(1)^2*x(3) + 30*x(1)*x(2)^2 - 60*x(1)^3*x(2) + 24*x(1)^5

Frank Harary and Edgar M. Palmer, Graphical Enumeration, 1973.
Robert James Riddell, Contributions to the theory of condensation, Dissertation, University of Michigan, Ann Arbor, 1951.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 1995, pp. 18-23.

Alois P. Heinz, Table of n, a(n) for n = 1..451
M. Bernstein and N. J. A. Sloane, Some Canonical Sequences of Integers, Linear Algebra and its Applications, Vol. 226-228 (1995), pp. 57-72. Erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
N. J. A. Sloane, Transforms.
Eric W. Weisstein MathWorld, Logarithmic Transform.

Some LOG transform pairs are, n >= 1: A006125(n-1) and A033678(n); A006125(n) and A001187(n); A006125(n+1) and A062740(n); A000045(n) and A112005(n); A000045(n+1) and A007553(n); A000040(n) and A007447(n); A000051(n) and (-1)*A263968(n-1); A002416(n) and A062738(n); A000290(n) and A033464(n-1); A029725(n-1) and A116652(n-1); A052332(n) and A002031(n+1); A027641(n)/A027642(n) and (-1)*A060054(n+1)/(A075180(n-1).
Cf. A274804, A274844, A127671, A000203.
Cf. A112005, A007553, A062740, A007447, A062738, A033464, A116652, A002031, A003704, A003707, A155585, A000142, A226968.

nmax:=22: with(numtheory): b := proc(n): sigma(n) end: a:= proc(n) option remember; b(n) - add(k*binomial(n, k)*b(n-k)*a(k), k=1..n-1)/n: end: seq(a(n), n=1..nmax); # End first LOG program.
nmax:=22: with(numtheory): b := proc(n): sigma(n) end: t1 := log(1 + add(b(n)*x^n/n!, n=1..nmax+1)): t2 := series(t1, x, nmax+1): a := proc(n): n!*coeff(t2, x, n) end: seq(a(n), n=1..nmax); # End second LOG program.
nmax:=22: with(numtheory): b := proc(n): sigma(n) end: f := series(exp(add(r(n)*x^n/n!, n=1..nmax+1)), x, nmax+1): d := proc(n): n!*coeff(f, x, n) end: a(1):=b(1): r(1):= b(1): for n from 2 to nmax+1 do r(n) := solve(d(n)-b(n), r(n)): a(n):=r(n): od: seq(a(n), n=1..nmax); # End third LOG program.

a[1] = 1; a[n_] := a[n] = DivisorSigma[1, n] - Sum[k*Binomial[n, k] * DivisorSigma[1, n-k]*a[k], {k, 1, n-1}]/n; Table[a[n], {n, 1, 22}] (* Jean-François Alcover, Feb 27 2017 *)

N=33; x='x+O('x^N); Vec(serlaplace(log(1+sum(n=1,N,sigma(n)*x^n/n!)))) \\ Joerg Arndt, Feb 27 2017

a(n) = b(n) - Sum_{k = 1..n-1}((k*binomial(n, k)*b(n-k)*a(k))/n), n >= 1, with b(n) = A000203(n) = sigma(n).

E.g.f. log(1+ Sum_{n >= 1}(b(n)*x^n/n!)), n >= 1, with b(n) = A000203(n) = sigma(n).

A197743 The number of connected components in all labeled directed graphs (with self loops allowed) on n nodes.

Original entry on oeis.org

0, 2, 20, 600, 70048, 34265920, 69135737856, 563921434969088, 18455775305195147264, 2418183926567027902291968, 1267698967252460350153517105152, 2658483881480146168943131337243754496, 22300809002478630462447974400280680553512960

Offset: 0

Geoffrey Critzer, Oct 17 2011

nonn

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

Cf. A062738, A186236.

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

seq(n)={my(g=log(sum(k=0, n, 2^(k^2)*x^k/k!) + O(x*x^n))); Vec(serlaplace(g*exp(g)), -(n+1))} \\ Andrew Howroyd, Nov 07 2019

E.g.f.: B(A(x)) where A(x) = log(Sum_{k=1..n} 2^(n^2)x^n/n!) and B(x)= x*exp(x).

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

Terms a(11) and beyond from Andrew Howroyd, Nov 07 2019

A127911 Number of nonisomorphic partial functional graphs with n points which are not functional graphs.

Original entry on oeis.org

0, 1, 3, 9, 26, 74, 208, 586, 1647, 4646, 13135, 37247, 105896, 301880, 862498, 2469480, 7083690, 20353886, 58571805, 168780848, 486958481, 1406524978, 4066735979, 11769294050, 34090034328, 98820719105, 286672555274

Offset: 0

Jonathan Vos Post, Feb 06 2007

Partial functional graphs (digraphs) with at least one node of outdegree = 0.

			a(0) = 0 because the null graph is trivially both partial functional and functional.
a(1) = 1 because there are two partial functional graphs on one point: the point with, or without, a loop; the point with loop is the identity function, but without a loop the naked point is the unique merely partial functional case.
a(2) = 3 because there are A126285(2) enumerates the 6 partial functional graphs on 2 points, of which 3 are functional, 6 - 3 = 3.
a(3) = A126285(3) - A001372(3) = 16 - 7 = 9.
a(4) = 45 - 19 = 26.
a(5) = 121 - 47 = 74.
a(6) = 338 - 130 = 208.
a(7) = 929 - 343 = 586.
a(8) = 2598 - 951 = 1647.
a(9) = 7261 - 2615 = 4646.
a(10) = 20453 - 7318 = 13135.

S. Skiena, "Functional Graphs." Section 4.5.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 164-165, 1990.

Eric Weisstein's World of Mathematics, Functional Graph.

Cf. A000081, A000273, A001372, A002861, A003027, A003085, A062738, A116950, A126285, A127909-A127915.

a(n) = A126285(n) - A001372(n).

Euler transform of (A002861 + A000081) - Euler transform of A002861.

A127912 Number of nonisomorphic disconnected mappings (or mapping patterns) from n points to themselves; number of disconnected endofunctions.

Original entry on oeis.org

0, 1, 3, 10, 27, 79, 218, 622, 1753, 5007, 14274, 40954, 117548, 338485, 975721, 2817871, 8146510, 23581381, 68322672, 198138512, 575058726, 1670250623, 4854444560, 14117859226, 41081418963, 119606139728

Offset: 0

Jonathan Vos Post, Feb 06 2007

Number of endofunctions on n points whose functional digraphs (with loops allowed) are nontrivially the directed sum of two or more digraphs of endofunctions.

			a(0) = 0, as the null digraph is formally neither connected nor disconnected.
a(1) = 0, as the unique endofunction on one point is the identity function on one value and is connected.
a(2) = 1, as there are 3 endofunctions on two points, two of which are "prime endofunctions" and one of which is the direct sum of two copies of the unique endofunction on one point, namely two points-with-loops, or the identity function on two values; 3 - 2 = 1.
a(3) = A001372(3) - A002861(3) = 7 - 4 = 3.
a(4) = A001372(4) - A002861(4) = 19 - 9 = 10.
a(5) = A001372(5) - A002861(5) = 47 - 20 = 27.
a(6) = 130 - 51 = 79.
a(7) = 343 - 125 = 218.
a(8) = 951 - 329 = 622.
a(9) = 2615 - 862 = 1753.
a(10) = 7318 - 2311 = 5007.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.6.
R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.399 and 41.401.

N. G. de Bruijn and D. A. Klarner, Multisets of aperiodic cycles, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 359--368. MR0666861(84i:05008).
Eric Weisstein's World of Mathematics, Functional Graph.

Cf. A000081, A000273, A001372, A002861, A003027, A003085, A062738, A116950, A126285, A127909-A127915.

a(n) = A001372(n) - A002861(n).

A191249 Triangular array T(n,k) read by rows: number of labeled relations of the n-set with exactly k connected components.

Original entry on oeis.org

2, 12, 4, 432, 72, 8, 61344, 3888, 288, 16, 32866560, 665280, 21600, 960, 32, 68307743232, 407306880, 4328640, 95040, 2880, 64, 561981464819712, 965518299648, 2948037120, 21893760, 362880, 8064, 128

Offset: 1

Geoffrey Critzer, May 28 2011

T(n,k) is the number of binary relations R on {1,2,...,n} such that the reflexive, symmetric and transitive closure of R is an equivalence relation with exactly k classes.
Row sums are A002416 = 2^(n^2).
Column 1 is A062738.
T(n,n) = 2^n is the number of binary relations that are a subset of the diagonal relation.

			2
12       4
432      72     8
61344    3888   288   16
32866560 665280 21600 960 32

a=Sum[2^(n^2) x^n/n!,{n,0,10}];
Transpose[Table[Drop[Range[0, 10]! CoefficientList[Series[Log[a]^n/n!, {x, 0, 10}],x],1], {n, 1, 10}]] // Grid

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

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

Geoffrey Critzer, Oct 07 2012

Row sums = A062738.

			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

Cf. A062735.

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

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

A226358 Number of labeled relations on {1,2,...,n} such that 1 and 2 are in the same component.

Original entry on oeis.org

0, 0, 12, 456, 63264, 33261504, 68578235904, 562670659193856, 18444482155274686464, 2417777758564741377613824, 1267640925339738611935051382784, 2658450920454274160572632643718086656, 22300734564407398196216147429929635837640704

Offset: 0

Geoffrey Critzer, Jun 04 2013

nonn

A062738(n) < a(n) < A002416 for n > 2.

			a(3) = 456 because there are 432 connected relations on [3].  Then there are 12 connected relations on [2] and for each the element 3 may be related to itself or not.
432 + 2*12 = 456.

Cf. A226349, A224510.

nn=10; g=Sum[2^n^2 x^n/n!, {n, 0, nn+2}]; Join[{0,0}, Range[0,nn]! * CoefficientList[Series[D[D[Log[g],x],x]g ,{x, 0, nn}], x]]

E.g.f. is the double integral of A''(x)*B(x) where A(x) is the e.g.f. for A062738 and B(x) is the e.g.f. for A002416.

cp's OEIS Frontend

A003027 Number of weakly connected digraphs with n labeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A274805 The logarithmic transform of sigma(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A197743 The number of connected components in all labeled directed graphs (with self loops allowed) on n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A127911 Number of nonisomorphic partial functional graphs with n points which are not functional graphs.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A127912 Number of nonisomorphic disconnected mappings (or mapping patterns) from n points to themselves; number of disconnected endofunctions.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A191249 Triangular array T(n,k) read by rows: number of labeled relations of the n-set with exactly k connected components.

Views

Author

Keywords

Comments

Examples

Programs

Mathematica

Formula

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).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A226358 Number of labeled relations on {1,2,...,n} such that 1 and 2 are in the same component.