|
|
A173469
|
|
Number of permutations of length n that can be sorted in 2^(n-1)-1 steps of Elizalde and Winkler's homing algorithm
|
|
0
|
|
|
1, 2, 5, 16, 62, 280, 1440, 8296, 52864, 368848, 2794864, 22842048, 200201408, 1872466944, 18608903968, 195778297664, 2173272774016, 25380361760000, 311011886153856, 3989579297299712, 53458990592638976, 746817531317769728
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,2
|
|
COMMENTS
|
The maximum number of steps that the homing algorithm can take to sort a permutation of length n is 2^(n-1)-1. This sequence counts permutations for which it is possible to use these many steps.
|
|
REFERENCES
|
S. Elizalde and P. Winkler, Sorting by Placement and Shift, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009.
|
|
LINKS
|
|
|
FORMULA
|
a(n) is the coefficient of t^n in the generating function F(t,t), where F(u,v) satisfies the partial differential equation F(u,v)=u*v+u*v*D_u(f)+u*v*D_v(f)-u^2*v^2*D_u(D_v(f)).
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|