[seqfan] Re: Modular Partitions

Tue May 6 06:18:58 CEST 2014

I've written up a preliminary version of my proof - see "A Note on Modular
Partitions and Necklaces", which is linked to from A047996 and A241926.

On Sat, May 3, 2014 at 7:21 PM, Neil Sloane <njasloane at gmail.com> wrote:

> I think it is OK.
> We have three things that we want to match up:
> I Molien series
> II. Necklaces
> III. Ways to write 0 as a sum of k terms in Z/nZ
>
> I = III because generating function for no. of solutions = Mol series for
> cyclic group
> I = II by Polya theory.
>
> Neil
>
>
>
>
> On Sat, May 3, 2014 at 6:54 PM, Neil Sloane <njasloane at gmail.com> wrote:
>
>> PS I take it back. That g.f. was not right. Stay tuned!
>>
>>
>> On Sat, May 3, 2014 at 2:56 PM, Neil Sloane <njasloane at gmail.com> wrote:
>>
>>> > 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
>>>
>>>
>>
>>
>> --
>> 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
>>
>>
>
>
> --
> 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
>
>

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