|
| |
|
|
A114494
|
|
Triangle read by rows: T(n,k) is number of hill-free Dyck paths of semilength n and having k returns to the x-axis. (A Dyck path is said to be hill-free if it has no peaks at level 1).
|
|
1
| |
|
|
0, 1, 2, 5, 1, 14, 4, 42, 14, 1, 132, 48, 6, 429, 165, 27, 1, 1430, 572, 110, 8, 4862, 2002, 429, 44, 1, 16796, 7072, 1638, 208, 10, 58786, 25194, 6188, 910, 65, 1, 208012, 90440, 23256, 3808, 350, 12, 742900, 326876, 87210, 15504, 1700, 90, 1, 2674440, 1188640
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| Row 1 contains one term; row n contains floor(n/2) terms (n>=2). Row sums are the Fine numbers (A000957). Column 1 yields the Catalan numbers (n>=2). Sum(k*T(n,k),k=1..floor(n/2)) = A114495(n)
|
|
|
REFERENCES
| E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241, 2001, 241-265.
|
|
|
FORMULA
| T(n, k)=(k/(n-k))binomial(2n-2k, n-2k) (1<=k<=floor(n/2)). G.f.=1/(1-tz^2*C^2)-1, where C=[1-sqrt(1-4z)]/(2z) is the Catalan function.
|
|
|
EXAMPLE
| T(5,2)=4 because we have UUD(D)UUDUD(D), UUD(D)UUUDD(D), UUDUD(D)UUD(D) and UUUDD(D)UUD(D), where U=(1,1), D=(1,-1) (returns to the axis are shown between parentheses).
Triangle starts:
0;
1;
2;
5,1;
14,4;
42,14,1;
132,48,6;
429,165,27,1
|
|
|
MAPLE
| T:=proc(n, k) if k<=floor(n/2) then k*binomial(2*n-2*k, n-2*k)/(n-k) else 0 fi end: 0; for n from 2 to 15 do seq(T(n, k), k=1..floor(n/2)) od; # yields sequence in triangular form
|
|
|
CROSSREFS
| Cf. A000957, A000108, A114495.
Sequence in context: A089618 A156067 A101920 * A118964 A073187 A138159
Adjacent sequences: A114491 A114492 A114493 * A114495 A114496 A114497
|
|
|
KEYWORD
| nonn,tabf
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 01 2005
|
| |
|
|
