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

Author

Benoit Cloitre, Mar 12 2002

Keywords

• nonn
• easy

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).

Crossrefs

A diagonal of A233308 (for n > 1).

Cf. A000079.

Programs

Magma

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

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 *)

Sage

def a(n): return 3*2**n+0**n-3 # Torlach Rush, Jan 09 2025

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