Arrangements of Objects

Suppose there are $n$ bins each having $k$ objects. Assume that capacity of each bin is also $k$. Now we want to rearrange the objects such that each bin contains $k$ objects but this time if $x,y$ belong to the same bin, then $x,y$ were in different bins in the original arrangement.

Questions:

1. Does there always exist such a rearrangements? why ?

2. What is the official name of this problem in the literature ?

• When bins capacity is one the counting version of the problem known as derangement. But I think your problem is better suited at math.se. Sep 10 '14 at 18:17
• @Saeed I dont think a derangement is the $k=1$ case. In fact the in the $k=1$ case any arrangement is vacuously admitted. The requirement is not that all items change bins, but that if two items share a bin in the new arrangement, they must have not shared a bin in the initial arrangement. Sep 11 '14 at 6:03
• @SashoNikolov, I read it in the way that, they are not allowed to be in their original bin and also they are not allowed to be in same bin as their initial bin. Sep 11 '14 at 8:34
• @SashoNikolov is correct, when k=1, then any permutation is valid Sep 11 '14 at 8:41

Maybe I miss something, but it looks obvious that if $k<=n$ then you can rearrange the objects in the simplest way. Number the objects of each bin from 0 to k-1 and move object i to the i'th next bin.

Before:
bin A: {A0, A1, A2}
bin B: {B0, B1, B2}
bin C: {C0, C1, C2}
bin D: {D0, D1, D2}

After:
bin A: {A0, D1, C2}
bin B: {B0, A1, D2}
bin C: {C0, B1, A2}
bin D: {D0, C1, B2}

Question 1: No

counterexample: bin 1 = $[1,2,3]$, bin 2 = $[4,5,6]$

• What if we put the restriction of k<n ? Sep 11 '14 at 2:24