cp's OEIS Frontend

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

%I A007482 M2893 #153 Apr 18 2025 13:01:32
%S A007482 1,3,11,39,139,495,1763,6279,22363,79647,283667,1010295,3598219,
%T A007482 12815247,45642179,162557031,578955451,2061980415,7343852147,
%U A007482 26155517271,93154256107,331773802863,1181629920803,4208437368135
%N A007482 a(n) is the number of subsequences of [ 1, ..., 2n ] in which each odd number has an even neighbor.
%C A007482 The even neighbor must differ from the odd number by exactly one.
%C A007482 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 A007482 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 A007482 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 A007482 From _Gary W. Adamson_, Aug 06 2010: (Start)
%C A007482 Starting with "1" = INVERT transform of A002605: (1, 2, 6, 16, 44, ...).
%C A007482 Example: a(3) = 39 = (16, 6, 2, 1) dot (1, 1, 3, 11) = (16 + 6 + 6 + 11). (End)
%C A007482 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 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 A007482 With offset 1 (a(0) = 0, a(1) = 1) this is a divisibility sequence. - _Michael Somos_, Jun 03 2015
%C A007482 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 A007482 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 A007482 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 A007482 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 A007482 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 A007482 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A007482 Stephen Wolfram, A New Kind of Science, Wolfram Media, 2002, p. 439.
%H A007482 T. D. Noe, <a href="/A007482/b007482.txt">Table of n, a(n) for n = 0..200</a>
%H A007482 Paul Barry, <a href="https://arxiv.org/abs/2504.09719">Notes on Riordan arrays and lattice paths</a>, arXiv:2504.09719 [math.CO], 2025. See pp. 13, 29.
%H A007482 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 A007482 R. K. Guy and William O. J. Moser, <a href="https://web.archive.org/web/2024*/https://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 A007482 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=442">Encyclopedia of Combinatorial Structures 442</a>
%H A007482 Peter Karpov, <a href="http://inversed.ru/InvMem.htm#InvMem_26">InvMem, Item 26</a>
%H A007482 Peter Karpov, <a href="/A007482/a007482_1.png">Illustration of initial terms (n = 1..8)</a>
%H A007482 Yuriy Sibirmovsky, <a href="/A007482/a007482_1.jpg">A fractal with number of elements described by a(n)</a>
%H A007482 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,2).
%F A007482 G.f.: 1/(1-3*x-2*x^2).
%F A007482 a(n) = 3*a(n-1) + 2*a(n-2).
%F A007482 a(n) = (ap^(n+1)-am^(n+1))/(ap-am), where ap = (3+sqrt(17))/2 and am = (3-sqrt(17))/2.
%F A007482 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 A007482 The Hankel transform of this sequence is [1,2,0,0,0,0,0,0,0,...]. - _Philippe Deléham_, Nov 21 2007
%F A007482 a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)2^k*3^(n-2k). - _Paul Barry_, Apr 23 2005
%F A007482 a(n) = Sum_{k=0..n} A112906(n,k). - _Philippe Deléham_, Nov 21 2007
%F A007482 a(n) = - a(-2-n) * (-2)^(n+1) for all n in Z. - _Michael Somos_, Jun 03 2015
%F A007482 If c = (3 + sqrt(17))/2, then c^n = (A206776(n) + sqrt(17)*a(n-1)) / 2. - _Michael Somos_, Oct 13 2016
%F A007482 a(n) = 3^n*hypergeom([(1-n)/2,-n/2], [-n], -8/9) for n>=1. - _Peter Luschny_, Jun 28 2017
%F A007482 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 A007482 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 A007482 a(n) = (sqrt(2)*i)^n * ChebyshevU(n, -3*i/(2*sqrt(2))). - _G. C. Greubel_, Dec 24 2021
%F A007482 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 A007482 G.f. = 1 + 3*x + 11*x^2 + 39*x^3 + 139*x^4 + 495*x^5 + 1763*x^6 + ...
%e A007482 From _M. F. Hasler_, Jun 16 2019: (Start)
%e A007482 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 A007482 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 A007482 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 A007482 (End)
%p A007482 a := n -> `if`(n=0, 1, 3^n*hypergeom([(1-n)/2,-n/2], [-n], -8/9)):
%p A007482 seq(simplify(a(n)), n = 0..23); # _Peter Luschny_, Jun 28 2017
%t A007482 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 A007482 LinearRecurrence[{3,2},{1,3},30] (* _Harvey P. Dale_, May 25 2013 *)
%t A007482 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 A007482 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 A007482 (Sage) [lucas_number1(n,3,-2) for n in range(1, 25)] # _Zerinvary Lajos_, Apr 22 2009
%o A007482 (PARI) {a(n) = 2*imag(( (3 + quadgen(68)) / 2)^(n+1))}; /* _Michael Somos_, Jun 03 2015 */
%o A007482 (Haskell)
%o A007482 a007482 n = a007482_list !! (n-1)
%o A007482 a007482_list = 1 : 3 : zipWith (+)
%o A007482                (map (* 3) $ tail a007482_list) (map (* 2) a007482_list)
%o A007482 -- _Reinhard Zumkeller_, Oct 21 2015
%o A007482 (Maxima) a(n) := if n=0 then 1 elseif n=1 then 3 else 3*a(n-1)+2*a(n-2);
%o A007482 makelist(a(n),n,0,12); /* _Emanuele Munarini_, Jun 28 2017 */
%o A007482 (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 A007482 Row sums of triangle A073387.
%Y A007482 Cf. A000045, A000129, A001045, A007455, A007481, A007483, A007484, A015518, A201000 (prime subsequence), A052913 (binomial transform), A026597 (inverse binomial transform).
%Y A007482 Cf. A206776.
%K A007482 nonn,easy,nice
%O A007482 0,2
%A A007482 _N. J. A. Sloane_