Suppose there are $N$ people at a round table. How many ways, denoted as $n(N,p)$, are there to pick $p$ out of $N$ people where $p\geq 2$, so at least two are sitting next to each other?
For example $N=5$:
$n(5,2) = 5$ as $(1,2),(2,3),(3,4),(4,5),(5,1)$
$n(5,3) = 10$ as $(1,2,3), (1,2,4), (1,2,5), (2,3,4), (2,3,5), (3,4,1), (3,4,5), (4,5,1), (4,5,2), (5,1,3)$
Eventually I would like to find $n(N,p)$ in closed form.
Thanks
Let's try to count the number of ways to pick p out of N people at a round table in which no two are sitting next to one another; call it m(N,p). m(5,2) = 5 by the following argument: pick person 0, add 2 to get person 2, then add 3 to get back to person 0. We have partitioned 5 into two terms, 5 = 2 + 3 where each term is > 1. Similarly, pick person 0, add 3 to get person 3, then add 2 to get back to person 0; 5 = 3 + 2. There are two ordered partitions of 5 = a + b where a, b > 1. Starting at 0, they give us the pairs (0,2) and (0,3). Starting at 1, they give us the pairs (1,3) and (1,4). Starting at 2: (2,4) and (2,0). Starting at 3: (3,0) and (3,1). Starting at 4: (4,1) and (4,2). That looks like 10 pairs altogether, but we have double counted: each pair appears twice. Dividing by 2, we get 5 unique pairs of seats which are not together, namely (0,2), (0,3), (1,3), (1,4), (2,4). m(5,2) = 5. Finally, that allows us to compute n(5,2) = c(5,2) - m(5,2) = 10 - 5 = 5 where c is the number of choices with no restrictions.
m(5,3) = 0 because there is no partition of 5 into 3 parts each of which is > 1 (3 x 2 = 6 > 5). So n(5,3) = c(5,3) - m(5,3) = 10 - 0 = 10.
m(6,2): we need to partition 6 into two parts, each of which is > 1. The options are 6 = 2+4, 6 = 3+3, 6 = 4+2. Starting at 0, we get pairs (0,2), (0,3), (0,4), and so on around the circle. There are 6x3 = 18 pairs altogether, but we have double counted, so there are 9 unique pairs. m(6,2) = 9, so n(6,2) = c(6,2) - m(6,2) = 15 - 9 = 6.
m(6,3): we need to partition 6 into three parts, each of which is > 1. There is only one way: 6 = 2 + 2 + 2. Starting at 0, we get (0,2,4). Starting at 1, (1,3,5). Then (2,4,0), (3,5,1), (4,0,2), (5,3,1). We have 6 triples, but we have triple counted, so there are only 2 unique triples. Then n(6,3) = c(6,3) - m(6,3) = 20 - 2 = 18.
m(6,4) = 0: there's no way to partition 6 into four parts, each of which is > 1. It follows that n(6,4) = c(6,4) - m(6,4) = 15 - 0 = 15.
Now we're ready to tackle the general case. For m(N,p), we need to calculate the number of ordered partitions of N into p parts where each part is > 1. That is the same as the number of ordered partitions of N-p into p parts where each part is > 0. That number turns out to be c(N-p-1,p-1). We can see that by writing N-p-1 = 1 + 1 + ... + 1 and then choosing p-1 of the plus signs as boundaries between one term of our partition and the next. E.g., 7 into 3 parts > 1 is equivalent to 4 into 3 parts > 0, but 4 = 1 + 1 + 1 + 1; choosing 3-1 = 2 of the plus signs, we get 4 = 1 + 1 + 2, 4 = 1 + 2 + 1, 4 = 2 + 1 + 1, so the required partitions of 7 are 7 = 2 + 2 + 3, 7 = 2 + 3 + 2, 7 = 3 + 2 + 2.
We have almost calculated m(N,p), but remember we overcount p-tuples by a factor of p (we count rotations of any p-tuple separately). So it follows that m(N,p) = c(N-p-1,p-1)/p.
Finally we get a formula for n(N,p) = c(N,p) - c(N-p-1,p-1)/p.
You should test that formula in many different cases by counting with a computer program.
