A217200 Number of permutations in S_{n+2} containing an increasing subsequence of length n.

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

Author

Alois P. Heinz, Sep 27 2012

Keywords

• nonn
• easy

Examples

			a(2) = 23: only one of 4! = 24 permutations of {1,2,3,4} has no increasing subsequence of length 2: 4321.
		

Links

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

Crossrefs

A diagonal of A214152.

Programs

Maple

a:= n-> 3+(2+(1+(n+2)*n)*n)*n/2-`if`(n=0, 1, 0):
seq(a(n), n=0..60);

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.