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

Author

Alois P. Heinz, Sep 27 2012

Keywords

• nonn
• easy

Examples

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

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).

Crossrefs

A diagonal of A214152.

Programs

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 *)

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.