OFFSET
1,4
COMMENTS
Can be considered as the number of maximal chains in a poset whose nodes are the possible states of the sequence. In this sense it counts the same things as A002846 when the elements of that poset are taken modulo 3.
Originally this entry had a reference to a paper on the arXiv by Caleb Ji, Enumerative Properties of Posets Corresponding to a Certain Class of No Strategy Games, arXiv:1608.06025 [math.CO], 2016. However, this article has since been removed from the arXiv. - N. J. A. Sloane, Sep 07 2018
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..1000
C. Ji, Example for a(7)
FORMULA
a(n) = f(0, n, 0) where f(a, b, c) is the number of ways to reach one number beginning with a zeros, b ones, and c twos.
Then f(a, b, c) = f_1 + f_2 + f_3 + f_4 where f_1 = f(a-1, b, c) if a>=2 or a, b >=1 or a,c >=1, f_2 = f(a, b-2, c+1) if b >= 2, f_3 = f(a, b+1, c-2) if c >= 2, and f_4 = f(a+1, b-1, c-1) if b, c >= 1, and each are 0 otherwise. Initial terms: f(a, b, c) = 1 for all 1 <= a+b+c <= 2, where a, b, c >= 0.
EXAMPLE
For n = 4, the two ways are 1111 -> 211 -> 10 -> 1 and 1111 -> 211 -> 22 -> 1.
MAPLE
b:= proc(x, y, z) option remember;
`if`(x+y+z=1, 1, `if`(y>0 and z>0, b(x+1, y-1, z-1), 0)+
`if`(x>1 or x>0 and y>0 or x>0 and z>0, b(x-1, y, z), 0)+
`if`(y>1, b(x, y-2, z+1), 0)+`if`(z>1, b(x, y+1, z-2), 0))
end:
a:= n-> b(0, n, 0):
seq(a(n), n=1..35); # Alois P. Heinz, Aug 18 2016
MATHEMATICA
b[x_, y_, z_] := b[x, y, z] = If[x+y+z==1, 1, If[y>0 && z>0, b[x+1, y-1, z-1], 0] + If[x>1 || x>0 && y>0 || x>0 && z>0, b[x-1, y, z], 0] + If[y>1, b[x, y-2, z+1], 0] + If[z>1, b[x, y+1, z-2], 0]]; a[n_]:= b[0, n, 0]; Array[a, 35] (* Jean-François Alcover, Aug 07 2017, after Alois P. Heinz *)
PROG
(Python)
from sympy.core.cache import cacheit
@cacheit
def b(x, y, z): return 1 if x + y + z==1 else (b(x + 1, y - 1, z - 1) if y>0 and z>0 else 0) + (b(x - 1, y, z) if x>1 or x>0 and y>0 or x>0 and z>0 else 0) + (b(x, y - 2, z + 1) if y>1 else 0) + (b(x, y + 1, z - 2) if z>1 else 0)
def a(n): return b(0, n, 0)
print([a(n) for n in range(1, 36)]) # Indranil Ghosh, Aug 09 2017, after Maple code
CROSSREFS
KEYWORD
nonn
AUTHOR
Caleb Ji, Aug 16 2016
EXTENSIONS
a(19)-a(32) from Alois P. Heinz, Aug 18 2016
STATUS
approved