%I #113 Aug 11 2024 23:40:17
%S 0,3,12,39,120,363,1092,3279,9840,29523,88572,265719,797160,2391483,
%T 7174452,21523359,64570080,193710243,581130732,1743392199,5230176600,
%U 15690529803,47071589412,141214768239
%N a(n) = (3^n - 3)/2.
%C 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
%C 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
%C Number of monic irreducible polynomials of degree 1 in GF(3)[x1,...,xn]. - _Max Alekseyev_, Jan 23 2006
%C 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
%C Binomial transform yields A134057. Inverse binomial transform yields A062510 with one additional 0 in front. - _R. J. Mathar_, Jun 18 2008
%C 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
%C For n > 1: A008344(a(n)) = a(n). - _Reinhard Zumkeller_, May 09 2012
%C Also the number of edges in the (n-1)-Hanoi graph. - _Eric W. Weisstein_, Jun 18 2017
%C 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
%C Also the number of minimum vertex cuts in the n-Apollonian network. - _Eric W. Weisstein_, Dec 20 2020
%H Vincenzo Librandi, <a href="/A029858/b029858.txt">Table of n, a(n) for n = 1..300</a>
%H Allan Bickle, <a href="https://allanbickle.wordpress.com/wp-content/uploads/2016/05/sierpinskigraphpaper2.pdf">Properties of Sierpinski Triangle Graphs</a>, Springer PROMS 448 (2021) 295-303.
%H Natalia Agudelo Muñetón, Agustín Moreno Cañadas, Pedro Fernando Fernández Espinosa, and Isaías David Marín Gaviria, <a href="https://doi.org/10.3390/math9233042">Brauer Configuration Algebras and Their Applications in Graph Energy Theory</a>, Mathematics (2021) Vol. 9, 3042.
%H A. Born, C. A. J. Hukrnes, and G. J. Woeginger, <a href="http://dx.doi.org/10.1016/S0020-0190(02)00483-0">How to detect a counterfeit coin: adaptive versus non-adaptive solutions</a>, Inf. Proc. Lett. 86 (2003) 137-141.
%H G. Darby, <a href="http://www.delphiforfun.org/Programs/counterfeitcoin.htm">The Counterfeit Coin</a>
%H L. Halbeisen and N. Hungerbuhler, <a href="http://dx.doi.org/10.1016/0012-365X(94)00232-8">The general counterfeit coin problem</a>, Discr. Math 147 (1-3) (1995) 139-150, Theorem 1 with b=1.
%H A. Hinz, S. Klavzar, and S. Zemljic, <a href="https://doi.org/10.1016/j.dam.2016.09.024">A survey and classification of Sierpinski-type graphs</a>, Discrete Applied Mathematics 217 3 (2017), 565-600.
%H B. Manvel, <a href="http://www.jstor.org/stable/2689732">Counterfeit coin problems</a>, Math. Mag. 50 (2) (1977) 90-92, theorem 2.
%H A. Stenger and J. Wert, <a href="http://web.archive.org/web/20050425080128/http://www.mathnerds.com/mathnerds/best/TwelveCoins/hint1.asp">The Twelve Coins (or Twelve bags of Gold)</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ApollonianNetwork.html">Apollonian Network</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EdgeCount.html">Edge Count</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HanoiGraph.html">Hanoi Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimumVertexCut.html">Minimum Vertex Cut</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3).
%F a(n) = 3*a(n-1) + 3. - _Alexandre Wajnberg_, Apr 25 2005
%F O.g.f: 3*x^2/((1-x)*(1-3*x)). - _R. J. Mathar_, Jun 18 2008
%F a(n) = 3^(n-1) + a(n-1) (with a(1)=0). - _Vincenzo Librandi_, Nov 18 2010
%F a(n) = 3*A003462(n-1). - _R. J. Mathar_, Sep 10 2015
%F E.g.f.: 3*(-1 + exp(2*x))*exp(x)/2. - _Ilya Gutkovskiy_, Apr 19 2016
%F a(n) = A067771(n-1) - 3. - _Allan Bickle_, Jul 30 2020
%F a(n) = sigma(A008776(n-2)) for n>=2. - _Flávio V. Fernandes_, Apr 20 2021
%e For the Sierpiński triangle, Level 1 is a triangle, so a(1) = 0.
%e Level 2 has three corners (degree 2) and three degree 4 vertices, so a(2) = 3.
%e The level 2 Hanoi graph has 3 triangles joined by 3 edges, so a(2+1) = 12.
%p a:=n->sum(3^j,j=1..n): seq(a(n),n=0..23); # _Zerinvary Lajos_, Jun 27 2007
%t Table[(3^n - 3)/2, {n, 24}] (* _Alonso del Arte_, Dec 29 2014 *)
%o (Magma) [(3^n-3)/2: n in [1..30]]; // _Vincenzo Librandi_, Jun 05 2011
%o (PARI) a(n)=(3^n-3)\2 \\ _Charles R Greathouse IV_, Apr 17 2012
%o (Haskell)
%o a029858 = (`div` 2) . (subtract 3) . (3 ^)
%o a029858_list = iterate ((+ 3) . (* 3)) 0
%o -- _Reinhard Zumkeller_, May 09 2012
%Y Cf. A055154, A003462, A007051, A034472, A024023.
%Y Cf. A000203, A008776.
%Y Cf. A007283, A029858, A067771, A233774, A233775, A246959 (Sierpiński triangle graphs).
%Y Cf. A000225, A029858, A058809, A375256 (Hanoi graphs).
%K nonn,easy
%O 1,2
%A _Christian G. Bower_
%E Corrected by _T. D. Noe_, Nov 07 2006