Displaying 1-10 of 12 results found.
1, 1, 3, 19, 225, 4841, 192355, 14537643, 2135997537, 616565334097, 351243585487331, 395958973398105283, 885030941975862363649, 3928075680727698371316537, 34658158001445631936261356547, 608435501761943981290097259909211
COMMENTS
a(n) is the number of ways to designate a node in each connected component over all simple labeled graphs on n nodes.
FORMULA
E.g.f.: exp(A(x)) where A(x) is the e.g.f. for A053549.
MAPLE
g:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*g(k), k=1..n-1)/n)
end:
a:= proc(n) option remember; `if`(n=0, 1, add(
binomial(n-1, j-1) *j*g(j) *a(n-j), j=1..n))
end:
MATHEMATICA
nn=20; a=Sum[2^Binomial[n, 2]x^n/n!, {n, 0, nn}]; Range[0, nn]! CoefficientList[Series[Exp[x D[Log[a], x]], {x, 0, nn}], x]
PROG
(PARI) seq(n)={Vec(serlaplace(exp(x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))))))} \\ Andrew Howroyd, Jun 18 2018
Reversion of [1,2,12,152,3640,...] ( A053549).
+20
0
1, 2, -4, 72, -2168, 114864, -10671216, 1787642272, -557621854080, 332091938264960, -383877081387120640, 870132605833456937472, -3891989736269204588784384, 34485850497928703119235323904, -606809291874393995479640098992128
REVEGF transform of [1,2,12,152,3640,...] ( A053549).
+20
0
1, 4, 12, 128, -2360, 225504, -31479056, 7663698176, -3268091071872, 2502155367185920, -3525130171601665792, 9336272433375180957696, -47283253230423958235278336, 463782058088334028985937178624, -8890882429150197015851583349985280
E.g.f. is obtained by reversion of e.g.f. for A053549.
+20
0
1, -2, 0, -32, -1000, -61104, -6622448, -1274984320, -444075170688, -286507347953920, -349824570713902592, -821921957328576534528, -3760909487461975276739584, -33794780371666462710538704896, -599695123654141294961479035617280
REFERENCES
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.20, G^<-1>(x).
MAPLE
seriestoseries(G, 'revogf'); # where G is e.g.f. for A053549; i.e. use ordinary reversion on the e.g.f. and treat answer as another e.g.f.
Number of connected labeled graphs with n nodes.
(Formerly M3671 N1496)
+10
154
1, 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, 34496488594816, 35641657548953344, 73354596206766622208, 301272202649664088951808, 2471648811030443735290891264, 40527680937730480234609755344896, 1328578958335783201008338986845427712
COMMENTS
"Based on experimental data obtained using the software LattE [14] and the Online Encyclopedia of Integer Sequences [19], we make the following conjecture: Conjecture 11. For j >= 2, Vol(C_j ) is equal to the number of labeled connected graphs on j - 1 vertices." [Beck et al., 2011]
For n > 1, a(n) is log-convex. Furthermore, a(n+1)*a(n-1) ~ 2*a(n)*a(n). - Ran Pan, Oct 28 2015 a(n) is also the number of tournaments on {1,...,n} for which 1 is reachable from every vertex. - Don Knuth, Aug 06 2020
REFERENCES
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 398-402.
D. G. Cantor, personal communication.
Cowan, D. D.; Mullin, R. C.; Stanton, R. G. Counting algorithms for connected labelled graphs. Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pp. 225-236. Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975. MR0414417 (54 #2519).
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 518.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 7.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.1.
H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 78.
LINKS
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018. M. Konvalinka and I. Pak, Cayley compositions, partitions, polytopes, and geometric bijections, Journal of Combinatorial Theory, Series A, Volume 123, Issue 1, April 2014, Pages 86-91.
FORMULA
n * 2^binomial(n, 2) = Sum_{k=1..n} binomial(n, k) * k * a(k) * 2^binomial(n-k, 2).
E.g.f.: 1 + log(Sum_{n>=0} 2^binomial(n, 2) * x^n / n!). - Michael Somos, Jun 12 2000
EXAMPLE
E.g.f.: 1 + x + x^2/2! + 4*x^3/3! + 38*x^4/4! + 728*x^5/5! + 26704*x^6/6! + 1866256*x^7/7! + 251548592*x^8/8! + ...
MAPLE
t1 := 1+log( add(2^binomial(n, 2)*x^n/n!, n=0..30)): t2 := series(t1, x, 30): A001187 := n->n!*coeff(t2, x, n); # second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*a(k), k=1..n-1)/n)
end:
# Alternative:
a := proc(n) option remember;
2^((n-1)*n/2) - add(binomial(n-1, k)*2^((k-n+1)*(k-n+2)/2)*a(k+1), k=0..n-2)
end:
MATHEMATICA
m:=20; g = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, m}]; Range[0, m]! CoefficientList[Series[Log[g] +1, {x, 0, m}], x] (* Geoffrey Critzer, Nov 12 2011 *) a[n_]:= a[n]= If[n==0, 1, 2^(n*(n-1)/2) - Sum[k*Binomial[n, k]* 2^((n-k)*(n-k-1)/2)*a[k], {k, 1, n-1}]/n]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Apr 09 2014, after Alois P. Heinz *) a[ n_]:= If[n<0, 0, n! SeriesCoefficient[1 +Log[ Sum[2^(k(k-1)/2) x^k/k!, {k, 0, n}]], {x, 0, n}]]; (* Michael Somos, Jul 11 2019 *)
PROG
(PARI) {a(n) = if(n<0, 0, n! * polcoeff( 1 + log( sum( k=0, n, 2^binomial(k, 2) * x^k / k!, x * O(x^n))), n))}; /* Michael Somos, Jun 12 2000 */ (Sage)
@cached_function
if n == 0: return 1
return 2^(n*(n-1)/2)- sum(k*binomial(n, k)*2^((n-k)*(n-k-1)/2)* A001187(k) for k in (1..n-1))/n (Magma)
m:=30;
f:= func< x | 1+Log( (&+[2^Binomial(n, 2)*x^n/Factorial(n): n in [0..m+3]]) ) >;
R<x>:=PowerSeriesRing(Rationals(), m);
CROSSREFS
Logarithmic transform of A006125 (labeled graphs).
Number of 2-edge-connected labeled graphs on n nodes.
+10
38
0, 0, 0, 1, 10, 253, 11968, 1047613, 169181040, 51017714393, 29180467201536, 32121680070545657, 68867078000231169536, 290155435185687263172693, 2417761175748567327193407488, 40013922635723692336670167608181, 1318910073755307133701940625759574016
COMMENTS
Essentially the same sequence arises as the number of connected bridgeless labeled graphs (graphs that are k-edge connected for k >= 2, starting elements of this sequence are 1, 1, 0, 1, 10, 253, 11968, ...).
The spanning edge-connectivity of a graph is the minimum number of edges that must be removed (without removing incident vertices) to obtain a graph that is disconnected or covers fewer vertices. This sequence counts graphs with spanning edge-connectivity >= 2, which, for n > 1, are connected graphs with no bridges. - Gus Wiseman, Sep 20 2019
MATHEMATICA
seq[n_] := Module[{v, p, q, c}, v[_] = 0; p = x*D[#, x]& @ Log[ Sum[ 2^Binomial[k, 2]*x^k/k!, {k, 0, n}] + O[x]^(n+1)]; q = x*E^p; p -= q; For[k = 3, k <= n, k++, c = Coefficient[p, x, k]; v[k] = c*(k-1)!; p -= c*q^k]; Join[{0}, Array[v, n]]];
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]], {2}], Length[Intersection@@s[[#]]]>0&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
spanEdgeConn[vts_, eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds], Union@@#!=vts||Length[csm[#]]!=1&];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], spanEdgeConn[Range[n], #]>=2&]], {n, 0, 5}] (* Gus Wiseman, Sep 20 2019 *)
PROG
seq(n)={my(v=vector(n));
my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))));
my(q=x*exp(p)); p-=q;
for(k=3, n, my(c=polcoeff(p, k)); v[k]=c*(k-1)!; p-=c*q^k);
(PARI) seq(n)={my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n)))); Vec(serlaplace(log(x/serreverse(x*exp(p)))/x-1), -(n+1))} \\ Andrew Howroyd, Dec 28 2020
CROSSREFS
Row sums of A327069 if the first two columns are removed. BII-numbers of set-systems with spanning edge-connectivity >= 2 are A327109. Graphs with spanning edge-connectivity 2 are A327146. Graphs with non-spanning edge-connectivity >= 2 are A327200. 2-vertex-connected graphs are A013922. Graphs without endpoints are A059167. Graphs with spanning edge-connectivity 1 are A327071.
AUTHOR
Yifei Chen (yifei(AT)mit.edu), Jul 17 2004
The exponential transform of sigma(n).
+10
12
1, 1, 4, 14, 69, 367, 2284, 15430, 115146, 924555, 7991892, 73547322, 718621516, 7410375897, 80405501540, 914492881330, 10873902417225, 134808633318271, 1738734267608613, 23282225008741565, 323082222240744379, 4638440974576329923, 68794595993688306903
COMMENTS
The exponential transform [EXP] transforms an input sequence b(n) into the output sequence a(n). The EXP transform is the inverse of the logarithmic transform [LOG], see the Weisstein link and the Sloane and Plouffe reference. This relation goes by the name of Riddell's formula. For information about the logarithmic transform see A274805. The EXP transform is related to the multinomial transform, see A274760 and the second formula. The definition of the EXP transform, see the second formula, shows that n >= 1. To preserve the identity LOG[EXP[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 exponential transform, otherwise information about b(0) will be lost in transformation.
In the a(n) formulas, see the examples, the multinomial coefficients A178867 appear. We observe that a(0) = 1 and provides no information about any value of b(n), this notwithstanding it is customary to start the a(n) sequence with a(0) = 1.
The Maple programs can be used to generate the exponential transform of a sequence. The first program uses a formula found by Alois P. Heinz, see A007446 and the first formula. The second program uses the definition of the exponential transform, see the Weisstein link and the second formula. The third program uses information about the inverse of the exponential transform, see A274805.
REFERENCES
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.
LINKS
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]
FORMULA
a(n) = Sum_{j=1..n} (binomial(n-1,j-1) * b(j) * a(n-j)), n >= 1 and a(0) = 1, with b(n) = A000203(n) = sigma(n). E.g.f. exp(Sum_{n >= 1}(b(n)*x^n/n!) with b(n) = sigma(n) = A000203(n).
EXAMPLE
a(0) = 1
a(1) = x(1)
a(2) = x(1)^2 + x(2)
a(3) = x(1)^3 + 3*x(1)*x(2) + x(3)
a(4) = x(1)^4 + 6*x(1)^2*x(2) + 4*x(1)*x(3) + 3*x(2)^2 + x(4)
a(5) = x(1)^5 + 10*x(1)^3*x(2) + 10*x(1)^2*x(3) + 15*x(1)*x(2)^2 + 5*x(1)*x(4) + 10*x(2)*x(3) + x(5)
MAPLE
nmax:=21: with(numtheory): b := proc(n): sigma(n) end: a:= proc(n) option remember; if n=0 then 1 else add(binomial(n-1, j-1) * b(j) *a(n-j), j=1..n) fi: end: seq(a(n), n=0..nmax); # End first EXP program.
nmax:= 21: with(numtheory): b := proc(n): sigma(n) end: t1 := exp(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=0..nmax); # End second EXP program.
nmax:=21: with(numtheory): b := proc(n): sigma(n) end: f := series(log(1+add(q(n)*x^n/n!, n=1..nmax+1)), x, nmax+1): d := proc(n): n!*coeff(f, x, n) end: a(0):=1: q(0):=1: a(1):=b(1): q(1):=b(1): for n from 2 to nmax+1 do q(n) := solve(d(n)-b(n), q(n)): a(n):=q(n): od: seq(a(n), n=0..nmax); # End third EXP program.
MATHEMATICA
a[0] = 1; a[n_] := a[n] = Sum[Binomial[n-1, j-1]*DivisorSigma[1, j]*a[n-j], {j, 1, n}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 22 2017 *) nmax = 20; CoefficientList[Series[Exp[Sum[DivisorSigma[1, k]*x^k/k!, {k, 1, nmax}]], {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jun 08 2021 *)
CROSSREFS
Cf. A177208, A177209, A006351, A197505, A144180, A256180, A033462, A198046, A134954, A145460, A188489, A005432, A029725, A124213, A002801.
Triangle read by rows where T(n,k) is the number of labeled simple connected graphs with n vertices and exactly k bridges.
+10
7
1, 1, 0, 0, 1, 0, 1, 0, 3, 0, 10, 12, 0, 16, 0, 253, 200, 150, 0, 125, 0, 11968, 7680, 3600, 2160, 0, 1296, 0, 1047613, 506856, 190365, 68600, 36015, 0, 16807, 0, 169181040, 58934848, 16353792, 4695040, 1433600, 688128, 0, 262144, 0, 51017714393, 12205506096, 2397804444, 500828832, 121706550, 33067440, 14880348, 0, 4782969, 0
COMMENTS
A bridge is an edge that, if removed without removing any incident vertices, disconnects the graph. Connected graphs with no bridges are counted by A095983 (2-edge-connected graphs). Warning: In order to be consistent with A001187, we have treated the n = 0 and n = 1 cases in ways that are not consistent with A095983.
EXAMPLE
Triangle begins:
1
1 0
0 1 0
1 0 3 0
10 12 0 16 0
253 200 150 0 125 0
MATHEMATICA
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[If[n<=1&&k==0, 1, Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Length[csm[#]]==1&&Count[Table[Length[Union@@Delete[#, i]]<n||Length[csm[Delete[#, i]]]>1, {i, Length[#]}], True]==k&]]], {n, 0, 4}, {k, 0, n}]
PROG
T(n)={my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))), v=Vec(1+serreverse(serreverse(log(x/serreverse(x*exp(p))))/exp(x*y+O(x^n))))); vector(#v, k, max(0, k-2)!*Vecrev(v[k], k)) }
{ my(A=T(8)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Dec 28 2020
CROSSREFS
Row sums without the first column are A327071.
E.g.f. satisfies: L(x) = x*Sum_{n>=0} (1/n!)*Product_{k=0..n-1} L(2^k*x).
+10
4
1, 2, 12, 152, 3640, 160224, 13063792, 2012388736, 596666619648, 344964885948160, 392058233038486784, 880255154481199466496, 3916538634445633156373504, 34603083354426212294072477696
COMMENTS
An analog of the LambertW function.
FORMULA
a(n) = n* A001187(n), where A001187(n) is the number of connected labeled graphs with n nodes. Let B(x) = Sum_{n>=0} 2^(n(n-1)/2)*x^n/n! then
. L(x) = x*d/dx log(B(x)) = x*B'(x)/B(x) and
. 1/B(x) = Sum_{n>=0} (-1)^n/n!*Product_{k=0..n-1} L(2^k*x).
EXAMPLE
E.g.f.: L(x) = x + 2*x^2/2! + 12*x^3/3! + 152*x^4/4! + 3640*x^5/5! +...
which is invariant under the series:
L(x)/x = 1 + L(x) + L(x)L(2x)/2! + L(x)L(2x)L(4x)/3! + L(x)L(2x)L(4x)L(8x)/4! +...
Let B(x) = 1 + x + 2*x^2/2! + 8*x^3/3! + 64*x^4/4! + 1024*x^5/5! +...
so that log(B(x)) = x + x^2/2! + 4*x^3/3! + 38*x^4/4! + 728*x^5/5! +...+ A001187(n)*x^n/n! +... then L(x) = x*d/dx log(B(x)) which also satisfies:
1/B(x) = 1 - L(x) + L(x)L(2x)/2! - L(x)L(2x)L(4x)/3! + L(x)L(2x)L(4x)L(8x)/4! -+...
PROG
(PARI) {a(n, r=1)=local(A=x+x^2); for(i=1, n, A=x*sum(m=0, n, r^m/m!*prod(k=0, m-1, subst(A, x, 2^k*x+x*O(x^n))))); n!*polcoeff(A, n)}
Triangular array read by rows: T(n,k) is the number of rooted labeled simple graphs on {1,2,...,n} such that the root is in a component of size k; n>=1, 1<=k<=n.
+10
1
1, 2, 2, 6, 6, 12, 32, 24, 48, 152, 320, 160, 240, 760, 3640, 6144, 1920, 1920, 4560, 21840, 160224, 229376, 43008, 26880, 42560, 152880, 1121568, 13063792, 16777216, 1835008, 688128, 680960, 1630720, 8972544, 104510336, 2012388736
REFERENCES
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973, page 7.
EXAMPLE
1;
2, 2;
6, 6, 12;
32, 24, 48, 152;
320, 160, 240, 760, 3640;
MAPLE
b:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*b(k), k=1..n-1)/n)
end:
T:= (n, k)-> binomial(n, k)*k*b(k)*2^((n-k)*(n-k-1)/2):
MATHEMATICA
nn = 10; g = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn}]; a =
Drop[Range[0, nn]! CoefficientList[Series[Log[g], {x, 0, nn}], x],
1]; Table[
Table[Binomial[n, k] k a[[k]] 2^Binomial[n - k, 2], {k, 1, n}], {n,
1, 7}] // Grid
Search completed in 0.021 seconds
| 
