 Forum index » Science and Technology » Math » Combinatorics
Author Message
Dom
science forum beginner

Joined: 15 Feb 2006
Posts: 25 Posted: Fri May 05, 2006 10:10 pm    Post subject: How Many Combinations for THIS?? Okay...

If you have a 4x4 grid, with a "tile" in each square, how many placement
combinations are possible if any tile can be placed in any grid square
and can be orientated in any direction (in 90 degrees turns)?

If someone can explain how this would be calculated, this would be
GREATLY appreciated!!

Thanks for any advice in advance :)

Dom Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593 Posted: Fri May 05, 2006 10:43 pm    Post subject: Re: How Many Combinations for THIS?? Dom wrote:
 Quote: Okay... If you have a 4x4 grid, with a "tile" in each square, how many placement combinations are possible if any tile can be placed in any grid square and can be orientated in any direction (in 90 degrees turns)? If someone can explain how this would be calculated, this would be GREATLY appreciated!!

If the tiles are all indistinguishable, the answer is 4^16, since every
tile can be placed in one of 4 directions. If the tiles are all
distinct, the answer is 16! * 4^16 (16! = 1 * 2 * ... * 16), since
there are 16! ways to place 16 tiles.

--- Christopher Heckman Dom
science forum beginner

Joined: 15 Feb 2006
Posts: 25 Posted: Fri May 05, 2006 11:40 pm    Post subject: Re: How Many Combinations for THIS?? Proginoskes wrote:
 Quote: Dom wrote: Okay... If you have a 4x4 grid, with a "tile" in each square, how many placement combinations are possible if any tile can be placed in any grid square and can be orientated in any direction (in 90 degrees turns)? If someone can explain how this would be calculated, this would be GREATLY appreciated!! If the tiles are all indistinguishable, the answer is 4^16, since every tile can be placed in one of 4 directions. If the tiles are all distinct, the answer is 16! * 4^16 (16! = 1 * 2 * ... * 16), since there are 16! ways to place 16 tiles. --- Christopher Heckman

So if I understand this right, if I have 16 different tiles (lets say
they are identified as A, B, C... P) there would be
89,862,698,310,039,500,000,000 different combinations?

However, would I be right in thinking that this could be divided by 4
because the whole grid will completed with an identical
sequence/pattern, but rotated through each 90 degrees? Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593 Posted: Sat May 06, 2006 5:47 am    Post subject: Re: How Many Combinations for THIS?? Dom wrote:
 Quote: Proginoskes wrote: Dom wrote: Okay... If you have a 4x4 grid, with a "tile" in each square, how many placement combinations are possible if any tile can be placed in any grid square and can be orientated in any direction (in 90 degrees turns)? If someone can explain how this would be calculated, this would be GREATLY appreciated!! If the tiles are all indistinguishable, the answer is 4^16, since every tile can be placed in one of 4 directions. If the tiles are all distinct, the answer is 16! * 4^16 (16! = 1 * 2 * ... * 16), since there are 16! ways to place 16 tiles. So if I understand this right, if I have 16 different tiles (lets say they are identified as A, B, C... P) there would be 89,862,698,310,039,500,000,000 different combinations?

That looks right.

 Quote: However, would I be right in thinking that this could be divided by 4 because the whole grid will completed with an identical sequence/pattern, but rotated through each 90 degrees?

Yes. And if you count horizontal and verticle reflections of a pattern
as being the same, you would divide by 2 (twice). But this wasn't
stated in the original problem.

--- Christopher Heckman Dom
science forum beginner

Joined: 15 Feb 2006
Posts: 25 Posted: Sat May 06, 2006 8:11 am    Post subject: Re: How Many Combinations for THIS?? Proginoskes wrote:
 Quote: Dom wrote: Proginoskes wrote: Dom wrote: Okay... If you have a 4x4 grid, with a "tile" in each square, how many placement combinations are possible if any tile can be placed in any grid square and can be orientated in any direction (in 90 degrees turns)? If someone can explain how this would be calculated, this would be GREATLY appreciated!! If the tiles are all indistinguishable, the answer is 4^16, since every tile can be placed in one of 4 directions. If the tiles are all distinct, the answer is 16! * 4^16 (16! = 1 * 2 * ... * 16), since there are 16! ways to place 16 tiles. So if I understand this right, if I have 16 different tiles (lets say they are identified as A, B, C... P) there would be 89,862,698,310,039,500,000,000 different combinations? That looks right. However, would I be right in thinking that this could be divided by 4 because the whole grid will completed with an identical sequence/pattern, but rotated through each 90 degrees? Yes. And if you count horizontal and verticle reflections of a pattern as being the same, you would divide by 2 (twice). But this wasn't stated in the original problem.

Sorry, the rotation/reflection part didn't occur to me until after I had
originally posted!

So... dividing by 4 to remove rotation duplicates give me
22,465,674,577,509,900,000,000 combinations, then dividing by 2 to
remove reflection duplicates gives me 11,232,837,288,754,900,000,000
combinations so far. Excellent.

Now to throw another spanner in the works! What if 8 out of the 16 tiles
couln't be placed in the centre 4 squares of the grid? How many
combinations would I be left with then?

