A267479 Number A(n,k) of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 6, 1, 0, 1, 1, 6, 43, 1, 0, 1, 1, 6, 90, 352, 1, 0, 1, 1, 6, 90, 1879, 3114, 1, 0, 1, 1, 6, 90, 2520, 47024, 29004, 1, 0, 1, 1, 6, 90, 2520, 102011, 1331664, 280221, 1, 0, 1, 1, 6, 90, 2520, 113400, 5176504, 41250519, 2782476, 1, 0

Offset: 0

Author

Alois P. Heinz, Jan 15 2016

Keywords

• nonn
• tabl

Examples

			Square array A(n,k) begins:
  1, 1,     1,       1,       1,       1,       1, ...
  0, 1,     1,       1,       1,       1,       1, ...
  0, 1,     6,       6,       6,       6,       6, ...
  0, 1,    43,      90,      90,      90,      90, ...
  0, 1,   352,    1879,    2520,    2520,    2520, ...
  0, 1,  3114,   47024,  102011,  113400,  113400, ...
  0, 1, 29004, 1331664, 5176504, 7235651, 7484400, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..30, flattened
• Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, arXiv:1505.01389, 2015
• Shalosh B. Ekhad and Doron Zeilberger, The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r, 2014

Crossrefs

Columns k=0-4 give: A000007, A000012, A220097, A266734, A266735.

Main diagonal gives A000680.

First lower diagonal gives A267532.

Cf. A214015, A267480.

Formula

A(n,k) = Sum_{i=0..k} A267480(n,i).