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,1

Links

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

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

Adjacent sequences: A217197 A217198 A217199 * A217201 A217202 A217203

Keyword

nonn,easy

Author

Alois P. Heinz, Sep 27 2012

Status

approved