A217193 - OEIS

%I #18 Jul 28 2021 17:07:30

%S 6,24,119,588,2279,6996,18043,40884,83923,159404,284431,482108,782799,

%T 1225508,1859379,2745316,3957723,5586364,7738343,10540204,14140151,

%U 18710388,24449579,31585428,40377379,51119436,64143103,79820444,98567263,120846404,147171171

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

%H Alois P. Heinz, <a href="/A217193/b217193.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (7, -21, 35, -35, 21, -7, 1).

%F 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.

%F 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.

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

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

%p seq(a(n), n=0..40);

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

%Y A diagonal of A214152.

%K nonn,easy

%O 0,1

%A _Alois P. Heinz_, Sep 27 2012