A319369 -id:A319369

Search: a319369 -id:a319369

Displaying 1-3 of 3 results found.

page 1

A316651

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

+10
30

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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

LINKS

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

FORMULA

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)

EXAMPLE

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).

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)):

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

MATHEMATICA

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 *)

PROG

(PARI) \\ 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

CROSSREFS

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

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

Row sums of A319376.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jul 09 2018

EXTENSIONS

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

STATUS

approved

A319254

Array read by antidiagonals: T(n,k) is the number of series-reduced rooted trees with n leaves of k colors.

+10
11

1, 2, 1, 3, 3, 2, 4, 6, 10, 5, 5, 10, 28, 40, 12, 6, 15, 60, 156, 170, 33, 7, 21, 110, 430, 948, 785, 90, 8, 28, 182, 965, 3396, 6206, 3770, 261, 9, 36, 280, 1890, 9376, 28818, 42504, 18805, 766, 10, 45, 408, 3360, 21798, 97775, 256172, 301548, 96180, 2312

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Not all colors need to be used.

See table 2.3 in the Johnson reference.

LINKS

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

Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. South Carolina, 2012.

EXAMPLE

Array begins:

==================================================================

n\k| 1 2 3 4 5 6 7

---+--------------------------------------------------------------

1 | 1 2 3 4 5 6 7 ...

2 | 1 3 6 10 15 21 28 ...

3 | 2 10 28 60 110 182 280 ...

4 | 5 40 156 430 965 1890 3360 ...

5 | 12 170 948 3396 9376 21798 44856 ...

6 | 33 785 6206 28818 97775 269675 642124 ...

7 | 90 3770 42504 256172 1068450 3496326 9632960 ...

8 | 261 18805 301548 2357138 12081605 46897359 149491104 ...

9 | 766 96180 2195100 22253672 140160650 645338444 2379859608 ...

...

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)):

seq(seq(A(n, 1+d-n), n=1..d), d=1..12); # Alois P. Heinz, Sep 17 2018

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]];

Table[A[n, 1 + d - n], {d, 1, 12}, {n, 1, d}] // Flatten (* Jean-François Alcover, Sep 11 2019, after Alois P. Heinz *)

PROG

(PARI) \\ here R(n, k) gives k'th column as a vector.

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}

{my(T=Mat(vector(8, k, R(8, k)~))); for(n=1, #T~, print(T[n, ]))} \\ Andrew Howroyd, Sep 15 2018

CROSSREFS

Columns 1..5 are A000669, A050381, A220823, A220824, A220825.

Main diagonal is A319369.

Cf. A141610, A242249, A255517, A256064, A256068, A319376.

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Sep 15 2018

STATUS

approved

A319580

Number of binary rooted trees with n leaves of n colors and all non-leaf nodes having out-degree 2.

+10
2

1, 3, 18, 215, 3600, 80136, 2213036, 73068543, 2806959015, 123002168300, 6055381161852, 330885794632536, 19872950226273053, 1301261803764756855, 92259974680854975000, 7041606755629152575055, 575638367425376279620662, 50180725346542105445190603

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Not all of the n colors need to be used.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..352

V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012.

MAPLE

A:= proc(n, k) option remember; `if`(n<2, k*n, `if`(n::odd, 0,

(t-> t*(1-t)/2)(A(n/2, k)))+add(A(i, k)*A(n-i, k), i=1..n/2))

end:

a:= n-> A(n$2):

seq(a(n), n=1..20); # Alois P. Heinz, Sep 23 2018

MATHEMATICA

A[n_, k_] := A[n, k] = If[n < 2, k n, If[OddQ[n], 0, Function[t, t(1-t) / 2][A[n/2, k]]] + Sum[A[i, k] A[n - i, k], {i, 1, n/2}]];

a[n_] := A[n, n];

Array[a, 20] (* Jean-François Alcover, Apr 10 2020, after Alois P. Heinz *)

PROG

(PARI) a(n)={my(v=vector(n)); v[1]=n; for(n=2, n, v[n]=sum(j=1, (n-1)\2, v[j]*v[n-j]) + if(n%2, 0, binomial(v[n/2]+1, 2))); v[n]} \\ Andrew Howroyd, Sep 23 2018

CROSSREFS

Main diagonal of A319539.

Cf. A319369, A319541.

KEYWORD

nonn

AUTHOR

Andrew Howroyd, Sep 23 2018

STATUS

approved

page 1

Search completed in 0.009 seconds