login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A102892 Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges in which the number of edges from the root to the first branch point is k. 3
1, 0, 1, 1, 0, 2, 5, 3, 0, 4, 25, 16, 6, 0, 8, 130, 83, 32, 12, 0, 16, 700, 442, 166, 64, 24, 0, 32, 3876, 2420, 884, 332, 128, 48, 0, 64, 21945, 13566, 4840, 1768, 664, 256, 96, 0, 128, 126500, 77539, 27132, 9680, 3536, 1328, 512, 192, 0, 256 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

The statistic "number of edges from the root to the first branchpoint" is equal to 0 if root is a branchpoint and it is equal to the total number of edges if there is no branchpoint.

Row n contains n+1 terms.

Row sums yield the ternary numbers (A001764).

Column 0 yields A102893.

Column 1 yields A030983.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..1274

M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301-313, 1998.

FORMULA

T(n, 0) = 5*binomial(3n-1, n-2)/(3n-1) for n > 0.

T(n, k) = [2^(k-1)/(n-k+1)]binomial(3n-3k+1, n-k)-[2^k/(n-k)]binomial(3n-3k-2, n-k-1) for 0 < k < n.

T(n, n) = 2^(n-1) (n > 0).

G.f.: (1/2)*g(2-g) + g^2*(1-2*z)/(2*(1-2*t*z)), where g = 1 + z*g^3 is the g.f. of the ternary numbers (A001764).

EXAMPLE

T(2,0)=1 because we have /\ and T(2,2)=2 because we have /_ and _\.

Triangle starts:

    1;

    0,  1;

    1,  0,  2;

    5,  3,  0,  4;

   25, 16,  6,  0, 8;

  130, 83, 32, 12, 0, 16;

  ...

MAPLE

T:=proc(n, k) if n=0 and k=0 then 1 elif k=0 then 5*binomial(3*n-1, n-2)/(3*n-1) elif k<n then (2^(k-1)/(n-k+1))*binomial(3*n-3*k+1, n-k)-(2^k/(n-k))*binomial(3*n-3*k-2, n-k-1) elif k=n then 2^(n-1) else 0 fi end: for n from 0 to 10 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

MATHEMATICA

T[n_, k_] := Which[n == 0 && k == 0, 1, k == 0, 5*Binomial[3n - 1, n - 2]/(3n - 1), k<n, (2^(k-1)/(n - k + 1))*Binomial[3n - 3k + 1, n - k] - (2^k/(n-k))*Binomial[3n - 3k - 2, n - k - 1], k == n, 2^(n-1), True, 0];

Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-Fran├žois Alcover, Jul 06 2018, from Maple *)

PROG

(PARI)

T(n, k) = {if(k==0, if(n==0, 1, 5*binomial(3*n-1, n-2)/(3*n-1)), if(n<=k, if(n==k, 2^(n-1), 0), 2^(k-1)*binomial(3*n-3*k+1, n-k)/(n-k+1) - 2^k*binomial(3*n-3*k-2, n-k-1)/(n-k)))}

for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 06 2017

CROSSREFS

Cf. A001764, A102893, A030983.

Sequence in context: A130280 A160127 A011035 * A132898 A265318 A279536

Adjacent sequences:  A102889 A102890 A102891 * A102893 A102894 A102895

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Jan 16 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 25 19:13 EDT 2019. Contains 323576 sequences. (Running on oeis4.)