0
$\begingroup$

Given the following $8$ LEGO bricks:

  • $3$ pieces of length $6$
  • $5$ pieces of the length $8$

In how many ways can they be ordered in one layer (one row)?

Total number of ways to order the bricks (permutations): $8!$

But we get some repeated permutations since we have duplicated elements, in e.g:

$S_1=\{6,6,6,8,8,8,8,8\}$

$S_2=\{6,6,6,8,8,8,8,8\}$

So how can I account for the repeated ones?

Update

Permutations, bricks with length $6$: $3!$

Permutations, bricks with length $8$: $5!$

Since their mutual order doesn't matter, we might remove them?

${\displaystyle \frac{8!}{3!\cdot5!}}$

Is this correct?

$\endgroup$
  • $\begingroup$ Are the pieces being arranged in a row? $\endgroup$ – N. F. Taussig Oct 2 '18 at 11:16
  • $\begingroup$ @N.F.Taussig Yes exactly. $\endgroup$ – phx Oct 2 '18 at 11:26
0
$\begingroup$

Quite Easy.

Just consider the fact that all pieces of same dimensions are exactly similar; and that you can't distinguish them.

If you want to arrange n objects in a row such that $ r_1 $are of 1 kind, $r_2 $ are of other kind,....and $r_n $ are of another similar kind, then you can arrange these n objects in $$ \frac {n!}{(r_1)! \cdot (r_2)! \cdot \cdot \cdot (r_n)!} $$

This is because, you want to avoid those cases when similar kind objects are inter-arranged; i.e. assume that your 3 pieces are named as p1,p2 and p3 and other 5 as q1,q2,q3,q4 and q5 (though all p's and q's are similar)
Now, if you just take 8!, p1,p2,p3,q1,q2,q3,q4,q5 and p1,p3,p2,q1,q2,q3,q4,q5 will be considered as different, and counted twice; although they are similar.

So, you avoid this over-counting by preventing inter-arrangements of p1,p2,p3 in 3! and of q1,q2,q3,q4,q5 in 5! ways, and divide 8! by 3! and 5!

So, here n=8, $r_1$=3 and $r_2$=5
$$ \frac {8!}{3! \cdot 5!} $$
is your answer.

$\endgroup$
1
$\begingroup$

We have eight positions to fill with three pieces of length six and five pieces of length eight.

Notice that the sequence is completely determined by choosing which three of these eight positions are filled with pieces of length six. In how many ways can you choose three of the eight positions to fill with pieces of length six?

$$\binom{8}{3}$$

I suggest that you verify that this works by listing the distinguishable sequences for a simpler problem such as three pieces of length six and two pieces of length eight.

$\endgroup$
1
$\begingroup$

I think it's important to understand the structure of the problem. N.F. Taussig's answer is the correct thinking, but Idea's answer is the general solution, so what is the intuition?

For any instance where you must fill some slots with items, and the order of the items in those slots does not matter, you must use choose, where

$$ C(n;r) = \binom{n}{r} = \frac {n!}{k!(n-k)!} $$

Consider the set of possible classes, (brick lengths in this problem,) $1, 2, \dots k$ where the brick counts per class are $r_1, r_2, \dots r_k$. Since you want to place all of these bricks, the total number of slots that will contain bricks is the sum of the $r_i$ which we will call $n$. That is, in a generalized LEGO problem (assuming they're all of the same color), each class $r_i$ contains one or more bricks of all the same size, and if you want to arrange them all, you must place all bricks from all classes.

Since you are placing $n$ bricks, you have $n$ slots to fill. Start with the bricks of the first class. This is $C(n; r_1)$: this is the count of all ways of occupying $n$ slots with your bricks of length 1.

How do you place the second class? Since $n$ slots are now occupied by $r_1$ bricks, you have only $n-r_1$ slots left, leaving you with $C(n-r_1; r_2)$ ways to place bricks from the second class. Take the product to determine the total number of ways of doing the above: for each of the ways to place the $r_1$, you have a number of ways to place the $r_2$.

Placing the remaining classes is $C(n-r_1-r_2; r_3)$, $C(n-r_1-r_2-r_3; r_4)$ and so on, eventually ending on class $k$ where you have $C(r_k$ slots left$;r_k$ bricks$) = 1$, indicating the fact that the placement of the other $r_{k-1}$ classes determines the placement of the final class. Using the definition of choose, this works out algebraically:

$$ \binom{n}{r_1}\binom{n-r_1}{r_2}\binom{n-r_1-r_2}{r_3}\cdots\binom{r_k=n-r_1-r_2-\dots r_{k-1}}{r_k} \\ = \frac{n!}{r_1!(n-r_1)!}\frac{n-r_1!}{r_2!(n-r_1-r_2)!}\frac{n-r_1-r_2!}{r_3!(n-r_1-r_2-r_3)!}\cdots\frac{r_k}{r_k!(r_k-r_k)!} $$ Given that the last product is 1, you can cancel out the $n-r_1-r_2-\dots$ terms, leaving only the $r_i!$ terms in the denominator: $$ \frac{n!}{r_1!r_2!r_3!\dots r_k!} $$ Thanks for being patient with the long-winded answer, but combinatorics is like a puzzle and requires a special way of thinking, and hopefully I've communicated that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.