[seqfan] Re: Modular Partitions

[Li-yao Xia]

This is a proof in the case where "gcd(n, k) = 1". William Keith solved 
it for "n prime". (Below, (n, k) became (p, n).) So the result is still 
incomplete.

I hadn't heard about Molien series before. In the OEIS, they are linked 
to the first rows of the triangle (n = 3: A007997, n = 4: A008610, n = 
5: A008646, but no mention for n = 6: A032191), but maybe the 
identity---if it is true---has already been established in general: that 
the Molien series for the cyclic group of order n gives the numbers of 
necklaces with n white beads and k black beads.

If that is the case, following from the reply by Roland Bacher, it 
answers the main question. However, it doesn't show a bijection.

Li-yao Xia

-------- Original Message --------
Subject: [seqfan] Re: Modular Partitions
From: franktaw at netscape.net
To: seqfan at list.seqfan.eu
Date: 05/03/2014 06:17 PM

Is this a proof that the number of "modular partitions" is equinumerous
with the number of necklaces?

Right now that is, as a conjecture, awaiting review for A047996.

Franklin T. Adams-Watters

-----Original Message-----
From: Li-yao Xia <li-yao.xia at ens.fr>
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Sent: Sat, May 3, 2014 11:05 am
Subject: [seqfan]  Re: Modular Partitions


There is a link to necklaces when p and n are coprime which generalizes
William Keith's result.

By giving up primality, we lose the fact that rotation-equivalence of
profiles partitions them into equal-sized classes (i.e., the object of
paragraph 3, "If we add 1 to each part,...").

However, having p and n coprime still allows the next paragraph to be
generalized:

  > (...) But adding 1 to each of n parts adds n to the total mod p, so
the residue of the profiles mod p are all distinct, and hence exactly
one of them is 0 mod p. (...)

In other words, equivalence classes of profiles are in bijection with
modular partitions.

Independently of coprimality of p and n, these equivalence classes are
in fact (in bijection with) necklaces, as is explained next.

A profile describes the number n(t) of parts of size t in a partition,
thus it is given by a sequence (n(0) ... n(p-1)), where n(t) is
nonnegative and n(0) + ... + n(p-1) = n (a total of n parts).

E.g., when (p, n) = (5, 4), the partition [0 3 3 4] is associated to
(1 0 0 2 1). (one 0, no 1, no 2, two 3s, one 4)

If we consider such sequences (n(t)) up to cyclic-shifts---which is the
same as adding a constant to all parts of a partition---they are in fact
necklaces with p white beads and n black beads, each n(t) indicating the
number of black beads between two successive white beads.

When p and n are not coprime, that function from partitions to their
profiles up to rotation is not a bijection. Shifting by p/gcd(n,p)
transforms a valid p-modular partition into another valid one, possibly
the same.

E.g., (p, n) = (6, 3), gcd(6, 3) = 3, T(6, 3) = 10

"Profiles" on the left those in the same class are gathered, partitions
on the right with their sums:

(3 0 0 0 0 0) | [0 0 0]  0
(0 0 3 0 0 0) | [2 2 2]  6
(0 0 0 0 3 0) | [4 4 4] 12

(1 1 0 0 0 1) | [0 1 5]  6
(0 1 1 1 0 0) | [1 2 3]  6
(0 0 0 1 1 1) | [3 4 5] 12

(1 0 0 2 0 0) | [0 3 3]  6
(0 0 1 0 0 2) | [2 5 5] 12
(0 2 0 0 1 0) | [1 1 4]  6

(1 0 1 0 1 0) | [0 2 4]  6

Impossible profiles:

(1 2 0 0 0 0)
(2 1 0 0 0 0)
(1 0 2 0 0 0)
(2 0 1 0 0 0)
(1 1 0 1 0 0)
(1 0 1 1 0 0)

Li-yao Xia

-------- Original Message --------
Subject: [seqfan] Re: Modular Partitions
From: William Keith <william.keith at gmail.com>
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Date: 05/03/2014 07:19 AM

Chris' conjectures are accurate.

Suppose we are in the case n !==0 mod p.  Diagram one of Jen's partitions
in Z/pZ into n parts with a Ferrers diagram, with parts of size 0 noted.
It will fit in a p-1 by n box.  Choose any profile, to create a Ferrers
diagram; there are (n+p-1)-choose-n possible profiles.

If we add 1 to each part, rotating any new parts of size p to the end as
parts of size 0, we can do so p times and get back our original profile.
If p is prime and n !==0 mod p, then none of this group of p modpartitions
can possibly be the same: Suppose you had k parts of size 0, t additions
ago, then now you have k parts of size t.  If this is the same partition as
the one t additions ago, then you must have had k parts of size t, so now
you have k parts of size 2t, etc, until you had k parts of each size to
begin with, i.e. p divides n.

So we can group the p resulting profiles. But adding 1 to each of n parts
adds n to the total mod p, so the residue of the profiles mod p are all
distinct, and hence exactly one of them is 0 mod p. Thus there are (1/p)
(n-1+p choose n) partitions of 0 mod p with n parts when p is prime, p not
dividing n.

When n = kp, then exactly the one partition listed above will be separate
from the groups; take (1/p)[(n+p-1 choose n) - 1] + 1.    QED.

I think this diagram technique, and some sort of rotation counting, should
also be able to prove symmetry.  I don't know anything about Molien
series.  (Yet.)  If something from that subject proves symmetry I'd be
interested in seeing it.  But I would also like to see a map defined in
terms of the modpartitions themselves that gives symmetry in n and k.

William Keith

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/



_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/




_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/