To extend A018216 Maximal number of subgroups in a group with n elements

[Max Alekseyev]

On Dec 1, 2007 7:00 PM, Jonathan Post <jvospost3 at gmail.com> wrote:

> We can get another sequence out of this process of seeking the maxima.
>
> a(n) = Sum of number of subgroups of all nonisomorphic groups of order n.
>
> Comment: with multiplicity, i.e. Z_2 X Z_2 has 3 isomorphic subgroups
> Z_2, so contributes 3 to the sum for a(4).  Every group has itself and
> the trivial group as subgroups, so a(1) = 1 where these are the same,
> and n>1 has a(n) => 2.  a(p) = 2 for prime p.
>
>  1, 2, 2, 6, 2, 4, 2, 24, 7, 4, 2, 12, 2, 4, 4
>
> Offset 1,2
>
> examples:
> n  a(n)  explanation (not list itself and trivial group)
> 1  1
> 2  2
> 3  2
> 4  6     Z_4 has Z_2,  Z_2 X Z_2 has 3 of Z_2

In addition to four Z_2 mentioned above, you have one Z_4, one Z_2 X
Z_2, and two trivial subgroups (of Z_4 and of Z_2 X Z_2). So, a(4)
must be equal 8. Don't you agree?

This sequence goes as

1, 2, 2, 8, 2, 4, 2, 28, 9, 4, 2, 16, 2, 4, 4, 125, 2, 18, 2, 16, 4,
4, 2, 56, 11, 4, 42, 16, 2, 8, 2, 626, 4, 4, 4, 72, 2, 4, 4, 56, 2, 8,
2, 16, 18, 4, 2, 250, 13, 22, 4, 16, 2, 84, 4, 56, 4, 4, 2, 32, 2, 4,
18, 4273, 4, 8, 2, 16, 4, 8, 2, 252, 2, 4, 22, 16, 4, 8, 2, 250, 304,
4, 2, 32, 4, 4, 4, 56, 2, 36, 4, 16, 4, 4, 4, 1252, 2, 26, 18, 88

Regards,
Max




ap> From seqfan-owner at ext.jussieu.fr  Tue Dec  4 02:34:53 2007
ap> Return-Path: <seqfan-owner at ext.jussieu.fr>
ap> From: "Andrew Plewe" <aplewe at sbcglobal.net>
ap> To: "'Seqfan'" <seqfan at ext.jussieu.fr>
ap> Subject: Duplicate hunting cont.
ap> Date: Mon, 3 Dec 2007 17:34:34 -0800
ap> ....
ap> These two sequences:
ap> 
ap> http://www.research.att.com/~njas/sequences/?q=id:A004306|id:A000803&fmt=0
ap> 
ap> are the same from "24" onwards. Will they always be the same after that
ap> point?
ap> ...

Yes.

Proof follows by writing down the two generating functions, shifting indices
by multiplication with powers of the independent variable, then showing that
the o.g.f's are the same modulo some polynomials:

A000803 o.g.f = -x^2*(3x-2) /(x-1)/(x^3+x^2+x-1) = 2(-5x^2+1)/(x^3+x^2+x-1)-2/(x-1) .

A004306 o.g.f = -10x^3-6x^2-3x-7+2(x^2+2x-3)/(x^3+x^2+x-1)-2/(x-1)

If we write down the o.g.f. of A004306 with the leading 1,1,2,6 removed, so
the o.g.f. starts with 24x^4+44x^5+... we have
A004306-1-x-2x^2-6x^3 = (some polynomial in x)+2(-23x^2+18x-3)/(x^3+x^2+x-1)-2/(x-1)
To shift the sequence up by 2 indices, multiply by x^2 and re-expand the
partial fractions to get
x^2(A004306-1-x-2x^2-6x^3) = (some polynomial in x)+2(-5x^2+1)/(x^3+x^2+x-1)-2/(x-1)

If we write down the o.g.f. of A000803 with the leading 0,0,8,4,8,16 removed, so
the o.g.f. starts with 24x^6+44x^7+..., we have
A000803-8x^2-4x^3-8x^4-16x^5 = (some polynomial in x)+2(-5x^2+1)/(x^3+x^2+x-1)-2/(x-1).

So indeed up to some leading polynomial and the shift in indices, the essential
bodies of the two generating functions which will produce the bulk of the infinity
of all the other terms in the two series are identical. qed.

Richard Mathar, http://www.strw.leidenuniv.nl/~mathar
the sequence, the majority of what is left over resembles any other sequence modulo some
enables us to do so-:).