11255 - Necklace

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

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]

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]

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]

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]

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]

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]

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]

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

[Robert Gerbicz]

For necklace with n pearls, there are 2n permutations.

For n=1 there is only 1 permutation, not 2*1.

[luckylucker]

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

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

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?

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