A265164 - OEIS

%I #62 May 15 2022 05:14:25

%S 1,3,15,101,841,8283,93815,1198029,16997041,264864419,4492081151,

%T 82299283669,1618674299769,33997164987019,759059595497511,

%U 17945237236457533,447676430154815137,11748882878147100691,323494584038834863087,9322205037165367256837

%N Sum of the n-th row of the array A265163(n, k).

%C A right-jump in a permutation consists of taking an element and moving it somewhere to its right.

%C 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 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 The number b(n,k) of permutations of size n in B(k) is given by the array A265163.

%C The row sums give the present sequence (i.e. this counts the permutations of any size in the basis B(k)).

%C The column sums give the sequence A265165 (i.e. this counts the permutations of size n in any B(k)).

%H Vaclav Kotesovec, <a href="/A265164/b265164.txt">Table of n, a(n) for n = 0..200</a>

%H 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.

%e G.f. = 1 + 3*x + 15*x^2 + 101*x^3 + 841*x^4 + 8283*x^5 + 93815*x^6 + 1198029*x^7 + ...

%e The basis permutations for B(1) are 312, 321, and 2143, thus a(1)=3.

%e The basis permutations for B(2) are 4123, 4132, 4213, 4231, 4312, 4321, 21534, 21543, 31254, 32154, 31524, 31542, 32514, 32541, and 214365, thus a(2)=15.

%t a[ n_] := Module[ {A, s, F}, If[ n < 0, 0, A = 1 - x + O[x]^(2 n + 3); s = Sqrt[1 + 4 y + O[y]^(n + 2)]; F = y ((1 - 1/s) A^((1 + s)/2) + (1 + 1/s) A^((1 - s)/2))/2; Sum[ SeriesCoefficient[ SeriesCoefficient[ F, {x, 0, n + k}] (n + k)!, {y, 0, k}], {k, 2, 2 + n}]]]; (* _Michael Somos_, Jan 27 2017 *)

%o (PARI) {a(n) = my(A, s, F); if( n<0, 0, A = 1 - x + x * O(x^(2*n+2)); s = sqrt(1 + 4*y + y * O(y^(n+1))); F = y * ((1 - 1/s) * A^((1 + s)/2) + (1 + 1/s) * A^((1 - s)/2)) / 2; sum(k=2, 2+n, polcoeff( polcoeff( F, n+k) * (n+k)!, k)))}; /* _Michael Somos_, Jan 27 2017 */

%Y Cf. A265163, A265165.

%K nonn

%O 0,2

%A _Cyril Banderier_, Dec 07 2015; revised Feb 06 2017