Seat n people in 4 benches

Question

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..

Answer 1

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

Answer 2

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$.

Answer 3

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.