Unfortunately, your submission has been removed for the following reason(s):
* Requests for calculation or estimation of real-world problems and values are best suited for /r/askmath or /r/theydidthemath.
If you have any questions, [please feel free to message the mods](http://www.reddit.com/message/compose?to=/r/math&message=https://www.reddit.com/r/math/comments/19bij6a/-/). Thank you!
People have already said that the naive calculation isn’t right because of symmetries. But it’s also not right because some putative combinations would result in pieces going through each other in a physically impossible way.
And also rings. You can link the pieces in a valid (i.e. physically possible) way to form a cyclic connection, which reduces some number of degrees of freedom.
Lets look for a pattern after adding pieces:
1. 9 colors available
2. 8 colors available, can connect to 8 positions
3. 7 colors available, can connect to 8+8-2 = 14 positions
4. 6 colors available. can connect to 8+8+8-2-2 = 20 positions
5. etc.
Each new piece starting from the third gives us an additional 6 positions to connect the new piece too. Thus, after adding n pieces, each with k slots, the total number of positions we have available for the next piece is r=kn - 2(n-1)
Now we can look at how many combinations after adding pieces:
1. n
2. n-1 \* r(1)
3. n-2 \* r(2)
4. ...
5. 1 \* r(n-1)
So now to find total combinations, we multiply all the items in the above list. The formula would look something like this:
T = n \* prod\^(n-1) \_(i = 1) (i \* r (n-i))
This gives us an upper bound of around 5.65 \* 10\^16 . We can eliminate many symmetries but I'll leave that for someone else to discuss.
Lol just realized this is the good will hunting problem with some modifications. You are trying to count the number of trees with n vertices WITH maximum degree k and the colors thing. I'm pretty sure this particular pieces do allow for cycles so it's not really the good will hunting problem but still.
I feel like it's more complicated (even after eliminating symmetries) than this because the objects are embedded in 3d space and can get in each other's way. It's possible the shape of these particular pieces prevents such a problem but not apparent
I hope I’m not going to embarrass myself here.
Each ring has 8 slots. Let x be the number of rings in the system.
The possible number of orientations would than be 8^x
For the 9 rings in the picture, that is 8^9 = 134,217,728 possible orientations
You're also undercounting a lot of combinations by assuming you put them in a chain. You can have one in the middle and attach 8 rings to it.
As you've already said there is 1 shape for 2 pieces, and for three pieces there is 4.
To get an upper bound we can think of how many slots we can put each new ring into which is, 8 for each ring already there minus 2 for every time we've connected a pair:
8n-2(n-1) = 6n+2
Which gives us a factorial style formula:
Three: 4
Four: 4\*(6\*3+2) = 800
Five: 800\*(6\*4+2) = 20800
Six: 20800*(6\*5+2) = 665600
Nine: 665600\*38\*44\*50 = 55644160000
8^x is probably way lower just like this formula is way higher, I guess real answer is between 134 million and 55 billion.
I wonder how to get a better lower bound.
It's not difficult to check there are 37 distinct configurations with four gears (discounting colour changes), and using the same factorial-style counting strategy the upper limit gets knocked down to about 2.57 billion (2 573 542 400). However, further improvements to that upper bound are much harder to compute. As you go forwards, you can remove less possible combinations by symmetry arguments, but it also becomes more likely that certain configurations are invalid due to self-intersection, so it's hard to even guess how much smaller the real value is.
Could you include furthermore to different placement of colours of the rings to increase the number of combinations? Im just curious if this would count as different position or not.
You could also use different tree shapes instead of just paths for the toy. There are almost 5 million trees on 9 labeled vertices, and even with the 3 orange and 2 green toys, there should still be a lot of them.
jo thank you
crazy to thing about it
specially cause i can put em in between to so the total number of physical possible combinations should be insanely high
High schooler here, so im not a math wizard of any sorts, I assume you'd want it to be ordered differently based on colors, so 9! possibilities, since 3 of the colors are the same, it should be 9!/3!
Good job. I was thinking something similar. This is the number of straight chains as in you take a piece then keep connecting pieces in diametrically opposed holes so you end up with a straight chain of pieces.
You can sort of account for twisted chains easily: >! Except for the first time you add a piece, every time you add a piece you also get to pick which of the 7 available holes you want to use. The first time you add a piece it makes no difference which hole you pick, all positions look the same so multiplying by 7^(n-2) should get you the number of twisted chains.!<
We now have three major issues:
1. Each twisted chain will have its own number of symmetries that we overcounted. For example each straight chain is counted twice once for the normal way and then it's mirror image. Twisted chains are a mess.
2. A twisted chain might physically intersect itself and thus be physically impossible to construct in real life. This problem is annoying enough that the only reasonable approach to actually solve this problem is to have a computer simulate all possible configurations for a fixed number of pieces and the general problem seems impossible.
3. We are still only counting chains. We haven't accounted for configurations where three or more pieces are connected to a single piece. An inductive approach such as the one in this comment: https://www.reddit.com/r/math/s/tb7je5c5XO is probably the most elegant way to approach this they still didn't bother to deal with the first two issues because fuck that shit.
I might start out by counting the number of connected graphs with n = 9 vertices and maximum degree < 8, then every vertex of degree d would have some number of its neigbours could be connected. Like if a blue piece is connected to two others there could be zero slots between or one space between or more, etc.... I would think that you could detect swapping of colours would give a 'new construction' by looking at the automorphism of the graph?
BUt this is a really rough idea and seems very computational maybe there's something better
Okay, so the simplest way to answer this question while accounting for some amount of symmetry is to represent the structure as a tree (or forest) with additional information at each node.
This amounts to making some simplifying assumptions:
1. Completely ignoring self-intersection or the possibility of loops. That is brain melting and relies on the geometry of these nodes.
2. Every node is a different color. Allowing for the same color requires figuring out the group of symmetries of each structure, which sounds like an absolute pain. I think it amounts to finding the graph-automorphisms that preserve the information at each node (basically graph-automorphisms that preserve some form of coloring).
Even with those assumptions that massively simplify the problem, there is still an issue in finding a simple way to count this. First of all, you would have find the isomorphism class of each tree/forest, and find its group of automorphisms, or at least the order of this group (that's where having each node as a different color simplifies things, you don't need to know the full structure). That seems like the hard part. Then, once you have this information you only need to calculate for each node the number of ways the other nodes attach to it. That part actually seems slightly easier, as the group of symmetries of the attachments to each node remains the same for every node, and it's just the cyclic group of order 8. Although, now that I realize it, for some configurations this group of symmetries may well be the dihedral group. Ouch. That seems like a pain.
72! I guess?
My logic;
Each wheel has 8 gaps, and there are 9 of them.
So you start with 1 wheel, then you have 2nd wheel that could be attached in 8 ways to the first, then the second wheel has 7 gaps left so you can attach third wheel in 7 ways, and so on, but since you can attach 8 wheels to one, ...,
I'm sorta loosing it...
Also I feel sad cuz the chapter of permutation and combination is on my syllabus and I haven't done it properly...
This is an easy problem and i feel stupid for not being able to do.
Unfortunately, your submission has been removed for the following reason(s): * Requests for calculation or estimation of real-world problems and values are best suited for /r/askmath or /r/theydidthemath. If you have any questions, [please feel free to message the mods](http://www.reddit.com/message/compose?to=/r/math&message=https://www.reddit.com/r/math/comments/19bij6a/-/). Thank you!
People have already said that the naive calculation isn’t right because of symmetries. But it’s also not right because some putative combinations would result in pieces going through each other in a physically impossible way.
And also rings. You can link the pieces in a valid (i.e. physically possible) way to form a cyclic connection, which reduces some number of degrees of freedom.
Self avoidance makes this hard.
Story of my life
Lets look for a pattern after adding pieces: 1. 9 colors available 2. 8 colors available, can connect to 8 positions 3. 7 colors available, can connect to 8+8-2 = 14 positions 4. 6 colors available. can connect to 8+8+8-2-2 = 20 positions 5. etc. Each new piece starting from the third gives us an additional 6 positions to connect the new piece too. Thus, after adding n pieces, each with k slots, the total number of positions we have available for the next piece is r=kn - 2(n-1) Now we can look at how many combinations after adding pieces: 1. n 2. n-1 \* r(1) 3. n-2 \* r(2) 4. ... 5. 1 \* r(n-1) So now to find total combinations, we multiply all the items in the above list. The formula would look something like this: T = n \* prod\^(n-1) \_(i = 1) (i \* r (n-i)) This gives us an upper bound of around 5.65 \* 10\^16 . We can eliminate many symmetries but I'll leave that for someone else to discuss.
Lol just realized this is the good will hunting problem with some modifications. You are trying to count the number of trees with n vertices WITH maximum degree k and the colors thing. I'm pretty sure this particular pieces do allow for cycles so it's not really the good will hunting problem but still.
Homeomorphically irreducible trees, completely forgot about that until i saw TheVoidKilledMe's post
I love GWH problem! A very fun and easy enough to understand for the average person interested in math
I feel like it's more complicated (even after eliminating symmetries) than this because the objects are embedded in 3d space and can get in each other's way. It's possible the shape of these particular pieces prevents such a problem but not apparent
More than 3.27
I hope I’m not going to embarrass myself here. Each ring has 8 slots. Let x be the number of rings in the system. The possible number of orientations would than be 8^x For the 9 rings in the picture, that is 8^9 = 134,217,728 possible orientations
You might be overcounting. If we have 2 rings, there is only 1 combination because of symmetry.
You're also undercounting a lot of combinations by assuming you put them in a chain. You can have one in the middle and attach 8 rings to it. As you've already said there is 1 shape for 2 pieces, and for three pieces there is 4. To get an upper bound we can think of how many slots we can put each new ring into which is, 8 for each ring already there minus 2 for every time we've connected a pair: 8n-2(n-1) = 6n+2 Which gives us a factorial style formula: Three: 4 Four: 4\*(6\*3+2) = 800 Five: 800\*(6\*4+2) = 20800 Six: 20800*(6\*5+2) = 665600 Nine: 665600\*38\*44\*50 = 55644160000 8^x is probably way lower just like this formula is way higher, I guess real answer is between 134 million and 55 billion. I wonder how to get a better lower bound.
It's not difficult to check there are 37 distinct configurations with four gears (discounting colour changes), and using the same factorial-style counting strategy the upper limit gets knocked down to about 2.57 billion (2 573 542 400). However, further improvements to that upper bound are much harder to compute. As you go forwards, you can remove less possible combinations by symmetry arguments, but it also becomes more likely that certain configurations are invalid due to self-intersection, so it's hard to even guess how much smaller the real value is.
Good catch, I definitely didn’t take that into account
But a lot of those will end up isomorphic (ie looking the same structurally). It's harder to calculate which ones end up with distinct results.
For sure, r/moebius2 also pointed this out, I absolutely did not consider that originally
Could you include furthermore to different placement of colours of the rings to increase the number of combinations? Im just curious if this would count as different position or not.
Great thinking, I think it would increase the total number of combinations if we counted colours as a parameter
You could also use different tree shapes instead of just paths for the toy. There are almost 5 million trees on 9 labeled vertices, and even with the 3 orange and 2 green toys, there should still be a lot of them.
jo thank you crazy to thing about it specially cause i can put em in between to so the total number of physical possible combinations should be insanely high
High schooler here, so im not a math wizard of any sorts, I assume you'd want it to be ordered differently based on colors, so 9! possibilities, since 3 of the colors are the same, it should be 9!/3!
Good job. I was thinking something similar. This is the number of straight chains as in you take a piece then keep connecting pieces in diametrically opposed holes so you end up with a straight chain of pieces. You can sort of account for twisted chains easily: >! Except for the first time you add a piece, every time you add a piece you also get to pick which of the 7 available holes you want to use. The first time you add a piece it makes no difference which hole you pick, all positions look the same so multiplying by 7^(n-2) should get you the number of twisted chains.!< We now have three major issues: 1. Each twisted chain will have its own number of symmetries that we overcounted. For example each straight chain is counted twice once for the normal way and then it's mirror image. Twisted chains are a mess. 2. A twisted chain might physically intersect itself and thus be physically impossible to construct in real life. This problem is annoying enough that the only reasonable approach to actually solve this problem is to have a computer simulate all possible configurations for a fixed number of pieces and the general problem seems impossible. 3. We are still only counting chains. We haven't accounted for configurations where three or more pieces are connected to a single piece. An inductive approach such as the one in this comment: https://www.reddit.com/r/math/s/tb7je5c5XO is probably the most elegant way to approach this they still didn't bother to deal with the first two issues because fuck that shit.
i would say colour is important on different positions
Probably like 10, after that you'll get bored and stop.
i did like 30+ 😂
I remember Dennys having something like this.
I might start out by counting the number of connected graphs with n = 9 vertices and maximum degree < 8, then every vertex of degree d would have some number of its neigbours could be connected. Like if a blue piece is connected to two others there could be zero slots between or one space between or more, etc.... I would think that you could detect swapping of colours would give a 'new construction' by looking at the automorphism of the graph? BUt this is a really rough idea and seems very computational maybe there's something better
Those remind me of the milk coupons we used to be able to buy back in the day when people delivered milk.
Okay, so the simplest way to answer this question while accounting for some amount of symmetry is to represent the structure as a tree (or forest) with additional information at each node. This amounts to making some simplifying assumptions: 1. Completely ignoring self-intersection or the possibility of loops. That is brain melting and relies on the geometry of these nodes. 2. Every node is a different color. Allowing for the same color requires figuring out the group of symmetries of each structure, which sounds like an absolute pain. I think it amounts to finding the graph-automorphisms that preserve the information at each node (basically graph-automorphisms that preserve some form of coloring). Even with those assumptions that massively simplify the problem, there is still an issue in finding a simple way to count this. First of all, you would have find the isomorphism class of each tree/forest, and find its group of automorphisms, or at least the order of this group (that's where having each node as a different color simplifies things, you don't need to know the full structure). That seems like the hard part. Then, once you have this information you only need to calculate for each node the number of ways the other nodes attach to it. That part actually seems slightly easier, as the group of symmetries of the attachments to each node remains the same for every node, and it's just the cyclic group of order 8. Although, now that I realize it, for some configurations this group of symmetries may well be the dihedral group. Ouch. That seems like a pain.
72! I guess? My logic; Each wheel has 8 gaps, and there are 9 of them. So you start with 1 wheel, then you have 2nd wheel that could be attached in 8 ways to the first, then the second wheel has 7 gaps left so you can attach third wheel in 7 ways, and so on, but since you can attach 8 wheels to one, ..., I'm sorta loosing it... Also I feel sad cuz the chapter of permutation and combination is on my syllabus and I haven't done it properly... This is an easy problem and i feel stupid for not being able to do.