possible seeting arrangments given number of people, and number of chairs, chairs can be empty

Question

Given a number of people (represented by the letter $p$), and a number of chairs (represented by the letter $c$), what equation can I use to figure out how many possible seating arrangements there are?

The catch?
Chairs can be empty and not everyone has to be in a chair.

So for example given 3 chairs and 5 people the following 6 options exist for the first chair:

• chair is empty
• person A sits in chair
• person B sits in chair
• person C sits in chair
• person D sits in chair
• person E sits in chair

For the second chair it gets really complicated. If no one sits in the first chair then you have the same 6 options available for the second chair, however if, for example, person B sits in the first chair, you have 5 options (the six above not including "person B sits in chair") available for the second chair. It gets really complicated from here.

BTW, I'm kind of new to the subject and I'm not sure what tags to use. I'd appreciate it if someone could add the relevant tags.

Answer 1

Let $P$ be the set of $p$ people and $C$ the set of $c$ chairs. To construct a seating arrangement we must first choose an $S\subseteq P$ to be seated; clearly we must have $|S|\le c$. Then we have $c$ choices for a seat for the first member of $S$, $c-1$ for the second, and so on, so if $|S|=k$, we can seat $S$ in

$$c(c-1)\dots(c-k+1)=\frac{c!}{(c-k)!}=\binom{c}kk!=c^{\underline k}$$

different ways, where $x^{\underline n}$ is a falling factorial. There are $\binom{p}k$ subsets of $P$ of size $k$, so just from them we have $\binom{p}kc^{\underline k}$ seating arrangements. Finally, $k$ can run from $0$ through $\min\{c,p\}$, and we’ve a total of

$$\sum_{k=0}^{\min\{c,p\}}\binom{p}k\binom{c}kk!=\sum_{k=0}^{\min\{c,p\}}\binom{p}kc^{\underline k}$$

arrangements.

Answer 2

I believe that it is not so complicated. If k is count of empty chairs, then we have the possibility of empty chairs ${c}\choose {k}$ and we have $f = c - k$ occupied and the $p\cdot (p-1)\cdot .. (p-f) = {{p!}\over (p-f)!} = {{p!}\over (p-c+k)!}$ option arrangement of occupied seats.
The number of empty seats may be in the interval $k\in\left[ {c-p,\;c} \right]$, so if c is count of possible seetings arrangement then: $$ c = \sum_{max(c-p, 0)}^c {{c}\choose {k}}\cdot {{p!}\over (p-c+k)!} $$