|
|
A078008
|
|
Expansion of (1-x)/( (1+x)*(1-2*x) ).
|
|
134
|
|
|
1, 0, 2, 2, 6, 10, 22, 42, 86, 170, 342, 682, 1366, 2730, 5462, 10922, 21846, 43690, 87382, 174762, 349526, 699050, 1398102, 2796202, 5592406, 11184810, 22369622, 44739242, 89478486, 178956970, 357913942, 715827882, 1431655766, 2863311530, 5726623062
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Conjecture: a(n) = the number of fractions in the infinite Farey row of 2^n terms with even denominators. Compare the Salamin & Gosper item in the Beeler et al. link. - Gary W. Adamson, Oct 27 2003
Counts closed walks starting and ending at the same vertex of a triangle. 3*a(n) = P(C_n, 3) chromatic polynomial for 3 colors on cyclic graph C_n. A078008(n) + 2*A001045(n) = 2^n provides decomposition of Pascal's triangle. - Paul Barry, Nov 17 2003
Permutations with one fixed point avoiding 123 and 132.
The inverse g.f. generates sequence 1, 0, -2, -2, -2, -2, ...
a(n) gives the number of oriented (i.e., unreduced for symmetry) meanders on an (n+2) X 3 rectangular grid; see A201145. - Jon Wild, Nov 22 2011
Pisano period lengths: 1, 1, 6, 1, 4, 6, 6, 2, 18, 4, 10, 6, 12, 6, 12, 2, 8, 18, 18, 4, ... - R. J. Mathar, Aug 10 2012
a(n) is the number of length n binary words that end in an odd length run of 0's if we do not include the first letter of the word in our run length count. a(4) =6 because we have 0000, 0010, 0110, 1000, 1010, 1110. - Geoffrey Critzer, Dec 16 2013
a(n) is the top left entry of the n-th power of any of the six 3 X 3 matrices [0, 1, 1; 1, 1, 1; 1, 0, 0], [0, 1, 1; 1, 1, 0; 1, 1, 0], [0, 1, 1; 1, 0, 1; 1, 1, 0], [0, 1, 1; 1, 1, 0; 1, 0, 1], [0, 1, 1; 1, 0, 1; 1, 0, 1] or [0, 1, 1; 1, 0, 0; 1, 1, 1]. - R. J. Mathar, Feb 04 2014
a(n) is the number of compositions of n into parts of two kinds without part 1. - Gregory L. Simay, Jun 04 2018
a(n) is the number of words of length n over a binary alphabet whose position in the lexicographic order is a multiple of three. a(3) = 2: aba, bab. - Alois P. Heinz, Apr 13 2022
a(n) is the number of words of length n over a ternary alphabet starting with a fixed letter (say, 'a') and ending in a different letter, such that no two adjacent letters are the same. a(4) = 6: abab, abac, abcb, acab, acac, acbc. - Ignat Soroko, Jul 19 2023
|
|
REFERENCES
|
Kenneth Edwards, Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 1.1.10a.
|
|
LINKS
|
|
|
FORMULA
|
Euler expands(1-x)/(1 - x - 2*x^2) into an infinite series and finds that the coefficient of the n-th term is (2^n + (-1)^n 2)/3. Section 226 shows that Euler could have easily found the recursion relation: a(n) = a(n-1) + 2a(n-2) with a(0) = 1 and a(1) = 0. - V. Frederick Rickey (fred-rickey(AT)usma.edu), Feb 10 2006. [Typos corrected by Jaume Oliver Lafont, Jun 01 2009]
a(n) = Sum_{k=0..floor(n/3)} binomial(n, f(n)+3*k) where f(n) = (0, 2, 1, 0, 2, 1, ...) = A080424(n). - Paul Barry, Feb 20 2003
E.g.f. (exp(2*x) + 2*exp(-x))/3. - Paul Barry, Apr 20 2003
a(n) = (2^n + 2*(-1)^n)/3. - Mario Catalani (mario.catalani(AT)unito.it), Aug 29 2003
a(n) = T(n, i/(2*sqrt(2)))(-i*sqrt(2)^n - U(n-1, i/(2*sqrt(2)))(-i*sqrt(2))^(n-1)/2 - Paul Barry, Nov 17 2003
a(n) = 2*a(n-1) + 2*(-1)^n for n > 0, with a(0)=1.
a(n) = Sum_{k=0..n} (-1)^k*(2^(n-k-1) + 0^(n-k)/2). (End)
If p[1] =0, and p[i]=2, (i>1), and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det A. - Milan Janjic, Apr 29 2010
a(n) = 2*(a(n-2) + a(n-3) + a(n-4) ... + a(0)), that is, twice the sum of all the previous terms except the last; with a(0) = 1 and a(1) = 0. - Benoit Jubin, Nov 21 2011
G.f.: 1 - x + x*Q(0), where Q(k) = 1 + 2*x^2 + (2*k+3)*x - x*(2*k+1 + 2*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 05 2013
G.f.: 1+ x^2*Q(0), where Q(k) = 1 + 1/(1 - x*(4*k+1+2*x)/(x*(4*k+3+2*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 01 2014
a(n) = -a(2-n) * (-2)^(n-1) = (3/2)*(a(n-1) + a(n-2)) - a(n-3) for all n in Z. - Michael Somos, Mar 18 2022
|
|
EXAMPLE
|
G.f. = 1 + 2*x^2 + 2*x^3 + 6*x^4 + 10*x^5 + 22*x^6 + ... - Michael Somos, Mar 18 2022
|
|
MATHEMATICA
|
CoefficientList[Series[(1-x)/(1-x-2x^2), {x, 0, 40}], x] (* Harvey P. Dale, Mar 30 2011 *)
|
|
PROG
|
(Magma) [(2^n + 2*(-1)^n)/3: n in [0..40]]; // G. C. Greubel, Jun 28 2019
(Sage) [(2^n + 2*(-1)^n)/3 for n in (0..40)] # G. C. Greubel, Jun 28 2019
(GAP) List([0..40], n-> (2^n + 2*(-1)^n)/3) # G. C. Greubel, Jun 28 2019
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|