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

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, 35, 36, 38, 39, 40, 41, 46, 47, 48, 49, 51, 52, 53, 54, 57, 58, 59, 60, 62, 63, 64, 65, 69, 70, 71, 72, 74, 75, 76, 77, 80, 81, 82, 83, 85, 86, 87, 88, 94, 95, 96, 97, 99, 100, 101

Offset

1,3

Comments

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

References

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

Links

T. D. Noe, Table of n, a(n) for n=1..1000

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II

L. Babai, On the length of subgroup chains in the symmetric group, Commun. Algebra, 14 (1986), 1729-1736.

P. J. Cameron, M. Gadouleau, J. D. Mitchell, Y. Peresse, Chains of subsemigroups, arXiv preprint arXiv:1501.06394 [math.GR], 2015.

Peter J. Cameron; Ron Solomon; Alexandre Turull, Chains of subgroups in symmetric groups, J. Algebra 127 (1989), no. 2, 340-352.

Donald M. Davis, Divisibility by 2 and 3 of certain Stirling numbers, arXiv:0807.2629 [math.NT], Jul 16, 2008.

Formula

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

G.f.: 1/(1-x) * (-1/(1-x^2) + Sum(k>=0, x^2^k/(1-x^2^k))). - Ralf Stephan, Apr 13 2002

Maple

A000120 := proc(n)
    convert(n, base, 2) ;
    add(i, i=%) ;
end proc:
A007238 := proc(n)
    floor((3*n-1)/2)-A000120(n) ;
end proc:
seq(A007238(n), n=1..20) ;

Mathematica

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 *)
Table[Ceiling[(3n)/2]-DigitCount[n, 2, 1]-1, {n, 70}] (* Harvey P. Dale, Nov 20 2021 *)

Prog

(PARI) vector(70, n, ceil(3*n/2) - hammingweight(n) - 1) \\ Joerg Arndt, May 16 2016

Crossrefs

Sequence in context: A346993 A098166 A217445 * A083875 A165291 A080762

Adjacent sequences: A007235 A007236 A007237 * A007239 A007240 A007241

Keyword

nonn,nice

Author

N. J. A. Sloane, Simon Plouffe

Status

approved