| Displaying 1-10 of 10 results found.
page
1
Erroneous version of A108919.
(Formerly M4897 N2099)
+20
1
1, 0, 1, 1, 13, 51, 601, 4806, 39173, 775351
COMMENTS
Callan points out that this is an incorrect version of A108919. - Joerg Arndt, Jul 01 2014
REFERENCES
John Riordan, personal communication.
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).
Number of series-reduced planted trees with n nodes.
(Formerly M0768 N0293)
+10
145
0, 0, 1, 0, 1, 1, 2, 3, 6, 10, 19, 35, 67, 127, 248, 482, 952, 1885, 3765, 7546, 15221, 30802, 62620, 127702, 261335, 536278, 1103600, 2276499, 4706985, 9752585, 20247033, 42110393, 87733197, 183074638, 382599946, 800701320, 1677922740, 3520581954
COMMENTS
The initial term is 0 by convention, though a good case can be made that it should be 1 instead.
Series-reduced trees contain no node with valency 2; see A000014 for the unrooted series-reduced trees. - Joerg Arndt, Mar 03 2015 For n>=2, a(n+1) is the number of unordered rooted trees (see A000081) with n nodes where nodes cannot have out-degree 1, see example. Imposing the condition only at non-root nodes gives A198518. - Joerg Arndt, Jun 28 2014 For n>=3, a(n+1) is the number of unordered rooted trees with n nodes where all limbs are of length >= 2. Limbs are the paths from the leafs (towards the root) to the nearest branching point (with the root considered to be a branching point). - Joerg Arndt, Mar 03 2015 A rooted tree is lone-child-avoiding if no vertex has exactly one child, and topologically series-reduced if no vertex has degree 2. This sequence counts unlabeled lone-child-avoiding rooted trees with n - 1 vertices. Topologically series-reduced rooted trees are counted by A001679, which is essentially the same as A059123. - Gus Wiseman, Jan 20 2020
REFERENCES
D. G. Cantor, personal communication.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 525.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62.
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).
FORMULA
G.f.: A(x) satisfies A(x) = (x^2/(1+x))*exp( Sum_{k>=1} A(x^k)/(k*x^k) ) [Harary and E. M. Palmer, 1973, p. 62, Eq. (3.3.8)].
G.f.: A(x) = Sum_{n>=2} a(n) * x^n = x^2 / ((1 + x) * Product_{k>0} (1 - x^k)^a(k+1)). - Michael Somos, Oct 06 2003 a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.189461985660850563... and c = 0.1924225474701550354144525345664845514828912790855223729854471406053655209... - Vaclav Kotesovec, Jun 26 2014
EXAMPLE
--------------- Examples (i=internal,e=external): ---------------------------
|.n=2.|..n=4..|..n=5..|...n=6.............|....n=7..........................|
|.....|.......|.......|.............e...e.|................e.e.e......e...e.|
|.....|.e...e.|.e.e.e.|.e.e.e.e...e...i...|.e.e.e.e.e...e....i....e.e...i...|
|..e..|...i...|...i...|....i........i.....|.....i..........i..........i.....|
|..e..|...e...|...e...|....e........e.....|.....e..........e..........e.....|
-----------------------------------------------------------------------------
G.f. = x^2 + x^4 + x^5 + 2*x^6 + 3*x^7 + 6*x^8 + 10*x^9 + 19*x^10 + ...
The a(8) = 6 rooted trees with 7 nodes as described in the comment are:
: level sequence out-degrees (dots for zeros)
: 1: [ 0 1 2 3 3 2 1 ] [ 2 2 2 . . . . ]
: O--o--o--o
: .--o
: .--o
: .--o
:
: 2: [ 0 1 2 2 2 2 1 ] [ 2 4 . . . . . ]
: O--o--o
: .--o
: .--o
: .--o
: .--o
:
: 3: [ 0 1 2 2 2 1 1 ] [ 3 3 . . . . . ]
: O--o--o
: .--o
: .--o
: .--o
: .--o
:
: 4: [ 0 1 2 2 1 2 2 ] [ 2 2 . . 2 . . ]
: O--o--o
: .--o
: .--o--o
: .--o
:
: 5: [ 0 1 2 2 1 1 1 ] [ 4 2 . . . . . ]
: O--o--o
: .--o
: .--o
: .--o
: .--o
:
: 6: [ 0 1 1 1 1 1 1 ] [ 6 . . . . . . ]
: O--o
: .--o
: .--o
: .--o
: .--o
: .--o
:
(End)
The a(2) = 1 through a(9) = 10 unlabeled lone-child-avoiding rooted trees with n - 1 nodes (empty n = 3 column shown as dot) are:
o . (oo) (ooo) (oooo) (ooooo) (oooooo) (ooooooo)
(o(oo)) (o(ooo)) (o(oooo)) (o(ooooo))
(oo(oo)) (oo(ooo)) (oo(oooo))
(ooo(oo)) (ooo(ooo))
((oo)(oo)) (oooo(oo))
(o(o(oo))) ((oo)(ooo))
(o(o(ooo)))
(o(oo)(oo))
(o(oo(oo)))
(oo(o(oo)))
(End)
MAPLE
with (powseries): with (combstruct): n := 30: sys := {B = Prod(C, Z), S = Set(B, 1 <= card), C = Union(Z, S)}: A001678 := 1, 0, 1, seq(count([S, sys, unlabeled], size=i), i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com) # second Maple program:
with(numtheory):
b:= proc(n) option remember; `if`(n=0, 1, add(add(
d*a(d+1), d=divisors(j))*b(n-j), j=1..n)/n)
end:
a:= proc(n) option remember; `if`(n<2, 0,
`if`(n=2, 1, b(n-2)-a(n-1)))
end:
MATHEMATICA
b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*a[d+1], {d, Divisors[j]}]*b[n-j], {j, 1, n}]/n]; a[n_] := a[n] = If[n < 2, 0, If[n == 2, 1, b[n-2] - a[n-1]]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Sep 24 2014, after Alois P. Heinz *) terms = 38; A[_] = 0; Do[A[x_] = (x^2/(1+x))*Exp[Sum[A[x^k]/(k*x^k), {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms}]; CoefficientList[A[x], x] (* Jean-François Alcover, Jan 12 2018 *) urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]], {ptn, IntegerPartitions[n-1]}];
Table[If[n<=1, 0, Length[Select[urt[n-1], FreeQ[#, {_}]&]]], {n, 0, 10}] (* Gus Wiseman, Jan 20 2020 *)
PROG
(PARI) (a(n) = if( n<4, n==2, T(n-2, n-3))); /* where */ {T(n, k) = if( n<1 || k<1, (n==0) && (k>=0), sum(j=1, k, sum(i=1, n\j, T(n-i*j, min(n-i*j, j-1)) * binomial( a(j+1) + i-1, i))))}; /* Michael Somos, Jun 04 2002 */ (PARI) {a(n) = local(A); if( n<3, n==2, A = x / (1 - x^2) + O(x^n); for(k=3, n-2, A /= (1 - x^k + O(x^n))^polcoeff(A, k)); polcoeff(A, n-1))}; /* Michael Somos, Oct 06 2003 */
CROSSREFS
Unlabeled rooted trees are counted by A000081. Topologically series-reduced rooted trees are counted by A001679. Labeled lone-child-avoiding rooted trees are counted by A060356. Labeled lone-child-avoiding unrooted trees are counted by A108919. Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636. Singleton-reduced rooted trees are counted by A330951.
Matula-Goebel numbers of lone-child-avoiding rooted trees.
+10
44
1, 4, 8, 14, 16, 28, 32, 38, 49, 56, 64, 76, 86, 98, 106, 112, 128, 133, 152, 172, 196, 212, 214, 224, 256, 262, 266, 301, 304, 326, 343, 344, 361, 371, 392, 424, 428, 448, 454, 512, 524, 526, 532, 602, 608, 622, 652, 686, 688, 722, 742, 749, 766, 784, 817
COMMENTS
We say that a rooted tree is lone-child-avoiding if no vertex has exactly one child.
The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of its branches. This gives a bijective correspondence between positive integers and unlabeled rooted trees.
An alternative definition: n is in the sequence iff n is 1 or the product of two or more not necessarily distinct prime numbers whose prime indices already belong to the sequence. For example, 14 is in the sequence because 14 = prime(1) * prime(4) and 1 and 4 both already belong to the sequence.
EXAMPLE
The sequence of all lone-child-avoiding rooted trees together with their Matula-Goebel numbers begins:
1: o
4: (oo)
8: (ooo)
14: (o(oo))
16: (oooo)
28: (oo(oo))
32: (ooooo)
38: (o(ooo))
49: ((oo)(oo))
56: (ooo(oo))
64: (oooooo)
76: (oo(ooo))
86: (o(o(oo)))
98: (o(oo)(oo))
106: (o(oooo))
112: (oooo(oo))
128: (ooooooo)
133: ((oo)(ooo))
152: (ooo(ooo))
172: (oo(o(oo)))
MATHEMATICA
nn=2000;
primeMS[n_]:=If[n===1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
srQ[n_]:=Or[n===1, With[{m=primeMS[n]}, And[Length[m]>1, And@@srQ/@m]]];
Select[Range[nn], srQ]
CROSSREFS
These trees are counted by A001678. The case with more than two branches is A331490. Unlabeled rooted trees are counted by A000081. Topologically series-reduced rooted trees are counted by A001679. Labeled lone-child-avoiding rooted trees are counted by A060356. Labeled lone-child-avoiding unrooted trees are counted by A108919. MG numbers of singleton-reduced rooted trees are A330943. MG numbers of topologically series-reduced rooted trees are A331489. Cf. A007097, A061775, A109082, A109129, A111299, A196050, A198518, A276625, A291441, A291442, A331488.
EXTENSIONS
Updated with corrected terminology by Gus Wiseman, Jan 20 2020
Expansion of e.g.f.: -LambertW(-x/(1+x)).
+10
33
0, 1, 0, 3, 4, 65, 306, 4207, 38424, 573057, 7753510, 134046671, 2353898196, 47602871329, 1013794852266, 23751106404495, 590663769125296, 15806094859299329, 448284980183376078, 13515502344669830287
COMMENTS
Also the number of labeled lone-child-avoiding rooted trees with n nodes. A rooted tree is lone-child-avoiding if it has no unary branchings, meaning every non-leaf node covers at least two other nodes. The unlabeled version is A001678(n + 1). - Gus Wiseman, Jan 20 2020
FORMULA
a(n) = Sum_{k=1..n} (-1)^(n-k)*n!/k!*binomial(n-1, k-1)*k^(k-1). a(n) = Sum_{k=0..n} Stirling1(n, k)* A058863(k). - Vladeta Jovovic, Sep 17 2003
EXAMPLE
Non-isomorphic representatives of the a(7) = 4207 trees, written as root[branches], are:
1[2,3[4,5[6,7]]]
1[2,3[4,5,6,7]]
1[2[3,4],5[6,7]]
1[2,3,4[5,6,7]]
1[2,3,4,5[6,7]]
1[2,3,4,5,6,7]
(End)
MAPLE
seq(coeff(series( -LambertW(-x/(1+x)), x, n+1), x, n)*n!, n = 0..20); # G. C. Greubel, Mar 16 2020
MATHEMATICA
CoefficientList[Series[-LambertW[-x/(1+x)], {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Nov 27 2012 *) sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
a[n_]:=If[n==1, 1, n*Sum[Times@@a/@Length/@stn, {stn, Select[sps[Range[n-1]], Length[#]>1&]}]];
PROG
(PARI) { for (n=0, 100, f=n!; a=sum(k=1, n, (-1)^(n - k)*f/k!*binomial(n - 1, k - 1)*k^(k - 1)); write("b060356.txt", n, " ", a); ) } \\ Harry J. Smith, Jul 04 2009 (PARI) my(x='x+O('x^20)); concat([0], Vec(serlaplace(-lambertw(-x/(1+x))))) \\ G. C. Greubel, Feb 19 2018 (GAP) List([0..20], n->Sum([1..n], k->(-1)^(n-k)*Factorial(n)/Factorial(k) *Binomial(n-1, k-1)*k^(k-1))); # Muniru A Asiru, Feb 19 2018
CROSSREFS
The unlabeled version is A001678(n + 1). The case where the root is fixed is A108919. Unlabeled rooted trees are counted by A000081. Lone-child-avoiding rooted trees with labeled leaves are A000311. Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636. Singleton-reduced rooted trees are counted by A330951. Cf. A000669, A004111, A005121, A048816, A292504, A316651, A316652, A318231, A318813, A330465, A330624.
Expansion of e.g.f. LambertW( -x/(1-x) ) / (-x).
+10
28
1, 2, 9, 67, 717, 10141, 179353, 3816989, 95076537, 2714895433, 87457961421, 3138260371225, 124147801973605, 5368353187693757, 251928853285058433, 12752446755011776741, 692625349011401620209, 40178978855796929378065, 2479383850197948228950293
COMMENTS
An interesting property of this e.g.f. A(x) is that the sum of coefficients of x^k, k=0..n, in 1/A(x)^n equals zero, for n > 1.
FORMULA
E.g.f. A(x) = Sum_{n>=0} a(n)*x^n/n! satisfies:
(1) A(x) = LambertW( -x/(1-x) ) / (-x).
(2) A(x) = exp( x*A(x) ) / (1-x).
(3) A(x) = log( (1-x) * A(x) ) / x.
(4) A( x/(exp(x) + x) ) = exp(x) + x.
(5) A(x) = (1/x) * Series_Reversion( x/(exp(x) + x) ).
(6) Sum_{k=0..n} [x^k] 1/A(x)^n = 0, for n > 1.
(7) [x^(n+1)/(n+1)!] 1/A(x)^n = -n for n >= (-1).
a(n) ~ (1 + exp(1))^(n + 3/2) * n^(n-1) / exp(n + 1/2). - Vaclav Kotesovec, Mar 15 2022 a(n) = n! * Sum_{k=0..n} (k+1)^(k-1) * binomial(n,k)/k!. - Seiichi Manyama, Sep 24 2022
EXAMPLE
E.g.f.: A(x) = 1 + 2*x + 9*x^2/2! + 67*x^3/3! + 717*x^4/4! + 10141*x^5/5! + 179353*x^6/6! + 3816989*x^7/7! + ...
such that A(x) = exp(x*A(x)) / (1-x), where
exp(x*A(x)) = 1 + x + 5*x^2/2! + 40*x^3/3! + 449*x^4/4! + 6556*x^5/5! + 118507*x^6/6! + ... + A052868(n)*x^n/n! + ... which equals LambertW(-x/(1-x)) * (1-x)/(-x).
Related table.
Another defining property of the e.g.f. A(x) is illustrated here.
The table of coefficients of x^k/k! in 1/A(x)^n begins:
n=1: [1, -2, -1, -7, -71, -961, -16409, -339571, ...];
n=2: [1, -4, 6, -2, -24, -362, -6644, -144538, ...];
n=3: [1, -6, 21, -33, -3, -63, -1395, -34275, ...];
n=4: [1, -8, 44, -148, 232, -4, -152, -4876, ...];
n=5: [1, -10, 75, -395, 1305, -2045, -5, -355, ...];
n=6: [1, -12, 114, -822, 4224, -13806, 21636, -6, ...];
n=7: [1, -14, 161, -1477, 10381, -52507, 170401, -267043, -7, ...];
...
from which we can illustrate that the partial sum of coefficients of x^k, k=0..n, in 1/A(x)^n equals zero, for n > 1, as follows:
n=1:-1 = 1 + -2;
n=2: 0 = 1 + -4 + 6/2!;
n=3: 0 = 1 + -6 + 21/2! + -33/3!;
n=4: 0 = 1 + -8 + 44/2! + -148/3! + 232/4!;
n=5: 0 = 1 + -10 + 75/2! + -395/3! + 1305/4! + -2045/5!;
n=6: 0 = 1 + -12 + 114/2! + -822/3! + 4224/4! + -13806/5! + 21636/6!;
n=7: 0 = 1 + -14 + 161/2! + -1477/3! + 10381/4! + -52507/5! + 170401/6! + -267043/7!;
...
PROG
(PARI) {a(n) = n!*polcoeff( (1/x)*serreverse( x/(exp(x +x^2*O(x^n)) + x) ), n)}
for(n=0, 30, print1(a(n), ", "))
(PARI) my(x='x+O('x^30)); Vec(serlaplace(lambertw(-x/(1-x))/(-x))) \\ Michel Marcus, Mar 17 2022 (PARI) a(n) = n!*sum(k=0, n, (k+1)^(k-1)*binomial(n, k)/k!); \\ Seiichi Manyama, Sep 24 2022
G.f. satisfies: A(x) = exp( Sum_{n>=1} A(x^n)/(1+x^n) * x^n/n ).
+10
13
1, 1, 1, 2, 3, 5, 9, 16, 29, 54, 102, 194, 375, 730, 1434, 2837, 5650, 11311, 22767, 46023, 93422, 190322, 389037, 797613, 1639878, 3380099, 6983484, 14459570, 29999618, 62357426, 129843590, 270807835, 565674584, 1183301266, 2478624060, 5198504694, 10916110768, 22948299899
COMMENTS
For n>=1, a(n) is the number of rooted trees (see A000081) with n non-root nodes where non-root nodes cannot have out-degree 1, see the note by David Callan and the example. Imposing the condition also for the root node gives A001678. - Joerg Arndt, Jun 28 2014 Compare definition to G(x) = exp( Sum_{n>=1} G(x^n)*x^n/n ), where G(x) is the g.f. of A000081, the number of rooted trees with n nodes. Number of forests of lone-child-avoiding rooted trees with n unlabeled vertices. - Gus Wiseman, Feb 03 2020
FORMULA
Euler transform of coefficients in A(x)/(1+x), where g.f. A(x) = Sum_{n>=0} a(n)*x^n.
a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711..., c = 1.3437262442171062526771597... . - Vaclav Kotesovec, Sep 03 2014
EXAMPLE
G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 5*x^5 + 9*x^6 + 16*x^7 + 29*x^8 +...
where
log(A(x)) = A(x)/(1+x)*x + A(x^2)/(1+x^2)*x^2/2 + A(x^3)/(1+x^3)*x^3/3 +...
The coefficients in A(x)/(1+x) begin:
[1, 0, 1, 1, 2, 3, 6, 10, 19, 35, 67, 127, 248, 482, 952, 1885, 3765, ...]
from which g.f. A(x) may be generated by the Euler transform:
A(x) = 1/((1-x)^1*(1-x^2)^0*(1-x^3)^1*(1-x^4)^1*(1-x^5)^2*(1-x^6)^3*(1-x^7)^6*(1-x^8)^10*(1-x^9)^19*(1-x^10)^35*...).
The a(6) = 9 rooted trees with 6 non-root nodes as described in the comment are:
: level sequence out-degrees (dots for zeros)
: 1: [ 0 1 2 3 3 3 2 ] [ 1 2 3 . . . . ]
: O--o--o--o
: .--o
: .--o
: .--o
:
: 2: [ 0 1 2 3 3 2 2 ] [ 1 3 2 . . . . ]
: O--o--o--o
: .--o
: .--o
: .--o
:
: 3: [ 0 1 2 3 3 2 1 ] [ 2 2 2 . . . . ]
: O--o--o--o
: .--o
: .--o
: .--o
:
: 4: [ 0 1 2 2 2 2 2 ] [ 1 5 . . . . . ]
: O--o--o
: .--o
: .--o
: .--o
: .--o
:
: 5: [ 0 1 2 2 2 2 1 ] [ 2 4 . . . . . ]
: O--o--o
: .--o
: .--o
: .--o
: .--o
:
: 6: [ 0 1 2 2 2 1 1 ] [ 3 3 . . . . . ]
: O--o--o
: .--o
: .--o
: .--o
: .--o
:
: 7: [ 0 1 2 2 1 2 2 ] [ 2 2 . . 2 . . ]
: O--o--o
: .--o
: .--o--o
: .--o
:
: 8: [ 0 1 2 2 1 1 1 ] [ 4 2 . . . . . ]
: O--o--o
: .--o
: .--o
: .--o
: .--o
:
: 9: [ 0 1 1 1 1 1 1 ] [ 6 . . . . . . ]
: O--o
: .--o
: .--o
: .--o
: .--o
: .--o
(End)
The a(0) = 1 through a(6) = 9 rooted trees with n + 1 nodes where non-root vertices cannot have out-degree 1:
o (o) (oo) (ooo) (oooo) (ooooo) (oooooo)
((oo)) ((ooo)) ((oooo)) ((ooooo))
(o(oo)) (o(ooo)) (o(oooo))
(oo(oo)) (oo(ooo))
((o(oo))) (ooo(oo))
((o(ooo)))
((oo)(oo))
((oo(oo)))
(o(o(oo)))
(End)
MAPLE
with(numtheory):
b:= proc(n) b(n):= `if`(n=0, 1, a(n)-b(n-1)) end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(
d*b(d-1), d=divisors(j))*a(n-j), j=1..n)/n)
end:
MATHEMATICA
b[n_] := b[n] = If[n==0, 1, a[n] - b[n-1]];
a[n_] := a[n] = If[n==0, 1, Sum[Sum[d*b[d-1], {d, Divisors[j]}]*a[n-j], {j, 1, n}]/n];
urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]], {ptn, IntegerPartitions[n-1]}];
Table[Length[Select[urt[n], FreeQ[Z@@#, {_}]&]], {n, 10}] (* Gus Wiseman, Jan 22 2020 *)
PROG
(PARI) {a(n)=local(A=1+x); for(i=1, n, A=exp(sum(m=1, n, subst(A/(1+x), x, x^m+x*O(x^n))*x^m/m))); polcoeff(A, n)}
CROSSREFS
Unlabeled rooted trees are A000081. Lone-child-avoiding rooted trees are A001678(n+1). Topologically series-reduced rooted trees are A001679. Labeled lone-child-avoiding rooted trees are A060356.
Number of homeomorphically irreducible rooted trees (also known as series-reduced rooted trees, or rooted trees without nodes of degree 2) on n labeled nodes.
+10
12
1, 2, 0, 16, 25, 576, 2989, 51584, 512649, 8927200, 130956001, 2533847328, 48008533885, 1059817074512, 24196291364925, 609350187214336, 16135860325700881, 459434230368302016, 13788624945433889593, 439102289933675933600, 14705223056221892676741
REFERENCES
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
FORMULA
a(n) = n*(n-2)!*Sum_{k=0..n-2} (-1)^k*binomial(n, k)*(n-k)^(n-k-2)/(n-k-2)!, n>1.
E.g.f.: x*(exp( - LambertW(-x/(1+x))) - (LambertW(-x/(1+x))/2 )^2).
E.g.f.: -(1+x)*LambertW(-x/(1+x)) - (x/2)*LambertW(-x/(1+x))^2. - G. C. Greubel, Mar 07 2020
EXAMPLE
The a(1) = 1 through a(4) = 16 trees (in the format root[branches], empty column shown as dot) are:
1 1[2] . 1[2,3,4]
2[1] 1[2[3,4]]
1[3[2,4]]
1[4[2,3]]
2[1,3,4]
2[1[3,4]]
2[3[1,4]]
2[4[1,3]]
3[1,2,4]
3[1[2,4]]
3[2[1,4]]
3[4[1,2]]
4[1,2,3]
4[1[2,3]]
4[2[1,3]]
4[3[1,2]]
(End)
MAPLE
seq( `if`(n=1, 1, n*(n-2)!*add((-1)^k*binomial(n, k)*(n-k)^(n-k-2)/(n-k-2)!, k=0..n-2)), n=1..20); # G. C. Greubel, Mar 07 2020
MATHEMATICA
f[n_] := If[n < 2, 1, n(n - 2)!Sum[(-1)^k*Binomial[n, k](n - k)^(n - 2 - k)/(n - 2 - k)!, {k, 0, n - 2}]]; Table[ f[n], {n, 19}] (* Robert G. Wilson v, Feb 12 2005 *) sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
lrt[set_]:=If[Length[set]==0, {}, Join@@Table[Apply[root, #]&/@Join@@Table[Tuples[lrt/@stn], {stn, sps[DeleteCases[set, root]]}], {root, set}]];
Table[Length[Select[lrt[Range[n]], Length[#]!=2&&FreeQ[Z@@#, _Integer[_]]&]], {n, 6}] (* Gus Wiseman, Jan 22 2020 *)
PROG
(Magma) [1] cat [n*Factorial(n-2)*(&+[(-1)^k*Binomial(n, k)*(n-k)^(n-k-2)/Factorial(n-k-2): k in [0..n-2]]): n in [2..20]]; // G. C. Greubel, Mar 07 2020 (Sage) [1]+[n*factorial(n-2)*sum((-1)^k*binomial(n, k)*(n-k)^(n-k-2)/factorial( n-k-2) for k in (0..n-2)) for n in (2..20)] # G. C. Greubel, Mar 07 2020
CROSSREFS
The unlabeled unrooted version is A000014. The lone-child-avoiding version is A060356.
Number of rooted labeled trees on n nodes such that every nonroot node is the child of a branching node or of the root.
+10
7
0, 1, 2, 3, 16, 85, 696, 6349, 72080, 918873, 13484080, 219335281, 3962458248, 78203547877, 1680235050872, 38958029188485, 970681471597216, 25847378934429361, 732794687650764000, 22032916968153975769, 700360446794528578520
COMMENTS
Here, a branching node is a node with at least two children.
In other words, a(n) is the number of labeled rooted trees on n nodes such that the path from every node towards the root reaches a branching node (or the root) in one step.
Also labeled rooted trees that are lone-child-avoiding except possibly for the root. The unlabeled version is A198518. - Gus Wiseman, Jan 22 2020
FORMULA
E.g.f.: A(x) satisfies 1/(1 - (A(x) - x)) = B(x) where B(x) is the e.g.f. for A231797.
EXAMPLE
a(5) = 85:
...0................0...............0-o...
...|.............../ \............ /|\....
...o..............o o...........o o o...
../|\............/ \ ...................
.o o o..........o o ..................
These trees have 20 + 60 + 5 = 85 labelings.
The a(1) = 1 through a(4) = 16 trees (in the format root[branches]) are:
1 1[2] 1[2,3] 1[2,3,4]
2[1] 2[1,3] 1[2[3,4]]
3[1,2] 1[3[2,4]]
1[4[2,3]]
2[1,3,4]
2[1[3,4]]
2[3[1,4]]
2[4[1,3]]
3[1,2,4]
3[1[2,4]]
3[2[1,4]]
3[4[1,2]]
4[1,2,3]
4[1[2,3]]
4[2[1,3]]
4[3[1,2]]
(End)
MATHEMATICA
nn = 20; b = 1 + Sum[nn = n; n! Coefficient[Series[(Exp[x] - x)^n, {x, 0, nn}], x^n]*x^n/n!, {n, 1, nn}]; c = Sum[a[n] x^n/n!, {n, 0, nn}]; sol = SolveAlways[b == Series[1/(1 - (c - x)), {x, 0, nn}], x]; Flatten[Table[a[n], {n, 0, nn}] /. sol]
nn = 30; CoefficientList[Series[1+x-1/Sum[SeriesCoefficient[(E^x-x)^n, {x, 0, n}]*x^n, {n, 0, nn}], {x, 0, nn}], x] * Range[0, nn]! (* Vaclav Kotesovec, Jan 30 2015 *) sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
lrt[set_]:=If[Length[set]==0, {}, Join@@Table[Apply[root, #]&/@Join@@Table[Tuples[lrt/@stn], {stn, sps[DeleteCases[set, root]]}], {root, set}]];
Table[Length[Select[lrt[Range[n]], FreeQ[Z@@#, _Integer[_]]&]], {n, 6}] (* Gus Wiseman, Jan 22 2020 *)
CROSSREFS
Lone-child-avoiding rooted trees are A001678(n + 1). Labeled topologically series-reduced rooted trees are A060313. Labeled lone-child-avoiding unrooted trees are A108919.
Number of labeled series-reduced rooted trees with n vertices and more than two branches of the root.
+10
7
0, 0, 0, 4, 5, 186, 847, 17928, 166833, 3196630, 45667391, 925287276, 17407857337, 393376875906, 8989368580935, 229332484742416, 6094576250570849, 174924522900914094, 5271210321949744111, 168792243040279327860, 5674164658298121248361, 200870558472768096534490
COMMENTS
A rooted tree is series-reduced if no vertex (including the root) has degree 2.
Also labeled lone-child-avoiding rooted trees with n vertices and more than two branches, where a rooted tree is lone-child-avoiding if no vertex has exactly one child.
FORMULA
a(n) = Sum_{k=1..n} (-1)^(n-k)*k^(k-2)*n*(n-2)!*binomial(n-1,k-1)*(2*k*n - n - k^2)/k!) for n > 1.
E.g.f.: -x - LambertW(-x/(1+x)) - (x/2)*LambertW(-x/(1+x))^2.
(End)
EXAMPLE
Non-isomorphic representatives of the a(7) = 847 trees (in the format root[branches]) are:
1[2,3,4[5,6,7]]
1[2,3,4,5[6,7]]
1[2,3,4,5,6,7]
MATHEMATICA
lrt[set_]:=If[Length[set]==0, {}, Join@@Table[Apply[root, #]&/@Join@@Table[Tuples[lrt/@stn], {stn, sps[DeleteCases[set, root]]}], {root, set}]];
Table[Length[Select[lrt[Range[n]], Length[#]>2&&FreeQ[#, _[_]]&]], {n, 6}]
PROG
(PARI) a(n) = {if(n<=1, 0, sum(k=1, n, (-1)^(n-k)*k^(k-2)*n*(n-2)!*binomial(n-1, k-1)*(2*k*n - n - k^2)/k!))} \\ Andrew Howroyd, Dec 09 2020 (PARI) seq(n)={my(w=lambertw(-x/(1+x) + O(x*x^n))); Vec(serlaplace(-x - w - (x/2)*w^2), -n)} \\ Andrew Howroyd, Dec 09 2020
CROSSREFS
The non-series-reduced version is A331577. Lone-child-avoiding rooted trees are counted by A001678. Topologically series-reduced rooted trees are counted by A001679. Labeled topologically series-reduced rooted trees are counted by A060313. Labeled lone-child-avoiding rooted trees are counted by A060356. Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636. Matula-Goebel numbers of series-reduced rooted trees are A331489.
E.g.f. A(x) satisfies A(x) = exp(x*A(x)/(1 + x)).
+10
3
1, 1, 1, 4, 17, 116, 907, 9010, 102097, 1348408, 19939571, 330204854, 6015657529, 120016789348, 2597201945899, 60667591974826, 1520434054966433, 40710815980598000, 1159627208850209251, 35018022339726428926, 1117395892399939407241, 37569709612314269554396
FORMULA
E.g.f.: -(1 + x) * LambertW(-x/(1 + x)) / x.
a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n-1,k-1) * (k+1)^(k-1) * n! / k!.
a(n) ~ (exp(1) - 1)^(n + 1/2) * n^(n-1) / exp(n - 1/2). - Vaclav Kotesovec, Jul 01 2020
MATHEMATICA
nmax = 21; A[_] = 0; Do[A[x_] = Exp[x A[x]/(1 + x)] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] Range[0, nmax]!
nmax = 21; CoefficientList[Series[-(1 + x) LambertW[-x/(1 + x)]/x, {x, 0, nmax}], x] Range[0, nmax]!
Table[Sum[(-1)^(n - k) Binomial[n - 1, k - 1] (k + 1)^(k - 1) n!/k!, {k, 0, n}], {n, 0, 21}]
PROG
(PARI) my(N=30, x='x+O('x^N)); Vec(serlaplace(exp(-lambertw(-x/(1+x))))) \\ Seiichi Manyama, Mar 05 2023
Search completed in 0.018 seconds
|