login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A276027 Number of ways to transform a sequence of n ones to a single number by continually removing two numbers and replacing them with their sum modulo 3. 3
1, 1, 1, 2, 4, 7, 18, 43, 93, 266, 702, 1687, 5136, 14405, 36898, 117016, 341842, 914064, 2983027, 8972121, 24743851, 82478973, 253555061, 715745648, 2424954125, 7582390623, 21796481477, 74805170349, 237095926682, 691568408221, 2398418942361, 7686495623620 (list; graph; refs; listen; history; text; internal format)
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.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..1000

C. Ji, Enumerative Properties of Posets Corresponding to a Certain Class of No Strategy Games, arXiv:1608.06025 [math.CO], 2016

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 map(a, xrange(1, 36)) # Indranil Ghosh, Aug 09 2017, after Maple code

CROSSREFS

Cf. A002846, A117143.

Similar to A002846 with nodes taken modulo 3.

A117143 is the total number of nodes in this poset.

Sequence in context: A259351 A232484 A223013 * A101569 A225435 A243049

Adjacent sequences:  A276024 A276025 A276026 * A276028 A276029 A276030

KEYWORD

nonn

AUTHOR

Caleb Ji, Aug 16 2016

EXTENSIONS

a(19)-a(32) from Alois P. Heinz, Aug 18 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 18:24 EST 2018. Contains 299628 sequences. (Running on oeis4.)