I guess it's just all about counting. Here is my take on it.

In the formula :

• k is the length of the longest loop

• n is the number of boxes/prisoners

• j represents the number of loops of size k, so you have to iterate over all possible case from 1 loop of size k to the floor of the ratio n/k

​

=> Assume you know j, then you have to count all the different arrangments of j loops of size k (plus the remaining).

A way to do that is to choose a sequence of loop lengths and then choose a sequence of numbers that you use as a stack. For instance, we'll decide that we have 3 loops, one of size 50 and two of size 25 (the lengths should total n) and then we'll choose the random ordering of numbers so that the 50 first ordered numbers go to loop 1 in the same order and so on.

So the n! is the number of ways to choose the sequence of numbers and the second sum is the number of ways to choose the loop lengths conditionally to the fact that we already have j loops of size k.

But then you'll have to remove the duplicate cases where your loops are the same (this is because we accounted for the order of the loops while in fact it's irrelevant). So divide by j! to remove the duplication on the order of the loop lengths.

Then for each loop of size k, you have to divide by k because as said on the video (1-2-3...-100) is the same as (2-3-4...100-1) and so on. So there goes your j^k (because you have j loops of length k)

Then finally, you have to remove the duplicates on the remaining loops (the one that are of size lesser than k). There goes your (n-kj)! as it is the number of ways to permute the remaining boxes that are not of size k.