|
|
A135306
|
|
Triangle read by rows: T(n,k) = the number of Dyck paths of semilength n with k UDDU's.
|
|
3
|
|
|
1, 1, 2, 4, 1, 9, 5, 23, 17, 2, 63, 54, 15, 178, 177, 69, 5, 514, 594, 273, 49, 1515, 1997, 1056, 280, 14, 4545, 6698, 4077, 1308, 168, 13827, 22487, 15545, 5745, 1140, 42, 42540, 75701, 58377, 24695, 6105, 594, 132124, 255455, 216864, 103862, 29810
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Row 0 has 1 term; row n (n >= 1) has ceiling(n/2) terms.
Row sums yield the Catalan numbers (A000108).
T(2n+1, n) = binomial(2n,n)/(n+1) (the Catalan numbers, A000108). (End)
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = (1/n)*binomial(n,k)*Sum_{j=k..floor((n-1)/2)} (-1)^(j-k)*binomial(n-k, j-k)*binomial(2n-3j, n-j+1).
G.f.: G = G(t,z) satisfies z*G^3 - ((1-t)*z+1)*G^2 + (1+2*(1-t)*z)*G - (1-t)*z = 0. (End)
|
|
EXAMPLE
|
Triangle begins:
1;
1;
2;
4, 1;
9, 5;
23, 17, 2;
63, 54, 15;
178, 177, 69, 5;
514, 594, 273, 49;
1515, 1997, 1056, 280, 14;
4545, 6698, 4077, 1308, 168;
...
T(4,1) = 5 because we have U(UDDU)DUD, U(UDDU)UDD, UU(UDDU)DD, UDU(UDDU)D and UUD(UDDU)D (the UDDU's are shown between parentheses).
|
|
MAPLE
|
A135306 := proc(n, k) if n =0 then 1 ; else add((-1)^(j-k)*binomial(n-k, j-k)*binomial(2*n-3*j, n-j+1), j=k..floor((n-1)/2)) ; %*binomial(n, k)/n ; fi ; end: for n from 0 to 20 do for k from 0 to max(0, (n-1)/2) do printf("%a, ", A135306(n, k)) ; od: od: # R. J. Mathar, Dec 08 2007
T:=proc(n, k) options operator, arrow: binomial(n, k)*(sum((-1)^(j-k)*binomial(n-k, j-k)*binomial(2*n-3*j, n-j+1), j=k..floor((1/2)*n-1/2)))/n end proc: 1; for n to 13 do seq(T(n, k), k=0..ceil((n-2)*1/2)) end do; # yields sequence in triangular form; Emeric Deutsch, Dec 15 2007
|
|
MATHEMATICA
|
T[n_, k_] := Binomial[n, k]*Sum[(-1)^(j-k)*Binomial[n-k, j-k]*Binomial[2*n - 3*j, -j+n+1], {j, k, (n-1)/2}]/n; T[0, 0] = 1; Table[T[n, k], {n, 0, 13}, {k, 0, If[n == 0, 0, Quotient[n-1, 2]]}] // Flatten (* Jean-François Alcover, Nov 27 2014, after Emeric Deutsch *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|