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 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the 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