login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

Cyril Banderier, Jean-Luc Baril, CĂ©line Moreira Dos Santos, Right jumps in permutations, Permutation Patterns 2015.

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

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

Sequence in context: A262125 A105868 A267163 * A057275 A057271 A021480

Adjacent sequences:  A265160 A265161 A265162 * A265164 A265165 A265166

KEYWORD

nonn,tabf

AUTHOR

Cyril Banderier, Dec 07 2015, with additional comments added Feb 06 2017.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 17 06:12 EST 2022. Contains 350378 sequences. (Running on oeis4.)