Displaying 1-10 of 23 results found.
0, 1, 2, 2, 3, 4, 6, 8, 12, 17, 27, 41, 67, 109, 187, 319, 568, 1013, 1855, 3416, 6404, 12075, 23056, 44265, 85737, 166918, 327094, 643843, 1273776, 2529846, 5045015, 10094831, 20267469, 40811048, 82413473, 166854359, 338648851, 688887026, 1404384063, 2868791176, 5871429462, 12038444069
COMMENTS
Number of series-reduced trees with <= n nodes.
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) # Alternative:
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 *) (* Alternative: *)
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 *) (* Alternative: *)
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.
Number of series-reduced rooted trees with n nodes.
(Formerly M0327 N0123)
+10
16
1, 1, 1, 0, 2, 2, 4, 6, 12, 20, 39, 71, 137, 261, 511, 995, 1974, 3915, 7841, 15749, 31835, 64540, 131453, 268498, 550324, 1130899, 2330381, 4813031, 9963288, 20665781, 42947715, 89410092, 186447559, 389397778, 814447067, 1705775653, 3577169927
COMMENTS
Also known as homeomorphically irreducible rooted trees, or rooted trees without nodes of degree 2.
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 topologically series-reduced rooted trees with n vertices. Lone-child-avoiding rooted trees with n - 1 vertices are counted by A001678. - Gus Wiseman, Jan 21 2020
REFERENCES
D. G. Cantor, personal communication.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Eq. (3.3.9).
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. = 1 + ((1+x)*f(x) - (f(x)^2+f(x^2))/2)/x where f(x) is g.f. for A001678 (homeomorphically irreducible planted trees by nodes). a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711... and c = 0.4213018528699249210965028... . - Vaclav Kotesovec, Jun 26 2014 For n > 1, this sequence counts lone-child-avoiding rooted trees with n nodes and more than two branches, plus lone-child-avoiding rooted trees with n - 1 nodes. So for n > 1, a(n) = A331488(n) + A001678(n). - Gus Wiseman, Jan 21 2020
EXAMPLE
G.f. = 1 + x + x^2 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 12*x^8 + 20*x^9 + ...
The a(1) = 1 through a(8) = 12 unlabeled topologically series-reduced rooted trees with n nodes (empty n = 3 column shown as dot) are:
o (o) . (ooo) (oooo) (ooooo) (oooooo) (ooooooo)
((oo)) ((ooo)) ((oooo)) ((ooooo)) ((oooooo))
(oo(oo)) (oo(ooo)) (oo(oooo))
((o(oo))) (ooo(oo)) (ooo(ooo))
((o(ooo))) (oooo(oo))
((oo(oo))) ((o(oooo)))
((oo(ooo)))
((ooo(oo)))
(o(oo)(oo))
(oo(o(oo)))
(((oo)(oo)))
((o(o(oo))))
(End)
MAPLE
with(powseries): with(combstruct): n := 30: Order := n+3: sys := {B = Prod(C, Z), S = Set(B, 1 <= card), C = Union(Z, S)}:
G001678 := (convert(gfseries(sys, unlabeled, x)[S(x)], polynom)) * x^2: G0temp := G001678 + x^2:
G001679 := G0temp / x + G0temp - (G0temp^2+eval(G0temp, x=x^2))/(2*x): A001679 := 0, seq(coeff(G001679, x^i), i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)
MATHEMATICA
terms = 37; (* F = G001678 *) F[_] = 0; Do[F[x_] = (x^2/(1 + x))*Exp[Sum[ F[x^k]/(k*x^k), {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms + 1}];
G[x_] = 1 + ((1 + x)/x)*F[x] - (F[x]^2 + F[x^2])/(2*x) + O[x]^terms;
(* Alternative: *)
urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]], {ptn, IntegerPartitions[n-1]}];
Table[Length[Select[urt[n], Length[#]!=2&&FreeQ[Z@@#, {_}]&]], {n, 15}] (* Gus Wiseman, Jan 21 2020 *)
PROG
(PARI) {a(n) = local(A); if( n<3, n>0, A = x / (1 - x^2) + x * O(x^n); for(k=3, n-1, A /= (1 - x^k + x * O(x^n))^polcoeff(A, k)); polcoeff( (1 + x)*A - x*(A^2 + subst(A, x, x^2)) / 2, n))};
CROSSREFS
Apart from initial term, same as A059123. Cf. A000055 (trees by nodes), A000014 (homeomorphically irreducible trees by nodes), A000669 (homeomorphically irreducible planted trees by leaves), A000081 (rooted trees by nodes). Matula-Goebel numbers of these trees are given by A331489. Lone-child-avoiding rooted trees are counted by A001678(n + 1).
Number of homeomorphically irreducible (or series-reduced) trees with n pendant nodes, or continua with n non-cut points, or leaves.
+10
16
1, 1, 1, 1, 2, 3, 7, 13, 32, 73, 190, 488, 1350, 3741, 10765, 31311, 92949, 278840, 847511, 2599071, 8044399, 25082609, 78758786, 248803504, 790411028, 2523668997, 8095146289, 26076714609, 84329102797, 273694746208
COMMENTS
Also, number of unrooted multifurcating tree shapes with n leaves [see Felsenstein].
REFERENCES
M. Cropper, J. Combin. Math. Combin. Comp., Vol. 24 (1997), 177-184.
Joseph Felsenstein, Inferring Phylogenies. Sinauer Associates, Inc., 2004, p. 33 (Beware errors!).
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62.
S. B. Nadler Jr., Continuum Theory, Academic Press.
FORMULA
G.f.: 1+(1+x-B(x))*B(x) where B(x) = x+x^2+2*x^3+5*x^4+12*x^5+33*x^6+90*x^7+... is g.f. for A000669.
MAPLE
A := series(1+(1+x-B)*B, x, 30); # where B = g.f. for A000669; A007827 := n->coeff(A, x, n);
MATHEMATICA
(* a9 = A000669 *) max = 29; a9[1] = 1; a9[n_] := (s = Series[1/(1 - x), {x, 0, n}]; Do[s = Series[s/(1 - x^k)^Coefficient[s, x^k], {x, 0, n}], {k, 2, n}]; Coefficient[s, x^n]/2); b[x_] := Sum[a9[n] x^n, {n, 1, max}]; gf[x_] := 1 + (1 + x - b[x])*b[x]; CoefficientList[ Series[gf[x], {x, 0, max}], x] (* Jean-François Alcover, Aug 14 2012 *)
CROSSREFS
Cf. A000014 (series-reduced trees), A000055 (trees), A000311, A000669 (series-reduced planted trees by leaves), A059123 (homeomorphically irreducible rooted trees by nodes), A271205 (series-reduced trees by leaves and nodes).
AUTHOR
Matthew Cropper (mmcrop01(AT)athena.louisville.edu)
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 (SageMath) [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.
Triangle giving number of trees with n >= 3 nodes and diameter d >= 2.
+10
10
1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 5, 2, 1, 1, 3, 8, 7, 3, 1, 1, 3, 14, 14, 11, 3, 1, 1, 4, 21, 32, 29, 14, 4, 1, 1, 4, 32, 58, 74, 42, 19, 4, 1, 1, 5, 45, 110, 167, 128, 66, 23, 5, 1
FORMULA
Reference gives recurrence.
EXAMPLE
1
1 1
1 1 1
1 2 2 1
1 2 5 2 1
1 3 8 7 3 1
1 3 14 14 11 3 1
1 4 21 32 29 14 4 1
1 4 32 58 74 42 19 4 1
1 5 45 110 167 128 66 23 5 1
1 5 65 187 367 334 219 88 29 5 1
1 6 88 322 755 850 645 328 123 34 6 1
Number of series-reduced labeled trees with n nodes.
(Formerly M3261)
+10
9
1, 1, 0, 4, 5, 96, 427, 6448, 56961, 892720, 11905091, 211153944, 3692964145, 75701219608, 1613086090995, 38084386700896, 949168254452993, 25524123909350112, 725717102391257347, 21955114496683796680
REFERENCES
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 188 (3.1.94)
F. Harary and E. M. Palmer, Graphical Enumeration. New York: Academic Press, 1973. (gives g.f. for unlabeled series-reduced trees)
R. C. Read, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
FORMULA
a(n) = Sum_{k=0..n-2} (-1)^k*(n-k)^(n-k-2)*binomial(n, k)*(n-2)!/(n-k-2)!, n>=2.
EXAMPLE
a(6) = 96 because there are two unlabeled series-reduced trees on six vertices, the star and the tree with two vertices of degree three and four leaves; the first of these can be labeled in 6 ways and the second in 90, for a total of 96. - Isabel C. Lugo (izzycat(AT)gmail.com), Aug 19 2004
MAPLE
if n = 1 then
1;
else
add( (-1)^(n-r)*binomial(n, r)*r^(r-2)/(r-2)!, r=2..n) ;
%*(n-2)! ;
end if;
MATHEMATICA
a[1] = a[2] = 1; a[3] = 0; a[n_] := n!*(n-2)!*Sum[ (-1)^k*(n-k)^(n-k-3) / (k!*(n-k-2)!^2*(n-k-1)), {k, 0, n-2}]; Table[a[n], {n, 1, 20}](* Jean-François Alcover, Feb 16 2012, after given formula *) (* Alternative: *)
u[1, 1] = 1; u[2, 1] = 0; u[2, 2] = 1; u[3, k_] := 0;
u[n_, k_] /; k <= 0 := 0;
u[n_, k_] /; k >= 1 :=
u[n, k] = (n (n - k) u[n - 1, k - 1] + n (n - 1) (n - 3) u[n - 2, k - 1])/k;
Table[Sum[u[n, m], {m, 1, n}], {n, 50}] (* David Callan, Jun 25 2014, fast generation, after R. C. Read link *)
PROG
(PARI) a(n) = if(n<=1, n==1, sum(k=0, n-2, (-1)^k*(n-k)^(n-k-2)*binomial(n, k)*(n-2)!/(n-k-2)!)) \\ Andrew Howroyd, Dec 18 2017 (Magma) [1] cat [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]];
(SageMath) [1]+[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
Number of unlabeled lone-child-avoiding rooted trees with n vertices and more than two branches (of the root).
+10
9
0, 0, 0, 1, 1, 2, 3, 6, 10, 20, 36, 70, 134, 263, 513, 1022, 2030, 4076, 8203, 16614, 33738, 68833, 140796, 288989, 594621, 1226781, 2536532, 5256303, 10913196, 22700682, 47299699, 98714362, 206323140, 431847121, 905074333, 1899247187, 3990145833, 8392281473
COMMENTS
Also the number of lone-child-avoiding rooted trees with n vertices and more than two branches.
EXAMPLE
The a(4) = 1 through a(9) = 10 trees:
(ooo) (oooo) (ooooo) (oooooo) (ooooooo) (oooooooo)
(oo(oo)) (oo(ooo)) (oo(oooo)) (oo(ooooo))
(ooo(oo)) (ooo(ooo)) (ooo(oooo))
(oooo(oo)) (oooo(ooo))
(o(oo)(oo)) (ooooo(oo))
(oo(o(oo))) (o(oo)(ooo))
(oo(o(ooo)))
(oo(oo)(oo))
(oo(oo(oo)))
(ooo(o(oo)))
MATHEMATICA
urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]], {ptn, IntegerPartitions[n-1]}];
Table[Length[Select[urt[n], Length[#]>2&&FreeQ[#, {_}]&]], {n, 10}]
CROSSREFS
The not necessarily lone-child-avoiding version is A331233. The Matula-Goebel numbers of these trees are listed by A331490. A000081 counts unlabeled rooted trees.
A001678 counts lone-child-avoiding rooted trees.
A001679 counts topologically series-reduced rooted trees.
A291636 lists Matula-Goebel numbers of lone-child-avoiding rooted trees.
A331489 lists Matula-Goebel numbers of series-reduced rooted trees.
Cf. A000014, A000669, A004250, A007097, A007821, A033942, A060313, A060356, A061775, A109082, A109129, A196050, A276625, A330943.
EXTENSIONS
Terminology corrected (lone-child-avoiding, not series-reduced) by Gus Wiseman, May 10 2021
Triangle read by rows: T(n,k) is the number of lone-child-avoiding rooted trees with n leaves of exactly k colors.
+10
8
1, 1, 1, 2, 6, 4, 5, 30, 51, 26, 12, 146, 474, 576, 236, 33, 719, 3950, 8572, 8060, 2752, 90, 3590, 31464, 108416, 175380, 134136, 39208, 261, 18283, 245916, 1262732, 3124650, 4014348, 2584568, 660032, 766, 94648, 1908858, 14047288, 49885320, 95715728, 101799712, 56555904, 12818912
COMMENTS
Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.
FORMULA
T(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)* A319254(n,i).
EXAMPLE
Triangle begins:
1;
1, 1;
2, 6, 4;
5, 30, 51, 26;
12, 146, 474, 576, 236;
33, 719, 3950, 8572, 8060, 2752;
90, 3590, 31464, 108416, 175380, 134136, 39208;
261, 18283, 245916, 1262732, 3124650, 4014348, 2584568, 660032;
...
The 12 trees counted by row n = 3:
(111) (112) (123)
(1(11)) (122) (1(23))
(1(12)) (2(13))
(1(22)) (3(12))
(2(11))
(2(12))
(End)
MAPLE
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
T:= (n, k)-> add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1):
MATHEMATICA
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[A[i, k] + j - 1, j] b[n - i j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n k, b[n, n - 1, k]];
T[n_, k_] := Sum[(-1)^(k - i)*Binomial[k, i]*A[n, i], {i, 1, k}];
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p], {p, Select[mps[m], 1<Length[#]<Length[m]&]}], m];
allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
Table[Sum[Length[Union[mtot[s]]], {s, Select[allnorm[n], Length[Union[#]]==k&]}], {n, 0, 5}, {k, 0, n}] (* Gus Wiseman, Dec 31 2020 *)
PROG
(PARI) \\ here R(n, k) is k-th column of A319254. EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n, k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v, [0]))[n])); v}
M(n)={my(v=vector(n, k, R(n, k)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k, i)*v[i])))}
{my(T=M(10)); for(n=1, #T~, print(T[n, ][1..n]))}
CROSSREFS
The unlabeled version, counting inequivalent leaf-colorings of lone-child-avoiding rooted trees, is A330465. Lone-child-avoiding rooted trees are counted by A001678 (shifted left once). 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 with more than two branches (of the root).
+10
8
8, 16, 28, 32, 56, 64, 76, 98, 112, 128, 152, 172, 196, 212, 224, 256, 266, 304, 343, 344, 392, 424, 428, 448, 512, 524, 532, 602, 608, 652, 686, 688, 722, 742, 784, 848, 856, 896, 908, 931, 1024, 1048, 1052, 1064, 1204, 1216, 1244, 1304, 1372, 1376, 1444
COMMENTS
We say that a rooted tree is (topologically) series-reduced if no vertex has degree 2.
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.
Also Matula-Goebel numbers of lone-child-avoiding rooted trees with more than two branches.
EXAMPLE
The sequence of all series-reduced rooted trees with more than two branches together with their Matula-Goebel numbers begins:
8: (ooo)
16: (oooo)
28: (oo(oo))
32: (ooooo)
56: (ooo(oo))
64: (oooooo)
76: (oo(ooo))
98: (o(oo)(oo))
112: (oooo(oo))
128: (ooooooo)
152: (ooo(ooo))
172: (oo(o(oo)))
196: (oo(oo)(oo))
212: (oo(oooo))
224: (ooooo(oo))
256: (oooooooo)
266: (o(oo)(ooo))
304: (oooo(ooo))
343: ((oo)(oo)(oo))
344: (ooo(o(oo)))
MATHEMATICA
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[1000], PrimeOmega[#]>2&&srQ[#]&]
CROSSREFS
These trees are counted by A331488. Unlabeled rooted trees are counted by A000081. Lone-child-avoiding rooted trees are counted by A001678. Topologically series-reduced rooted trees are counted by A001679. Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636. Matula-Goebel numbers of series-reduced rooted trees are A331489. Cf. A000014, A000669, A004250, A007097, A007821, A033942, A060313, A060356, A061775, A109082, A109129, A196050, A276625, A330943.
Search completed in 0.019 seconds
| 
