

A003946


Expansion of (1+x)/(13*x).


126



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Coordination sequence for infinite tree with valency 4.
The nth 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)mydeja.com), Mar 30 2001
a(n) is the number of nonreversing random walks of the length of n edges on a twodimensional 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 *i1 different types of the part i, (i=1,2,...).  Milan Janjic, Aug 26 2010
Number of lengthn 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(r1)*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 nSierpinski sieve graph.  Eric W. Weisstein, Dec 01 2017
Number of 3permutations of n elements avoiding the patterns 231, 321. See Bonichon and Sun.  Michel Marcus, Aug 19 2022


LINKS

T. D. Noe, Table of n, a(n) for n = 0..200
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, (an + b)color compositions, arXiv:1707.07798 [math.CO], 2017.
Nicolas Bonichon and PierreJean Morel, Baxter dpermutations and other pattern avoiding classes, arXiv:2202.12677 [math.CO], 2022.
D. J. Broadhurst, On the enumeration of irreducible kfold Euler sums and their roles in knot theory and field theory, arXiv:hepth/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
A. M. Nemirovsky et al., Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 10831108.
Nathan Sun, On dpermutations and Pattern Avoidance Classes, arXiv:2208.08506 [math.CO], 2022.
Eric Weisstein's World of Mathematics, Maximal Clique
Eric Weisstein's World of Mathematics, Sierpinski Sieve Graph
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (3).
Index entries for sequences related to trees


FORMULA

a(n) = floor(4*3^(n1)).  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(n1), 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)


EXAMPLE

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


MAPLE

if n = 0 then 1 else 4*3^(n1); 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, Dev 11 2012 *)
Join[{1}, LinearRecurrence[{3}, {4}, 20]] (* Eric W. Weisstein, Dec 01 2017 *)


PROG

(PARI) {a(n) = if( n<1, n==0, 4 * 3^(n1))}; /* Michael Somos, Jun 18 2002 */
(PARI) Vec((1+x)/(13*x) + O(x^100)) \\ Altug Alkan, Dec 07 2015
(Maxima) A003946[n]:=if n<1 then 1 else 4*3^(n1)$
makelist(A003946[n], n, 0, 30); /* Martin Ettl, Oct 29 2012 */
(Magma) [1] cat [4*3^(n1): n in [1..25]]; // Vincenzo Librandi, Dec 11 2012


CROSSREFS

Cf. A029653, A143865, column 4 in A265583, A015448.
Sequence in context: A168969 A169017 A169065 * A052156 A169113 A169161
Adjacent sequences: A003943 A003944 A003945 * A003947 A003948 A003949


KEYWORD

nonn,easy,nice,walk


AUTHOR

N. J. A. Sloane


EXTENSIONS

Additional comments from Michael Somos, Jun 18 2002
Edited by N. J. A. Sloane, Dec 04 2009


STATUS

approved



