A267480 Number T(n,k) of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 5, 0, 1, 42, 47, 0, 1, 351, 1527, 641, 0, 1, 3113, 43910, 54987, 11389, 0, 1, 29003, 1302660, 3844840, 2059147, 248749, 0, 1, 280220, 40970298, 265777225, 285588543, 82025038, 6439075, 0, 1, 2782475, 1364750889, 19104601915, 37783672691, 19773928713, 3507289363, 192621953

Offset: 0

Author

Alois P. Heinz, Jan 15 2016

Keywords

• nonn
• tabl

Examples

			Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,      5;
  0, 1,     42,       47;
  0, 1,    351,     1527,       641;
  0, 1,   3113,    43910,     54987,     11389;
  0, 1,  29003,  1302660,   3844840,   2059147,   248749;
  0, 1, 280220, 40970298, 265777225, 285588543, 82025038, 6439075;
		

Links

• Alois P. Heinz, Rows n = 0..18, 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

Main diagonal gives A006902.

Row sums give A000680.

Cf. A267479, A267532.

Formula

T(n,0) = A267479(n,0), T(n,k) = A267479(n,k) - A267479(n,k-1) for k>0.

Sum_{k=0..n-1} T(n,k) = A267532(n).