# A lego question

Hi

Something that I did during school but can't recollect now...

Have 20 different unique lego shapes, each one can fit into another and form a new shape. First can fit into second and form a new shape, second can fit into third or all the remaining 18 to bring about new shapes.

What would be the formula for this permutation / combination? How many total permutations / combination can be there with these 20?
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
this is the power set problem

the answer is   (2^20 - 1) = 1048575
0
Commented:
actually, the answer is going to be a lot bigger.

once you have a subset of n pieces, there may be n! (or more) unique ways to put them together.
you would have to look at the shapes and connection rules in more detail.
0
Author Commented:
I thought so, the answer should be in millions...even billions.
0
Commented:
Yes, there is no way to answer this question without knowing how many different ways each piece could fit with another.

Even if you did have all the pieces, it would be a very complicated problem because how you attach one piece will affect how many different ways you can connect the next piece.

If you are just stacking them (second one on top of first, etc) then it's a standard permutation and the answer is 20! which is 2,432,902,008,176,640,000 so billions doesn't even scratch the surface.

2^20 is just how many different combinations of pieces there are. As in, there are 2^20 different ways you could pick a subset of the pieces to attach. (2^20 - 1 is if you skip the case where you pick none of them).

20! may be more what you were remembering, but that doesn't take into account the different shapes and how they can connect differently.
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
If you look at the numbers in Paschal's triangle, that will tell you how many subsets there are for each number of pieces.  Then you can assume n! combinations for each subset.

This is probably closer but still very rough.
Legos-for-ExEx.PNG
0
Commented:
Of course that is still assuming only one way of connecting them. The exact same numbers would work for the different ways to build a deck out of 20 cards. There's nothing special yet about them being Legos.
0
Commented:
>> TommySzalapski
Of course that is still assuming only one way of connecting them.

I agree.  The approximation I gave is geared toward a 2-D stacking solution, more like domimos than cards.  But Legos can certainly take on complex 3D shapes as well.
0
Commented:
Huh, I thought it would come out cleaner. Looks like we have an incomplete gamma function problem now
http://www.wolframalpha.com/input/?i=sum+%28k!*%28n+choose+k%29%2C+k+from+0+to+n%29
0
Commented:
...and form a new shape.
Also, define "shape". Any given combination of pieces might give the same 'shape' that some other combination might give as a result.

Combinations of attachments and order of attachments isn't quite the same as 'shapes'.

Tom
0
Commented:
If all 20 pieces are different shapes, and you only stack them linearly, than any different combination would also be a different shape.

I looked at the pick-a-brick page on the lego.com site, and only found 14 different basic rectangular brick shapes.
1x1
1x2
1x3
1x4
1x6
1x8
1x10
1x12
1x16
2x2
2x3
2x4
2x6
2x8
If the rest of your 20 unique shapes are rectangular plates, we can deal with that as combinatorially equivalent to a brick, but if your 20 unique shapes also include slopes, angles or other specials that could make it harder.
If you also want to include combinations where more than one piece can be put on a given side of another piece, then that introduces interdependent constraints that can make the enumeration impossibly complex.
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Math / Science

From novice to tech pro — start learning today.