OFFSET
0,4
COMMENTS
T(n,k) (0 <= k <= n/2) is the number of dissections of a regular (n+2)-gon using k strictly disjoint diagonals (diagonals join nonconsecutive vertices and strictly disjoint means no two cross or share an endpoint).
Row n contains 1 + floor(n/2) entries. - Emeric Deutsch, Sep 18 2014
T(n,k) is the number of paths in B(n+1) that do not start with H and have k steps of weight 2 (i.e., H or u). Example: T(3,1) = 5 because the paths in B(4) that do not start with H are hhhh, hHh, hhH, uhd, hud, and udh; the last five contain exactly 1 step of weight 2. - Emeric Deutsch, Sep 18 2014
B(n) is the set of lattice paths of weight n that start in (0,0), end on the horizontal axis and never go below this axis, whose steps are of the following four kinds: h = (1,0) of weight 1, H = (1,0) of weight 2, u = (1,1) of weight 2, and d = (1,-1) of weight 1. The weight of a path is the sum of the weights of its steps. - Emeric Deutsch, Sep 18 2014
LINKS
G. C. Greubel, Rows n = 0..100 of triangle, flattened
M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306. - Emeric Deutsch, Sep 18 2014
FORMULA
T(n, k) = Narayana(n-k+2, k+1) - Narayana(n-k+1, k) where Narayana(n, k) = binomial(n, k)*binomial(n, k-1)/n is A001263.
G.f.: G=G(t,z) satisfies t*z^4*G^2 - (1 - z - 2*t*z^2 - t*z^3 + t^2*z^4)*G + 1 = 0. - Emeric Deutsch, Sep 18 2014
EXAMPLE
T(3,1) = 5 because there are 5 ways to insert a single diagonal into a pentagon.
Triangle begins:
1;
1;
1, 2;
1, 5;
1, 9, 3;
1, 14, 14;
1, 20, 40, 4;
1, 27, 90, 30;
MAPLE
eq := t*z^4*G^2-(1-z-2*t*z^2-t*z^3+t^2*z^4)*G+1 = 0: G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 18)): for n from 0 to 15 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 15 do seq(coeff(P[n], t, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form # Emeric Deutsch, Sep 18 2014
T := proc (n, k) if (1/2)*n+1/2 < k then 0 else binomial(n-k+2, k+1)*binomial(n-k+2, k)/(n-k+2)-binomial(n-k+1, k)*binomial(n-k+1, k-1)/(n-k+1) end if end proc: for n from 0 to 15 do seq(T(n, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form # Emeric Deutsch, Sep 18 2014
MATHEMATICA
Nara[n_, k_]:= Binomial[n, k]*Binomial[n, k-1]/n; T[n_, k_]:= Nara[n-k+2, k+1] - Nara[n-k+1, k]; Table[T[n, k], {n, 0, 15}, {k, 0, Floor[n/2]}]//Flatten (* G. C. Greubel, Dec 28 2019 *)
PROG
(PARI) T(n, k) = my(b=binomial); b(n-k+2, k+1)*b(n-k+2, k)/(n-k+2) - b(n-k+1, k)* b(n-k+1, k-1)/(n-k+1);
for(n=0, 15, for(k=0, n\2, print1(T(n, k), ", "))) \\ G. C. Greubel, Dec 28 2019
(Magma) B:=Binomial; T:= func< n, k | B(n-k+2, k+1)*B(n-k+2, k)/(n-k+2) - B(n-k+1, k)*B(n-k+1, k-1)/(n-k+1) >;
[T(n, k): k in [0..Floor(n/2)], n in [0..15]]; // G. C. Greubel, Dec 28 2019
(Sage)
b=binomial;
def T(n, k): return b(n-k+2, k+1)*b(n-k+2, k)/(n-k+2) - b(n-k+1, k)* b(n-k+1, k-1)/(n-k+1)
[[T(n, k) for k in (0..floor(n/2))] for n in (0..15)] # G. C. Greubel, Dec 28 2019
(GAP)
B:=Binomial;;
T:= function(n, k)
return B(n-k+2, k+1)*B(n-k+2, k)/(n-k+2) - B(n-k+1, k)*B(n-k+1, k-1)/(n-k+1);
end;
Flat(List([0..15], n-> List([0..Int(n/2)], k-> T(n, k) ))); # G. C. Greubel, Dec 28 2019
CROSSREFS
KEYWORD
easy,nonn,tabf
AUTHOR
David Callan, Mar 23 2004
STATUS
approved