|
%I #27 Mar 01 2020 06:47:42
%S 1,1,2,6,23,93,360,1312,4541,15111,48854,154674,482355,1487905,
%T 4553684,13857492,41998265,126912075,382702050,1152300166,3465813071,
%U 10416313221,31288785152,93950241096,282026883573,846449748943,2540120998190,7621973606682
%N Number of permutations of length n with at most two descents.
%H D. I. Bevan, <a href="http://oro.open.ac.uk/43875/">On the growth of permutation classes</a>, PhD thesis, The Open University, 2015.
%H Robert Brignall, Jakub Sliacan, <a href="https://arxiv.org/abs/1902.02705">Combinatorial specifications for juxtapositions of permutation classes</a>, arXiv:1902.02705 [math.CO], 2019.
%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (10,-40,82,-91,52,-12).
%F 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)).
%F a(n) = Sum_{k=0..3} A123125(n,k). - _Alois P. Heinz_, Sep 11 2019
%F a(n) = 3^n -n*2^n +n^2/2 -n/2. - _R. J. Mathar_, Sep 25 2019
%e For n=4, a(4) = 23 because the permutation 4321 is the only one of length 4 to have more than 2 descents.
%p b:= proc(u, o, k) option remember;
%p `if`(u+o=0, 1, add(b(u-j, o+j-1, k), j=1..u)+
%p `if`(k<2, add(b(u+j-1, o-j, k+1), j=1..o), 0))
%p end:
%p a:= n-> b(n, 0$2):
%p seq(a(n), n=0..28); # _Alois P. Heinz_, Sep 11 2019
%t LinearRecurrence[{10, -40, 82, -91, 52, -12}, {1, 1, 2, 6, 23, 93}, 30] (* _Jean-François Alcover_, Mar 01 2020 *)
%Y Permutations with at most one descent are given by A000325.
%Y Cf. A008292, A123125.
%K nonn,easy
%O 0,3
%A _Robert Brignall_, Sep 11 2019
|
