login
a(n) = 2^wt(floor(n/2)) (i.e., 2^A000120(floor(n/2)), or A001316(floor(n/2))).
17

%I #73 Jan 11 2024 10:58:17

%S 1,1,2,2,2,2,4,4,2,2,4,4,4,4,8,8,2,2,4,4,4,4,8,8,4,4,8,8,8,8,16,16,2,

%T 2,4,4,4,4,8,8,4,4,8,8,8,8,16,16,4,4,8,8,8,8,16,16,8,8,16,16,16,16,32,

%U 32,2,2,4,4,4,4,8,8,4,4,8,8,8,8,16,16,4,4,8,8,8,8,16,16,8,8,16,16,16,16,32

%N a(n) = 2^wt(floor(n/2)) (i.e., 2^A000120(floor(n/2)), or A001316(floor(n/2))).

%C Number of conjugacy classes in the symmetric group S_n that have odd number of elements.

%C Also sequence A001316 doubled.

%C Number of even numbers whose binary expansion is a child of the binary expansion of n. - _Nadia Heninger_ and _N. J. A. Sloane_, Jun 06 2008

%C First differences of A151566. Sequence gives number of toothpicks added at the n-th generation of the leftist toothpick sequence A151566. - _N. J. A. Sloane_, Oct 20 2010

%C The Fi1 and Fi1 triangle sums, see A180662 for their definitions, of Sierpiński's triangle A047999 equal this sequence. - _Johannes W. Meijer_, Jun 05 2011

%C Also number of odd entries in n-th row of triangle of Stirling numbers of the first kind. - _Istvan Mezo_, Jul 21 2017

%D I. G. MacDonald: Symmetric functions and Hall polynomials Oxford: Clarendon Press, 1979. Page 21.

%H Indranil Ghosh, <a href="/A060632/b060632.txt">Table of n, a(n) for n = 0..65536</a> (terms 0..1000 from Harry J. Smith)

%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]

%H Christina Talar Bekaroğlu, <a href="https://scholarworks.calstate.edu/concern/theses/bk128j63v">Analyzing Dynamics of Larger than Life: Impacts of Rule Parameters on the Evolution of a Bug's Geometry</a>, Master's thesis, Calif. State Univ. Northridge (2023). See p. 92.

%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>

%H <a href="/index/To#toothpick">Index entries for sequences related to toothpick sequences</a>

%F a(n) = sum{k=0..floor(n/2), C(n, 2k) mod 2} - _Paul Barry_, Jan 03 2005, Edited by _Harry J. Smith_, Sep 15 2009

%F a(n) = gcd(A056040(n), 2^n). - _Peter Luschny_, Jun 30 2011

%F G.f.: (1 + x) * Product_{k>=0} (1 + 2*x^(2^(k+1))). - _Ilya Gutkovskiy_, Jul 19 2019

%e a(3) = 2 because in S_3 there are two conjugacy classes with odd number of elements, the trivial conjugacy class and the conjugacy class of transpositions consisting of 3 elements: (12),(13),(23).

%e From _Omar E. Pol_, Oct 12 2011 (Start):

%e Written as a triangle:

%e 1,

%e 1,

%e 2,2,

%e 2,2,4,4,

%e 2,2,4,4,4,4,8,8,

%e 2,2,4,4,4,4,8,8,4,4,8,8,8,8,16,16,

%e 2,2,4,4,4,4,8,8,4,4,8,8,8,8,16,16,4,4,8,8,8,8,16,16,8,...

%e (End)

%p A060632 := proc(n) local k; add(binomial(n,2*k) mod 2, k=0..floor(n/2)); end: seq(A060632(n),n=0..94); # edited by _Johannes W. Meijer_, May 28 2011

%p A060632 := n -> 2^add(i, i = convert(iquo(n,2), base, 2)); # _Peter Luschny_, Jun 30 2011

%p A060632 := n -> igcd(2^n, n! / iquo(n,2)!^2); # _Peter Luschny_, Jun 30 2011

%t a[n_] := 2^DigitCount[Floor[n/2], 2, 1]; Table[a[n], {n, 0, 94}] (* _Jean-François Alcover_, Feb 25 2014 *)

%o (PARI) for (n=0, 1000, write("b060632.txt", n, " ", sum(k=0, floor(n/2), binomial(n, 2*k) % 2)) ) \\ _Harry J. Smith_, Sep 14 2009

%o (PARI) a(n)=2^hammingweight(n\2) \\ _Charles R Greathouse IV_, Feb 06 2017

%o (Magma) a000120:=func< n | &+Intseq(n, 2) >; [ 2^a000120(Floor(n/2)): n in [0..100] ]; // _Klaus Brockhaus_, Oct 15 2010

%o (Python)

%o def A060632(n):

%o return 2**bin(n/2)[2:].count("1") # _Indranil Ghosh_, Feb 06 2017

%Y Cf. A000120, A001316, A139251, A151566, A160407.

%K nonn

%O 0,3

%A Avi Peretz (njk(AT)netvision.net.il), Apr 15 2001

%E More terms from _James A. Sellers_, Apr 16 2001

%E Edited by _N. J. A. Sloane_, Jun 06 2008; Oct 11 2010

%E a(0) = 1 added by _N. J. A. Sloane_, Sep 14 2009

%E Formula corrected by _Harry J. Smith_, Sep 15 2009