%I #27 Apr 03 2015 17:57:05
%S 1,2,6,21,52,105,186,301,456,657,910,1221,1596,2041,2562,3165,3856,
%T 4641,5526,6517,7620,8841,10186,11661,13272,15025,16926,18981,21196,
%U 23577,26130,28861,31776,34881,38182,41685,45396,49321,53466,57837,62440,67281,72366
%N The number of permutations of length n sortable by 3 prefix reversals (in the pancake sorting sense).
%C Essentially the same as A069778.
%H H. Dweighter, <a href="http://www.jstor.org/stable/2318260">Elementary problems and solutions</a>, problem E2569. Amer. Math. Monthly 82 (1975), 1010.
%H C. Homberger, <a href="http://arxiv.org/abs/1410.2657">Patterns in Permutations and Involutions: A Structural and Enumerative Approach</a>, arXiv preprint 1410.2657, 2014.
%H C. Homberger, V. Vatter, <a href="http://arxiv.org/abs/1308.4946">On the effective and automatic enumeration of polynomial permutation classes</a>, arXiv preprint arXiv:1308.4946, 2013.
%F G.f.: -1 + (x^6 - 3*x^5 + 6*x^4 + 4*x^2 - 3*x + 1)/(x - 1)^4.
%F a(n) = (n-1)*(n^2-3*n+3) for n>2, a(1)=1, a(2)=2. [_Bruno Berselli_, Aug 22 2013]
%e There are only 3 permutations of length 4 which cannot be sorted by 3 pancake reversals.
%t CoefficientList[Series[(1/x) (-1 + (x^6 - 3 x^5 + 6 x^4 + 4 x^2 - 3 x + 1)/(x - 1)^4), {x, 0, 50}], x] (* _Bruno Berselli_, Aug 22 2013 *)
%Y Cf. A000027, A002522.
%K nonn,easy
%O 1,2
%A _Vincent Vatter_, Aug 21 2013
|