11255 - Necklace

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

11255 - Necklace

Post by baodog »

Hi,

Nevermind... I got it. Sorry.. I typed 1255 instead of 11255. The trick is to precompute multinomials for the multinomials
in the cycle index of the dihedral group.
... They all fit nicely in long long ....... :-)

p.s.,

For those interested in Polya counting, see this description:

http://www.geocities.com/markoriedelde/ ... ollier.pdf

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

Isn't the dp just this: f(i,j,k) = f(i-1,j,k)+f(i,j-1,k)+f(i,j,k-1) ?
Of course, I'm not putting the boundary cases. You don't need Bigint since 3^40 fits nicely.

This problem is a nightmare if one hasn't heard about Burnside Lemma or whatever that is called before.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Pascal's Pyramid/Simplex

Post by baodog »

Thanks. I get AC in 0.012 seconds now !!!
Btw, these recursive formulas for multinomials
is a generalization of pascal's triangle.
in 3D, it's called Pascal's Pyramid
in N-D it's called Pascal's simplex.

There is a nice proof here:

http://www.math.rutgers.edu/~erowland/p ... lices.html

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

Help

Post by pineapple »

It is trivial to pre-calculate the Pascal's triangle.
But it only can get the coefficients for all the permutations of a single case.
for example,when a=b=c=2,we get f[2][2][2]=90.(dp or combination)
Who can tell me how to do next?
Because there are so many same permutations by rotating or flipping,and the final answer is 11.
Thanks in advance!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

Figure out how to deal with over counting.
Burnside's Lemma tells us that.
In our case:
the number of different necklace = average number of assignments fixed by the permutations of the necklace.

Here, permutations are rotations or flips or both. For necklace with n pearls, there are 2n permutations.
Also, an assignment f is fixed by a permutation p iff p(f) and f are not distinguishable.

For example, rotations and/or flips.
Rotation is the tricky one.

Let's examine the case for a=b=c=1.
n=3, so 2n=6 permutations.
Identity: By definition, every assignments are fixed by the identity, so there are 6 of them.
For any other permutations, no assignments are fixed.
So the solution is (6+0+0+0+0+0)/6 = 1

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

For a=b=c=2:
For simplicity, lets label the positions around the necklace with 1 to 6 clockwise.
n=6, so 12 permutations:
There are 4 types of rotations:
1: Identity (for example 1->1, 2->2, ... 6->6):
f(2,2,2) = 90 since everything is fixed

2: Rotate clockwise by 1 (for example 1->2, 2->3, ..., 6->1):
Only way for any assignment be fixed is color of all are equal, so
no assignments are fixed.

3: Rotate clockwise by 2 (for example 1->3, 2->4, ..., 6->2):
Only way for it to be fixed is color 1 = color 3 = color 5, and color 2 = color 4 = color 6, which is also impossible.

4: Rotate clockwise by 3 (for example 1->4, ...):
Here if color 1= color 4, color 2=color 5, color 3 = color 6, then it is fixed. The number of assignments of this type is f(1,1,1)=6

Rotate clockwise by 4 has same number as clockwise by 2. (both type 3)
Rotate clockwise by 5 has same number as clockwise by 1. (both type 2)

There are 2 main types of flips here. Each consists of 3 permutations.
The first type is where the flip axis is on 2 beads. Example:
1<->1, 2<->6,3<->5,4<->4.
The other type is where flip axis is on midpoint of 2 beads . Example:
1<->2, 3<->6, 4<->5.
For both of these type, there are f(1,1,1) assignments that are fixed.

So the solution is (1*90+2*0+2*0+1*6+3*6+3*6)/12 = 11

As you can see, counting the rotations is the most tricky part. There are only 3 types of flips. Two of the types are shown above, the other type is the only type for odd n.

Hint: number of types of rotation is actually the number of divisors of n.

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

Post by pineapple »

Thanks for your help.
Actually,I have read some relational article since this problem add to problemset,I can't understand this point.Can you send me your AC code by PM.
I'm a Chinese newbie,just began it one year ago,but you can see me in the AuthorRanklist,now 10th.
I know you are a great helper.I have seen you in many posts.
I also know your rank is higher than me,but don't know your name.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

pineapple wrote:Thanks for your help.
Actually,I have read some relational article since this problem add to problemset,I can't understand this point.Can you send me your AC code by PM.
I'm a Chinese newbie,just began it one year ago,but you can see me in the AuthorRanklist,now 10th.
I know you are a great helper.I have seen you in many posts.
I also know your rank is higher than me,but don't know your name.
Hehe. You rank is even higher than mine. I'm rank 11th.

I sent something by pm.

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

Post by pineapple »

I have send you an email to sclo@sfu.ca

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz »

sclo wrote: For necklace with n pearls, there are 2n permutations.
For n=1 there is only 1 permutation, not 2*1.

luckylucker
New poster
Posts: 1
Joined: Thu Mar 13, 2008 9:16 am
Location: UK
Contact:

great topic

Post by luckylucker »

Great )))))))))))))
WBR,
Alex

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 11255 - Necklace

Post by serur »

It's all very well if one had infinite supply of beads of each color: just substitute `3' into the circular polynomial obtained by Polya enumeration.
But the point of this problem is: How to deal with finite supply of beads of each color? A tiny hint would be appreciated.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 11255 - Necklace

Post by serur »

Let P_k = P(a,b,c) be the multivariate polynomial (a^k + b^k + c^k), 1 <=k <= n. Let A,B,C be the number of beads of each color, A+B+C = n.
Let s be one of the 2n transformations, and let j_k = j_k(s) stand for the number of cycles of length k in the decomposition of s.
Then we are asked to find for every s the coefficient of [a^A * b^B * c^C] in the expansion of {P_{1}}^j_{1} * {P_{2}}^j_{2} * \ldots * {P_{n}}^j_{n}.
You solved the problem this way?
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 11255 - Necklace

Post by serur »

Well, the recursive formulas give us full control over {P_k}^{j_k}, that is, over (a^k+b^k+c^k)^{j_k}.
But how to handle the product of {P_k}^{j_k}'s ?
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Post Reply

Return to “Volume 112 (11200-11299)”