login
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
OFFSET
0,3
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.
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.
Sequence in context: A150287 A150288 A150289 * A012866 A150290 A150291
KEYWORD
nonn,easy
AUTHOR
Robert Brignall, Sep 11 2019
STATUS
approved