A029858 a(n) = (3^n - 3)/2.

0, 3, 12, 39, 120, 363, 1092, 3279, 9840, 29523, 88572, 265719, 797160, 2391483, 7174452, 21523359, 64570080, 193710243, 581130732, 1743392199, 5230176600, 15690529803, 47071589412, 141214768239

Offset: 1

Author

Christian G. Bower

Keywords

• nonn
• easy

Comments

Also the number of 2-block covers of a labeled n-set. a(n) = A055154(n,2). Generally, number of k-block covers of a labeled n-set is T(n,k) = (1/k!)*Sum_{i = 1..k + 1} Stirling1(k + 1,i)*(2^(i - 1) - 1)^n. In particular, T(n,2) = (1/2!)*(3^n - 3), T(n,3) = (1/3!)*(7^n - 6*3^n + 11), T(n,4) = (1/4)!*(15^n - 10*7^n + 35*3^n - 50), ... - Vladeta Jovovic, Jan 19 2001

Conjectured to be the number of integers from 0 to 10^(n-1) - 1 that lack 0, 1, 2, 3, 4, 5 and 6 as a digit. - Alexandre Wajnberg, Apr 25 2005. This is easily verified to be true. - Renzo Benedetti, Sep 25 2008

Number of monic irreducible polynomials of degree 1 in GF(3)[x1,...,xn]. - Max Alekseyev, Jan 23 2006

Also, the greatest number of identical weights among which an odd one can be identified and it can be decided if the odd one is heavier or lighter, using n weighings with a comparing balance. If the odd one only needs to be identified, the sequence starts 4, 13, 40 and is A003462 (3^n - 1)/2, n > 1. - Tanya Khovanova, Dec 11 2006; corrected by Samuel E. Rhoads, Apr 18 2016

Binomial transform yields A134057. Inverse binomial transform yields A062510 with one additional 0 in front. - R. J. Mathar, Jun 18 2008

Numbers k where the recurrence s(0)=0, if s(k-1) >= k then s(k) = s(k-1) - k otherwise s(k) = s(k-1) + k produces s(k) = 0. - Hugo Pfoertner, Jan 05 2012

For n > 1: A008344(a(n)) = a(n). - Reinhard Zumkeller, May 09 2012

Also the number of edges in the (n-1)-Hanoi graph. - Eric W. Weisstein, Jun 18 2017

A level 1 Sierpiński triangle graph is a triangle. Level n+1 is formed from three copies of level n by identifying pairs of corner vertices of each pair of triangles. a(n) is the number of degree 4 vertices in the level n Sierpinski triangle graph. - Allan Bickle, Jul 30 2020

Also the number of minimum vertex cuts in the n-Apollonian network. - Eric W. Weisstein, Dec 20 2020

Also the minimum number of turns in n-dimensional Euclidean space needed to visit all 3^n points of the grid {0, 1, 2}^n, moving in straight lines between turns (repeated visits and direction changes at non-grid points are allowed). - Marco Ripà, Aug 06 2025

Examples

			For the Sierpiński triangle, Level 1 is a triangle, so a(1) = 0.
Level 2 has three corners (degree 2) and three degree 4 vertices, so a(2) = 3.
The level 2 Hanoi graph has 3 triangles joined by 3 edges, so a(2+1) = 12.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..300
• Allan Bickle, Properties of Sierpinski Triangle Graphs, Springer PROMS 448 (2021) 295-303.
• Natalia Agudelo Muñetón, Agustín Moreno Cañadas, Pedro Fernando Fernández Espinosa, and Isaías David Marín Gaviria, Brauer Configuration Algebras and Their Applications in Graph Energy Theory, Mathematics (2021) Vol. 9, 3042.
• Alex Born, Cor A. J. Hukrnes, and Gerhard J. Woeginger, How to detect a counterfeit coin: adaptive versus non-adaptive solutions, Inf. Proc. Lett. 86 (2003) 137-141.
• Gary Darby, The Counterfeit Coin
• Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See p. 17.
• Lorenz Halbeisen and Norbert Hungerbuhler, The general counterfeit coin problem, Discr. Math 147 (1-3) (1995) 139-150, Theorem 1 with b=1.
• Andreas Hinz, Sandi Klavzar, and Sara Sabrina Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
• Bennet Manvel, Counterfeit coin problems, Math. Mag. 50 (2) (1977) 90-92, theorem 2.
• Marco Ripà, Solving the 106 years old 3^k points problem with the clockwise-algorithm, Journal of Fundamental Mathematics and Applications, 2020, 3(2), 84-97.
• Allen Stenger and Jack Wert, The Twelve Coins (or Twelve bags of Gold)
• Eric Weisstein's World of Mathematics, Apollonian Network
• Eric Weisstein's World of Mathematics, Edge Count
• Eric Weisstein's World of Mathematics, Hanoi Graph
• Eric Weisstein's World of Mathematics, Minimum Vertex Cut
• Index entries for linear recurrences with constant coefficients, signature (4,-3).

Crossrefs

Cf. A055154, A003462, A007051, A034472, A024023.

Cf. A000203, A008776.

Cf. A007283, A029858, A067771, A233774, A233775, A246959 (Sierpiński triangle graphs).

Cf. A000225, A029858, A058809, A375256 (Hanoi graphs).

Programs

Haskell

a029858 = (`div` 2) . (subtract 3) . (3 ^)
a029858_list = iterate ((+ 3) . (* 3)) 0
-- Reinhard Zumkeller, May 09 2012

Magma

[(3^n-3)/2: n in [1..30]]; // Vincenzo Librandi, Jun 05 2011

Maple

a:=n->sum(3^j,j=1..n): seq(a(n),n=0..23); # Zerinvary Lajos, Jun 27 2007

Mathematica

Table[(3^n - 3)/2, {n, 24}] (* Alonso del Arte, Dec 29 2014 *)

PARI

a(n)=(3^n-3)\2 \\ Charles R Greathouse IV, Apr 17 2012

Formula

a(n) = 3*a(n-1) + 3. - Alexandre Wajnberg, Apr 25 2005

O.g.f: 3*x^2/((1-x)*(1-3*x)). - R. J. Mathar, Jun 18 2008

a(n) = 3^(n-1) + a(n-1) (with a(1)=0). - Vincenzo Librandi, Nov 18 2010

a(n) = 3*A003462(n-1). - R. J. Mathar, Sep 10 2015

E.g.f.: 3*(-1 + exp(2*x))*exp(x)/2. - Ilya Gutkovskiy, Apr 19 2016

a(n) = A067771(n-1) - 3. - Allan Bickle, Jul 30 2020

a(n) = sigma(A008776(n-2)) for n>=2. - Flávio V. Fernandes, Apr 20 2021

Extensions

Corrected by T. D. Noe, Nov 07 2006