

A033820


Triangle read by rows: T(k,j) = ((2*j+1)/(k+1))*binomial(2*j,j)*binomial(2*k2*j,kj).


1



1, 1, 3, 2, 4, 10, 5, 9, 15, 35, 14, 24, 36, 56, 126, 42, 70, 100, 140, 210, 462, 132, 216, 300, 400, 540, 792, 1716, 429, 693, 945, 1225, 1575, 2079, 3003, 6435, 1430, 2288, 3080, 3920, 4900, 6160, 8008, 11440, 24310, 4862, 7722, 10296, 12936, 15876, 19404
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

f(n,k) = 2^{n2(k2)}sum(T(k2,j)*binomial(n+2*(k2j),2*(k2j)),j=0..k2) is the number of length n kary strings (k >= 2) which avoid a rising triple (pattern 123) or any other given 3letter permutation pattern.
Row sums are the powers of 4. This is explained by a simple statistic on the 4^n lattice paths of length 2n formed from upsteps U=(1,1) and downsteps D=(1,1). For such a path, define X = number of upsteps that lie above ground level (GL), the horizontal line through the initial vertex, and before the last vertex at GL. For UDDUUUUDDU for instance, the last vertex at GL follows the fourth step, and so X = 1. T(n,k) is the number of these paths with X=nk. For example, T(2,1)=4 counts UDUU, UDDU, UDDD, DUUD because each has nk=1 upsteps above GL and before the last vertex at GL.  David Callan, Nov 21 2011


LINKS

Table of n, a(n) for n=0..50.
Alexander Burstein, Enumeration of words with forbidden patterns, Ph.D. thesis, University of Pennsylvania, 1998.
Ira Gessel, Super ballot numbers, J. Symbolic Computation 14 (1992), 179194.
Walter Shur, Two GameSet Inequalities, J. Integer Seqs., Vol. 6, 2003.


FORMULA

T(k,0) = binomial(2*k, k)/(k+1), the kth Catalan number; T(k,k) = binomial(2*(k+1),k+1)/2, half the (k+1)st central binomial coefficient sum of entries in row k (over j) = 2^{2*(k1)}
T(k,j) = sum(C(ki)D(i), i=0..j), C(i) = binomial(2*i,i)/(i+1), D(i) = binomial(2*i,i).
G.f.: 2/(14*x*y+sqrt((14*x)*(14*x*y))).  Vladeta Jovovic, Dec 14 2003


EXAMPLE

{1},
{1, 3},
{2, 4, 10},
{5, 9, 15, 35},
{14, 24, 36, 56, 126},
{42, 70, 100, 140, 210, 462},
{132, 216, 300, 400, 540, 792, 1716},
...


CROSSREFS

Cf. A000108, A000984, A000302.
Essentially a reflected version of A078817.
Sequence in context: A338243 A338246 A084793 * A095259 A260596 A265353
Adjacent sequences: A033817 A033818 A033819 * A033821 A033822 A033823


KEYWORD

nonn,tabl


AUTHOR

Alexander Burstein


EXTENSIONS

More terms from Vladeta Jovovic, Dec 10 2003


STATUS

approved



