<p>Maybe I miss something, but it looks obvious that if $k&lt;=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.</p>

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

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

CC BY-SA 3.0
2014-09-12T12:31:44.123Z
2014-09-12T12:31:44.123Z
Florian F
<p>Question 1: No</p>

<p>counterexample: bin 1 = $[1,2,3]$, bin 2 = $[4,5,6]$</p>

CC BY-SA 3.0
2014-09-11T02:24:11.347Z
What if we put the restriction of k<n ?
Dibyayan
CC BY-SA 3.0
2014-09-10T18:01:42.713Z
2014-09-10T18:01:42.713Z
bbejot
<p>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.</p>

<p>Questions: </p>

<ol>
<li><p>Does there always exist such a rearrangements? why ?</p></li>
<li><p>What is the official name of this problem in the literature ?</p></li>
</ol>

<p>Any link/hint would be helpful.</p>

CC BY-SA 3.0
2014-09-10T18:17:03.080Z
When bins capacity is one the counting version of the problem known as [derangement](http://en.wikipedia.org/wiki/Derangement). But I think your problem is better suited at math.se.
Saeed
CC BY-SA 3.0
2014-09-11T06:03:13.517Z
@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.
Sasho Nikolov
CC BY-SA 3.0
2014-09-11T08:34:30.653Z
@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.
Saeed
CC BY-SA 3.0
2014-09-11T08:41:33.443Z
@SashoNikolov is correct, when k=1, then any permutation is valid
Dibyayan
<reference-request><graph-theory><co.combinatorics>
Arrangements of Objects
Dibyayan
# Arrangements of Objects

(Asked by: username_0 on 2014-09-10)

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 ?

Any link/hint would be helpful.

**Tags:** reference-request, graph-theory, co.combinatorics

> **Comments:**
> **username_1**: When bins capacity is one the counting version of the problem known as [derangement](http://en.wikipedia.org/wiki/Derangement). But I think your problem is better suited at math.se.  
> **username_2**: @username_1 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.  
> **username_1**: @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.  
> **username_0**: @SashoNikolov is correct, when k=1, then any permutation is valid  

---

## 2 answers

### Answer by username_3 on 2014-09-12. Score: 2 | Accepted answer

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}


---

### Answer by username_4 on 2014-09-10. Score: 2

Question 1: No

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

> **Comments:**
> **username_0**: What if we put the restriction of k<n ?  

---

