1
$\begingroup$

We have $4$ pockets each containing $4$ placement positions, we want to obtain an estimate on the number of possible arrangements, when the exact set of allowed elements is given: $$ls=[a,a,a,a,b,b,c,c,d,d,x,y] \tag{1}$$ and numbers [1:4] are used for empty slots. For example if one pocket is of the form -,a,-,- then it corresponds to $1$ empty slot then letter a then $2$ empty slots.

Only real restriction is that each pocket can only contain 4 elements at most, and the size is always 4. Two different examples to clarify the size discussion: a,b,c,d has $4$ letters, thus size $4$, another would be 1,a,2 which has $1$ letter thus 1+1+2 = 4. Another clarification, for example a,b,c,d is distinct from b,a,c,d, else we would be counting combinations.

I'm really interested to learn how one should go about doing the count of arrangements of all four pockets, when there are restrictions such as above on pockets. For simplicity, let us assume for the moment that all items in $(1)$ without exception should be inserted into pockets. One example of an arrangement would be: $$a,b,c,d - c,b,a,a - d,a,x,y - 4$$

  • Essentially the question is: how many possible arrangements are there like the above?
  • The main difficulty to me, lies on the one hand in the fact that we have restrictions, and that once one pocket is filled and we move to the next, the set of elements for the remaining pockets has changed. If we had only one pocket then the problem would translate to: Permutation of $n$ objects taken $4$ at a time.

As pointed out by Ian Miller, the problem can effectively be formulated in terms of number of permutations of n elements with repetition. So as an additional sub-question: how to include restrictions such as the a's only allowed to be in certain number of positions (e.g. from 1 to 8 i.e. first 2 pockets, or 8 to 12 etc).

$\endgroup$
  • $\begingroup$ Are permutations of pockets distinct? $$a,b,c,4-c,b,a,a-d,a,x,y-4$$versus$$4-a,b,c,4-c,b,a,a-d,a,x,y$$ $\endgroup$ – Ian Miller Oct 23 '15 at 12:10
  • $\begingroup$ @IanMiller Yes there are counted as distinct, sorry I should clarified this, forgot. Thanks for pointing it out. Probably we can ignore this fact at first and only include the permutations it leads to later on, right? $\endgroup$ – user186225 Oct 23 '15 at 12:13
  • 1
    $\begingroup$ If they are distinct then you can ignore the pockets and just focus on the possible permutations of the sixteen items: $a,a,a,a,b,b,c,c,d,d,x,y,-,-,-,-$. $\endgroup$ – Ian Miller Oct 23 '15 at 12:15
1
$\begingroup$

There is a typo in Miller's answer, it should be $\dfrac{16!}{4!4!2!2!2!}$, as there are $2$ each of $b,c,d$

The ans can also be got by placing elements which will make dealing with the restrictions easier.

$\dbinom{16}{4}\dbinom{12}{4}\dbinom 82\dbinom 62 \dbinom 42\dbinom21\dbinom11 = 4540536000 = T $, say

To come now to the restrictions:

x and y can't be next to each other :

They can be next to each other as $xy$ or $yx$, and we treat as if there are only 15 slots,

so $2*\dbinom{15}1\dbinom{14}4\dbinom{10}4\dbinom62\dbinom42\dbinom22 = P$, say

and ans = $T - P$

4 a's can only be in pockets 1-8: Place them first and go on

$\dbinom84\dbinom{12}4\dbinom82\dbinom62\dbinom42\dbinom21\dbinom11$

PS

The expressions can, of course, be condensed as multinomial coefficients,

e.g. the $2_{nd}$ answer would be $\dbinom{16}{4,4,2,2,2,1,1}-2\dbinom{15}{1,4,4,2,2,2}$

$\endgroup$
2
$\begingroup$

16! ways to place all the items (include 4 null objects). The four $a$'s are identical so 4! ways to interchange those. The four $-$'s are identical so 4! ways to interchange those. The two $b$'s are identical so 2! ways to interchange those. The two $c$'s are identical so 2! ways to interchange those.

Answer: $$\frac{16!}{4!4!2!2!}=9081072000$$

(If you only want combination of pockets then its just another divide by $4!$ arrangements of pockets.)

$\endgroup$

Your Answer

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