login
A265165
a(n) = sum of the n-th column of the array A265163(n,k). See Comments for more details.
6
1, 0, 1, 2, 7, 32, 179, 1182, 8993, 77440, 744425, 7901410, 91774375, 1157782560, 15764338315, 230416499390, 3598316747905, 59792454064640, 1053360827319185, 19610513077334850, 384703418451703175, 7931544941793536800, 171459202078545968675, 3877969156687438765150
OFFSET
0,4
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
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);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
a(n-j)*binomial(n-2, j-2)*(j-1)!, j=2..n))
end:
seq(a(n), n=0..23); # Alois P. Heinz, Jul 03 2023
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
KEYWORD
nonn
AUTHOR
Cyril Banderier, Dec 07 2015; revised Feb 06 2017
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Jul 03 2023
STATUS
approved