|
| |
|
|
A007482
|
|
a(n) is the number of subsequences of [ 1, ..., 2n ] in which each odd number has an even neighbor.
(Formerly M2893)
|
|
47
|
|
|
|
1, 3, 11, 39, 139, 495, 1763, 6279, 22363, 79647, 283667, 1010295, 3598219, 12815247, 45642179, 162557031, 578955451, 2061980415, 7343852147, 26155517271, 93154256107, 331773802863, 1181629920803, 4208437368135
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
The even neighbor must differ from the odd number by exactly one.
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.
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
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
Starting with "1" = INVERT transform of A002605: (1, 2, 6, 16, 44, ...).
Example: a(3) = 39 = (16, 6, 2, 1) dot (1, 1, 3, 11) = (16 + 6 + 6 + 11). (End)
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
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
With offset 1 (a(0) = 0, a(1) = 1) this is a divisibility sequence. - Michael Somos, Jun 03 2015
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
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
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
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
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
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Stephen Wolfram, A New Kind of Science, Wolfram Media, 2002, p. 439.
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: 1/(1-3*x-2*x^2).
a(n) = 3*a(n-1) + 2*a(n-2).
a(n) = (ap^(n+1)-am^(n+1))/(ap-am), where ap = (3+sqrt(17))/2 and am = (3-sqrt(17))/2.
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
The Hankel transform of this sequence is [1,2,0,0,0,0,0,0,0,...]. - Philippe Deléham, Nov 21 2007
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)2^k*3^(n-2k). - Paul Barry, Apr 23 2005
a(n) = - a(-2-n) * (-2)^(n+1) for all n in Z. - Michael Somos, Jun 03 2015
If c = (3 + sqrt(17))/2, then c^n = (A206776(n) + sqrt(17)*a(n-1)) / 2. - Michael Somos, Oct 13 2016
a(n) = 3^n*hypergeom([(1-n)/2,-n/2], [-n], -8/9)) for n>=1. - Peter Luschny, Jun 28 2017
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
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
a(n) = (sqrt(2)*i)^n * ChebyshevU(n, -3*i/(2*sqrt(2))). - G. C. Greubel, Dec 24 2021
|
|
|
EXAMPLE
|
G.f. = 1 + 3*x + 11*x^2 + 39*x^3 + 139*x^4 + 495*x^5 + 1763*x^6 + ...
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.
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.
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.
(End)
|
|
|
MAPLE
|
a := n -> `if`(n=0, 1, 3^n*hypergeom([(1-n)/2, -n/2], [-n], -8/9)):
|
|
|
MATHEMATICA
|
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 *)
LinearRecurrence[{3, 2}, {1, 3}, 30] (* Harvey P. Dale, May 25 2013 *)
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 *)
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 *)
|
|
|
PROG
|
(Sage) [lucas_number1(n, 3, -2) for n in range(1, 25)] # Zerinvary Lajos, Apr 22 2009
(PARI) {a(n) = 2*imag(( (3 + quadgen(68)) / 2)^(n+1))}; /* Michael Somos, Jun 03 2015 */
(Haskell)
a007482 n = a007482_list !! (n-1)
a007482_list = 1 : 3 : zipWith (+)
(map (* 3) $ tail a007482_list) (map (* 2) a007482_list)
(Maxima) a(n) := if n=0 then 1 elseif n=1 then 3 else 3*a(n-1)+2*a(n-2);
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
