11255  Necklace
Moderator: Board moderators
11255  Necklace
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
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
Pascal's Pyramid/Simplex
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 ND it's called Pascal's simplex.
There is a nice proof here:
http://www.math.rutgers.edu/~erowland/p ... lices.html
Btw, these recursive formulas for multinomials
is a generalization of pascal's triangle.
in 3D, it's called Pascal's Pyramid
in ND it's called Pascal's simplex.
There is a nice proof here:
http://www.math.rutgers.edu/~erowland/p ... lices.html
Help
It is trivial to precalculate 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!
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!
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
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
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.
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.
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.
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.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.
I sent something by pm.
I have send you an email to sclo@sfu.ca

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

 New poster
 Posts: 1
 Joined: Thu Mar 13, 2008 9:16 am
 Location: UK
 Contact:
Re: 11255  Necklace
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.
But the point of this problem is: How to deal with finite supply of beads of each color? A tiny hint would be appreciated.
Re: 11255  Necklace
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?
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
Re: 11255  Necklace
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 ?
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