[seqfan] Re: Modular Partitions

Sun May 4 01:21:44 CEST 2014

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