login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A033820 Triangle read by rows: T(k,j) = ((2*j+1)/(k+1))*binomial(2*j,j)*binomial(2*k-2*j,k-j). 1

%I

%S 1,1,3,2,4,10,5,9,15,35,14,24,36,56,126,42,70,100,140,210,462,132,216,

%T 300,400,540,792,1716,429,693,945,1225,1575,2079,3003,6435,1430,2288,

%U 3080,3920,4900,6160,8008,11440,24310,4862,7722,10296,12936,15876,19404

%N Triangle read by rows: T(k,j) = ((2*j+1)/(k+1))*binomial(2*j,j)*binomial(2*k-2*j,k-j).

%C f(n,k) = 2^{n-2(k-2)}sum(T(k-2,j)*binomial(n+2*(k-2-j),2*(k-2-j)),j=0..k-2) is the number of length n k-ary strings (k >= 2) which avoid a rising triple (pattern 123) or any other given 3-letter permutation pattern.

%C 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=n-k. For example, T(2,1)=4 counts UDUU, UDDU, UDDD, DUUD because each has n-k=1 upsteps above GL and before the last vertex at GL. - _David Callan_, Nov 21 2011

%H Alexander Burstein, <a href="http://www.alexanderburstein.org/tiki-download_file.php?fileId=3">Enumeration of words with forbidden patterns</a>, Ph.D. thesis, University of Pennsylvania, 1998.

%H Ira Gessel, <a href="http://www.sciencedirect.com/science/article/pii/0747717192900342">Super ballot numbers</a>, J. Symbolic Computation 14 (1992), 179-194.

%H Walter Shur, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Shur/shur51.html">Two Game-Set Inequalities</a>, J. Integer Seqs., Vol. 6, 2003.

%F T(k,0) = binomial(2*k, k)/(k+1), the k-th 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*(k-1)}

%F T(k,j) = sum(C(k-i)D(i), i=0..j), C(i) = binomial(2*i,i)/(i+1), D(i) = binomial(2*i,i).

%F G.f.: 2/(1-4*x*y+sqrt((1-4*x)*(1-4*x*y))). - _Vladeta Jovovic_, Dec 14 2003

%e {1},

%e {1, 3},

%e {2, 4, 10},

%e {5, 9, 15, 35},

%e {14, 24, 36, 56, 126},

%e {42, 70, 100, 140, 210, 462},

%e {132, 216, 300, 400, 540, 792, 1716},

%e ...

%Y Cf. A000108, A000984, A000302.

%Y Essentially a reflected version of A078817.

%K nonn,tabl

%O 0,3

%A _Alexander Burstein_

%E More terms from _Vladeta Jovovic_, Dec 10 2003

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 05:14 EST 2019. Contains 329839 sequences. (Running on oeis4.)