login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A052551 Expansion of 1/((1 - x)*(1 - 2*x^2)). 22
1, 1, 3, 3, 7, 7, 15, 15, 31, 31, 63, 63, 127, 127, 255, 255, 511, 511, 1023, 1023, 2047, 2047, 4095, 4095, 8191, 8191, 16383, 16383, 32767, 32767, 65535, 65535, 131071, 131071, 262143, 262143, 524287, 524287, 1048575, 1048575, 2097151, 2097151 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Equals row sums of triangle A137865. - Gary W. Adamson, Feb 18 2008

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

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

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

Doubling of A000225(n+1), n >= 0 entries. First differences give A077957. - Wolfdieter Lang, Apr 08 2018

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

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

From Werner Schulte, Mar 04 2019: (Start)

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).

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).

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,...).

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.

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).

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,...).

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.

(End)

REFERENCES

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

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..2000

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 488

Donatella Merlini, Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.

N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.

Eric Weisstein's World of Mathematics, Elementary Cellular Automaton

S. Wolfram, A New Kind of Science

Wolfram Research, Wolfram Atlas of Simple Programs

Index entries for sequences related to cellular automata

Index to 2D 5-Neighbor Cellular Automata

Index to Elementary Cellular Automata

Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

FORMULA

G.f.: 1/((1 - x)*(1 - 2*x^2)).

Recurrence: a(1) = 1, a(0) = 1, -2*a(n) - 1 + a(n+2) = 0.

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.

a(n) = A016116(n+2) - 1. - R. J. Mathar, Jun 15 2009

a(n) = A060546(n+1) - 1. - Filip Zaludek, Dec 10 2016

From Robert A. Russell, Oct 15 2018: (Start)

a(n-2) = S2(floor(n/2)+1,2), where S2 is the Stirling subset number A008277.

a(n-2) = 2*A056326(n) - A000225(n) = A000225(n) - 2*A122746(n-2) = A056326(n) - A122746(n-2).

a(n-2) = 2*A056357(n) - A056295(n) = A056295(n) - 2*A059053(n) = A056357(n) - A059053(n). (End)

From Federico Provvedi, Nov 22 2018: (Start)

a(n) = 2^( 1 + floor(n/2) ) - 1.

a(n) = ( (-1)^n*(sqrt(2)-1) + sqrt(2) + 1 ) * 2^( (n - 1)/2 ) - 1.  (End)

E.g.f.: 2*cosh(sqrt(2)*x) + sqrt(2)*sinh(sqrt(2)*x) - cosh(x) - sinh(x). - Franck Maminirina Ramaharo, Nov 23 2018

MAPLE

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

MATHEMATICA

Table[StirlingS2[Floor[n/2] + 2, 2], {n, 0, 50}] (* Robert A. Russell, Dec 20 2017 *)

Drop[LinearRecurrence[{1, 2, -2}, {0, 1, 1}, 50], 1] (* Robert A. Russell, Oct 14 2018 *)

CoefficientList[Series[1/((1-x)*(1-2*x^2)), {x, 0, 50}], x] (* Stefano Spezia, Oct 16 2018 *)

2^(1+Floor[(Range[0, 50])/2])-1 (* Federico Provvedi, Nov 22 2018 *)

((-1)^#(Sqrt[2]-1)+Sqrt[2]+1)2^((#-1)/2)-1&@Range[0, 50] (* Federico Provvedi, Nov 23 2018 *)

PROG

(MAGMA) [2^Floor(n/2)-1: n in [2..50]]; // Vincenzo Librandi, Aug 16 2011

(PARI) x='x+O('x^50); Vec(1/((1-x)*(1-2*x^2))) \\ Altug Alkan, Mar 19 2018

(GAP) Flat(List([1..21], n->[2^n-1, 2^n-1])); # Muniru A Asiru, Oct 16 2018

(Sage) [2^(floor(n/2)) -1 for n in (2..50)] # G. C. Greubel, Mar 04 2019

CROSSREFS

Cf. A000225, A077957, A136865, A289404, A289405, A032085.

Column 2 (offset by two) of A304972.

Cf. A000225 (oriented), A056326 (unoriented), and A122746(n-2) (chiral) for rows.

Cf. A056295 (oriented), A056357 (unoriented), and A059053 (chiral) for cycles.

Sequence in context: A263794 A086530 A147402 * A147096 A147252 A147104

Adjacent sequences:  A052548 A052549 A052550 * A052552 A052553 A052554

KEYWORD

easy,nonn

AUTHOR

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

EXTENSIONS

More terms from James A. Sellers, Jun 06 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 25 03:49 EST 2020. Contains 331241 sequences. (Running on oeis4.)