cp's OEIS Frontend

A007238 Length of longest chain of subgroups in S_n.

%I A007238 M0945 #45 Nov 20 2021 14:16:21
%S A007238 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 A007238 35,36,38,39,40,41,46,47,48,49,51,52,53,54,57,58,59,60,62,63,64,65,69,
%U A007238 70,71,72,74,75,76,77,80,81,82,83,85,86,87,88,94,95,96,97,99,100,101
%N A007238 Length of longest chain of subgroups in S_n.
%C A007238 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 A007238 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007238 T. D. Noe, <a href="/A007238/b007238.txt">Table of n, a(n) for n=1..1000</a>
%H A007238 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 A007238 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 A007238 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 A007238 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 A007238 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 A007238 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 A007238 a(n) = ceiling(3n/2) - b(n) - 1, where b(n) = # 1's in binary expansion of n (A000120).
%F A007238 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 A007238 A000120 := proc(n)
%p A007238     convert(n,base,2) ;
%p A007238     add(i,i=%) ;
%p A007238 end proc:
%p A007238 A007238 := proc(n)
%p A007238     floor((3*n-1)/2)-A000120(n) ;
%p A007238 end proc:
%p A007238 seq(A007238(n),n=1..20) ;
%t A007238 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 A007238 Table[Ceiling[(3n)/2]-DigitCount[n,2,1]-1,{n,70}] (* _Harvey P. Dale_, Nov 20 2021 *)
%o A007238 (PARI) vector(70, n, ceil(3*n/2) - hammingweight(n) - 1) \\ _Joerg Arndt_, May 16 2016
%K A007238 nonn,nice
%O A007238 1,3
%A A007238 _N. J. A. Sloane_, _Simon Plouffe_