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

Author

Robert Brignall, Sep 11 2019

Keywords

• nonn
• easy

Examples

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

Links

• 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).

Crossrefs

Permutations with at most one descent are given by A000325.

Cf. A008292, A123125.

Programs

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 *)

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