A007483 -id:A007483 - cp's OEIS frontend

A269522 Number of active (ON, black) cells in n-th stage of growth of two-dimensional cellular automaton defined by "Rule 622", based on the 5-celled von Neumann neighborhood.

1, 5, 9, 21, 25, 37, 57, 69, 89, 101, 121, 133, 169, 205, 257, 309, 361, 333, 377, 381, 385, 461, 465, 509, 601, 653, 697, 781, 889, 845, 1097, 1077, 1353, 1205, 1305, 1349, 1345, 1357, 1321, 1437, 1553, 1589, 1601, 1709, 1729, 1813, 1937, 2069, 2361, 2181

Offset: 0

Robert Price, Feb 28 2016

Initialized with a single black (ON) cell at stage zero.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Robert Price, Table of n, a(n) for n = 0..300
Robert Price, Diagrams of first 20 stages
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168, 2015
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Index entries for sequences related to cellular automata
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata

Cf. A007483, A072272, A170878, A253908.

rule=622; stages=300; ca=CellularAutomaton[ {rule,{2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}}, {{{1}},0}, stages]; (* Start with single black cell *) Map[Function[Apply[Plus,Flatten[#1]]],ca] (* Count ON cells at each stage *)

A193731 Mirror of the triangle A193730.

Original entry on oeis.org

1, 1, 2, 3, 8, 4, 9, 30, 28, 8, 27, 108, 144, 80, 16, 81, 378, 648, 528, 208, 32, 243, 1296, 2700, 2880, 1680, 512, 64, 729, 4374, 10692, 14040, 10800, 4896, 1216, 128, 2187, 14580, 40824, 63504, 60480, 36288, 13440, 2816, 256, 6561, 48114, 151632, 272160, 308448, 229824, 112896, 35328, 6400, 512

Offset: 0

Clark Kimberling, Aug 04 2011

A193731 is obtained by reversing the rows of the triangle A193730.

Triangle T(n,k), read by rows, given by (1,2,0,0,0,0,0,0,0,...) DELTA (2,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 05 2011

			First six rows:
   1;
   1,   2;
   3,   8,   4;
   9,  30,  28,   8;
  27, 108, 144,  80,  16;
  81, 378, 648, 528, 208, 32;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A000012, A000079, A005053, A006234, A007483, A080420, A080421.
Cf. A080422, A080423, A084938, A130129, A133494, A153881.
Cf. A193722, A193730.

function T(n, k) // T = A193731
  if k lt 0 or k gt n then return 0;
  elif n lt 2 then return k+1;
  else return 3*T(n-1, k) + 2*T(n-1, k-1);
  end if;
end function;
[T(n, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Nov 20 2023

(* First program *)
z = 8; a = 2; b = 1; c = 2; d = 1;
p[n_, x_] := (a*x + b)^n ; q[n_, x_] := (c*x + d)^n
t[n_, k_] := Coefficient[p[n, x], x^k]; t[n_, 0] := p[n, x] /. x -> 0;
w[n_, x_] := Sum[t[n, k]*q[n + 1 - k, x], {k, 0, n}]; w[-1, x_] := 1
g[n_] := CoefficientList[w[n, x], {x}]
TableForm[Table[Reverse[g[n]], {n, -1, z}]]
Flatten[Table[Reverse[g[n]], {n, -1, z}]]  (* A193730 *)
TableForm[Table[g[n], {n, -1, z}]]
Flatten[Table[g[n], {n, -1, z}]]     (* A193731 *)
(* Second program *)
T[n_, k_]:= T[n, k]= If[k<0 || k>n, 0, If[n<2, k+1, 3*T[n-1, k] + 2*T[n -1, k-1]]];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Nov 20 2023 *)

def T(n, k): # T = A193731
    if (k<0 or k>n): return 0
    elif (n<2): return k+1
    else: return 3*T(n-1, k) + 2*T(n-1, k-1)
flatten([[T(n, k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Nov 20 2023

T(n,k) = A193730(n,n-k).
T(n,k) = 2*T(n-1,k-1) + 3*T(n-1,k) with T(0,0)=T(1,0)=1 and T(1,1)=2. - Philippe Deléham, Oct 05 2011
G.f.: (1-2*x)/(1-3*x-2*x*y). - R. J. Mathar, Aug 11 2015
From G. C. Greubel, Nov 20 2023: (Start)
T(n, 0) = A133494(n).
T(n, 1) = 2*A006234(n+2).
T(n, 2) = 4*A080420(n-2).
T(n, 3) = 8*A080421(n-3).
T(n, 4) = 16*A080422(n-4).
T(n, 5) = 32*A080423(n-5).
T(n, n) = A000079(n).
T(n, n-1) = A130129(n-1).
Sum_{k=0..n} T(n, k) = A005053(n).
Sum_{k=0..n} (-1)^k * T(n, k) = A153881(n).
Sum_{k=0..floor(n/2)} T(n-k, k) = A007483(n-1).
Sum_{k=0..floor(n/2)} (-1)^k * T(n-k, k) = A000012(n). (End)

A209171 Triangle of coefficients of polynomials v(n,x) jointly generated with A209170; see the Formula section.

Original entry on oeis.org

1, 3, 2, 6, 8, 3, 12, 25, 19, 5, 24, 68, 77, 40, 8, 48, 172, 259, 201, 80, 13, 96, 416, 782, 806, 478, 154, 21, 192, 976, 2200, 2825, 2222, 1067, 289, 34, 384, 2240, 5888, 9048, 8857, 5640, 2277, 532, 55, 768, 5056, 15184, 27160, 31787, 25184, 13483

Offset: 1

Clark Kimberling, Mar 08 2012

Column 1:  Fibonacci numbers (A000045).
Alternating row sums: 1,1,1,1,1,1,1,1,1,1,1,1,...
For a discussion and guide to related arrays, see A208510.
Subtriangle of (1, 2, -3/2, 1/2, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (0, 2, -1/2, -1/2, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Mar 10 2012

			First five rows:
   1;
   3,  2;
   6,  8,  3;
  12, 25, 19,  5;
  24, 68, 77, 40,  8;
First three polynomials v(n,x):
  1
  3 + 2x
  6 + 8x + 3x^2.
From _Philippe Deléham_, Mar 10 2012: (Start)
Triangle (1, 2, -3/2, 1/2, 0, 0, ...) DELTA (0, 2, -1/2, -1/2, 0, 0, ...) begins (0 <= k <= n):
   1;
   1,   0;
   3,   2,   0;
   6,   8,   3,   0;
  12,  25,  19,   5,   0;
  24,  68,  77,  40,   8,   0;
  48, 172, 259, 201,  80,  13,   0;
  96, 416, 782, 806, 478, 154,  21,   0; (End)

Cf. A209170, A208510.

u[1, x_] := 1; v[1, x_] := 1; z = 16;
u[n_, x_] := u[n - 1, x] + (x + 1)*v[n - 1, x];
v[n_, x_] := (x + 1)*u[n - 1, x] + (x + 1)*v[n - 1, x] + 1;
Table[Expand[u[n, x]], {n, 1, z/2}]
Table[Expand[v[n, x]], {n, 1, z/2}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Flatten[%]    (* A209170 *)
Table[Expand[v[n, x]], {n, 1, z}]
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
Flatten[%]    (* A209171 *)

u(n,x) = u(n-1,x) + (x+1)*v(n-1,x),
v(n,x) = (x+1)*u(n-1,x) + (x+1)*v(n-1,x)+1,
where u(1,x)=1, v(1,x)=1.
T(n,k) = 2*T(n-1,k) + T(n-1,k-1) + T(n-2,k-1) + T(n-2,k-2), T(1,0) = 1, T(2,0) = 3, T(2,1) = 2. - Philippe Deléham, Mar 10 2012
Sum_{k=0..n} T(n,k)*x^k = A000012(n), A003945(n-1), A007483(n-1) for x = -1, 0, 1 respectively. - Philippe Deléham, Mar 10 2012
G.f.: (-1-x-x*y)*x*y/(-1+2*x+x*y+x^2*y^2+x^2*y). - R. J. Mathar, Aug 12 2015

A138277 Total number of active nodes of the Rule 150 cellular automaton on an infinite Bethe lattice with coordination number 4 (with a single 1 as initial condition).

Original entry on oeis.org

1, 5, 13, 49, 109, 473, 1081, 4037, 8749, 37913, 88465, 325021, 717337, 3108461, 7095613, 26490289, 57395629, 248714393, 580333585, 2132141341, 4707150193, 20397650837, 46548642709, 173816036825, 376630110937, 1632063814061, 3808148899477, 13991111158153

Offset: 0

Jens Christian Claussen (claussen(AT)theo-physik.uni-kiel.de), Mar 11 2008

nonn

See A138276 for the corresponding sequence for a Bethe lattice with coordination number 3.
See A001045 for the corresponding sequence on a 1D lattice (equivalent to a k=2 Bethe lattice); this is based on the Jacobsthal sequence A001045.
See A072272 for the corresponding sequence on a 2D lattice (based on A007483).
Related to Cellular Automata.

			Let x_0 be the state (0 or 1) of the focal node and x_i the state of every node that is i steps away from the focal node. In time step n=0, all x_i=0 except x_0=1 (start with a single seed). In the next step, x_1=1 as they have 1 neighbor being 1. For n=2, the x_1 nodes have 1 neighbor being 1 (x_0) and themselves being 1; the sum being 2, modulo 2, resulting in x_1=0.
The focal node and outmost nodes x_n are always 1.
Thus one has the patterns
x_0, x_1, x_2, ...
1
1 1
1 0 1
1 0 1 1
1 0 0 0 1
1 1 0 1 1 1
1 0 0 0 1 0 1
1 1 0 1 1 0 1 1
1 0 0 0 0 0 0 0 1
(N.B.: This is equivalent to the right half plane of Rule 150 in 1D.)
The nodes have the multiplicities 1,4,12,36,108,324,972,...
The sequence then is obtained by
a(n)= x_0(n) + 4*(x_1(n) + sum_(i=2...n) x_i(n) * 3^(i-1)).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Jens Christian Claussen, Time-evolution of the Rule 150 cellular automaton activity from a Fibonacci iteration [broken link]
Jens Christian Claussen, Time-evolution of the Rule 150 cellular automaton activity from a Fibonacci iteration, arXiv:math.CO/0410429.
Jan Nagler and Jens Christian Claussen (2005), 1/f^alpha spectra in elementary cellular automata and fractal signals, Phys. Rev. E 71 (2005), 067103

Cf. A138276, A072272, A007483, A071053, A001045.

nmax = 30;
states = CellularAutomaton[150, {{1}, 0}, nmax];
T[n_, i_] := states[[n+1, nmax+i+1]];
a[n_] := T[n, 0] + 4(T[n, 1]+Sum[3^(i-1) T[n, i], {i, 2, n}]);
Table[a[n], {n, 0, nmax}] (* Jean-François Alcover, Aug 20 2018 *)

The total number of nodes in state 1 after n iterations (starting with a single 1) of the Rule 150 cellular automaton on an infinite Bethe lattice with coordination number 4. Rule 150 sums the values of the focal node and its k neighbors, then applies modulo 2.

a(9)-a(27) from Alois P. Heinz, Jun 28 2015

A331211 Number of green nodes in n-th power graph W exponentiation of a cycle graph with 7 blue nodes and one green node.

Original entry on oeis.org

1, 15, 117, 891, 6777, 51543, 392013, 2981475, 22675761, 172461663, 1311666021, 9975943179, 75872547369, 577052549415, 4388802753213, 33379264377459, 253867706760033, 1930803860947887, 14684827767302997, 111686210555580315, 849435201142733529, 6460422977475127287

Offset: 0

George Strand Vajagich, Mar 01 2020

			For n = 2 take g(1)=15 and b(1)=51. Multiply b(1) by 2 to get 102 add 15 to get 117.
For n = 3 take g(2)=117 and b(2)=387. Multiply b(2) by 2 to get 774 add 177 to get 891.

Colin Barker, Table of n, a(n) for n = 0..1000
Thezebraherd user, Graph W multiplication, Youtube video.
Index entries for linear recurrences with constant coefficients, signature (8,-3).

Cf. A332936 (number of blue nodes).

Similar sequences with a cycle size 3..6 are: A007483, A048876, A189274(n+1), A054490.

Vec((1 + 7*x) / (1 - 8*x + 3*x^2) + O(x^20)) \\ Colin Barker, Mar 03 2020

g=1
b=7
sg=0
sb=0
bl=[]
gl=[]
for int in range(1,20):
  sg=g*1+b*2
  sb=b*7+g*2
  g=sg
  b=sb
  gl.append(g)
  bl.append(b)
print(gl)

a(n) = a(n-1) + 2*b(n-1), b(n) = 2*a(n-1) + 7*b(n-1) with a(0) = 1 and b(0) = 7 where b(n) = A332936(n).
From Colin Barker, Mar 03 2020: (Start)
G.f.: (1 + 7*x) / (1 - 8*x + 3*x^2).
a(n) = 8*a(n-1) - 3*a(n-2) for n>1.
(End)
From Stefano Spezia, Mar 03 2020: (Start)
a(n) = ((4 - sqrt(13))^n*(-11 + sqrt(13)) + (4 + sqrt(13))^n*(11 + sqrt(13)))/(2*sqrt(13)).
E.g.f.: exp(4*x)*cosh(sqrt(13)*x) + (11*exp(4*x)*sinh(sqrt(13)*x))/sqrt(13).
(End)

a(14)-a(21) from Stefano Spezia, Mar 03 2020

Typo in a(14) fixed by Colin Barker, Apr 26 2020

A374096 Number of edge covers of fan graph F_{1,n}.

Original entry on oeis.org

1, 4, 16, 59, 214, 768, 2745, 9792, 34900, 124339, 442906, 1577540, 5618665, 20011452, 71272296, 253840779, 904068526, 3219889720, 11467810393, 40843217384, 145465283884, 518082304131, 1845177508818, 6571697181084, 23405446635913, 83359734391300, 296890096642144

Offset: 1

Feryal Alayont, Jun 28 2024

			The fan graph F_{1,2} is the cycle with three vertices and has 4 edge covers.
The graph F_{1,3} is formed by adding a chord to the cycle with four vertices. The cycle C_4 has 7 edge covers, so there are 7 edge covers of F_{1,3} without the chord. If the chord is there, the two endpoints are covered. To cover the remaining two vertices, we need at least one of the two edges on each side of each vertex, giving us 3*3 choices total. So we have 16 edge covers for F_{1,3}.
We interpret F_{1,1} to be the path with two vertices with one edge cover.

Paolo Xausa, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Fan Graph
Index entries for linear recurrences with constant coefficients, signature (4,0,-5,-2).

LinearRecurrence[{4, 0, -5, -2}, {1, 4, 16, 59}, 30] (* Paolo Xausa, Jan 22 2025 *)

a(n) = 4*a(n-1)-5*a(n-3)-2*a(n-4).
G.f.: x/((1 - x - x^2)*(1 - 3*x - 2*x^2)). - Stefano Spezia, Jun 29 2024
a(n) = A007483(n-1) - A212804(n). - R. J. Mathar, Jun 29 2024

A052986 Expansion of ( 1-2x ) / ( (x-1)(2x^2+3x-1) ).

Original entry on oeis.org

1, 2, 7, 24, 85, 302, 1075, 3828, 13633, 48554, 172927, 615888, 2193517, 7812326, 27824011, 99096684, 352938073, 1257007586, 4476898903, 15944711880, 56787933445, 202253224094, 720335539171, 2565513065700, 9137210275441, 32542656957722, 115902391424047

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1060
Index entries for linear recurrences with constant coefficients, signature (4,-1,-2).

I:=[1, 2, 7]; [n le 3 select I[n] else 4*Self(n-1)-Self(n-2)-2*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jun 23 2012

spec := [S,{S=Sequence(Union(Prod(Union(Sequence(Union(Z,Z)),Z),Z),Z))},unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);

Join[{a=1,b=2},Table[c=3*b+2*a-1;a=b;b=c,{n,100}]] (* Vladimir Joseph Stephan Orlovsky, Jan 17 2011*)
LinearRecurrence[{4,-1,-2},{1,2,7},40] (* Vincenzo Librandi, Jun 23 2012 *)

a(n) = round((1/4+(2^(-3-n)*((3-sqrt(17))^n*(-5+3*sqrt(17))+(3+sqrt(17))^n*(5+3*sqrt(17))))/sqrt(17))) \\ Colin Barker, Sep 02 2016

G.f.: (1-2*x)/(1-4*x+x^2+2*x^3).
Recurrence: {a(0)=1, a(1)=2, -2*a(n)-3*a(n+1)+a(n+2)+1=0}.
a(n) = Sum(-1/136*(-13-27*r+6*r^2)*r^(-1-n) where r=RootOf(1-4*_Z+_Z^2+2*_Z^3)).
a(n) = (1/4+(2^(-3-n)*((3-sqrt(17))^n*(-5+3*sqrt(17))+(3+sqrt(17))^n*(5+3*sqrt(17))))/sqrt(17)). - Colin Barker, Sep 02 2016
4*a(n) = 1+3*A007482(n)-2*A007482(n-1) - R. J. Mathar, Feb 27 2019
a(n)-a(n-1) = A007483(n-1). - R. J. Mathar, Jan 09 2025

More terms from James Sellers, Jun 06 2000

A101604 a(n) = 2a(n-1) + 5a(n-2) + 2*a(n-3).

Original entry on oeis.org

1, 2, 9, 30, 109, 386, 1377, 4902, 17461, 62186, 221481, 788814, 2809405, 10005842, 35636337, 126920694, 452034757, 1609945658, 5733906489, 20421610782, 72732645325, 259041157538, 922588763265, 3285848604870, 11702723341141

Offset: 0

Paul Barry, Dec 08 2004

Transform of 2^n under Riordan array A101603.

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,5,2).

Cf. A007483, A101603.

LinearRecurrence[{2,5,2},{1,2,9},30] (* Harvey P. Dale, Jun 01 2025 *)

G.f.: 1/((1+x)*(1-3*x-2*x^2));
a(n) = (3/4 + sqrt(17)/4)^n*(1/4 + 7*sqrt(17)/68) + (1/4 - 7*sqrt(17)/68)*(3/4 - sqrt(17)/4)^n + (-1)^n/2;
a(n) = (A007483(n) + (-1)^n)/2. - R. J. Mathar, Sep 21 2012

A138276 Total number of active nodes of the Rule 150 cellular automaton on an infinite Bethe lattice with coordination number 3 (with a single 1 as initial condition).

Original entry on oeis.org

1, 4, 6, 18, 30, 90, 102, 306, 510, 1530, 1542, 4626, 7110

Offset: 0

Jens Christian Claussen (claussen(AT)theo-physik.uni-kiel.de), Mar 11 2008

nonn

See A138277 for the corresponding sequence for a Bethe lattice with coordination number 4.
See A001045 for the corresponding sequence on a 1D lattice (equivalent to a k=2 Bethe lattice); this is based on the Jacobsthal sequence A001045.
See A072272 for the corresponding sequence on a 2D lattice (based on A007483).
Related to Cellular Automata.

			Let x_0 be the state (0 or 1) of the focal node and x_i the state of every node that is i steps away from the focal node. In time step n=0, all x_i=0 except x_0=1 (start with a single seed). In the next step, x_1=1 as they have 1 neighbor being 1. For n=2, the x_1 nodes have 1 neighbor being 1 (x_0) and
themselves being 1; the sum being 2, modulo 2, resulting in x_1=0. The focal node itself is 1 and has 3 neighbors being 1, sum being 4, modulo 2, resulting in x_0=0. The outmost nodes x_n are always 1.
Thus one has the patterns
x_0, x_1, x_2, ...
1
1 1
0 0 1
0 0 1 1
0 0 1 0 1
0 0 1 1 1 1
0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 0 1 0 1 0 1 0 1
0 0 1 1 1 1 1 1 1 1
0 0 1 0 0 0 0 0 0 0 1
After 2 time steps, the x_0 and x_1 stay frozen at zero and the remaining x_i are generated by Rule 60 (or Rule 90 on half lattice spacing).
These nodes have multiplicities 1,3,6,12,24,48,96,192,384,768,...
The sequence then is obtained by
a(n) = x_0(n) + 3 * Sum_{i=1..n} x_i(n) * 2^(i-1)

Jens Christian Claussen, Time-evolution of the Rule 150 cellular automaton activity from a Fibonacci iteration.
Jens Christian Claussen, Time-evolution of the Rule 150 cellular automaton activity from a Fibonacci iteration, arXiv:math.CO/0410429.
Jan Nagler and Jens Christian Claussen, 1/f^alpha spectra in elementary cellular automata and fractal signals, Phys. Rev. E 71 (2005), 067103

Cf. A138277, A072272, A007483, A071053, A001045.

The total number of nodes in state 1 after n iterations (starting with a single 1) of the Rule 150 cellular automaton on an infinite Bethe lattice with coordination number 3. Rule 150 sums the values of the focal node and its k neighbors, then applies modulo 2.

cp's OEIS Frontend

A269522 Number of active (ON, black) cells in n-th stage of growth of two-dimensional cellular automaton defined by "Rule 622", based on the 5-celled von Neumann neighborhood.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

A193731 Mirror of the triangle A193730.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A209171 Triangle of coefficients of polynomials v(n,x) jointly generated with A209170; see the Formula section.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A138277 Total number of active nodes of the Rule 150 cellular automaton on an infinite Bethe lattice with coordination number 4 (with a single 1 as initial condition).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A331211 Number of green nodes in n-th power graph W exponentiation of a cycle graph with 7 blue nodes and one green node.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A374096 Number of edge covers of fan graph F_{1,n}.

Views

Author

Keywords

Examples

Links

Programs

Mathematica

Formula

A052986 Expansion of ( 1-2*x ) / ( (x-1)*(2*x^2+3*x-1) ).

Views

Author

Keywords

Links

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A101604 a(n) = 2*a(n-1) + 5*a(n-2) + 2*a(n-3).

A052986 Expansion of ( 1-2x ) / ( (x-1)(2x^2+3x-1) ).

A101604 a(n) = 2a(n-1) + 5a(n-2) + 2*a(n-3).