A027649 -id:A027649 - cp's OEIS frontend

A255297 Number of ON cells after n generations of the odd-rule cellular automaton defined by OddRule 035 when started with a single ON cell.

1, 4, 4, 14, 4, 16, 14, 46, 4, 16, 16, 56, 14, 56, 46, 146, 4, 16, 16, 56, 16, 64, 56, 184, 14, 56, 56, 196, 46, 184, 146, 454, 4, 16, 16, 56, 16, 64, 56, 184, 16, 64, 64, 224, 56, 224, 184, 584, 14, 56, 56, 196, 56, 224, 196, 644, 46, 184, 184, 644

Offset: 0

N. J. A. Sloane and Doron Zeilberger, Feb 23 2015

nonn

Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249, 2015.
N. J. A. Sloane, On the No. of ON Cells in Cellular Automata, Video of talk in Doron Zeilberger's Experimental Math Seminar at Rutgers University, Feb. 05 2015: Part 1, Part 2
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Index entries for sequences related to cellular automata

Cf. A027649.

a27649[n_] := 2(3^n) - 2^n;
Table[Times @@ (a27649[Length[#]]&) /@ Select[Split[IntegerDigits[n, 2]], #[[1]] == 1&], {n, 0, 59}] (* Jean-François Alcover, Sep 15 2018 *)

Run length transform of A027649.

A336703 Rectangular array read by antidiagonals. T(n,k) is the number of length k walks from {} to [n] in the digraph representation of the superset/subset relation on P([n]) the powerset of [n], n>=0, k>=0.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 4, 1, 0, 1, 8, 14, 8, 1, 0, 1, 16, 50, 46, 16, 1, 0, 1, 32, 178, 278, 146, 32, 1, 0, 1, 64, 634, 1666, 1454, 454, 64, 1, 0, 1, 128, 2258, 9998, 14230, 7358, 1394, 128, 1, 0, 1, 256, 8042, 59986, 139750, 115546, 36590, 4246, 256, 1, 0

Offset: 0

Geoffrey Critzer, Jul 31 2020

The superset/subset relation on P([n]) is defined as: for all A,B in P([n]), A ~ B iff A is a subset of B or B is a subset of A.

			1, 1, 1,  1,   1,    1,     1,      1,       1,...
0, 1, 2,  4,   8,    16,    32,     64,      128,...
0, 1, 4,  14,  50,   178,   634,    2258,    8042,...
0, 1, 8,  46,  278,  1666,  9998,   59986,   359918,...
0, 1, 16, 146, 1454, 14230, 139750, 1371494, 13461638,...

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 339.

Cf. A027649 (column k=3, number of edges in the digraph).

(* gives first 7 rows and 11 columns in about 3 minutes *)
Table[a = Subsets[Range[n]];f[list_] := Map[Apply[SubsetQ, #] &, list];
  G = Map[f,Table[Table[{a[[i]], a[[j]]}, {i, 1, 2^n}], {j, 1, 2^n}]] //
    Boole; H = (G - IdentityMatrix[2^n]) + Transpose[(G - IdentityMatrix[2^n]) + IdentityMatrix[2^n]];b = Inverse[IdentityMatrix[2^n] - z H] // Simplify; MatrixForm[b]; nn = 10; CoefficientList[Series[b[[1, 2^n]], {z, 0, nn}], z], {n, 0,6}] // Grid

A338131 Triangle read by rows, T(n, k) = k^(n - k) + Sum_{i = 1..n-k} k^(n - k - i)*2^(i - 1), for 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 4, 4, 3, 1, 8, 8, 8, 4, 1, 16, 16, 20, 14, 5, 1, 32, 32, 48, 46, 22, 6, 1, 64, 64, 112, 146, 92, 32, 7, 1, 128, 128, 256, 454, 376, 164, 44, 8, 1, 256, 256, 576, 1394, 1520, 828, 268, 58, 9, 1, 512, 512, 1280, 4246, 6112, 4156, 1616, 410, 74, 10, 1

Offset: 0

Werner Schulte, Oct 11 2020

This number triangle is case s = 2 of the triangles T(s; n,k) depending on some fixed integer s. Here are several (generalized) formulas and properties (attention: negative values are possible if s < 0):
  (1) T(s; n,k) = k^(n-k) + Sum_{i=1..n-k} k^(n-k-i)*s^(i-1) for 0<=k<=n;
  (2) T(s; n,n) = 1 for n >= 0, and T(s; n,n-1) = n for n > 0;
  (3) T(s; n+1,k) = k * T(s; n,k) + s^(n-k) for 0<=k<=n;
  (4) T(s; n,k) = (k+s) * T(s; n-1,k) - s*k * T(s; n-2,k) for 0<=k<=n-2;
  (5) G.f. of column k: Sum_{n>=k} T(s; n,k)*t^n = ((1-(s-1)*t)/(1-s*t))
      *(t^k/(1-k*t)) when t^k/(1-k*t) is g.f. of column k>=0 of A004248.

			The number triangle T(n, k) for 0 <= k <= n starts:
n\ k :    0     1      2      3      4      5      6     7    8    9   10
=========================================================================
   0 :    1
   1 :    1     1
   2 :    2     2      1
   3 :    4     4      3      1
   4 :    8     8      8      4      1
   5 :   16    16     20     14      5      1
   6 :   32    32     48     46     22      6      1
   7 :   64    64    112    146     92     32      7     1
   8 :  128   128    256    454    376    164     44     8    1
   9 :  256   256    576   1394   1520    828    268    58    9    1
  10 :  512   512   1280   4246   6112   4156   1616   410   74   10   1

Cf. A004248.

For columns k = 0, 1, 2, 3, 4 see A011782, A000079, A001792, A027649, A010036 respectively.

T := proc(n, k) if k = 0 then `if`(n = 0, 1, 2^(n-1)) elif k = 2 then n*2^(n-3)
else (k^(n-k)*(1-k) + 2^(n-k))/(2-k) fi end:
seq(seq(T(n, k), k=0..n), n=0..10); # Peter Luschny, Oct 29 2020

T(n,k) = k^(n-k) + sum(i=1, n-k, k^(n-k-i) * 2^(i-1));
matrix(7,7, n, k, if(n>=k, T(n-1,k-1), 0)) \\ to see the triangle \\ Michel Marcus, Oct 12 2020

T(n,k) = ((k-1) * k^(n-k) - 2^(n-k)) / (k-2) if k <> 2, and T(n,2) = n * 2^(n-3) for n >= k.
T(n,n) = 1 for n >= 0, and T(n,n-1) = n for n > 0.
T(n+1,k) = k * T(n,k) + 2^(n-k) for 0 <= k <= n.
T(n,k) = (k+2) * T(n-1,k) - 2*k * T(n-2,k) for 0 <= k <= n-2.
T(n,k) = k * T(n-1,k) + T(n-1,k-1) - (k-1) * T(n-2,k-1) for 0 < k < n.
G.f. of column k >= 0: Sum_{n>=k} T(n,k) * t^n = ((1-t) / (1-2*t)) * (t^k / (1-k*t)) when t^k / (1-k*t) is g. f. of column k of A004248.
G.f.: Sum_{n>=0, k=0..n} T(n,k) * x^k * t^n = ((1-t) / (1-2*t)) * (Sum_{k>=0} (x*t)^k / (1-k*t)).

A385178 Triangle T(n,k) read by rows in which the n-th diagonal lists the n-th differences of A001047, 0 <= k <= n.

Original entry on oeis.org

0, 1, 1, 3, 4, 5, 7, 10, 14, 19, 15, 22, 32, 46, 65, 31, 46, 68, 100, 146, 211, 63, 94, 140, 208, 308, 454, 665, 127, 190, 284, 424, 632, 940, 1394, 2059, 255, 382, 572, 856, 1280, 1912, 2852, 4246, 6305, 511, 766, 1148, 1720, 2576, 3856, 5768, 8620, 12866, 19171

Offset: 0

Paul Curtz, Jun 20 2025

			Triangle begins:
    0;
    1,   1;
    3,   4,    5;
    7,  10,   14,   19;
   15,  22,   32,   46,   65;
   31,  46,   68,  100,  146,  211;
   63,  94,  140,  208,  308,  454,  665;
  127, 190,  284,  424,  632,  940, 1394, 2059;
  255, 382,  572,  856, 1280, 1912, 2852, 4246,  6305;
  511, 766, 1148, 1720, 2576, 3856, 5768, 8620, 12866, 19171;
  ...

Columns k=0..2: A000225, A033484, A053209 (sans 1).
Diagonals: A001047, A027649, A053581 (sans 1), A291012 (sans 2).
Cf. A028243 (row sums), A036561, A059268, A081656, A248216, A321003.

/* As triangle */ [[2^(n-k)*3^k - 2^k : k in [0..n]]: n in [0..9]]; // Vincenzo Librandi, Jun 27 2025

T:= proc(n,k) option remember;
     `if`(n=k, 3^n-2^n, T(n, k+1)-T(n-1, k))
    end:
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Jun 24 2025

t[n_, 0] := 3^n - 2^n; t[n_, k_] := t[n, k] = t[n + 1, k - 1] - t[n, k - 1]; Table[t[k, n - k], {n, 0, 9}, {k, 0, n}] // Flatten (* Amiram Eldar, Jun 20 2025 *)

T(n,n) = 3^n - 2^n = A001047(n).
T(n,k) = T(n,k+1) - T(n-1,k) for 0 <= k < n.
T(n,k) = 2^(n-k)*3^k - 2^k = A036561(n,k) - A059268(n,k).
T(2n,n) = A248216(n+1).

cp's OEIS Frontend

A255297 Number of ON cells after n generations of the odd-rule cellular automaton defined by OddRule 035 when started with a single ON cell.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A336703 Rectangular array read by antidiagonals. T(n,k) is the number of length k walks from {} to [n] in the digraph representation of the superset/subset relation on P([n]) the powerset of [n], n>=0, k>=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A338131 Triangle read by rows, T(n, k) = k^(n - k) + Sum_{i = 1..n-k} k^(n - k - i)*2^(i - 1), for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

Formula

A385178 Triangle T(n,k) read by rows in which the n-th diagonal lists the n-th differences of A001047, 0 <= k <= n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Magma

Maple

Mathematica

Formula