|
%I #88 Dec 31 2023 10:18:12
%S 1,2,6,14,30,62,126,254,510,1022,2046,4094,8190,16382,32766,65534,
%T 131070,262142,524286,1048574,2097150,4194302,8388606,16777214,
%U 33554430,67108862,134217726,268435454,536870910,1073741822,2147483646,4294967294,8589934590
%N Expansion of (1-x+2x^2)/((1-x)*(1-2x)).
%C 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,...
%C From Peter C. Heinig (algorithms(AT)gmx.de), Apr 17 2007: (Start)
%C 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.
%C 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.
%C Examples: a(1)=2 because the two tuples of length one are: ({1}) and ({2}).
%C 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}).
%C 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)
%C 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
%C 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
%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 645", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. - _Robert Price_, Jul 19 2017
%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.
%H Vincenzo Librandi, <a href="/A095121/b095121.txt">Table of n, a(n) for n = 0..1000</a>
%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_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2).
%F G.f.: (1-x+2*x^2)/((1-x)*(1-2*x)).
%F a(n) = A000918(n+1), n >= 1.
%F a(n) = 2*2^n - 2 + 0^n; a(n) = 3*a(n-1) - 2*a(n-2).
%F a(0)=1, a(1)=2, a(n) = 2*a(n-1) + 2 for n>1. - _Philippe Deléham_, Sep 28 2006
%F a(n) = Sum_{k=0..n} 2^k*A123110(n,k). - _Philippe Deléham_, Feb 09 2007
%F 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
%F E.g.f.: 1 + 2*exp(x)*(exp(x) - 1). - _Stefano Spezia_, Feb 25 2022
%p 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
%p for k from 1 to 31 do 2*(2^k-1); od;
%t Join[{1}, LinearRecurrence[{3, -2}, {2, 6}, 50]] (* _Vladimir Joseph Stephan Orlovsky_, Feb 24 2012 *)
%t Join[{1},NestList[2#+2&,2,40]] (* _Harvey P. Dale_, Dec 25 2013 *)
%o (Magma) [-2+4*2^(n-1)+(Binomial(2*n,n) mod 2): n in [0..40]]; // _Vincenzo Librandi_, Aug 14 2015
%o (PARI) Vec((1-x+2*x^2)/((1-x)*(1-2*x)) + O(x^40)) \\ _Michel Marcus_, Aug 14 2015
%o (PARI) vector(100, n, n--; if(n==0, 1, 2*2^n-2)) \\ _Altug Alkan_, Nov 26 2015
%Y Cf. A000108, A000225, A000918, A002783, A007814, A048881, A123110, A127509, A151821, A175654.
%Y Row sums of A131108, A132046, A153861, and A193815.
%K easy,nonn
%O 0,2
%A _Paul Barry_, May 28 2004
%E Edited by _N. J. A. Sloane_, Apr 25 2007
|
