%I M0963 #54 Jun 26 2023 14:34:06
%S 0,1,2,4,5,7,9,11,12,15,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,
%T 46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,
%U 92,94,96,98,100
%N Rotation distance between binary trees on n nodes.
%C Sleator et al. conjecture that a(n) = 2n-6 for all n >= 11.
%C Lionel Pournin proved that a(n) = 2n-6 for all n >= 11. - _David Radcliffe_, Apr 18 2016
%D D. D. Sleator, R. E. Tarjan and W. P. Thurston, Rotation distance, in T. M. Cover and Gopinath, eds., Open Problems in Communication and Computation, Springer, NY 1987, pp. 130-137.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Harvey P. Dale, <a href="/A005152/b005152.txt">Table of n, a(n) for n = 1..1000</a>
%H Patrick Dehornoy, <a href="http://dx.doi.org/10.1016/j.aim.2009.09.016">On the rotation distance between binary trees</a>, Adv. Math. 223 (2010), no. 4, 1316-1355.
%H Lionel Pournin, <a href="http://arxiv.org/abs/1207.6296">The diameter of associahedra</a>, arXiv:1207.6296 [math.CO], 2012-2014; Advances in Mathematics 259 (2014): 13-42.
%H Daniel D. Sleator, <a href="/A005152/a005152.pdf">Email to N. J. A. Sloane</a>, May 15 1991.
%H Daniel D. Sleator, Robert E. Tarjan, William P. Thurston, <a href="http://dx.doi.org/10.1090/S0894-0347-1988-0928904-4">Rotation distance, triangulations and hyperbolic geometry</a>, J. Amer. Math. Soc. 1 (1988), no. 3, 647-681.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Tree_rotation">Tree rotation</a>.
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2, -1).
%F a(n) = 2n-6 for n >= 11.
%F From _Chai Wah Wu_, Feb 20 2018: (Start)
%F a(n) = 2*a(n-1) - a(n-2) for n > 12.
%F G.f.: x*(x^11 - 2*x^10 + 2*x^9 - x^8 + x^5 - x^4 + x^3 + x)/(x - 1)^2. (End)
%t a[n_] := If[n < 11, {0, 1, 2, 4, 5, 7, 9, 11, 12, 15}[[n]], 2n - 6]; Array[a, 53] (* _Jean-François Alcover_, Jan 24 2019 *)
%t LinearRecurrence[{2,-1},{0,1,2,4,5,7,9,11,12,15,16,18},60] (* _Harvey P. Dale_, Aug 21 2021 *)
%K nonn,nice
%O 1,3
%A _N. J. A. Sloane_
%E Offset corrected by _David Radcliffe_, Apr 18 2016