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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A126217 Triangle read by rows: T(n,k) is the number of 321-avoiding permutations of {1,2,...,n} having longest increasing subsequence of length k (1<=k<=n). 2
1, 1, 1, 0, 4, 1, 0, 4, 9, 1, 0, 0, 25, 16, 1, 0, 0, 25, 81, 25, 1, 0, 0, 0, 196, 196, 36, 1, 0, 0, 0, 196, 784, 400, 49, 1, 0, 0, 0, 0, 1764, 2304, 729, 64, 1, 0, 0, 0, 0, 1764, 8100, 5625, 1225, 81, 1, 0, 0, 0, 0, 0, 17424, 27225, 12100, 1936, 100, 1, 0, 0, 0, 0, 0, 17424, 88209 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

The row sums are the Catalan numbers (A000108). T(2n,n)=(C(n))^2=A001246(n), where the C(n) are the Catalan numbers.

Also T(n,k) = Number of Dyck paths of semilength n with midpoint height = 2*k-n. David Scambler (dscambler AT bmm.com), Nov 25 2010

REFERENCES

E. Deutsch, A. J. Hildebrand and H. S. Wilf, Longest increasing subsequences in pattern-restricted permutations, The Electronic Journal of Combinatorics, 9(2), 2003, #R12.

LINKS

Table of n, a(n) for n=1..73.

FORMULA

T(n,k)=[(2k-n+1)C(n+1,n-k)/(n+1)]^2 if floor((n+1)/2)<=k<=n; T(n,k)=0 otherwise. [N.B.: floor((n+1)/2) <= k  <=>  n/2 <= k.]

EXAMPLE

T(4,2)=4 because we have 2143, 3142, 2413 and 3412.

Triangle starts:

1;

1,1;

0,4,1;

0,4,9,1;

0,0,25,16,1;

0,0,25,81,25,1;

T(4,2)=4 because 2*2-4 = zero and Dyck 4-paths with midpoint height of zero are UUDDUUDD, UUDDUDUD, UDUDUUDD and UDUDUDUD.

MAPLE

T:=proc(n, k) if floor((n+1)/2)<=k and k<=n then ((2*k-n+1)*binomial(n+1, k+1)/(n+1))^2 else 0 fi end: for n from 1 to 13 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form

PROG

(PARI) T(n, k)=if(n<=2*k, (2*k-n+1)*binomial(n+1, n-k)\(n+1))^2  \\ [M. F. Hasler, Nov 24 2010]

CROSSREFS

Cf. A000108, A001246.

Sequence in context: A122388 A094918 A110146 * A108944 A117377 A046784

Adjacent sequences:  A126214 A126215 A126216 * A126218 A126219 A126220

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Dec 22 2006

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified April 23 17:46 EDT 2014. Contains 240946 sequences.