login
A217200
Number of permutations in S_{n+2} containing an increasing subsequence of length n.
2
2, 6, 23, 78, 207, 458, 891, 1578, 2603, 4062, 6063, 8726, 12183, 16578, 22067, 28818, 37011, 46838, 58503, 72222, 88223, 106746, 128043, 152378, 180027, 211278, 246431, 285798, 329703, 378482, 432483, 492066, 557603, 629478, 708087, 793838, 887151, 988458
OFFSET
0,1
LINKS
FORMULA
a(0) = 2, a(n) = 3+n+n^2/2+n^3+n^4/2 for n>0.
G.f.: (x^5-3*x^4+3*x^3+13*x^2-4*x+2)/(1-x)^5.
EXAMPLE
a(2) = 23: only one of 4! = 24 permutations of {1,2,3,4} has no increasing subsequence of length 2: 4321.
MAPLE
a:= n-> 3+(2+(1+(n+2)*n)*n)*n/2-`if`(n=0, 1, 0):
seq(a(n), n=0..60);
CROSSREFS
A diagonal of A214152.
Sequence in context: A245125 A290954 A220213 * A110068 A247211 A150275
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Sep 27 2012
STATUS
approved