A079105 Number of permutations of length n, in which all monotone subsequences of length 4 are descending or all such subsequences are ascending, containing the minimum number of such subsequences subject to that constraint.

1, 2, 6, 22, 86, 306, 882, 1764, 1764, 8738, 6892, 1682, 4614, 4182, 1250, 3750, 3750, 1250, 3750, 3750, 1250, 3750, 3750, 1250, 3750, 3750, 1250, 3750, 3750, 1250, 3750, 3750, 1250, 3750, 3750, 1250, 3750, 3750, 1250, 3750, 3750, 1250, 3750, 3750, 1250

Offset

1,2

Comments

Periodic with period 3 from a(15) onwards.

Links

Table of n, a(n) for n=1..45.

Joseph Myers, The minimum number of monotone subsequences, Electronic J. Combin. 9(2) (2002), #R4.

Index entries for linear recurrences with constant coefficients, signature (0, 0, 1).

Formula

G.f.: x*(432*x^16 +864*x^15 +432*x^14 +2710*x^13 +4124*x^12 +82*x^11 -5128*x^10 -7856*x^9 -1458*x^8 -1678*x^7 -860*x^6 -300*x^5 -84*x^4 -21*x^3 -6*x^2 -2*x -1) / ((x -1)*(x^2 +x +1)). - Colin Barker, Jul 06 2013

Mathematica

Join[{1, 2, 6, 22, 86, 306, 882, 1764, 1764, 8738, 6892, 1682, 4614, 4182}, LinearRecurrence[{0, 0, 1}, {1250, 3750, 3750}, 31]] (* Ray Chandler, Aug 25 2015 *)

Crossrefs

Cf. A079102, A079103, A079104, A079106.

Sequence in context: A150254 A148497 A206736 * A079104 A116705 A116708

Adjacent sequences: A079102 A079103 A079104 * A079106 A079107 A079108

Keyword

nonn,easy

Author

Joseph Myers, Dec 23 2002

Status

approved