|
|
A265163
|
|
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).
|
|
3
|
|
|
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, 0, 720, 3708, 3104, 700, 50, 1, 0, 0, 0, 0, 0, 0, 5040, 33984, 39708, 13400, 1610, 72, 1, 0, 0, 0, 0, 0, 0, 0, 40320, 341136, 525240, 244708, 43320, 3206, 98, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A right-jump in a permutation consists of taking an element and moving it somewhere to its right.
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.
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").
The number b(n,k) of permutations of size n in B(k) is given by the array in the present sequence.
The row sums give the sequence A265164 (i.e. this counts the permutations of any size in the basis B(k)).
The column sums give the sequence A265165 (i.e. this counts the permutations of size n in any B(k)).
|
|
LINKS
|
|
|
EXAMPLE
|
The number b(n, k) of basis permutations of length n where 2<=n<=11.
k\n | 2 3 4 5 6 7 8 9 10 11 | #B_k
0 | 1 | 1
1 | 0 2 1 | 3
2 | 0 0 6 8 1 | 15
3 | 0 0 0 24 58 18 1 | 101
4 | 0 0 0 0 120 444 244 32 1 | 841
5 | 0 0 0 0 0 720 3708 3104 700 50 | 8232
6 | 0 0 0 0 0 0 5040 33984 39708 13400 | 78732
----+--------------------------------------------------+------
Sum | 1 2 7 32 179 1182 8993 77440 744425 7901410 |
----+--------------------------------------------------+------
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|