A217193 Number of permutations in S_{n+3} containing an increasing subsequence of length n.

6, 24, 119, 588, 2279, 6996, 18043, 40884, 83923, 159404, 284431, 482108, 782799, 1225508, 1859379, 2745316, 3957723, 5586364, 7738343, 10540204, 14140151, 18710388, 24449579, 31585428, 40377379, 51119436, 64143103, 79820444, 98567263, 120846404, 147171171

Offset

0,1

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (7, -21, 35, -35, 21, -7, 1).

Formula

a(0) = 6, a(1) = 24, a(n) = (n^6+6*n^5+10*n^4+4*n^3+19*n^2+62*n+66)/6 for n>1.

G.f.: (4*x^8-23*x^7+53*x^6-60*x^5+32*x^4+49*x^3+77*x^2-18*x+6)/(1-x)^7.

Example

a(2) = 119: only one of 5! = 120 permutations of {1,2,3,4,5} has no increasing subsequence of length 2: 54321.

Maple

a:= n-> 11+(62+(19+(4+(10+(6+n)*n)*n)*n)*n)*n/6-`if`(n<2, 5-n, 0):
seq(a(n), n=0..40);

Mathematica

CoefficientList[Series[(4x^8-23x^7+53x^6-60x^5+32x^4+49x^3+77x^2-18x+6)/ (1-x)^7, {x, 0, 40}], x] (* or *) LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {6, 24, 119, 588, 2279, 6996, 18043, 40884, 83923}, 50] (* Harvey P. Dale, Jul 28 2021 *)

Crossrefs

A diagonal of A214152.

Sequence in context: A293257 A223752 A293236 * A109583 A352807 A100934

Adjacent sequences: A217190 A217191 A217192 * A217194 A217195 A217196

Keyword

nonn,easy

Author

Alois P. Heinz, Sep 27 2012

Status

approved