login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A101449
Triangle read by rows: T(n,k) is number of noncrossing trees with n edges and having k nonroot nodes of degree 1.
3
1, 1, 2, 4, 4, 4, 11, 24, 12, 8, 41, 88, 96, 32, 16, 146, 410, 440, 320, 80, 32, 564, 1752, 2460, 1760, 960, 192, 64, 2199, 7896, 12264, 11480, 6160, 2688, 448, 128, 8835, 35184, 63168, 65408, 45920, 19712, 7168, 1024, 256, 35989, 159030, 316656, 379008
OFFSET
1,3
COMMENTS
Row n contains n terms.
Row sums yield the ternary numbers (A001764).
The average number of nonroot nodes of degree 1 over all noncrossing trees with n edges is 4n(n-1)(2n+1)/(3(3n-1)(3n-2)) ~ 8n/27.
LINKS
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.
M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301-313, 1998.
FORMULA
T(n, k) = [2^k/(n-k)]*binomial(n-1, k)*Sum_{i=1..n-k} (-1)^(n-k-i)*2^(n-k-i)*binomial(n-k, i)*binomial(3i, i-1), 0 <= k < n).
T(n,k) = 2^k*binomial(n-1,k)*A030981(n-k).
EXAMPLE
T(2,0)=1 (/\); T(2,1)=2 (/_, _\ ).
Triangle begins:
1;
1, 2;
4, 4, 4;
11, 24, 12, 8;
41, 88, 96, 32, 16;
MAPLE
T:=proc(n, k) if k<n then 2^k*binomial(n-1, k)*sum((-1)^(n-k-i)*2^(n-k-i)*binomial(n-k, i)*binomial(3*i, i-1), i=1..n-k)/(n-k) else 0 fi end: for n from 1 to 10 do seq(T(n, k), k=0..n-1) od; # yields sequence in triangular form
MATHEMATICA
T[n_, k_] := If[k<n, 2^k*Binomial[n-1, k]*Sum[(-1)^(n-k-i)*2^(n-k-i)* Binomial[n-k, i]*Binomial[3*i, i-1], {i, 1, n-k}]/(n-k), 0];
Table[T[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jul 06 2018, from Maple *)
PROG
(PARI) T(n, k)={if(k<n, 2^k*binomial(n-1, k)*sum(i=1, n-k, (-1)^(n-k-i)*2^(n-k-i)*binomial(n-k, i)*binomial(3*i, i-1))/(n-k))}
for(n=1, 10, for(k=0, n-1, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 06 2017
CROSSREFS
Cf. A001764, A030981 (column 0).
Sequence in context: A260588 A107058 A332336 * A221564 A134188 A140295
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jan 17 2005
STATUS
approved