A326355 Number of permutations of length n with at most two descents.

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

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