A003946 - OEIS

%I #169 Jun 13 2024 11:38:18

%S 1,4,12,36,108,324,972,2916,8748,26244,78732,236196,708588,2125764,

%T 6377292,19131876,57395628,172186884,516560652,1549681956,4649045868,

%U 13947137604,41841412812,125524238436,376572715308,1129718145924

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

%C Coordination sequence for infinite tree with valency 4.

%C 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

%C 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

%C 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

%C 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

%C Equals row sums of triangle A143865. - _Gary W. Adamson_, Sep 04 2008

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

%C 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

%C 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

%C The sequence is the INVERTi transform of A015448: (1, 5, 21, 89, 377, ...). - _Gary W. Adamson_, Aug 06 2016

%C 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

%C 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

%C Also the number of maximal cliques in the n-Sierpinski sieve graph. - _Eric W. Weisstein_, Dec 01 2017

%C Number of 3-permutations of n elements avoiding the patterns 231, 321. See Bonichon and Sun. - _Michel Marcus_, Aug 19 2022

%H T. D. Noe, <a href="/A003946/b003946.txt">Table of n, a(n) for n = 0..200</a>

%H Feryal Alayont and Evan Henning, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Alayont/ala4.html">Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.

%H Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, <a href="https://arxiv.org/abs/1707.07798">(an + b)-color compositions</a>, arXiv:1707.07798 [math.CO], 2017.

%H Nicolas Bonichon and Pierre-Jean Morel, <a href="https://arxiv.org/abs/2202.12677">Baxter d-permutations and other pattern avoiding classes</a>, arXiv:2202.12677 [math.CO], 2022.

%H D. J. Broadhurst, <a href="http://arXiv.org/abs/hep-th/9604128">On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory</a>, arXiv:hep-th/9604128, 1996.

%H John Elias, <a href="/A003946/a003946.png">Illustration: Sierpinski Hexagrams</a>

%H I. M. Gessel and Ji Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Gessel/gessel6.html">Compositions and Fibonacci identities</a>, J. Int. Seq. 16 (2013) 13.4.5

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=305">Encyclopedia of Combinatorial Structures 305</a>

%H Milan Janjic, <a href="http://www.pmfbl.org/janjic/">Enumerative Formulas for Some Functions on Finite Sets</a>

%H Amya Luo, <a href="https://math.dartmouth.edu/theses/undergrad/2024/Luo-thesis.pdf">Pattern Avoidance in Nonnesting Permutations</a>, Undergraduate Thesis, Dartmouth College (2024). See p. 3.

%H A. M. Nemirovsky et al., <a href="http://dx.doi.org/10.1007/BF01049010">Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers</a>, J. Statist. Phys., 67 (1992), 1083-1108.

%H Nathan Sun, <a href="https://arxiv.org/abs/2208.08506">On d-permutations and Pattern Avoidance Classes</a>, arXiv:2208.08506 [math.CO], 2022.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalClique.html">Maximal Clique</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SierpinskiSieveGraph.html">Sierpinski Sieve Graph</a>

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

%H <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (3).

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F a(n) = floor(4*3^(n-1)). - _Michael Somos_, Jun 18 2002

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

%F The Hankel transform of this sequence is [1,-4,0,0,0,0,0,0,0,0,...]. - _Philippe Deléham_, Nov 21 2007

%F 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

%F From _Mario C. Enriquez_, Apr 01 2017: (Start)

%F (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.

%F (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. = 1 + 4*x + 12*x^2 + 36*x^3 + 108*x^4 + 324*x^5 + 972*x^6 + 2916*x^7 + ...

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

%t Join[{1}, 4 3^Range[0, 30]] (* _Vladimir Joseph Stephan Orlovsky_, Jun 14 2009 *)

%t Join[{1}, NestList[3# &, 4, 30]] (* _Harvey P. Dale_, Nov 30 2011 *)

%t CoefficientList[Series[(1 + x)/(1 - 3 x), {x, 0, 30}], x] (* _Vincenzo Librandi_, Dev 11 2012 *)

%t Join[{1}, LinearRecurrence[{3}, {4}, 20]] (* _Eric W. Weisstein_, Dec 01 2017 *)

%o (PARI) {a(n) = if( n<1, n==0, 4 * 3^(n-1))}; /* _Michael Somos_, Jun 18 2002 */

%o (PARI) Vec((1+x)/(1-3*x) + O(x^100)) \\ _Altug Alkan_, Dec 07 2015

%o (Maxima) A003946[n]:=if n<1 then 1 else 4*3^(n-1)$

%o makelist(A003946[n],n,0,30); /* _Martin Ettl_, Oct 29 2012 */

%o (Magma) [1] cat [4*3^(n-1): n in [1..25]]; // _Vincenzo Librandi_, Dec 11 2012

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

%K nonn,easy,nice,walk

%O 0,2

%A _N. J. A. Sloane_

%E Additional comments from _Michael Somos_, Jun 18 2002

%E Edited by _N. J. A. Sloane_, Dec 04 2009