0

Consider a sequence: $$S_0 = 1, 2, 3, ..N$$

Let $S_1$, $S_2$, $S_3$, ..., $S_k$ be $N$-length permutations of $S_0$ such that for any $(i,j)$ | $1 \le i < j \le k$, the sequences $S_i$ and $S_j$ are derangements of each other (i.e, they do not have any element in the same position).

How many such sets $\{S_1, S_2, .. S_k\}$ exist that are not permutations of each other?

If $k=2$, it is easy: there are $N!$ ways to form $S_1$ and then $!N$ derangements to form $S_2$, giving us $(N! \times !N)/2$ sets.

For $k = N$, I think there are only $N!$ such sets: once $S_1$ is formed, all other sequences will be a unique cyclic shift of $S_1$

For $k > N$, the answer is $0$.

Can anyone help me for general values of $k$ and $N$?

Thanks!

Karthick
  • 1
  • I think you are basically looking at Latin rectangles. The $k=N$ case is Latin squares, and I fear you are grossly under-counting them. – Angina Seng Jun 02 '17 at 05:18
  • Looks like I didn't search enough: same question asked (but no answers yet): https://math.stackexchange.com/questions/1682662/derangements-relative-to-multiple-arrangements – Karthick Jun 02 '17 at 05:25

0 Answers0