The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #2 Mar 31 2012 10:29:58
%S 1,2,5,16,62,280,1440,8296,52864,368848,2794864,22842048,200201408,
%T 1872466944,18608903968,195778297664,2173272774016,25380361760000,
%U 311011886153856,3989579297299712,53458990592638976,746817531317769728
%N Number of permutations of length n that can be sorted in 2^(n-1)-1 steps of Elizalde and Winkler's homing algorithm
%C 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.
%D S. Elizalde and P. Winkler, Sorting by Placement and Shift, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009.
%H S. Elizalde and P. Winkler, <a href="http://arxiv.org/abs/0809.2957"> Sorting by placement and shift</a>
%F 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)).
%K nonn
%O 2,2
%A _Sergi Elizalde_, Feb 18 2010