2
$\begingroup$

How many ways are there to seat n people in 4 benches so that no bench is left empty with order?

Hints from the teacher

  • Each bench should have at least 1 person

  • This question is similar to distributing different object among n children

  • The answer is one line

I am not sure how to deal with this question, but this was what I tried.

Let $A_i$ be the set of all distributions in which $i-$th bench is empty.

Then $|A_i| = (n-1)^4$ for each $i$.

$|A_i\cap A_j|= (n-2)^4$ for each $i\ne j$

$|A_i\cap A_j\cap A_k|= (n-3)^4$ for each $i\ne j\ne k\ne i$

$|A_i\cap A_j\cap A_k \cap A_l|= (n-4)^4 = 1$ for all pairvise different $i,j,k,l,m$

Now we are interested in $$\Big| \bigcap_{i=1}^n \overline A_i\Big| = \Big|\; \overline{\bigcup_{i=1}^n A_i}\;\Big| = n^4-\Big|\; \bigcup_{i=1}^n A_i\;\Big| $$We have by PIE: \begin{eqnarray*} \Big|\; \bigcup_{i=1}^n A_i\;\Big| &=& \sum_{i=1}^n \Big|\; A_i\ \Big| - \sum_{i=1}^n \Big|\;A_i\cap A_j\ \Big|+...\\ &=& 4\cdot (n-1)^4-2n\cdot (n-2)^4+2n\cdot (n-3)^4-4 ..... +0=\\ \end{eqnarray*}

So the final answer is $n^4-$(the above value).

Am I correct, or is there something that I am doing wrong?

Edit: Also maybe I want to apply pigeonhole principle since n items are to be put into m containers, with n > m, then at least one container must contain more than one item..

$\endgroup$
  • $\begingroup$ What does "empty with order" mean? $\endgroup$ – NicNic8 May 23 '18 at 19:04
  • $\begingroup$ Are the benches distinguishable? Are the people? Please edit to include a clear example. If $n=4$, say, what is the answer? $\endgroup$ – lulu May 23 '18 at 19:04
  • $\begingroup$ How did you obtain the factor $2n$ for the coefficient of $(n - 2)^4$? What does it represent? $\endgroup$ – N. F. Taussig May 23 '18 at 19:13
  • $\begingroup$ @NicNic8 no bench is left empty so it means that each bench should have at least 1 person with an order is the seating arrangements. $\endgroup$ – nano mano May 23 '18 at 19:13
  • $\begingroup$ @lulu how will people be identical.. Then it is 1 person, ofc they are different as well as the benches. Also, isn't n unlimited number of people since it didn't specify? $\endgroup$ – nano mano May 23 '18 at 19:15
3
$\begingroup$

We have $n!$ permutations of students. Now lets take a permutation $i_1, i_2, .., i_n$ we want to distribute it in 4 slots. That means we have n-1 positions at which we can cut the set and we need to cut it at three of them, so the answer is

$n! * {n-1 \choose 3}$

P.s. no partition will be empty because the first cut is after the first element, the last one is before the last, and there is one element between any two consecutive cuts

$\endgroup$
  • 1
    $\begingroup$ I assume $i=n$? Also, don't forget that you need somebody on each bench. $\endgroup$ – lulu May 23 '18 at 19:41
  • $\begingroup$ You're right sorry, I'll try to figure it out $\endgroup$ – narek Bojikian May 23 '18 at 19:47
  • 1
    $\begingroup$ You are close, here, but not correct. If you take $n=5$ and $k=4$ (as in the OP's question) you'll see that your text gives the correct answer but your formula does not. $\endgroup$ – lulu May 23 '18 at 19:48
  • $\begingroup$ @lulu so it would be $ n+k-1 \choose k $ multiplied by $n!$ ?? $\endgroup$ – nano mano May 23 '18 at 19:54
  • 2
    $\begingroup$ The edited version is good. (+1) $\endgroup$ – lulu May 23 '18 at 20:28
1
$\begingroup$

A lot depends on exactly what is meant by "with order." If we take it to mean that both the order of the benches and the order in which people sit on each bench matter, then the answer is simple:

$$n!{n-1\choose3}$$

That is, line the people up from left to right, in any of $n!$ ways, then pick $3$ "break points" to decide which groups go to benches $1$, $2$, $3$, and $4$.

$\endgroup$
1
$\begingroup$

Let k = number of benches = 4

It is like we are distributing people to benches. If there were no restrictions, then it would have been $${n+4-1\choose 4-1}$$

Since we have a rule that each bench should have at least one person, then $$ x1+....+xn = 4$$

For any pair of positive integers n and k, the number of distinct k-tuples of positive integers whose sum is n is given by the binomial coefficient $xi∈Z,xi>0$ $${(n-k)+k-1\choose k-1} = {(n-4)+4-1\choose 4-1}$$

$$= {n-1\choose 4-1} == {n-1\choose 3} $$

The order matters, so we will need to multiply this by n! which is the arrangements that people could be seated.

Final answer: $$ n! \times {n-1\choose 3} $$

Now we are done solving this question by using the stars and bars method.

$\endgroup$
  • 1
    $\begingroup$ Completely sound. (+1) $\endgroup$ – lulu Jun 2 '18 at 23:34

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.