A061776 Start with a single triangle; at n-th generation add a triangle at each vertex, allowing triangles to overlap; sequence gives number of triangles in n-th generation.

1, 3, 6, 12, 18, 30, 42, 66, 90, 138, 186, 282, 378, 570, 762, 1146, 1530, 2298, 3066, 4602, 6138, 9210, 12282, 18426, 24570, 36858, 49146, 73722, 98298, 147450, 196602, 294906, 393210, 589818, 786426, 1179642, 1572858, 2359290, 3145722, 4718586, 6291450

Offset: 0

Author

N. J. A. Sloane, R. K. Guy, Jun 23 2001

Keywords

• nonn
• nice
• easy

Comments

Number of 3-colorings of the (n,2)-Turán graph. - Alois P. Heinz, Jun 07 2024

References

• R. Reed, The Lemming Simulation Problem, Mathematics in School, 3 (#6, Nov. 1974), front cover and pp. 5-6.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• R. Reed, The Lemming Simulation Problem, Mathematics in School, 3 (#6, Nov. 1974), front cover and pp. 5-6. [Scanned photocopy of pages 5, 6 only, with annotations by R. K. Guy and N. J. A. Sloane]
• Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Crossrefs

A061777 gives total population of triangles at n-th generation.

Cf. A266972.

Programs

Maple

A061776 := proc(n) if n mod 2 = 0 then 6*(2^(n/2)-1); else 3*(2^((n-1)/2)-1)+3*(2^((n+1)/2)-1); fi; end; # for n >= 1

Mathematica

a[0]=1; a[n_/;EvenQ[n]]:=6*(2^(n/2)-1); a[n_/;OddQ[n]] := 3*(2^((n-1)/2)-1) + 3*(2^((n+1)/2)-1); a /@ Range[0, 37] (* Jean-François Alcover, Apr 22 2011, after Maple program *)
CoefficientList[Series[(1 + 2 x) (1 + x^2) / ((1 - x) (1 - 2 x^2)), {x, 0, 40}], x] (* Vincenzo Librandi, Jun 19 2013 *)
LinearRecurrence[{1,2,-2},{1,3,6,12},40] (* Harvey P. Dale, Mar 27 2019 *)

PARI

a(n)=([0,1,0; 0,0,1; -2,2,1]^n*[1;3;6])[1,1] \\ Charles R Greathouse IV, Feb 19 2017

Formula

Explicit formula given in Maple line.

a(n) = a(n-1)+2*a(n-2)-2*a(n-3) for n>3. G.f.: (1+2*x)*(1+x^2)/((1-x)*(1-2*x^2)). - Colin Barker, May 08 2012

a(n) = 3*A027383(n-1) for n>0, a(0)=1. - Bruno Berselli, May 08 2012