login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A326355 Number of permutations of length n with at most two descents. 0
1, 1, 2, 6, 23, 93, 360, 1312, 4541, 15111, 48854, 154674, 482355, 1487905, 4553684, 13857492, 41998265, 126912075, 382702050, 1152300166, 3465813071, 10416313221, 31288785152, 93950241096, 282026883573, 846449748943, 2540120998190, 7621973606682 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

Table of n, a(n) for n=0..27.

D. I. Bevan, On the growth of permutation classes, PhD thesis, The Open University, 2015.

Robert Brignall, Jakub Sliacan, Combinatorial specifications for juxtapositions of permutation classes, arXiv:1902.02705 [math.CO], 2019.

Index entries for linear recurrences with constant coefficients, signature (10,-40,82,-91,52,-12).

FORMULA

G.f: 1/(1-z) + z^2/((1-z)^2*(1-2*z)) + z^3*(1+z-4*z^2)/((1-z)^3*(1-2*z)^2*(1-3*z)).

a(n) = Sum_{k=0..3} A123125(n,k). - Alois P. Heinz, Sep 11 2019

a(n) = 3^n -n*2^n +n^2/2 -n/2. - R. J. Mathar, Sep 25 2019

EXAMPLE

For n=4, a(4) = 23 because the permutation 4321 is the only one of length 4 to have more than 2 descents.

MAPLE

b:= proc(u, o, k) option remember;

      `if`(u+o=0, 1, add(b(u-j, o+j-1, k), j=1..u)+

      `if`(k<2, add(b(u+j-1, o-j, k+1), j=1..o), 0))

    end:

a:= n-> b(n, 0$2):

seq(a(n), n=0..28);  # Alois P. Heinz, Sep 11 2019

MATHEMATICA

LinearRecurrence[{10, -40, 82, -91, 52, -12}, {1, 1, 2, 6, 23, 93}, 30] (* Jean-Fran├žois Alcover, Mar 01 2020 *)

CROSSREFS

Permutations with at most one descent are given by A000325.

Cf. A008292, A123125.

Sequence in context: A150287 A150288 A150289 * A012866 A150290 A150291

Adjacent sequences:  A326352 A326353 A326354 * A326356 A326357 A326358

KEYWORD

nonn,easy

AUTHOR

Robert Brignall, Sep 11 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 30 19:05 EDT 2020. Contains 334729 sequences. (Running on oeis4.)