[seqfan] Re: Modular Partitions

Neil Sloane njasloane at gmail.com
Sat May 3 20:56:56 CEST 2014


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

I believe I have a proof of this using generating functions.
That is, there is a g.f. for A(n,k) = number of ways of writing 0
as a sum of k terms in Z/nZ which shows that this number is equal to
U(n,k) := (1/n)* Sum_{ d | gcd(n,k)}  phi(d) binomial(n/d, k/d) (see
A047996).
The trick is to consider G(x,t) = Prod_{j=1..n} (1+t*x^j).
Write G(x,t) = Sum_{i}  a_{i}(t) x^i.
Then a_0(t) + a_n(t) + a_{2n}(t) + ... = Sum_k A(n,k)*t^k.
I haven't written out all the details, but I think it works.

By the way, the formula in A241926 wasn't quite right.
The correct formula is
T(n,k) := (1/(n+k))* Sum_{ d | gcd(n,k)}  phi(d) binomial((n+k)/d, k/d)
 it follows at once that T(n,k) = T(k,n), so this shows that Jens Voss's
original table is indeed symmetric.

Neil



On Sat, May 3, 2014 at 12:17 PM, <franktaw at netscape.net> wrote:

> 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/
>



-- 
Dear Friends, I have now retired from AT&T. New coordinates:

Neil J. A. Sloane, President, OEIS Foundation
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com



More information about the SeqFan mailing list