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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A101431 Triangle read by rows: T(n,k) is number of noncrossing trees with n edges and having k nonroot branch nodes. 2
1, 3, 9, 3, 27, 28, 81, 174, 18, 243, 900, 285, 729, 4185, 2703, 135, 2187, 18144, 19908, 3024, 6561, 74844, 125496, 38640, 1134, 19683, 297432, 711018, 369696, 32886, 59049, 1148175, 3725190, 2943090, 528930, 10206, 177147, 4330260, 18379548, 20588040, 6228585, 363528 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Row n contains ceiling(n/2) terms.

Row sums yield the ternary numbers (A001764).

The average number of nonroot branch nodes over all noncrossing trees with n edges is 7n(n-1)(n-2)/(3(3n-1)(3n-2)) ~ 7n/27 (see A045737).

LINKS

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

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) = (1/n)binomial(n, k)*Sum_{i=0..min(k, n-1-2k)} 3^(n-1-k-2i)*binomial(k, i)binomial(n-k, k+i+1), 0 <= k <= ceiling(n/2)-1.

G.f.: G=G(t, z) satisfies tzG^3 - (1 + 3tz - 3z)G + 1 + 2tz - 2z = 0.

EXAMPLE

T(2,0)=3 because /_, _\ and /\ have no nonroot branchnodes.

Triangle begins:

    1;

    3;

    9,    3;

   27,   28;

   81,  174,   18;

  243,  900,  285;

  729, 4185, 2703, 135;

  ...

MAPLE

T:= proc(n, k) if k=0 then 3^(n-1) else (1/n)*binomial(n, k)*sum(3^(n-1-k-2*i)*binomial(k, i)*binomial(n-k, k+i+1), i=0..min(k, n-1-2*k)) fi end: for n from 1 to 12 do seq(T(n, k), k=0..ceil(n/2)-1) od; # yields sequence in triangular form

MATHEMATICA

t[n_, k_] := (1/n)*Binomial[n, k]*Sum[3^(n - 1 - k - 2i)*Binomial[k, i]*Binomial[n - k, k + i + 1], {i, 0, Min[k, n - 1 - 2k]}]; Table[t[n, k], {n, 1, 12}, {k, 0, Ceiling[n/2] - 1}] // Flatten (* Jean-Fran├žois Alcover, Jan 21 2013, after Maple *)

PROG

(PARI)

T(n, k)={binomial(n, k)*sum(i=0, min(k, n-1-2*k), 3^(n-1-k-2*i)*binomial(k, i)*binomial(n-k, k+i+1))/n}

for(n=1, 10, for(k=0, ceil(n/2)-1, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 17 2017

CROSSREFS

Cf. A001764, A045737.

Sequence in context: A010259 A255583 A120429 * A120982 A293634 A125143

Adjacent sequences:  A101428 A101429 A101430 * A101432 A101433 A101434

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Jan 17 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 April 21 20:41 EDT 2019. Contains 322328 sequences. (Running on oeis4.)