JCA HomeIssue Contents

Formulas for the Number of States of an Interesting Finite Cellular Automaton and a Connection to Pascal’s Triangle
David J. Ettestad and Joaquin O. Carbonara

In 1992 Barry Cipra posed an interesting combinatorial counting problem. In essence, it asks for the number Sk,σ of configurations possible if a circular arrangement of k cups, each having σ stones, is modified by applying a particular transition rule that changes the distribution of stones. Carbonara and Green (1998) studied the integer sequence Sk,1 (a.k.a. Sk) and presented a recursive formula for it: Sk = 2S2r+1 + 2r−j Sd+1 + d2r − 2r+1 where k = 2r + 1 +d > 2, r ≥ 0 and 0 < d ≤ 2r. We note that this system is a finite Cellular Automaton. Taking advantage of previous work by Ettestad and Carbonara where properties of this CA are studied, we present here two non-recursive formulas for Sk,1, one of which involves the number of odd entries in the first nk rows of Pascal’s triangle.

Keywords: Cellular Automata, Combinatorics, Enumerative Combinatorics, Number Theory, Statistical mechanics.

Full Text (IP)