Dom Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593 Posted: Sun May 07, 2006 6:05 am    Post subject: Re: How Many Combinations for THIS?? Dom wrote:
 Quote: Proginoskes wrote: Dom wrote: Proginoskes wrote: Dom wrote: Okay... If you have a 4x4 grid, with a "tile" in each square, how many placement combinations are possible if any tile can be placed in any grid square and can be orientated in any direction (in 90 degrees turns)? If someone can explain how this would be calculated, this would be GREATLY appreciated!! If the tiles are all indistinguishable, the answer is 4^16, since every tile can be placed in one of 4 directions. If the tiles are all distinct, the answer is 16! * 4^16 (16! = 1 * 2 * ... * 16), since there are 16! ways to place 16 tiles. So if I understand this right, if I have 16 different tiles (lets say they are identified as A, B, C... P) there would be 89,862,698,310,039,500,000,000 different combinations? That looks right. However, would I be right in thinking that this could be divided by 4 because the whole grid will completed with an identical sequence/pattern, but rotated through each 90 degrees? Yes. And if you count horizontal and verticle reflections of a pattern as being the same, you would divide by 2 (twice). But this wasn't stated in the original problem. Sorry, the rotation/reflection part didn't occur to me until after I had originally posted! So... dividing by 4 to remove rotation duplicates give me 22,465,674,577,509,900,000,000 combinations, then dividing by 2 to remove reflection duplicates gives me 11,232,837,288,754,900,000,000 combinations so far. Excellent.

That only considers reflections in one direction to be the same
configuration. If neither reflection is considered to alter the tiling,
you divide by 2 again, to get 5,616,418,644,377,450,000,000.

 Quote: Now to throw another spanner in the works! What if 8 out of the 16 tiles couln't be placed in the centre 4 squares of the grid? How many combinations would I be left with then?

I'm still assuming that this isn't homework.

Place the 8 tiles first: P(12, = 12*11*10*9*8*7*6*5, then place the
other 8, to get 8!. Now, rotating tiles is treated similarly:

P(12, *8!*4^16 total possibilities,
P(12, *8!*4^16/4 if rotations are considered to be the same
configuration,
P(12, *8!*4^16/16 if rotations and reflections are considered to be
the same configuration.

--- Christopher Heckman Dom
science forum beginner

Joined: 15 Feb 2006
Posts: 25 Posted: Sun May 07, 2006 9:01 am    Post subject: Re: How Many Combinations for THIS?? Proginoskes wrote:
 Quote: Dom wrote: Proginoskes wrote: Dom wrote: Proginoskes wrote: Dom wrote: Okay... If you have a 4x4 grid, with a "tile" in each square, how many placement combinations are possible if any tile can be placed in any grid square and can be orientated in any direction (in 90 degrees turns)? If someone can explain how this would be calculated, this would be GREATLY appreciated!! If the tiles are all indistinguishable, the answer is 4^16, since every tile can be placed in one of 4 directions. If the tiles are all distinct, the answer is 16! * 4^16 (16! = 1 * 2 * ... * 16), since there are 16! ways to place 16 tiles. So if I understand this right, if I have 16 different tiles (lets say they are identified as A, B, C... P) there would be 89,862,698,310,039,500,000,000 different combinations? That looks right. However, would I be right in thinking that this could be divided by 4 because the whole grid will completed with an identical sequence/pattern, but rotated through each 90 degrees? Yes. And if you count horizontal and verticle reflections of a pattern as being the same, you would divide by 2 (twice). But this wasn't stated in the original problem. Sorry, the rotation/reflection part didn't occur to me until after I had originally posted! So... dividing by 4 to remove rotation duplicates give me 22,465,674,577,509,900,000,000 combinations, then dividing by 2 to remove reflection duplicates gives me 11,232,837,288,754,900,000,000 combinations so far. Excellent. That only considers reflections in one direction to be the same configuration. If neither reflection is considered to alter the tiling, you divide by 2 again, to get 5,616,418,644,377,450,000,000. Now to throw another spanner in the works! What if 8 out of the 16 tiles couln't be placed in the centre 4 squares of the grid? How many combinations would I be left with then? I'm still assuming that this isn't homework. Place the 8 tiles first: P(12, = 12*11*10*9*8*7*6*5, then place the other 8, to get 8!. Now, rotating tiles is treated similarly: P(12, *8!*4^16 total possibilities, P(12, *8!*4^16/4 if rotations are considered to be the same configuration, P(12, *8!*4^16/16 if rotations and reflections are considered to be the same configuration. --- Christopher Heckman

Hi Christopher,

Thanks for your explainations. It's not homework exactly - I found a
puzzle where the above rules apply and got it into my head that I wanted
to know how many combinations there could be. I've been trying to work
it out myself, but had no way of knowing whether my calculations were
correct (which they were up to a point, but then I just confused
myself). I don't know why it mattered to me really, but thanks for
putting my mind at ease!

Dom  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 The time now is Mon Mar 18, 2019 5:26 pm | All times are GMT Forum index » Science and Technology » Math » Combinatorics
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics How many combinations possible? nowwicked@yahoo.com Math 5 Tue Jun 27, 2006 6:35 pm Combinations satisfying linear equations? BDH Math 11 Tue Jun 27, 2006 9:58 am Combinations and Investment Strategies Baker Probability 0 Sun Jun 18, 2006 7:19 pm Maple bugs are ubiquitous: "Maple is not recognizing gree... Vladimir Bondarenko Math 0 Sat Apr 22, 2006 8:10 am Calculating how many m of n combinations in which an obje... roncace Combinatorics 2 Tue Apr 04, 2006 1:15 am