%I
%S 1,3,9,21,45,93,189,381,765,1533,3069,6141,12285,24573,49149,98301,
%T 196605,393213,786429,1572861,3145725,6291453,12582909,25165821,
%U 50331645,100663293,201326589,402653181,805306365,1610612733
%N G.f.: (x+2)*(x+1)/((x1)*(x2)) = Sum_{n>=0} a(n)*(x/2)^n.
%C Number of moves to solve Hard Pagoda puzzle.
%C Partial sums of A111286. Binomial transform of (1,2,4,2,4,2,4 ....).  _Paul Barry_, Feb 28 2003
%C Warren W. Kokko writes that this sequence also appears to give the number of scoring sequences for the Racer Dice Game with n dice.  _N. J. A. Sloane_, Feb 24 2015
%C From _Michel Lagneau_, Apr 27 2015: (Start)
%C For n > 0, a(n) is the number of identical bowls having the same weight except for one which has a higher weight than the others which are identifiable by a weighing machine using n weighings.
%C Example: a(2)=9 because two weighings are sufficient:
%C Start with 9 bowls;
%C Step 1: remove 3 bowls => there are still 6 bowls;
%C Step 2: first weighing of 6 bowls (3 bowls on each side of the weighing machine);
%C Step 3: if the machine is in equilibrium, we find immediately the unknown bowl with a second weighing from the first 3 removing bowls. Else, we find immediately the unknown bowl with a second weighing from the 3 heaviest bowls.
%C Note: If the unknown bowl has a lower weight, the reasoning is the same, but it is necessary to know whether the unknown bowl is heavier or lighter.
%C In the general case, we always remove 3 bowls in step 1.
%C (End)
%C The number of ternary words of length n that avoid {112,221}. G.f. [1+(k1)*x^2]/[1k*x+(k1)*x^2] at k=3. [Theorem 7.93 by Heubach and Mansour].  _R. J. Mathar_, May 22 2016
%C Apart from the first term, column 2 of A222057.  _Anton Zakharov_, Oct 27 2016
%D Richard I. Hess, Compendium of Over 7000 Wire Puzzles, privately printed, 1991.
%D Richard I. Hess, Analysis of Ring Puzzles, booklet distributed at 13th International Puzzle Party, Amsterdam, Aug 20 1993.
%D S. Heubach, T. Mansour, in Combinatorics of Compositions and words, Discr. Math. Applicat. (ed by K H Rosen), CRC Press 2010, p 300.
%D Warren W. Kokko, The Racer Dice Game, Manuscript, 2015.
%H Vincenzo Librandi, <a href="/A068156/b068156.txt">Table of n, a(n) for n = 0..1000</a>
%H Artur Schaefer, <a href="http://arxiv.org/abs/1602.02186">Endomorphisms of The Hamming Graph and Related Graphs</a>, arXiv preprint arXiv:1602.02186 [math.CO], 2016. See Table Remark 4.5.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,2).
%F a(0) = 1, a(n) = A060482(2n+1). For n > 0, a(n+1) = 2*a(n)+3.
%F G.f.: (1+2*x^2)/((12*x)*(1x)).  _Paul Barry_, Feb 28 2003
%F a(n) = 3*2^n+0^n3.  _Paul Barry_, Sep 04 2003
%F a(n) = A099257(A033484(n)+1) = 2*A033484(n) + 1.  _Reinhard Zumkeller_, Oct 09 2004
%F a(n) = 3*a(n1)  2*a(n2), n > 1.  _Vincenzo Librandi_, Nov 11 2011
%F a(n) = a(n1)+ 3*2^(n1); a(1)=3.  _Ctibor O. Zizka_, Apr 17 2008
%F E.g.f.: 1 + 3*(exp(x)  1)*exp(x).  _Ilya Gutkovskiy_, May 22 2016
%t Join[{1}, LinearRecurrence[{3, 2}, {3, 9}, 30]] (* _JeanFrançois Alcover_, Jan 08 2019 *)
%o (MAGMA) [3*2^n+0^n3 : n in [0..30]]; // _Vincenzo Librandi_, Nov 11 2011
%Y A diagonal of A233308 (for n > 1).
%K nonn,easy
%O 0,2
%A _Benoit Cloitre_, Mar 12 2002
