A326396 -id:A326396 - cp's OEIS frontend

A316651 Number of series-reduced rooted trees with n leaves spanning an initial interval of positive integers.

1, 2, 12, 112, 1444, 24086, 492284, 11910790, 332827136, 10546558146, 373661603588, 14636326974270, 628032444609396, 29296137817622902, 1476092246351259964, 79889766016415899270, 4622371378514020301740, 284719443038735430679268, 18601385258191195218790756

Offset: 1

Gus Wiseman, Jul 09 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches.

			The a(3) = 12 trees:
  (1(11)), (111),
  (1(12)), (2(11)), (112),
  (1(22)), (2(12)), (122),
  (1(23)), (2(13)), (3(12)), (123).

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A000081, A000311, A000669, A001678, A005804, A034691, A141268, A292504.
Cf. A316652, A316653, A316654, A316655, A316656, A319369.
Row sums of A319376.

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)):
a:= n-> add(add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1), k=1..n):
seq(a(n), n=1..20);  # Alois P. Heinz, Sep 18 2018

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]]]];
gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Sum[Length[gro[m]],{m,allnorm[n]}],{n,5}]
(* Second program: *)
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]];
a[n_] := Sum[Sum[A[n, k-j]*(-1)^j*Binomial[k, j], {j, 0, k-1}], {k, 1, n}];
Array[a, 20] (* Jean-François Alcover, May 09 2021, after Alois P. Heinz *)

\\ here R(n,k) is A000669, A050381, A220823, ...
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}
seq(n)={sum(k=1, n, R(n,k)*sum(r=k, n, binomial(r,k)*(-1)^(r-k)) )} \\ Andrew Howroyd, Sep 14 2018

From Vaclav Kotesovec, Sep 18 2019: (Start)
a(n) ~ c * d^n * n^(n-1), where d = 1.37392076830840090205551979... and c = 0.41435722857311602982846...
a(n) ~ 2*log(2)*A326396(n)/n. (End)

Terms a(9) and beyond from Andrew Howroyd, Sep 14 2018

A319376 Triangle read by rows: T(n,k) is the number of lone-child-avoiding rooted trees with n leaves of exactly k colors.

Original entry on oeis.org

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

Offset: 1

Andrew Howroyd, Sep 17 2018

Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.

			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;
  ...
From _Gus Wiseman_, Dec 31 2020: (Start)
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)

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)

Columns k=1..2 are A000669, A319377.
Main diagonal is A000311.
Row sums are A316651.
Cf. A141610, A242249, A255517, A256064, A256068, A319254, A319541, A326396.
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.
Cf. A000014, A000081, A000169, A005804, A206429, A330951.

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):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Sep 18 2018

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}];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 24 2019, after Alois P. Heinz *)
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],1Gus Wiseman, Dec 31 2020 *)

\\ 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]))}

T(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319254(n,i).

Sum_{k=1..n} k * T(n,k) = A326396(n). - Alois P. Heinz, Sep 11 2019

cp's OEIS Frontend

A316651 Number of series-reduced rooted trees with n leaves spanning an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions