|
%I #118 Sep 08 2022 08:44:59
%S 1,1,3,3,7,7,15,15,31,31,63,63,127,127,255,255,511,511,1023,1023,2047,
%T 2047,4095,4095,8191,8191,16383,16383,32767,32767,65535,65535,131071,
%U 131071,262143,262143,524287,524287,1048575,1048575,2097151,2097151
%N Expansion of 1/((1 - x)*(1 - 2*x^2)).
%C Equals row sums of triangle A137865. - _Gary W. Adamson_, Feb 18 2008
%C Also, the decimal representation of the diagonal from the corner to the origin of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 566", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. - _Robert Price_, Jul 05 2017
%C Number of nonempty subsets of {1,2,...,n+1} that contain only odd numbers. a(0) = a(1) = 1: {1}; a(6) = a(7) = 15: {1}, {3}, {5}, {7}, {1,3}, {1,5}, {1,7}, {3,5}, {3,7}, {5,7}, {1,3,5}, {1,3,7}, {1,5,7}, {3,5,7}, {1,3,5,7}. - _Enrique Navarrete_, Mar 16 2018
%C Number of nonempty subsets of {1,2,...,n+2} that contain only even numbers. a(0) = a(1) = 1: {2}; a(4) = a(5) = 7: {2}, {4}, {6}, {2,4}, {2,6}, {4,6}, {2,4,6}. - _Enrique Navarrete_, Mar 26 2018
%C Doubling of A000225(n+1), n >= 0 entries. First differences give A077957. - _Wolfdieter Lang_, Apr 08 2018
%C a(n-2) is the number of achiral rows or cycles of length n partitioned into two sets or the number of color patterns using exactly 2 colors. An achiral row or cycle is equivalent to its reverse. Two color patterns are equivalent if the colors are permuted. For n = 4, the a(n-2) = 3 row patterns are AABB, ABAB, and ABBA; the cycle patterns are AAAB, AABB, and ABAB. For n = 5, the a(n-2) = 3 patterns for both rows and cycles are AABAA, ABABA, and ABBBA. For n = 6, the a(n-2) = 7 patterns for rows are AAABBB, AABABB, AABBAA, ABAABA, ABABAB, ABBAAB, and ABBBBA; the cycle patterns are AAAAAB, AAAABB, AAABAB, AAABBB, AABAAB, AABABB, and ABABAB. - _Robert A. Russell_, Oct 15 2018
%C For integers m > 1, the expansion of 1/((1 - x)*(1 - m*x^2)) generates a(n) = sqrt(m)^(n + 1)*((-1)^n*(sqrt(m) - 1)) + sqrt(m) + 1)/(2*(m - 1)). It appears, for integer values of n >= 0 and m > 1, that it could be simplified in the integral domain a(n) = (m^(1 + floor(n/2)) - 1)/(m - 1). - _Federico Provvedi_, Nov 23 2018
%C From _Werner Schulte_, Mar 04 2019: (Start)
%C More generally: For some fixed integers q and r > 0 the expansion of A(q,r; x) = 1/((1-x)*(1-q*x^r)) generates coefficients a(q,r; n) = (q^(1+floor(n/r))-1)/(q-1) for n >= 0; the special case q = 1 leads to a(1,r; n) = 1 + floor(n/r).
%C The a(q,r; n) satisfy for n > r a linear recurrence equation with constant coefficients. The signature vector is given by the sum of two vectors v and w where v has terms 1 followed by r zeros, i.e., (1,0,0,...,0), and w has r-1 leading zeros followed by q and -q, i.e., (0,0,...,0,q,-q).
%C Let a_i(q,r; n) be the convolution inverse of a(q,r; n). The terms are given by the sum a_i(q,r; n) = b(n) + c(n) for n >= 0 where b(n) has terms 1 and -1 followed by infinitely zeros, i.e., (1,-1,0,0,0,...), and c(n) has r leading zeros followed by -q, q and infinitely zeros, i.e., (0,0,...,0,-q,q,0,0,0,...).
%C Here is an example for q = 3 and r = 5: The expansion of A(3,5; x) = 1/((1-x)*(1-3*x^5)) = Sum_{n>=0} a(3,5; n)*x^n generates the sequence of coefficients (a(3,5; n)) = (1,1,1,1,1,4,4,4,4,4,13,13,13,13,13,40,...) where r = 5 controls the repetition and q = 3 the different values.
%C The a(3,5; n) satisfy for n > 5 the linear recurrence equation with constant coefficients and signature (1,0,0,0,0,0) + (0,0,0,0,3,-3) = (1,0,0,0,3,-3).
%C The convolution inverse a_i(3,5; n) has terms (1,-1,0,0,0,0,0,0,0,...) + (0,0,0,0,0,-3,3,0,0,...) = (1,-1,0,0,0,-3,3,0,0,...).
%C For further examples and informations see A014983 (q,r = -3,1), A077925 (q,r = -2,1), A000035 (q,r = -1,1), A000012 (q,r = 0,1), A000027 (q,r = 1,1), A000225 (q,r = 2,1), A003462 (q,r = 3,1), A077953 (q,r = -2,2), A133872 (q,r = -1,2), A004526 (q,r = 1,2), A052551 (this sequence with q,r = 2,2), A077886 (q,r = -2,3), A088911 (q,r = -1,3), A002264 (q,r = 1,3) and A077885 (q,r = 2,3). The offsets might be different.
%C (End)
%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.
%H Vincenzo Librandi, <a href="/A052551/b052551.txt">Table of n, a(n) for n = 0..2000</a>
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=488">Encyclopedia of Combinatorial Structures 488</a>
%H Donatella Merlini, Massimo Nocentini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Merlini/merlini5.html">Algebraic Generating Functions for Languages Avoiding Riordan Patterns</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
%H N. J. A. Sloane, <a href="http://arxiv.org/abs/1503.01168">On the Number of ON Cells in Cellular Automata</a>, arXiv:1503.01168 [math.CO], 2015.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ElementaryCellularAutomaton.html">Elementary Cellular Automaton</a>
%H S. Wolfram, <a href="http://wolframscience.com/">A New Kind of Science</a>
%H Wolfram Research, <a href="http://atlas.wolfram.com/">Wolfram Atlas of Simple Programs</a>
%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%H <a href="https://oeis.org/wiki/Index_to_2D_5-Neighbor_Cellular_Automata">Index to 2D 5-Neighbor Cellular Automata</a>
%H <a href="https://oeis.org/wiki/Index_to_Elementary_Cellular_Automata">Index to Elementary Cellular Automata</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-2).
%F G.f.: 1/((1 - x)*(1 - 2*x^2)).
%F Recurrence: a(1) = 1, a(0) = 1, -2*a(n) - 1 + a(n+2) = 0.
%F a(n) = -1 + Sum((1/2)*(1 + 2*alpha)*alpha^(-1 - n)) where the sum is over alpha = the two roots of -1 + 2*x^2.
%F a(n) = A016116(n+2) - 1. - _R. J. Mathar_, Jun 15 2009
%F a(n) = A060546(n+1) - 1. - _Filip Zaludek_, Dec 10 2016
%F From _Robert A. Russell_, Oct 15 2018: (Start)
%F a(n-2) = S2(floor(n/2)+1,2), where S2 is the Stirling subset number A008277.
%F a(n-2) = 2*A056326(n) - A000225(n) = A000225(n) - 2*A122746(n-2) = A056326(n) - A122746(n-2).
%F a(n-2) = 2*A056357(n) - A056295(n) = A056295(n) - 2*A059053(n) = A056357(n) - A059053(n). (End)
%F From _Federico Provvedi_, Nov 22 2018: (Start)
%F a(n) = 2^( 1 + floor(n/2) ) - 1.
%F a(n) = ( (-1)^n*(sqrt(2)-1) + sqrt(2) + 1 ) * 2^( (n - 1)/2 ) - 1. (End)
%F E.g.f.: 2*cosh(sqrt(2)*x) + sqrt(2)*sinh(sqrt(2)*x) - cosh(x) - sinh(x). - _Franck Maminirina Ramaharo_, Nov 23 2018
%p spec := [S,{S=Prod(Sequence(Prod(Z,Union(Z,Z))),Sequence(Z))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);
%t Table[StirlingS2[Floor[n/2] + 2, 2], {n, 0, 50}] (* _Robert A. Russell_, Dec 20 2017 *)
%t Drop[LinearRecurrence[{1, 2, -2}, {0, 1, 1}, 50], 1] (* _Robert A. Russell_, Oct 14 2018 *)
%t CoefficientList[Series[1/((1-x)*(1-2*x^2)), {x, 0, 50}], x] (* _Stefano Spezia_, Oct 16 2018 *)
%t 2^(1+Floor[(Range[0,50])/2])-1 (* _Federico Provvedi_, Nov 22 2018 *)
%t ((-1)^#(Sqrt[2]-1)+Sqrt[2]+1)2^((#-1)/2)-1&@Range[0, 50] (* _Federico Provvedi_, Nov 23 2018 *)
%o (Magma) [2^Floor(n/2)-1: n in [2..50]]; // _Vincenzo Librandi_, Aug 16 2011
%o (PARI) x='x+O('x^50); Vec(1/((1-x)*(1-2*x^2))) \\ _Altug Alkan_, Mar 19 2018
%o (GAP) Flat(List([1..21],n->[2^n-1,2^n-1])); # _Muniru A Asiru_, Oct 16 2018
%o (Sage) [2^(floor(n/2)) -1 for n in (2..50)] # _G. C. Greubel_, Mar 04 2019
%Y Cf. A000225, A077957, A136865, A289404, A289405, A032085.
%Y Column 2 (offset by two) of A304972.
%Y Cf. A000225 (oriented), A056326 (unoriented), and A122746(n-2) (chiral) for rows.
%Y Cf. A056295 (oriented), A056357 (unoriented), and A059053 (chiral) for cycles.
%K easy,nonn
%O 0,3
%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000
%E More terms from _James A. Sellers_, Jun 06 2000
|
