A257198 Number of permutations of length n having exactly one descent such that the first element of the permutation is an odd number.

0, 0, 2, 6, 16, 36, 78, 162, 332, 672, 1354, 2718, 5448, 10908, 21830, 43674, 87364, 174744, 349506, 699030, 1398080, 2796180, 5592382, 11184786, 22369596, 44739216, 89478458, 178956942, 357913912, 715827852, 1431655734, 2863311498, 5726623028

Offset

1,3

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,2).

Formula

a(n) = 2*floor((2*2^n-3*n-1)/6).

a(n) = 2*A178420(n-1).

a(n) = A000295(n)-A000975(n-1).

From Colin Barker, Apr 19 2015: (Start)

a(n) = (-3-(-1)^n+2^(2+n)-6*n)/6.

a(n) = 3*a(n-1)-a(n-2)-3*a(n-3)+2*a(n-4).

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

(End)

Example

a(3)=2: (1 3 2, 3 1 2).
a(4)=6: (1 2 4 3, 1 3 2 4, 1 4 2 3, 1 3 4 2, 3 1 2 4, 3 4 1 2).

Mathematica

Table[2 Floor[(2 2^n - 3 n - 1) / 6], {n, 50}] (* Vincenzo Librandi, Apr 18 2015 *)

Prog

(Magma) [2*Floor((2*2^n-3*n-1)/6): n in [1..40]]; // Vincenzo Librandi, Apr 18 2015
(PARI) concat([0, 0], Vec(-2*x^3/((x-1)^2*(x+1)*(2*x-1)) + O(x^100))) \\ Colin Barker, Apr 19 2015
(PARI) a(n)=(2<<n-3*n-1)\6*2 \\ Charles R Greathouse IV, Apr 21 2015

Crossrefs

Cf. A178420, A000295, A000975, A167030 (first differences).

Sequence in context: A270810 A366098 A227035 * A053210 A066641 A265106

Adjacent sequences: A257195 A257196 A257197 * A257199 A257200 A257201

Keyword

nonn,easy

Author

Ran Pan, Apr 18 2015

Status

approved