login
a(n) is the number of subsequences of [ 1, ..., 2n ] in which each odd number has an even neighbor.
(Formerly M2893)
49

%I M2893 #147 Aug 03 2024 02:29:58

%S 1,3,11,39,139,495,1763,6279,22363,79647,283667,1010295,3598219,

%T 12815247,45642179,162557031,578955451,2061980415,7343852147,

%U 26155517271,93154256107,331773802863,1181629920803,4208437368135

%N a(n) is the number of subsequences of [ 1, ..., 2n ] in which each odd number has an even neighbor.

%C The even neighbor must differ from the odd number by exactly one.

%C If we defined this sequence by the recurrence (a(n) = 3*a(n-1) + 2*a(n-2)) that it satisfies, we could prefix it with an initial 0.

%C a(n) equals term (1,2) in M^n, M = the 3 X 3 matrix [1,1,2; 1,0,1; 2,1,1]. - _Gary W. Adamson_, Mar 12 2009

%C a(n) equals term (2,2) in M^n, M = the 3 X 3 matrix [0,1,0; 1,3,1; 0,1,0]. - _Paul Barry_, Sep 18 2009

%C From _Gary W. Adamson_, Aug 06 2010: (Start)

%C Starting with "1" = INVERT transform of A002605: (1, 2, 6, 16, 44, ...).

%C Example: a(3) = 39 = (16, 6, 2, 1) dot (1, 1, 3, 11) = (16 + 6 + 6 + 11). (End)

%C Pisano periods: 1, 1, 4, 1, 24, 4, 48, 2, 12, 24, 30, 4, 12, 48, 24, 4,272, 12, 18, 24, ... . - _R. J. Mathar_, Aug 10 2012

%C A007482 is also the number of ways of tiling a 3 X n rectangle with 1 X 1 squares, 2 X 2 squares and 2 X 1 (vertical) dominoes. - _R. K. Guy_, May 20 2015

%C With offset 1 (a(0) = 0, a(1) = 1) this is a divisibility sequence. - _Michael Somos_, Jun 03 2015

%C Number of elements of size 2^(-n) in a fractal generated by the second-order reversible cellular automaton, rule 150R (see the reference and the link). - _Yuriy Sibirmovsky_, Oct 04 2016

%C a(n) is the number of compositions (ordered partitions) of n into parts 1 (of three kinds) and 2 (of two kinds). - _Joerg Arndt_, Oct 05 2016

%C a(n) equals the number of words of length n over {0,1,2,3,4} in which 0 and 1 avoid runs of odd lengths. - _Milan Janjic_, Jan 08 2017

%C Start with a single cell at coordinates (0, 0), then iteratively subdivide the grid into 2 X 2 cells and remove the cells that have two '1's in their modulo 3 coordinates. a(n) is the number of cells after n iterations. Cell configuration converges to a fractal with approximate dimension 1.833. - _Peter Karpov_, Apr 20 2017

%C This is the Lucas sequence U(P=3,Q=-2), and hence for n>=0, a(n+2)/a(n+1) equals the continued fraction 3 + 2/(3 + 2/(3 + 2/(3 + ... + 2/3))) with n 2's. - _Greg Dresden_, Oct 06 2019

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D Stephen Wolfram, A New Kind of Science, Wolfram Media, 2002, p. 439.

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

%H Alexander Burstein and Opel Jones, <a href="https://arxiv.org/abs/2002.12189">Enumeration of Dumont permutations avoiding certain four-letter patterns</a>, arXiv:2002.12189 [math.CO], 2020.

%H R. K. Guy and William O. J. Moser, <a href="http://www.fq.math.ca/Scanned/34-2/guy.pdf">Numbers of subsequences without isolated odd members</a>, Fibonacci Quarterly, 34, No. 2, 152-155 (1996). Math. Rev. 97d:11017.

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

%H Peter Karpov, <a href="http://inversed.ru/InvMem.htm#InvMem_26">InvMem, Item 26</a>

%H Peter Karpov, <a href="/A007482/a007482_1.png">Illustration of initial terms (n = 1..8)</a>

%H Yuriy Sibirmovsky, <a href="/A007482/a007482_1.jpg">A fractal with number of elements described by a(n)</a>

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

%F G.f.: 1/(1-3*x-2*x^2).

%F a(n) = 3*a(n-1) + 2*a(n-2).

%F a(n) = (ap^(n+1)-am^(n+1))/(ap-am), where ap = (3+sqrt(17))/2 and am = (3-sqrt(17))/2.

%F Let b(0) = 1, b(k) = floor(b(k-1)) + 2/b(k-1); then, for n>0, b(n) = a(n)/a(n-1). - _Benoit Cloitre_, Sep 09 2002

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

%F a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)2^k*3^(n-2k). - _Paul Barry_, Apr 23 2005

%F a(n) = Sum_{k=0..n} A112906(n,k). - _Philippe Deléham_, Nov 21 2007

