|
|
A033877
|
|
Triangular array read by rows associated with Schroeder numbers: T(1,k) = 1; T(n,k) = 0 if k < n; T(n,k) = T(n,k-1) + T(n-1,k-1) + T(n-1,k).
|
|
21
|
|
|
1, 1, 2, 1, 4, 6, 1, 6, 16, 22, 1, 8, 30, 68, 90, 1, 10, 48, 146, 304, 394, 1, 12, 70, 264, 714, 1412, 1806, 1, 14, 96, 430, 1408, 3534, 6752, 8558, 1, 16, 126, 652, 2490, 7432, 17718, 33028, 41586, 1, 18, 160, 938, 4080, 14002, 39152, 89898, 164512, 206098
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
A106579 is in some ways a better version of this sequence, but since this was entered first it will be the main entry for this triangle.
The diagonals of this triangle are self-convolutions of the main diagonal A006318: 1, 2, 6, 22, 90, 394, 1806, ... . - Philippe Deléham, May 15 2005
Note that for the terms T(n,k) of this triangle n indicates the column and k the row.
The triangle sums, see A180662, link Schroeder's triangle with several sequences, see the crossrefs. The mirror of this triangle is A080247.
Quite surprisingly the Kn1p sums, p >= 1, are all related to A026003 and crystal ball sequences for n-dimensional cubic lattices (triangle offset is 0): Kn11(n) = A026003(n), Kn12(n) = A026003(n+2) - 1, Kn13(n) = A026003(n+4) - A005408(n+3), Kn14(n) = A026003(n+6) - A001844(n+4), Kn15(n) = A026003(n+8) - A001845(n+5), Kn16(n) = A026003(n+10) - A001846(n+6), Kn17(n) = A026003(n+12) - A001847(n+7), Kn18(n) = A026003(n+14) - A001848(n+8), Kn19(n) = A026003(n+16) - A001849(n+9), Kn110(n) = A026003(n+18) - A008417(n+10), Kn111(n) = A026003(n+20) - A008419(n+11), Kn112(n) = A026003(n+22) - A008421(n+12). (End)
T(n,k) is the number of normal semistandard Young tableaux with two columns, one of height k and one of height n. The recursion can be seen by performing jeu de taquin deletion on all instances of the smallest value. (If there are two instances of the smallest value, jeu de taquin deletion will always shorten the right column first and the left column second.) - Jacob Post, Jun 19 2018
|
|
LINKS
|
G. Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). (Annotated scanned copy)
|
|
FORMULA
|
As an upper right triangle: a(n, k) = a(n, k-1) + a(n-1, k-1) + a(n-1, k) if k >= n >= 0 and a(n, k) = 0 otherwise.
G.f.: Sum T(n, k)*x^n*y^k = (1-x*y-(x^2*y^2-6*x*y+1)^(1/2)) / (x*(2*y+x*y-1+(x^2*y^2-6*x*y+1)^(1/2))). - Vladeta Jovovic, Feb 16 2003
Another version of A000007 DELTA [0, 2, 1, 2, 1, 2, 1, 2, 1, 2, ...] = 1, 1, 0, 1, 2, 0, 1, 4, 6, 0, 1, 6, 16, 22, 0, 1, ..., where DELTA is Deléham's operator defined in A084938.
(t(n, k) as a lower triangle)
t(n, k) = t(n, k-1) + t(n-1, k-1) + t(n-1, k) with t(n, 1) = 1.
Sum_{k=1..n-1} t(n, k) = A238112(n), n > 1.
Sum_{k=1..n-1} (-1)^(k-1)*t(n, k) = (-1)^n*A001003(n-1), n > 1.
Sum_{k=1..n} (-1)^(k-1)*t(n, k) = A080243(n-1).
Sum_{k=1..floor((n+1)/2)} t(n-k+1, k) = A026003(n-1). (End)
|
|
EXAMPLE
|
Triangle starts:
1;
1, 2;
1, 4, 6;
1, 6, 16, 22;
1, 8, 30, 68, 90;
1, 10, 48, 146, 304, 394;
1, 12, 70, 264, 714, 1412, 1806;
|
|
MAPLE
|
T := proc(n, k) option remember; if n=1 then return(1) fi; if k<n then return(0) fi; T(n, k-1)+T(n-1, k-1)+T(n-1, k) end: seq(seq(T(n, k), n = 1..k), k=1..10); # Johannes W. Meijer, Sep 22 2010, revised Jul 17 2013
|
|
MATHEMATICA
|
T[1, _]:= 1; T[n_, k_]/; (k<n):= 0; T[n_, k_]:= T[n, k]= T[n, k-1] +T[n-1, k-1] + T[n-1, k]; Table[T[k, n], {n, 15}, {k, n}]//Flatten
|
|
PROG
|
(Haskell)
a033877 n k = a033877_tabl !! n !! k
a033877_row n = a033877_tabl !! n
a033877_tabl = iterate
(\row -> scanl1 (+) $ zipWith (+) ([0] ++ row) (row ++ [0])) [1]
(Sage)
@cached_function
def prec(n, k):
if k==n: return 1
if k==0: return 0
return prec(n-1, k-1)-2*sum(prec(n, k+i-1) for i in (2..n-k+1))
return [(-1)^k*prec(n, n-k) for k in (0..n-1)]
(SageMath)
@CachedFunction
if (k<0 or k>n): return 0
elif (k==1): return 1
else: return t(n, k-1) + t(n-1, k-1) + t(n-1, k)
flatten([[t(n, k) for k in range(1, n+1)] for n in range(1, 16)]) # G. C. Greubel, Mar 23 2023
(Magma)
function t(n, k)
if k le 0 or k gt n then return 0;
elif k eq 1 then return 1;
else return t(n, k-1) + t(n-1, k-1) + t(n-1, k);
end if;
end function;
[t(n, k): k in [1..n], n in [1..12]]; // G. C. Greubel, Mar 23 2023
|
|
CROSSREFS
|
Essentially same triangle as A080247 and A080245 but with rows read in reversed order. Also essentially the same triangle as A106579.
Triangle sums (see the comments): A001003 (Row1, Row2), A026003 (Kn1p, p >= 1), A006603 (Kn21), A227504 (Kn22), A227505 (Kn23), A006603(2*n) (Kn3), A001850 (Kn4), A227506 (Fi1), A010683 (Fi2).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|