|
| |
|
|
A006351
|
|
Number of series-parallel networks with n labeled edges. Also called yoke-chains by Cayley and MacMahon.
(Formerly M1885)
|
|
23
|
|
|
|
1, 2, 8, 52, 472, 5504, 78416, 1320064, 25637824, 564275648, 13879795712, 377332365568, 11234698041088, 363581406419456, 12707452084972544, 477027941930515456, 19142041172838025216, 817675811320888020992, 37044610820729973813248, 1774189422608238694776832
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
For a simple relationship to series-reduced rooted trees, partitions of n, and phylogenetic trees among other combinatoric constructs, see comments in A000311. - Tom Copeland, Jan 06 2021
|
|
|
REFERENCES
|
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.
P. A. MacMahon, Yoke-trains and multipartite compositions in connexion with the analytical forms called "trees", Proc. London Math. Soc. 22 (1891), 330-346; reprinted in Coll. Papers I, pp. 600-616. Page 333 gives A000084 = 2*A000669.
P. A. MacMahon, The combination of resistances, The Electrician, 28 (1892), 601-602; reprinted in Coll. Papers I, pp. 617-619.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 142.
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 Problem 5.40(a), S(x).
|
|
|
LINKS
|
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
|
|
|
FORMULA
|
E.g.f. is reversion of 2*log(1+x)-x.
Also exponential transform of A000311, define b by 1+sum b_n x^n / n! = exp ( 1 + sum a_n x^n /n!).
E.g.f.: A(x), B(x)=x*A(x) satisfies the differential equation B'(x)=(1+B(x))/(1-B(x)). - Vladimir Kruchinin, Jan 18 2011
The generating function A(x) satisfies the autonomous differential equation A'(x) = (1+A)/(1-A) with A(0) = 0. Hence the inverse function A^-1(x) = int {t = 0..x} (1-t)/(1+t) = 2*log(1+x)-x, which yields A(x) = -1-2*W(-1/2*exp((x-1)/2)), where W is the Lambert W function.
The expansion of A(x) can be found by inverting the above integral using the method of [Dominici, Theorem 4.1] to arrive at the result a(n) = D^(n-1)(1) evaluated at x = 0, where D denotes the operator g(x) -> d/dx((1+x)/(1-x)*g(x)). Compare with A032188.
Applying [Bergeron et al., Theorem 1] to the result x = int {t = 0..A(x)} 1/phi(t), where phi(t) = (1+t)/(1-t) = 1 + 2*t + 2*t^2 + 2*t^3 + ..., leads to the following combinatorial interpretation for the sequence: a(n) gives the number of plane increasing trees on n vertices where each vertex of outdegree k >=1 can be in one of 2 colors. An example is given below. (End)
A134991 gives (b.+c.)^n = 0^n , for (b_n)=A000311(n+1) and (c_0)=1, (c_1)=-1, and (c_n)=-2* A000311(n) = -A006351(n) otherwise. E.g., umbrally, (b.+c.)^2 = b_2*c_0 + 2 b_1*c_1 + b_0*c_2 =0. - Tom Copeland, Oct 19 2011
G.f.: 1/S(0) where S(k) = 1 - x*(k+1) - x*(k+1)/S(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 18 2011
a(n) = ((n-1)!*sum(k=1..n-1, C(n+k-1,n-1)*sum(j=1..k, (-1)^(j)*C(k,j)* sum(l=0..j, (C(j,l)*(j-l)!*2^(j-l)*(-1)^l*stirling1(n-l+j-1,j-l))/ (n-l+j-1)!)))), n>1, a(1)=1. - Vladimir Kruchinin, Jan 24 2012
G.f.: -1 + 2/Q(0), where Q(k)= 1 - k*x - x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013
a(n) ~ sqrt(2)*n^(n-1)/((2*log(2)-1)^(n-1/2)*exp(n)). - Vaclav Kotesovec, Jul 17 2013
G.f.: Q(0)/(1-x), where Q(k) = 1 - x*(k+1)/( x*(k+1) - (1 -x*(k+1))*(1 -x*(k+2))/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 10 2013
a(1) = 1; a(n) = a(n-1) + Sum_{k=1..n-1} binomial(n-1,k) * a(k) * a(n-k). - Ilya Gutkovskiy, Aug 28 2020
|
|
|
EXAMPLE
|
D^3(1) = (12*x^2+56*x+52)/(x-1)^6. Evaluated at x = 0 this gives a(4) = 52.
a(3) = 8: The 8 possible increasing plane trees on 3 vertices with vertices of outdegree k >= 1 coming in 2 colors, B or W, are
.......................................................
.1B..1B..1W..1W.....1B.......1W........1B........1W....
.|...|...|...|...../.\....../..\....../..\....../..\...
.2B..2W..2B..2W...2...3....2....3....3....2....3....2..
.|...|...|...|.........................................
.3...3...3...3.........................................
G.f. = x + 2*x^2 + 8*x^3 + 52*x^4 + 472*x^5 + 5504*x^6 + 78416*x^7 + ...
|
|
|
MAPLE
|
read transforms; t1 := 2*ln(1+x)-x; t2 := series(t1, x, 10); t3 := seriestoseries(t2, 'revogf'); t4 := SERIESTOLISTMULT(%);
# N denotes all series-parallel networks, S = series networks, P = parallel networks;
spec := [ N, N=Union(Z, S, P), S=Set(Union(Z, P), card>=2), P=Set(Union(Z, S), card>=2)}, labeled ]: A006351 := n->combstruct[count](spec, size=n);
A006351 := n -> add(combinat[eulerian2](n-1, k)*2^(n-k-1), k=0..n-1):
|
|
|
MATHEMATICA
|
max = 18; f[x_] := 2*Log[1+x]-x; Rest[ CoefficientList[ InverseSeries[ Series[ f[x], {x, 0, max}], x], x]]*Range[max]! (* Jean-François Alcover, Nov 25 2011 *)
|
|
|
PROG
|
(Maxima) a(n):=if n=1 then 1 else ((n-1)!*sum(binomial(n+k-1, n-1)* sum((-1)^(j)*binomial(k, j)*sum((binomial(j, l)*(j-l)!*2^(j-l)*(-1)^l* stirling1(n-l+j-1, j-l))/(n-l+j-1)!, l, 0, j), j, 1, k), k, 1, n-1)); /* Vladimir Kruchinin, Jan 24 2012 */
(Sage) # uses[eulerian2 from A201637]
def A006351(n): return add(A201637(n-1, k)*2^(n-k-1) for k in (0..n-1))
(PARI) x='x+O('x^66); Vec(serlaplace(serreverse( 2*log(1+x) - 1*x ))) \\ Joerg Arndt, May 01 2013
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
