login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A095121 Expansion of (1-x+2x^2)/((1-x)(1-2x)). 24
1, 2, 6, 14, 30, 62, 126, 254, 510, 1022, 2046, 4094, 8190, 16382, 32766, 65534, 131070, 262142, 524286, 1048574, 2097150, 4194302, 8388606, 16777214, 33554430, 67108862, 134217726, 268435454, 536870910, 1073741822, 2147483646, 4294967294, 8589934590 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

a(n+1)/2 = A000225(n). Binomial transform is A002783. Binomial transform of 2 - 2*0^n + (-1)^n or 1,1,3,1,3,1,3,1,...

From Peter C. Heinig (algorithms(AT)gmx.de), Apr 17 2007: (Start)

Number of n-tuples where each entry is chosen from the subsets of {1,2} such that the intersection of all n entries contains exactly one element.

There is the following general formula: The number T(n,k,r) of n-tuples where each entry is chosen from the subsets of {1,2,..,k} such that the intersection of all n entries contains exactly r elements is: T(n,k,r) = binomial(k,r) * (2^n - 1)^(k-r). This may be shown by exhibiting a bijection to a set whose cardinality is obviously binomial(k,r) * (2^n - 1)^(k-r), namely the set of all k-tuples where each entry is chosen from subsets of {1,..,n} in the following way: Exactly r entries must be {1,..,n} itself (there are binomial(k,r) ways to choose them) and the remaining (k-r) entries must be chosen from the 2^n-1 proper subsets of {1,..,n}, i.e., for each of the (k-r) entries, {1,..,n} is forbidden (there are, independent of the choice of the full entries, (2^n - 1)^(k-r) possibilities to do that, hence the formula). The bijection into this set is given by (X_1,..,X_n) |-> (Y_1,..,Y_k) where for each j in {1,..,k} and each i in {1,..,n}, i is in Y_j if and only if j is in X_i.

Examples: a(1)=2 because the two tuples of length one are: ({1}) and ({2}).

a(3)=14 because the fourteen tuples of length three are: ({1},{1},{1}), ({2},{2},{2}), ({1,2},{1},{1}), ({1},{1,2},{1}), ({1},{1},{1,2}), ({1,2},{2},{2}), ({2},{1,2},{2}), ({2},{2},{1,2}), ({1,2},{1,2},{1}), ({1,2},{1},{1,2}), ({1},{1,2},{1,2}), ({1,2}{1,2}{2}), ({1,2}{2}{1,2}), ({2}{1,2}{1,2}).

The image of this set of tuples under the bijection described in the comment is: ({1,2,3},{}), ({},{1,2,3}), ({1,2,3},{1}), ({1,2,3},{2}), ({1,2,3},{3}), ({1},{1,2,3}), ({2},{1,2,3}), ({3},{1,2,3}), ({1,2,3},{1,2}), ({1,2,3},{1,3}), ({1,2,3},{2,3}), ({1,2},{1,2,3}), ({1,3},{1,2,3}), ({2,3},{1,2,3}). Here exactly one entry is {1,..,n}={1,2,3} and the other is a proper subset. (End)

An elephant sequence, see A175654. For the corner squares just one A[5] vector, with decimal value 170, leads to this sequence. For the central square this vector leads to the companion sequence A151821. - Johannes W. Meijer, Aug 15 2010

Conjecture: a(n) is the least m>0 such that A007814(A000108(m)) = n, where A000108 gives the Catalan numbers and A007814(x) is the 2-adic valuation of x (cf. A048881). - L. Edson Jeffery, Nov 26 2015

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 645", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. - Robert Price, Jul 19 2017

REFERENCES

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

LINKS

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

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 (3,-2).

FORMULA

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

a(n) = A000918(n+1), n >= 1.

a(n) = 2*2^n - 2 + 0^n; a(n) = 3*a(n-1) - 2*a(n-2).

a(0)=1, a(1)=2, a(n) = 2*a(n-1) + 2 for n>1. - Philippe Deléham, Sep 28 2006

a(n) = Sum_{k=0..n} 2^k*A123110(n,k). - Philippe Deléham, Feb 09 2007

a(n) = -2 + 4*2^(n-1) + (binomial(2*n,n) mod 2). - Paolo P. Lava, Nov 19 2008

a(n) = 5*a(n-2) - 4*a(n-4) for n>4 [Because x(n)=f*x(n-1)+g*x(n-2) => x(n)=(f^2+2*g)*x(n-2)-g^2*x(n-4), here with f=3 and g=-2]. - Hermann Stamm-Wilbrandt, Aug 13 2015

MAPLE

ZL := [S, {S=Prod(B, B), B=Set(Z, 1 <= card)}, labeled]: seq(combstruct[ count](ZL, size=n), n=1..31); # Zerinvary Lajos, Mar 13 2007

for k from 1 to 31 do 2*(2^k-1); od;

MATHEMATICA

Join[{1}, LinearRecurrence[{3, -2}, {2, 6}, 50]] (* Vladimir Joseph Stephan Orlovsky, Feb 24 2012 *)

Join[{1}, NestList[2#+2&, 2, 40]] (* Harvey P. Dale, Dec 25 2013 *)

PROG

(MAGMA) [-2+4*2^(n-1)+(Binomial(2*n, n) mod 2): n in [0..40]]; // Vincenzo Librandi, Aug 14 2015

(PARI) Vec((1-x+2*x^2)/((1-x)*(1-2*x)) + O(x^40)) \\ Michel Marcus, Aug 14 2015

(PARI) vector(100, n, n--; if(n==0, 1, 2*2^n-2)) \\ Altug Alkan, Nov 26 2015

CROSSREFS

Cf. A000108, A000225, A000918, A002783, A007814, A048881, A123110, A127509, A151821, A175654.

Row sums of A131108, A132046, A153861, and A193815.

Sequence in context: A228038 A122958 A122959 * A296965 A000918 A059076

Adjacent sequences:  A095118 A095119 A095120 * A095122 A095123 A095124

KEYWORD

easy,nonn

AUTHOR

Paul Barry, May 28 2004

EXTENSIONS

Edited by N. J. A. Sloane, Apr 25 2007

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 May 21 18:43 EDT 2019. Contains 323444 sequences. (Running on oeis4.)