[seqfan] simple sequence not in OEIS

David Scambler dscambler at bmm.com
Mon Jul 23 06:15:39 CEST 2012


Number of permutations of 1..n for which the partial sum of signed displacements does not exceed 2.

e.g. n=5

s(i)             3  1  4  2  5 
s(i)-i           2 -1  1 -2  0
partial sum      2  1  2  0  0   // max = 2 so counted

s(i)             3  1  4  5  2 
s(i)-i           2 -1  1  1 -3
partial sum      2  1  2  3  0   // max = 3 so not counted

a(n) = 1, 1, 2, 6, 12, 25, 57, 124, 268, 588, 1285, 2801, 6118, 13362, ...

seems to be
g.f. 1/(1-n-n^2-3*n^3-n^4)


dave



More information about the SeqFan mailing list