A265163 - OEIS

%I #53 Nov 11 2019 00:41:34

%S 1,0,2,1,0,0,6,8,1,0,0,0,24,58,18,1,0,0,0,0,120,444,244,32,1,0,0,0,0,

%T 0,720,3708,3104,700,50,1,0,0,0,0,0,0,5040,33984,39708,13400,1610,72,

%U 1,0,0,0,0,0,0,0,40320,341136,525240,244708,43320,3206,98,1

%N Array of basis permutations, seen as a triangle read by rows: Row k (k >= 0) gives the values of b(n, k) = number of permutations of size n (2 <= n <= 2(k+1)) in the permutation basis B(k) (see Comments for further details).

%C A right-jump in a permutation consists of taking an element and moving it somewhere to its right.

%C The set P(k) of permutations reachable from the identity after at most k right-jumps is a permutation-pattern avoiding set: it coincides with the set of permutation avoiding a set of patterns.

%C We define B(k) to be the smallest such set of "forbidden patterns" (the permutation pattern community calls such a set a "basis" for P(k), and its elements can be referred to as "right-jump basis permutations").

%C The number b(n,k) of permutations of size n in B(k) is given by the array in the present sequence.

%C The row sums give the sequence A265164 (i.e. this counts the permutations of any size in the basis B(k)).

%C The column sums give the sequence A265165 (i.e. this counts the permutations of size n in any B(k)).

%H Cyril Banderier, Jean-Luc Baril, Céline Moreira Dos Santos, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/rightjump.pdf">Right jumps in permutations</a>, Permutation Patterns 2015.

%e The number b(n, k) of basis permutations of length n where 2<=n<=11.

%e k\n |  2  3  4   5   6    7    8     9     10      11  |  #B_k

%e 0   |  1                                               |     1

%e 1   |  0  2  1                                         |     3

%e 2   |  0  0  6   8   1                                 |    15

%e 3   |  0  0  0  24  58   18    1                       |   101

%e 4   |  0  0  0   0 120  444  244    32      1          |   841

%e 5   |  0  0  0   0   0  720 3708  3104    700      50  |  8232

%e 6   |  0  0  0   0   0    0 5040 33984  39708   13400  | 78732

%e ----+--------------------------------------------------+------

%e Sum |  1  2  7  32 179 1182 8993 77440 744425 7901410  |

%e ----+--------------------------------------------------+------

%Y Cf. A265164 (row sums B(k)), A265165 (column sums).

%K nonn,tabf

%O 0,3

%A _Cyril Banderier_, Dec 07 2015, with additional comments added Feb 06 2017.