%F a(n) = - a(-2-n) * (-2)^(n+1) for all n in Z. - _Michael Somos_, Jun 03 2015

%F If c = (3 + sqrt(17))/2, then c^n = (A206776(n) + sqrt(17)*a(n-1)) / 2. - _Michael Somos_, Oct 13 2016

%F a(n) = 3^n*hypergeom([(1-n)/2,-n/2], [-n], -8/9) for n>=1. - _Peter Luschny_, Jun 28 2017

%F a(n) = round(((sqrt(17) + 3)/2)^(n+1)/sqrt(17)). The distance of the argument from the nearest integer is about 1/2^(n+3). - _M. F. Hasler_, Jun 16 2019

%F E.g.f.: (1/17)*exp(3*x/2)*(17*cosh(sqrt(17)*x/2) + 3*sqrt(17)*sinh(sqrt(17)*x/2)). - _Stefano Spezia_, Oct 07 2019

%F a(n) = (sqrt(2)*i)^n * ChebyshevU(n, -3*i/(2*sqrt(2))). - _G. C. Greubel_, Dec 24 2021

%F G.f.: 1/(1 - 3*x - 2*x^2) = Sum_{n >= 0} x^n * Product_{k = 1..n} (k + 2*x + 2)/(1 + k*x) (a telescoping series). Cf. A015518. - _Peter Bala_, May 08 2024

%e G.f. = 1 + 3*x + 11*x^2 + 39*x^3 + 139*x^4 + 495*x^5 + 1763*x^6 + ...

%e From _M. F. Hasler_, Jun 16 2019: (Start)

%e For n = 0, (1, ..., 2n) = () is the empty sequence, which is equal to its only subsequence, which satisfies the condition voidly, whence a(0) = 1.

%e For n = 1, (1, ..., 2n) = (1, 2); among the four subsequences {(), (1), (2), (1,2)} only (1) does not satisfy the condition, whence a(1) = 3.

%e For n = 2, (1, ..., 2n) = (1, 2, 3, 4); among the sixteen subsequences {(), ..., (1,2,3,4)}, the 5 subsequences (1), (3), (1,3), (2,3,4) and (1,2,3,4) do not satisfy the condition, whence a(2) = 16 - 5 = 11.

%e (End)

%p a := n -> `if`(n=0, 1, 3^n*hypergeom([(1-n)/2,-n/2], [-n], -8/9)):

%p seq(simplify(a(n)), n = 0..23); # _Peter Luschny_, Jun 28 2017

%t a[n_]:=(MatrixPower[{{1,4},{1,2}},n].{{1},{1}})[[2,1]]; Table[a[n],{n,0,40}] (* _Vladimir Joseph Stephan Orlovsky_, Feb 19 2010 *)

%t LinearRecurrence[{3,2},{1,3},30] (* _Harvey P. Dale_, May 25 2013 *)

%t a[ n_] := Module[ {m = n + 1, s = 1}, If[ m < 0, {m, s} = -{m, (-2)^m}]; s SeriesCoefficient[ x / (1 - 3 x - 2 x^2), {x, 0, m}]]; (* _Michael Somos_, Jun 03 2015 *)

%t a[ n_] := With[{m = n + 1}, If[ m < 0, (-2)^m a[ -m], Expand[((3 + Sqrt[17])/2)^m - ((3 - Sqrt[17])/2)^m ] / Sqrt[17]]]; (* _Michael Somos_, Oct 13 2016 *)

%o (Sage) [lucas_number1(n,3,-2) for n in range(1, 25)] # _Zerinvary Lajos_, Apr 22 2009

%o (PARI) {a(n) = 2*imag(( (3 + quadgen(68)) / 2)^(n+1))}; /* _Michael Somos_, Jun 03 2015 */

%o (Haskell)

%o a007482 n = a007482_list !! (n-1)

%o a007482_list = 1 : 3 : zipWith (+)

%o (map (* 3) $ tail a007482_list) (map (* 2) a007482_list)

%o -- _Reinhard Zumkeller_, Oct 21 2015

%o (Maxima) a(n) := if n=0 then 1 elseif n=1 then 3 else 3*a(n-1)+2*a(n-2);

%o makelist(a(n),n,0,12); /* _Emanuele Munarini_, Jun 28 2017 */

%o (Magma) I:=[1,3]; [n le 2 select I[n] else 3*Self(n-1) + 2*Self(n-2): n in [1..30]]; // _G. C. Greubel_, Jan 16 2018

%Y Row sums of triangle A073387.

%Y Cf. A000045, A000129, A001045, A007455, A007481, A007483, A007484, A015518, A201000 (prime subsequence), A052913 (binomial transform), A026597 (inverse binomial transform).

%Y Cf. A206776.

%K nonn,easy,nice

%O 0,2

%A _N. J. A. Sloane_