# Combinations which do not have elements in common

I can choose 2 letters from the four letters $\{A,B,C,D\}$ in 6 combinations using the combination formula

$$\frac{n!}{ r! (n-r)!}$$

{A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D}


Consider now the collection of all subsets of a set of $n$ elements and restrict to those having exactly cardinality $k$, such as $k=2$ above. How can I find all combinations of groups of 2 or 3 or ... or $n$ (should be dynamic) of these which do not have letters in common? So, for example, I am expecting the result for combinations of two groups of $k=2$ elements to be the three collections below:

{{A, B}, {C, D}},

{{A, C}, {B, D}},

{{A, D}, {B, C}}


This is just a small example but I would like the algorithm to work for a large number of sets (I have more than 35000 sets).

-
The number of letters change or you will just use 4? – Spawn1701D Apr 18 '13 at 18:27
Aren't they the permutations, properly splitted? – Dr. belisarius Apr 18 '13 at 18:33
@belisarius I don't think so. For example, splitting ABCD into groups of two gives the same partition as splitting BACD, ABDC, BACD, CDAB, etc. – whuber Apr 18 '13 at 18:49
user, this may be a duplicate of your question, though phrased differently: mathematica.stackexchange.com/q/3044/121 -- please review that, and if it is not, make clear in this question why not. – Mr.Wizard Apr 19 '13 at 3:22
Yes, it is same, i couldn't find it. But I am not from pure mathematics, I am a programmer so want the programming algorithm to solve this problem. – user1191081 Apr 19 '13 at 12:55

It is desired to find all collections $P = \{A_1, A_2, \ldots, A_m\}$ of $m$ disjoint $k$-subsets of a finite set $X$. Such collections consist of two types: those which include a specified element of $X$ (say $a$) and those that do not. If $a \in A_j$ for some $j$ then we might as well reindex the elements of $P$ so that $j=1$. All possibilities for $A_1$ are found by adjoining all possible $k-1$-element subsets of $X - {a}$ to $a$, whereas all possibilities for the $A_2, \ldots, A_m$ are found recursively for $X - A_1$ with $m=1$. Otherwise, $a$ is not in any $A_j$ and we are left to find similar collections for $X - {a}$.

This gives the following recursive solution. It's not fast but it's not slow, either--see the timing example below.

Please note that the number of solutions grows very, very quickly with $k$ and $m$. Their number is computed with combinationsCount, which uses Multinomial to obtain

$$\frac{n!}{k!^m (n - m k)! m!}.$$

The numerator is the size of the permutation group on $X$ while the denominator is the size of the stabilizer of any collection $P$: it consists of all permutations that (a) separately permute the elements of the $A_j$, (b) permute the remaining elements in $X - \cup_j A_j$, and (c) then permute the $A_j$ among themselves.

combinations[x_List, k_Integer, 0] := {{}};
combinations[x_List, k_Integer, m_Integer] := {};
combinations[x_List, k_Integer, m_Integer] /;
k m <= Length[x] && k >= 1 && m >= 1 := Block[{y, with, without},
y = Prepend[#, First@x] & /@ Subsets[Rest@x, {k - 1}];
with = Flatten[Table[Prepend[#, z] & /@ combinations[Complement[x, z], k, m - 1], {z, y}], 1];
without = combinations[Rest@x, k, m];
with~Join~without
];
combinationsCount[n_, k_, m_] := Multinomial @@ Append[ConstantArray[k, m], n  - k m] / m!


### Examples

combinationsCount[6, 3, 2]


$10$

MatrixForm /@ combinations[{a, b, c, d, e, f}, 3, 2]


$\begin{array}{lllll} \left( \begin{array}{ccc} a & b & c \\ d & e & f \end{array} \right) & \left( \begin{array}{ccc} a & b & d \\ c & e & f \end{array} \right) & \left( \begin{array}{ccc} a & b & e \\ c & d & f \end{array} \right) & \left( \begin{array}{ccc} a & b & f \\ c & d & e \end{array} \right) & \left( \begin{array}{ccc} a & c & d \\ b & e & f \end{array} \right) \\ \left( \begin{array}{ccc} a & c & e \\ b & d & f \end{array} \right) & \left( \begin{array}{ccc} a & c & f \\ b & d & e \end{array} \right) & \left( \begin{array}{ccc} a & d & e \\ b & c & f \end{array} \right) & \left( \begin{array}{ccc} a & d & f \\ b & c & e \end{array} \right) & \left( \begin{array}{ccc} a & e & f \\ b & c & d \end{array} \right) \end{array}$

combinationsCount[13, 3, 4]


$200200$

AbsoluteTiming[Length@combinations[Range@13, 3, 4]]


$\{5.9153384,200200\}$

-