cp's OEIS Frontend

A265165 a(n) = sum of the n-th column of the array A265163(n,k). See Comments for more details.

%I A265165 #74 Jul 03 2023 20:20:46
%S A265165 1,0,1,2,7,32,179,1182,8993,77440,744425,7901410,91774375,1157782560,
%T A265165 15764338315,230416499390,3598316747905,59792454064640,
%U A265165 1053360827319185,19610513077334850,384703418451703175,7931544941793536800,171459202078545968675,3877969156687438765150
%N A265165 a(n) = sum of the n-th column of the array A265163(n,k). See Comments for more details.
%C A265165 A right-jump in a permutation consists of taking an element and moving it somewhere to its right.
%C A265165 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 A265165 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 A265165 The number b(n,k) of permutations of size n in B(k) is given by the array A265163.
%C A265165 The row sums give the sequence A265164 (i.e. this counts the permutations of any size in the basis B(k)).
%C A265165 The column sums give the present sequence (i.e. this counts the permutations of size n in any B(k)).
%H A265165 Alois P. Heinz, <a href="/A265165/b265165.txt">Table of n, a(n) for n = 0..450</a>
%H A265165 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.
%H A265165 Cyril Banderier, Florian Luca, <a href="https://arxiv.org/abs/1903.01986">On the period mod m of polynomially-recursive sequences: a case study</a>, arXiv:1903.01986 [math.NT], 2019.
%F A265165 a(n+2) = 2n*a(n+1) - (n^2-n-1)*a(n) if n>0.
%F A265165 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
%F A265165 E.g.f. A(x) satisfies 0 == 1 + A(x) - (1 - x)^2 * A''(x). - _Michael Somos_, Jan 27 2017
%F A265165 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
%F A265165 a(n) ~ n! * (1 + 1/sqrt(5)) / (2 * Gamma((sqrt(5)-1)/2) * n^((3-sqrt(5))/2)). - _Vaclav Kotesovec_, Jan 20 2019
%F A265165 a(n) = (-1)^(n+1) * Sum_{i=1..n+1} A008275(n+1,i) * A001519(i-1). - _Max Alekseyev_, Dec 05 2020
%e A265165 G.f. = x^2 + 2*x^3 + 7*x^4 + 32*x^5 + 179*x^6 + 1182*x^7 + 8993*x^8 + ...
%e A265165 The basis permutations of size 2 are 21 thus a(2)=1.
%e A265165 The basis permutations of size 3 are 312 and 321 thus a(3)=2.
%e A265165 The basis permutations of size 4 are 2143, 4123, 4132, 4213, 4231, 4312, 4321, thus a(4)=7.
%p A265165 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);
%p A265165 # second Maple program:
%p A265165 a:= proc(n) option remember; `if`(n=0, 1, add(
%p A265165       a(n-j)*binomial(n-2, j-2)*(j-1)!, j=2..n))
%p A265165     end:
%p A265165 seq(a(n), n=0..23);  # _Alois P. Heinz_, Jul 03 2023
%t A265165 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 *)
%t A265165 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 *)
%o A265165 (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 */
%o A265165 (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 */
%Y A265165 Cf. A000166, A000994, A001040, A265163, A265164.
%K A265165 nonn
%O A265165 0,4
%A A265165 _Cyril Banderier_, Dec 07 2015; revised Feb 06 2017
%E A265165 a(0)=1 prepended by _Alois P. Heinz_, Jul 03 2023