0
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Could you explain this in more elementary terms? :) $\endgroup$ Commented Mar 15, 2013 at 18:01
  • $\begingroup$ @Web_Designer: Not much more elementary, I’m afraid. I’m really using only a couple of things. One is the multiplication principle, which I used to get $c(c-1)\dots(c-k+1)$ total choices of seats for the $k$ members of $S$. Another is the fact that a set of $n$ elements has $\binom{n}k$ subsets of size $k$, where $\binom{n}k$ is a binomial coefficient. Can you pin down a little more narrowly where you need more explanation? $\endgroup$ Commented Mar 15, 2013 at 18:06
0
$\begingroup$

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)!} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .