A003946 Expansion of (1+x)/(1-3*x).

1, 4, 12, 36, 108, 324, 972, 2916, 8748, 26244, 78732, 236196, 708588, 2125764, 6377292, 19131876, 57395628, 172186884, 516560652, 1549681956, 4649045868, 13947137604, 41841412812, 125524238436, 376572715308, 1129718145924

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• walk

Comments

Coordination sequence for infinite tree with valency 4.

The n-th term of the coordination sequence of the infinite tree with valency 2m is the same as the number of reduced words of size n in the free group on m generators. In the five sequences A003946, A003948, A003950, A003952, A003954 m is 2, 3, 4, 5, 6. - Avi Peretz (njk(AT)netvision.net.il), Feb 23 2001 and Ola Veshta (olaveshta(AT)my-deja.com), Mar 30 2001

a(n) is the number of nonreversing random walks of the length of n edges on a two-dimensional square lattice, all beginning at a fixed point P. - Pawel P. Mazur (Pawel.Mazur(AT)pwr.wroc.pl), Apr 06 2005

Binomial transform of {1, 3, 5, 11, 21, 43, ...}, see A001045. Binomial transform is {1, 5, 21, 85, 341, 1365, ...}, see A002450. - Philippe Deléham, Jul 22 2005

For n >= 2, a(n) is equal to the number of functions f:{1,2,...,n+1}->{1,2,3} such that for fixed, different x_1, x_2 in {1,2,...,n} and fixed y_1, y_2 in {1,2,3} we have f(x_1) <> y_1 and f(x_2) <> y_2. - Milan Janjic, Apr 19 2007

Equals row sums of triangle A143865. - Gary W. Adamson, Sep 04 2008

Equals INVERT transform of the odd integers = 1/(1 - x - 3x^2 - 5x^3 - ...). - Gary W. Adamson, Jul 27 2009

a(n) is the number of generalized compositions of n+1 when there are 2 *i-1 different types of the part i, (i=1,2,...). - Milan Janjic, Aug 26 2010

Number of length-n strings of 4 letters with no two adjacent letters identical. The general case (strings of r letters) is the sequence with g.f. (1+x)/(1-(r-1)*x). - Joerg Arndt, Oct 11 2012

The sequence is the INVERTi transform of A015448: (1, 5, 21, 89, 377, ...). - Gary W. Adamson, Aug 06 2016

Let D(m) = {d(m,i)}, i = 1..q, denote the set of the q divisors of a number m, and consider s1(m) and s2(m) the sums of the divisors that are congruent to 1 and 2 (mod 3) respectively. For n > 0, the sequence a(n) lists the numbers m such that s1(m) = 5 and s2(m) = 2. - Michel Lagneau, Feb 09 2017

a(n) is the number of quaternary sequences of length n such that no two consecutive terms have distance 2. - David Nacin, May 31 2017

Also the number of maximal cliques in the n-Sierpinski gasket graph. - Eric W. Weisstein, Dec 01 2017

Number of 3-permutations of n elements avoiding the patterns 231, 321. See Bonichon and Sun. - Michel Marcus, Aug 19 2022

Examples

			G.f. = 1 + 4*x + 12*x^2 + 36*x^3 + 108*x^4 + 324*x^5 + 972*x^6 + 2916*x^7 + ...
		

Links

• T. D. Noe, Table of n, a(n) for n = 0..200
• Feryal Alayont and Evan Henning, Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.
• Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, (an + b)-color compositions, arXiv:1707.07798 [math.CO], 2017.
• Nicolas Bonichon and Pierre-Jean Morel, Baxter d-permutations and other pattern avoiding classes, arXiv:2202.12677 [math.CO], 2022.
• D. J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, arXiv:hep-th/9604128, 1996.
• John Elias, Illustration: Sierpinski Hexagrams
• I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 305
• Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
• Amya Luo, Pattern Avoidance in Nonnesting Permutations, Undergraduate Thesis, Dartmouth College (2024). See p. 3.
• A. M. Nemirovsky et al., Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108.
• Nathan Sun, On d-permutations and Pattern Avoidance Classes, arXiv:2208.08506 [math.CO], 2022.
• Eric Weisstein's World of Mathematics, Maximal Clique.
• Eric Weisstein's World of Mathematics, Sierpiński Gasket Graph.
• Index to divisibility sequences
• Index entries for linear recurrences with constant coefficients, signature (3).
• Index entries for sequences related to trees

Crossrefs

Cf. A029653, A143865, column 4 in A265583, A015448.

Programs

Magma

[1] cat [4*3^(n-1): n in [1..25]]; // Vincenzo Librandi, Dec 11 2012

Maple

if n = 0 then 1 else 4*3^(n-1); fi;

Mathematica

Join[{1}, 4 3^Range[0, 30]] (* Vladimir Joseph Stephan Orlovsky, Jun 14 2009 *)
Join[{1}, NestList[3# &, 4, 30]] (* Harvey P. Dale, Nov 30 2011 *)
CoefficientList[Series[(1 + x)/(1 - 3 x), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 11 2012 *)
Join[{1}, LinearRecurrence[{3}, {4}, 20]] (* Eric W. Weisstein, Dec 01 2017 *)

Maxima

A003946[n]:=if n<1 then 1 else 4*3^(n-1)$
makelist(A003946[n],n,0,30); /* Martin Ettl, Oct 29 2012 */

PARI

{a(n) = if( n<1, n==0, 4 * 3^(n-1))}; /* Michael Somos, Jun 18 2002 */

PARI

Vec((1+x)/(1-3*x) + O(x^100)) \\ Altug Alkan, Dec 07 2015

Formula

a(n) = floor(4*3^(n-1)). - Michael Somos, Jun 18 2002

a(n) = Sum_{k=0..n} A029653(n, k)*x^k for x = 2. - Philippe Deléham, Jul 10 2005

The Hankel transform of this sequence is [1,-4,0,0,0,0,0,0,0,0,...]. - Philippe Deléham, Nov 21 2007

a(n + 1) = (((1 + sqrt(-11))/2)^n + ((1 - sqrt(-11))/2)^n)^2 - (((1 + sqrt(-11))/2)^n - ((1 - sqrt(-11))/2)^n)^2. - Raphie Frank, Dec 07 2015

From Mario C. Enriquez, Apr 01 2017: (Start)

(L(a(n+k)) - 1)/a(n) reduces to the form C/a(n-1), where n > 1, k >= 0, L(a(n)) is the a(n)-th Lucas number and C = (L(a(n+k)) - 1)/3.

(L(a(n+k)) - 1)/3 mod (L(a(n)) - 1)/3 = (L(a(n)) - 1)/3 - 1, where n >= 1, k >= 0 and L(a(n)) is the a(n)-th Lucas number. (End)

E.g.f.: (4*exp(3*x) - 1)/3. - Stefano Spezia, Jan 31 2025

Extensions

Additional comments from Michael Somos, Jun 18 2002

Edited by N. J. A. Sloane, Dec 04 2009