A068156 G.f.: (x+2)*(x+1)/((x-1)*(x-2)) = Sum_{n>=0} a(n)*(x/2)^n.

1, 3, 9, 21, 45, 93, 189, 381, 765, 1533, 3069, 6141, 12285, 24573, 49149, 98301, 196605, 393213, 786429, 1572861, 3145725, 6291453, 12582909, 25165821, 50331645, 100663293, 201326589, 402653181, 805306365, 1610612733

Offset

0,2

Comments

Number of moves to solve Hard Pagoda puzzle.

Partial sums of A111286. Binomial transform of (1,2,4,2,4,2,4 ....). - Paul Barry, Feb 28 2003

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

From Michel Lagneau, Apr 27 2015: (Start)

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.

Example: a(2)=9 because two weighings are sufficient:

Start with 9 bowls;

Step 1: remove 3 bowls => there are still 6 bowls;

Step 2: first weighing of 6 bowls (3 bowls on each side of the weighing machine);

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.

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.

In the general case, we always remove 3 bowls in step 1.

(End)

The number of ternary words of length n that avoid {11-2,22-1}. G.f. [1+(k-1)*x^2]/[1-k*x+(k-1)*x^2] at k=3. [Theorem 7.93 by Heubach and Mansour]. - R. J. Mathar, May 22 2016

Apart from the first term, column 2 of A222057. - Anton Zakharov, Oct 27 2016

References

Richard I. Hess, Compendium of Over 7000 Wire Puzzles, privately printed, 1991.

Richard I. Hess, Analysis of Ring Puzzles, booklet distributed at 13th International Puzzle Party, Amsterdam, Aug 20 1993.

S. Heubach, T. Mansour, in Combinatorics of Compositions and words, Discr. Math. Applicat. (ed by K H Rosen), CRC Press 2010, p 300.

Warren W. Kokko, The Racer Dice Game, Manuscript, 2015.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Artur Schaefer, Endomorphisms of The Hamming Graph and Related Graphs, arXiv preprint arXiv:1602.02186 [math.CO], 2016. See Table Remark 4.5.

Index entries for linear recurrences with constant coefficients, signature (3,-2).

Formula

a(0) = 1, a(n) = A060482(2n+1). For n > 0, a(n+1) = 2*a(n)+3.

G.f.: (1+2*x^2)/((1-2*x)*(1-x)). - Paul Barry, Feb 28 2003

a(n) = 3*2^n+0^n-3. - Paul Barry, Sep 04 2003

a(n) = A099257(A033484(n)+1) = 2*A033484(n) + 1. - Reinhard Zumkeller, Oct 09 2004

a(n) = 3*a(n-1) - 2*a(n-2), n > 1. - Vincenzo Librandi, Nov 11 2011

a(n) = a(n-1)+ 3*2^(n-1); a(1)=3. - Ctibor O. Zizka, Apr 17 2008

E.g.f.: 1 + 3*(exp(x) - 1)*exp(x). - Ilya Gutkovskiy, May 22 2016

Mathematica

Join[{1}, LinearRecurrence[{3, -2}, {3, 9}, 30]] (* Jean-François Alcover, Jan 08 2019 *)
CoefficientList[Series[(1+2x^2)/((1-2x)(1-x)), {x, 0, 40}], x] (* Harvey P. Dale, Jan 02 2022 *)

Prog

(Magma) [3*2^n+0^n-3 : n in [0..30]]; // Vincenzo Librandi, Nov 11 2011

Crossrefs

A diagonal of A233308 (for n > 1).

Sequence in context: A192970 A110964 A107351 * A166452 A052101 A063830

Adjacent sequences: A068153 A068154 A068155 * A068157 A068158 A068159

Keyword

nonn,easy

Author

Benoit Cloitre, Mar 12 2002

Status

approved