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

Links

Table of n, a(n) for n=0..56.

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

Formula

Riordan gives a recurrence.

Example

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

Crossrefs

Columns give A002628, A002629, A002630.

Row sums give A000142.

Sequence in context: A120294 A186766 A343535 * A242783 A177250 A102786

Adjacent sequences: A047918 A047919 A047920 * A047922 A047923 A047924

Keyword

nonn,tabf,nice,easy

Author

N. J. A. Sloane

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

Status

approved