1
$\begingroup$

Lets say you have a circular table that seats $n$ people and $b\lt n -1$ identitcal boys. If you were to divide the boys into $k$ teams of size $\geq 1$, how many ways are there to seat the boys so that the teams sit together and have at least 1 empty seat separating them? Consider the seats to be unique (e.g. if we have only 1 boy, there are $n$ possible seating arrangements for him).

Consider the case where we have $n=6$, $b=4$, $k=2$, we can divide the boys into either 2 teams of 2 or a team of 3 and a team of 1. In the first case, there are 3 unique ways of arranging the boys and 6 ways in the second case, leaving 9 total seating arrangements. How can I generalize this? In the case where each team is of size 1, the problem boils down to finding the number of ways of choosing $k$ non-consecutive positions on a ring of size $n$, which has been well-documented. For bigger teams, the problem seems harder. I suspect I'll first need to calculate the $S(n,k)$, the Stirling number of the second kind to find the total number of possible teams and then finding the ways of arranging them.

Anyone have any ideas? Thanks!

Also, can anyone suggest a good reference for this kind of question

Improve this question
$\endgroup$
4
  • $\begingroup$ Do the members of a team sit together with no spaces between them? In your example, since the boys are identical it seems to me that there is only one way of seating two teams of two and one way of seating a team of three and a team of one, so two ways in all. $\endgroup$
    – Richard Stanley
    Mar 21, 2013 at 17:33
  • $\begingroup$ The members of the each team do sit together, with no spaces in between them. In my example, if we label the chairs around the table as 1, 2, ..., 6 then the for the team of 3 and the team of 1, the 6 seating assignments are given by (123, 5), (234, 6), (345, 1), etc. That is to say, I'm considering the seats to be unique, but not the boys occupying them. $\endgroup$
    – Bemao
    Mar 21, 2013 at 17:51
  • $\begingroup$ @Richard Stanley - thanks for the comment! I fixed the question to make it more clear. $\endgroup$
    – Bemao
    Mar 21, 2013 at 17:56
  • $\begingroup$ So, the teams are not distinct? You might as well consider patterns of $0$s and $1$s in a cycle. $\endgroup$
    – Douglas Zare
    Mar 21, 2013 at 20:28

1 Answer 1

Reset to default
4
$\begingroup$

Replace each occupied seat with a $1$ and each empty seat with a $0$.

Choose a seat $s_0$. Copy $s_0$ and break the cycle into a sequence of length $n+1$ so that $s_0$ is occupied iff the last location $s_n$ is occupied. This sequence is either a string of $k+1$ streaks of $1$s with $k$ streaks of $0$s between, with a total of $(b+1)$ $1$s and $(n-b)$ $0$s, or it is a string of $k+1$ streaks of $0$s with $k$ streaks of $1$s between, with a total of $(b)$ $1$s and $(n-b+1)$ $0$s. These sequences are uniquely determined by strictly positive compositions of the counts of $1$s and $0$s. The number of strictly positive compositions of $a$ into $b$ summands is $a-1 \choose b-1$. So, the total number is

$$ {b \choose k}{n-b-1 \choose k-1} + {n-b \choose k}{b-1\choose k-1}$$.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.