|
|
A120562
|
|
Sum of binomial coefficients binomial(i+j, i) modulo 2 over all pairs (i,j) of positive integers satisfying 3i+j=n.
|
|
13
|
|
|
1, 1, 1, 2, 1, 2, 2, 3, 1, 3, 2, 3, 2, 4, 3, 5, 1, 4, 3, 4, 2, 5, 3, 5, 2, 5, 4, 6, 3, 7, 5, 8, 1, 6, 4, 5, 3, 7, 4, 7, 2, 6, 5, 7, 3, 8, 5, 8, 2, 7, 5, 7, 4, 9, 6, 10, 3, 9, 7, 10, 5, 12, 8, 13, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
a(n) is the number of 'vectors' (..., e_k, e_{k-1}, ..., e_0) with e_k in {0,1,3} such that Sum_{k} e_k 2^k = n. a(2^n-1) = F(n+1)*a(2^{k+1}+j) + a(j) = a(2^k+j) + a(2^{k-1}+j) if 2^k > 4j. This sequence corresponds to the pair (3,1) as Stern's diatomic sequence [A002487] corresponds to (2,1) and Gould's sequence [A001316] corresponds to (1,1). There are many interesting similarities to A000119, the number of representations of n as a sum of distinct Fibonacci numbers.
The Ca1 and Ca2 triangle sums, see A180662 for their definitions, of Sierpinski's triangle A047999 equal this sequence. Some A120562(2^n-p) sequences, 0 <= p <= 32, lead to known sequences, see the crossrefs. - Johannes W. Meijer, Jun 05 2011
|
|
LINKS
|
|
|
FORMULA
|
Recurrence; a(0)=a(1)=1, a(2*n)=a(n) and a(2*n+1)=a(n)+a(n-1).
G.f.: A(x) = Product_{i>=0} (1 + x^(2^i) + x^(3*2^i)) = (1 + x + x^3)*A(x^2).
|
|
EXAMPLE
|
a(2^n)=1 since a(2n)=a(n).
|
|
MAPLE
|
p := product((1+x^(2^i)+x^(3*2^i)), i=0..25): s := series(p, x, 1000): for k from 0 to 250 do printf(`%d, `, coeff(s, x, k)) od:
|
|
MATHEMATICA
|
a[0] = a[1] = 1; a[n_?EvenQ] := a[n] = a[n/2]; a[n_?OddQ] := a[n] = a[(n-1)/2] + a[(n-1)/2 - 1]; Table[a[n], {n, 0, 64}] (* Jean-François Alcover, Sep 29 2011 *)
Nest[Append[#1, If[EvenQ@ #2, #1[[#2/2 + 1]], Total@ #1[[#2 ;; #2 + 1]] & @@ {#1, (#2 - 1)/2}]] & @@ {#, Length@ #} &, {1, 1}, 10^4 - 1] (* Michael De Vlieger, Feb 19 2019 *)
|
|
CROSSREFS
|
Cf. A000012 (p=0), A000045 (p=1, p=2, p=4, p=8, p=16, p=32), A000071 (p=3, p=6, p=12, p=13, p=24, p=26), A001610 (p=5, p=10, p=20), A001595 (p=7, p=14, p=28), A014739 (p=11, p=22, p=29), A111314 (p=15, p=30), A027961 (p=19), A154691 (p=21), A001911 (p=23). - Johannes W. Meijer, Jun 05 2011
Same recurrence for odd n as A000930.
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Sam Northshield (samuel.northshield(AT)plattsburgh.edu), Aug 07 2006
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|