login
Length of longest chain of subgroups in S_n.
(Formerly M0945)
3

%I M0945 #45 Nov 20 2021 14:16:21

%S 0,1,2,4,5,6,7,10,11,12,13,15,16,17,18,22,23,24,25,27,28,29,30,33,34,

%T 35,36,38,39,40,41,46,47,48,49,51,52,53,54,57,58,59,60,62,63,64,65,69,

%U 70,71,72,74,75,76,77,80,81,82,83,85,86,87,88,94,95,96,97,99,100,101

%N Length of longest chain of subgroups in S_n.

%C Starting at a(2), this is column 2 of Table 1 of the Donald M. Davis paper, p.32. - _Jonathan Vos Post_, Jul 17 2008

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A007238/b007238.txt">Table of n, a(n) for n=1..1000</a>

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.

%H J.-P. Allouche and J. Shallit, <a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">The Ring of k-regular Sequences, II</a>

%H L. Babai, <a href="http://dx.doi.org/10.1080/00927878608823393">On the length of subgroup chains in the symmetric group</a>, Commun. Algebra, 14 (1986), 1729-1736.

%H P. J. Cameron, M. Gadouleau, J. D. Mitchell, Y. Peresse, <a href="http://arxiv.org/abs/1501.06394">Chains of subsemigroups</a>, arXiv preprint arXiv:1501.06394 [math.GR], 2015.

%H Peter J. Cameron; Ron Solomon; Alexandre Turull, <a href="http://dx.doi.org/10.1016/0021-8693(89)90256-1">Chains of subgroups in symmetric groups</a>, J. Algebra 127 (1989), no. 2, 340-352.

%H Donald M. Davis, <a href="http://arxiv.org/abs/0807.2629">Divisibility by 2 and 3 of certain Stirling numbers</a>, arXiv:0807.2629 [math.NT], Jul 16, 2008.

%F a(n) = ceiling(3n/2) - b(n) - 1, where b(n) = # 1's in binary expansion of n (A000120).

%F G.f.: 1/(1-x) * (-1/(1-x^2) + Sum(k>=0, x^2^k/(1-x^2^k))). - _Ralf Stephan_, Apr 13 2002

%p A000120 := proc(n)

%p convert(n,base,2) ;

%p add(i,i=%) ;

%p end proc:

%p A007238 := proc(n)

%p floor((3*n-1)/2)-A000120(n) ;

%p end proc:

%p seq(A007238(n),n=1..20) ;

%t a[n_] := Ceiling[ 3n/2 ] - Count[ IntegerDigits[n, 2], 1] - 1; Table[ a[n], {n, 1, 70}] (* _Jean-François Alcover_, Jan 19 2012, after formula *)

%t Table[Ceiling[(3n)/2]-DigitCount[n,2,1]-1,{n,70}] (* _Harvey P. Dale_, Nov 20 2021 *)

%o (PARI) vector(70, n, ceil(3*n/2) - hammingweight(n) - 1) \\ _Joerg Arndt_, May 16 2016

%K nonn,nice

%O 1,3

%A _N. J. A. Sloane_, _Simon Plouffe_