1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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