A047921 Triangle of numbers a(n,k) = number of permutations on n letters containing k 3-sequences (n >= 0, 0<=k<=max(0,n-2)).

1, 1, 2, 5, 1, 21, 2, 1, 106, 11, 2, 1, 643, 62, 12, 2, 1, 4547, 406, 71, 13, 2, 1, 36696, 3046, 481, 80, 14, 2, 1, 332769, 25737, 3708, 559, 89, 15, 2, 1, 3349507, 242094, 32028, 4414, 640, 98, 16, 2, 1, 37054436, 2510733, 306723, 38893, 5164, 724, 107, 17, 2, 1

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• tabf
• nice
• easy

Examples

			Triangle begins:
       1;
       1;
       2;
       5,     1;
      21,     2,    1;
     106,    11,    2,   1;
     643,    62,   12,   2,  1;
    4547,   406,   71,  13,  2,  1;
   36696,  3046,  481,  80, 14,  2, 1;
  332769, 25737, 3708, 559, 89, 15, 2, 1;
  ...
		

Links

• J. Riordan, Permutations without 3-sequences, Bull. Amer. Math. Soc., 51 (1945), 745-748.

Crossrefs

Columns give A002628, A002629, A002630.

Row sums give A000142.

Formula

Riordan gives a recurrence.

Extensions

Edited and extended by Max Alekseyev, Sep 05 2010

a(0,0) = a(1,0) = 1 prepended by Alois P. Heinz, Apr 20 2021