This function appeared on page 870 in the discussion of binomial coefficients modulo 2, and will appear again in several other places in this book.

If balls are assumed to fall randomly on each side of each peg then with a large number of balls the final positions will approximate a binomial distribution.

And in the 1990s Ivan Korec and others showed that it could be done just with Mod[Binomial[a + b, a], k] with k = 6 or any product of primes—and that it could not be done with k a prime or prime power.

With a list s of possible symbols, c[s, n] gives all possible expressions with LeafCount[expr]  n : c[s_, 1] = s; c[s_, n_] := Flatten[ Table[Outer[#1[#2] &, c[s, n - m], c[s, m]], {m, n - 1}]] There are a total of Binomial[2n - 2, n - 1] Length[s] n /n such expressions.

Nand theorems The total number of expressions with n Nand s and s variables is: Binomial[2n, n]s n + 1 /(n + 1) (see page 897 ).

The number of such strings containing 2n characters is the n th Catalan number Binomial[2n, n]/(n + 1) (as obtained from the generating function (1 - Sqrt[1 - 4x])/(2x) ).

For k = 2 , the number of rules that conserve the total number of black cells can be computed from q = Binomial[n, Range[0, n]] as Apply[Times, q q ] .

From various number-theoretical results many relations can readily be encoded as integer equations: (a  0 ∨ b  0) ↔ a b  0 (a  0 ∧ b  0) ↔ a + b  0 a < b ↔ b  a + c + 1 a  Mod[b, c] ↔ (b  a + c d ∧ a < c) a  Quotient[b, c] ↔ (b  a c + d ∧ d < c) a  Binomial[b, c] ↔ With[{n = 2 b + 1}, (n + 1) b  n c (a + d n) + e ∧ e < n c ∧ a < n] a  b! ↔ a  Quotient[c b , Binomial[c, b]] a  GCD[b, c] ↔ (b c > 0 ∧ a d  b ∧ a e  c ∧ a + c f  b g) a  Floor[b/c] ↔ (a c + d  b ∧ d < c) PrimeQ[a] ↔ (GCD[(a - 1)!, a]  1 ∧ a > 1) a  BitAnd[c, d] ∧ b  BitOr[c, d] ↔ ( σ [c, a] ∧ σ [d, a] ∧ σ [b, c] ∧ σ [b, d] ∧ a + b  c + d)/. σ [x_, y_]  Mod[Binomial[x, y], 2]  1 where the last encoding uses the result on page 608 .

Other significant publications of mine providing relevant summaries were (the dates here are for actual publication—sometimes close to writing, but sometimes long delayed): • "Computers in science and mathematics" (September 1984) ( Scientific American article about foundations of the computational approach to science and mathematics) • "Cellular automata as models of complexity" (October 1984) ( Nature article introducing cellular automata) • "Geometry of binomial coefficients" (November 1984) (additive cellular automata and nested patterns) • "Twenty problems in the theory of cellular automata" (1985) (a list of unsolved problems to attack—most now finally resolved in this book) • "Tables of cellular automaton properties" (June 1986) (features of elementary cellular automata) • "Cryptography with cellular automata" (1986) (using rule 30 as a cryptosystem) • "Complex systems theory" (1988) (1984 speech suggesting the research direction for the new Santa Fe Institute)

Sierpiński pattern Other ways to generate step n of the pattern shown here in various orientations include: • Mod[Array[Binomial, {2, 2} n , 0], 2] (see pages 611 and 870 ) • 1 - Sign[Array[BitAnd, {2, 2} n , 0]] (see pages 608 and 871 ) • NestList[Mod[RotateLeft[#] + #, 2] &, PadLeft[{1}, 2 n ], 2 n - 1] (see page 870 ) • NestList[Mod[ListConvolve[{1, 1}, #, -1], 2] &, PadLeft[{1}, 2 n ], 2 n - 1] (see page 870 ) • IntegerDigits[NestList[BitXor[2#, #] &, 1, 2 n - 1], 2, 2 n ] (see page 906 ) • NestList[Mod[Rest[FoldList[Plus, 0, #]], 2] &, Table[1, {2 n }], 2 n - 1] (see page 1034 ) • Table[PadRight[ Mod[CoefficientList[(1 + x) t - 1 , x], 2], 2 n - 1], {t, 2 n }] (see pages 870 and 951 ) • Reverse[Mod[CoefficientList[Series[1/(1 - (1 + x)y), {x, 0, 2 n - 1}, {y, 0, 2 n - 1}], {x, y}], 2]] (see page 1091 ) • Nest[Apply[Join, MapThread[ Join, {{#, #}, {0 #, #}}, 2]] &, {{1}}, n] (compare page 1073 ) The positions of black squares can be found from: • Nest[Flatten[2# /.