Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Richard Stanley Mar 21 '13 at 17:33
    
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. –  Bemao Mar 21 '13 at 17:51
    
@Richard Stanley - thanks for the comment! I fixed the question to make it more clear. –  Bemao Mar 21 '13 at 17:56
    
So, the teams are not distinct? You might as well consider patterns of $0$s and $1$s in a cycle. –  Douglas Zare Mar 21 '13 at 20:28
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
Thanks! This is exactly what I was looking for. –  Bemao Mar 22 '13 at 15:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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