|
|
A220589
|
|
Number of simple skew-merged permutations with n elements.
|
|
2
|
|
|
2, 2, 8, 16, 44, 108, 284, 740, 1966, 5254, 14172, 38476, 105122, 288754, 797036, 2209588, 6149618, 17176186, 48129284, 135261796, 381169532, 1076824852, 3049109912, 8652239496, 24600592454, 70075316198, 199955694616
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
4,1
|
|
COMMENTS
|
A permutation is skew-merged if it is the union of an increasing subsequence and a decreasing subsequence. A permutation is simple if it does not contain a nontrivial interval.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (1-2*x-x^2+(x-1)*sqrt(1-2*x-3*x^2)) / (x+1).
Recurrence (for n>4): (n-4)*n*a(n) = (n^2-7*n+15)*a(n-1) + (n-3)*(5*n-17)*a(n-2) + 3*(n-4)*(n-3)*a(n-3). - Vaclav Kotesovec, Jan 16 2013
|
|
MATHEMATICA
|
Rest[Rest[Rest[Rest[CoefficientList[Series[(1-2*x-x^2+(x-1)*Sqrt[1-2*x-3*x^2])/(x+1), {x, 0, 20}], x]]]]] (* Vaclav Kotesovec, Jan 16 2013 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|