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

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A265165 a(n) = sum of the n-th column of the array A265163(n,k). See Comments for more details. 5
0, 1, 2, 7, 32, 179, 1182, 8993, 77440, 744425, 7901410, 91774375, 1157782560, 15764338315, 230416499390, 3598316747905, 59792454064640, 1053360827319185, 19610513077334850, 384703418451703175, 7931544941793536800, 171459202078545968675, 3877969156687438765150 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,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 A265163.

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 present sequence (i.e. this counts the permutations of size n in any B(k)).

LINKS

Table of n, a(n) for n=1..23.

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

Cyril Banderier, Florian Luca, On the period mod m of polynomially-recursive sequences: a case study, arXiv:1903.01986 [math.NT], 2019.

FORMULA

a(n+2) = 2n*a(n+1) - (n^2-n-1)*a(n) if n>0.

E.g.f.: -1 + (w * (1 - x)^(1 - w) - (1 - w) * (1 - x)^w) / sqrt(5) where w = (1 + sqrt(5))/2. - Michael Somos, Jan 27 2017

E.g.f. A(x) satisfies 0 == 1 + A(x) - (1 - x)^2 * A''(x). - Michael Somos, Jan 27 2017

0 = a(n)*(+4*a(n+1) + 2*a(n+2) - 6*a(n+3) + a(n+4)) + a(n+1)*(+4*a(n+1) + 6*a(n+2) - 4*a(n+3)) + a(n+2)*(+3*a(n+2)) if n>0. - Michael Somos, Jan 27 2017

a(n) ~ n! * (1 + 1/sqrt(5)) / (2 * Gamma((sqrt(5)-1)/2) * n^((3-sqrt(5))/2)). - Vaclav Kotesovec, Jan 20 2019

a(n) = (-1)^(n+1) * Sum_{i=1..n+1} A008275(n+1,i) * A001519(i-1). - Max Alekseyev, Dec 05 2020

EXAMPLE

G.f. = x^2 + 2*x^3 + 7*x^4 + 32*x^5 + 179*x^6 + 1182*x^7 + 8993*x^8 + ...

The basis permutations of size 2 are 21 thus a(2)=1.

The basis permutations of size 3 are 312 and 321 thus a(3)=2.

The basis permutations of size 4 are 2143, 4123, 4132, 4213, 4231, 4312, 4321, thus a(4)=7.

MAPLE

gfun[rectoproc]({(n^2+3*n+1)*a(n)+(-2*n-4)*a(n+1)+a(n+2), a(0)=0, a(1)=0, a(2)=1}, a(n), remember);

MATHEMATICA

a[ n_] := If[ n < 1, 0, With[ {w = (1 + Sqrt[5])/2}, n! SeriesCoefficient[ w (1 - x)^(1 - w) - (1 - w) (1 - x)^w, {x, 0, n}]/Sqrt[5] // Simplify]]; (* Michael Somos, Jan 27 2017 *)

RecurrenceTable[{a[n+2] == 2 n*a[n+1] - (n^2 - n - 1)*a[n], a[1] == 0, a[2] == 1}, a, {n, 1, 25}] (* Vaclav Kotesovec, Jan 20 2019 *)

PROG

(PARI) {a(n) = my(A); if( n<3, n==2, A = vector(n); A[2] = 1; for(k = 1, n-2, A[k + 2] = 2*k*A[k + 1] - (k^2 - k - 1)*A[k]); A[n])}; /* Michael Somos, Jan 27 2017 */

(PARI) {a(n) = my(w); if( n<1, 0, w = quadgen(5); n! * polcoeff( imag( w * (1 - x + x * O(x^n))^(1 - w) ), n))}; /* Michael Somos, Jan 27 2017 */

CROSSREFS

Cf. A265163, A265164.

Sequence in context: A190123 A006014 A121555 * A351813 A301465 A097900

Adjacent sequences:  A265162 A265163 A265164 * A265166 A265167 A265168

KEYWORD

nonn

AUTHOR

Cyril Banderier, Dec 07 2015; revised 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 26 04:47 EST 2022. Contains 358353 sequences. (Running on oeis4.)