login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007238 Length of longest chain of subgroups in S_n.
(Formerly M0945)
3
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 (list; graph; refs; listen; history; text; internal format)
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 *)

PROG

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

CROSSREFS

Sequence in context: A248554 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 20 17:09 EST 2019. Contains 329337 sequences. (Running on oeis4.)