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

%I #25 May 09 2021 07:57:02

%S 1,2,12,112,1444,24086,492284,11910790,332827136,10546558146,

%T 373661603588,14636326974270,628032444609396,29296137817622902,

%U 1476092246351259964,79889766016415899270,4622371378514020301740,284719443038735430679268,18601385258191195218790756

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

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

%H Andrew Howroyd, <a href="/A316651/b316651.txt">Table of n, a(n) for n = 1..200</a>

%F From _Vaclav Kotesovec_, Sep 18 2019: (Start)

%F a(n) ~ c * d^n * n^(n-1), where d = 1.37392076830840090205551979... and c = 0.41435722857311602982846...

%F a(n) ~ 2*log(2)*A326396(n)/n. (End)

%e The a(3) = 12 trees:

%e (1(11)), (111),

%e (1(12)), (2(11)), (112),

%e (1(22)), (2(12)), (122),

%e (1(23)), (2(13)), (3(12)), (123).

%p b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))

%p end:

%p A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):

%p a:= n-> add(add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1), k=1..n):

%p seq(a(n), n=1..20); # _Alois P. Heinz_, Sep 18 2018

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

%t gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];

%t allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];

%t Table[Sum[Length[gro[m]],{m,allnorm[n]}],{n,5}]

%t (* Second program: *)

%t b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0,

%t Sum[Binomial[A[i, k] + j - 1, j] b[n - i*j, i - 1, k], {j, 0, n/i}]]];

%t A[n_, k_] := If[n < 2, n*k, b[n, n - 1, k]];

%t a[n_] := Sum[Sum[A[n, k-j]*(-1)^j*Binomial[k, j], {j, 0, k-1}], {k, 1, n}];

%t Array[a, 20] (* _Jean-François Alcover_, May 09 2021, after _Alois P. Heinz_ *)

%o (PARI) \\ here R(n,k) is A000669, A050381, A220823, ...

%o EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}

%o R(n,k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v,[0]))[n])); v}

%o seq(n)={sum(k=1, n, R(n,k)*sum(r=k, n, binomial(r,k)*(-1)^(r-k)) )} \\ _Andrew Howroyd_, Sep 14 2018

%Y Cf. A000081, A000311, A000669, A001678, A005804, A034691, A141268, A292504.

%Y Cf. A316652, A316653, A316654, A316655, A316656, A319369.

%Y Row sums of A319376.

%K nonn

%O 1,2

%A _Gus Wiseman_, Jul 09 2018

%E Terms a(9) and beyond from _Andrew Howroyd_, Sep 14 2018