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