# How many ways are there to divide n dancers into dance circles where in each circle num of dancers >=2?

Question:Be n\geq 2, how many ways are they to divide n dancers to circles so each circle has at least 2 dancers?

I saw a similar question here but it was where order matter in the circles and without >=2. From what I understand of the question order in the circles or between the circles doesn't matter. I know you supposed to use the Inclusion–exclusion principle but not sure how. I got to find the num of circles can go from 1 to ⌈├ n/2⌉ ┤ and the Complement is where at least one circle is of size 1 and here I get stuck how to define things to use the Inclusion–exclusion

This is a surprisingly hard question!

First, we'll ignore the $$\geq 2$$ bit, and just split them into circles: this means that we need the number of non-empty partitions of a set of size $$n$$, which is the Bell number $$B_n$$. But then we need to subtract out those that include at least one singleton: we can do this by an inclusion-exclusion approach, first subtracting out all of those which leave the first person as a singleton (there are $$B_{n-1}$$ of them), then the same for the others (so that's $$\left(\array{n\\1}\right)$$ copies), then add back in all of those which we've done twice, and so on, via an inclusion-exclusion approach, leaving our final formula as

$$\sum\limits_{k=0}^n(-1)^k\left(\array{n\\k}\right)B_{n-k}.$$

Which isn't very useful if we don't know what the Bell numbers are, so we'll carry on and find a formula for $$B_n$$, so we can get that into something we can actually calculate conveniently. To do this, we'll note that $$B_n = \sum\limits_{k=0}^{n}\left\{\array{n\\k}\right\},$$ where $$\left\{\array{n\\k}\right\}$$ is the Stirling Number of the Second Kind, so our full formula is now:

$$\sum\limits_{k=0}^n(-1)^k\left(\array{n\\k}\right)\sum\limits_{i=0}^{n-k}\left\{\array{n-k\\i}\right\}.$$

Finally, there's an explicit formula for the Stirling Numbers of the Second Kind:

$$\left\{\array{n\\k}\right\} = \frac{1}{k!}\sum\limits_{i=0}^k(-1)^{k-i}\left(\array{k\\i}\right)i^n,$$ which we can substitute in to obtain our final formula: $$\sum\limits_{k=0}^n(-1)^k\left(\array{n\\k}\right)\sum\limits_{i=0}^{n-k}\frac{1}{i!}\sum\limits_{j=0}^i(-1)^{i-j}\left(\array{i\\j}\right)j^{n-k} = \sum\limits_{k=0}^n\sum\limits_{i=0}^k\sum\limits_{j=0}^i(-1)^{k+i-j}\left(\array{n\\k}\right)\left(\array{i\\j}\right)\frac{j^{n-k}}{i!}.$$

There's probably a less awful way of writing that, but I don't know what it might be.

• Thanks, I need to go over this a few times but seems like a great answer – Idan Daniel Dec 4 '18 at 14:02
• Just wrote it down and this is exactly what I needed, Just never would have thought to use bell numbers. Thanks alot – Idan Daniel Dec 4 '18 at 14:28