A099743 Number of permutations with exactly 1 valley which avoid the pattern 1324.

0, 0, 2, 15, 75, 313, 1179, 4161, 14051, 45993, 147195, 463345, 1440723, 4438905, 13582955, 41350977, 125404611, 379228489, 1144370139, 3447856017, 10375942835, 31198607385, 93749962827, 281584384225, 845476670115, 2537990291433, 7617326317499

Offset

1,3

Links

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

Index entries for linear recurrences with constant coefficients, signature (9,-30,44,-24).

Formula

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

From Colin Barker, Feb 14 2017: (Start)

a(n) = -7*2^(n-3) + 3^n - 9*2^(n-4)*n - 2^(n-4)*n^2.

a(n) = 9*a(n-1) - 30*a(n-2) + 44*a(n-3) - 24*a(n-4) for n>4.

(End)

Example

a(3) = 2 because 213 and 312 have exactly 1 valley and avoid 1324.

Prog

(PARI) concat(vector(2), Vec(x^3*(2-3*x) / ((1-2*x)^3*(1-3*x)) + O(x^30))) \\ Colin Barker, Feb 14 2017

Crossrefs

Cf. A000079.

Sequence in context: A178321 A007232 A308914 * A283842 A344215 A102289

Adjacent sequences: A099740 A099741 A099742 * A099744 A099745 A099746

Keyword

nonn,easy

Author

Mike Zabrocki, Nov 09 2004

Status

approved