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,6

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

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).

Example

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;

Crossrefs

Main diagonal gives A006902.

Row sums give A000680.

Cf. A267479, A267532.

Sequence in context: A184180 A256069 A356652 * A099221 A200415 A200418

Adjacent sequences: A267477 A267478 A267479 * A267481 A267482 A267483

Keyword

nonn,tabl

Author

Alois P. Heinz, Jan 15 2016

Status

approved