# Number of combinations when swapping two sets with some elements in both

This question is closely related to this other one: I have two sets and I want to know the number of possibilities I can do with the elements of these two sets.

As a possibility I mean changing elements ( 1 or several) from one set with elements from another set, but elements in a set cannot be repeated.

However in contrast with the other question, I have some element that are in both sets, and remember that I don't want the same element repeated in the same set:

With these pair of sets set1: {A, B, C, D, E, F, G}; set2: {A, D, H}, I would say that there are 5 possibilities: 5 elements from set1 that can be swapped with one element of set2:

Possibilities:
set1:{A, D, H, C, E, F, G}; set2: {A, D, B}
set1:{A, D, H, B, E, F, G}; set2: {A, D, C}
set1:{A, D, H, B, C, F, G}; set2: {A, D, E}
set1:{A, D, H, B, C, E, G}; set2: {A, D, F}
set1:{A, D, H, B, C, E, F}; set2: {A, D, G}


If element A or D are swapped, they will be repeated in one set (unless they are changed with themselves in which case we haven't done anything), and if element H is not in set1 it wouldn't have changed any element from set2 to set1.

But with these other pair, set1: {A, B, C, D, E, F, G}; set3: {A, H, I} I think that there are 12 possibilities with just changing one element between the sets (6*2) and then 15 if we change 2 elements from one set to the other ${6 \choose 4}$, in total 27.

I can't find a rule to generalize to different settings (having more shared elements, different size of sets, ...). Is there any mathematical/statistical rule to count this?

It is different from Cartesian product because I don't want to know the number of sets that can be created taking one element from each set.

• Because you evidently use the word "combination" in a different sense than its usual meaning in mathematics and statistics, you need to edit this question to provide a definition.
– whuber
Jul 19, 2018 at 15:24
• @whuber I edited the question but I think I used the word combination as defined in wikipedia: "combination is a selection of items from a collection...such that the order of selection does not matter", but I want this selection to be in two sets. Let me know how can I further clarify my question
– llrs
Jul 19, 2018 at 15:51
• I'm afraid I can't figure what rule you're using to determine which elements can be "swapped" and which ones not. If we understand a "swap" to mean exchanging two elements between the sets, then why in your example wouldn't it be possible to swap B with D, for instance, producing sets {A,C,D,E,F,G} and {A,B,H}? Is it perhaps that for any two sets $a$ and $b$ you are asking for all ways to pair an element of $a\setminus b$ with an element of $b\setminus a$? That's called the Cartesian product, by the way.
– whuber
Jul 19, 2018 at 17:06
• The pair you propose is not possible because then in the same set there would be two D. I'll look up the term (now I can't) but I'm atraid it might be not what I am looking for but it might be related.
– llrs
Jul 19, 2018 at 17:12
• @whuber I edited it again, I hope it is more clear now. Thanks for always helping me to refine my questions
– llrs
Jul 19, 2018 at 20:11

You seem to ask the following: given two sets $A$ and $B$ (in order), in how many ways can a new pair of sets of the same sizes as the original sets be created by removing one or more elements from $B$ and the same number of elements from $A$ and putting each collection back into the other set?

I hope it's obvious that we don't need to keep track of elements common to $A$ and $B$ (because swapping them does nothing). Thus, we may remove all common elements from each set, reducing the question to the case where $A$ and $B$ are disjoint.

Notice that the result consists of an ordered pair of disjoint subsets of the union of $A$ and $B$ and is determined (say) by the elements of the first set, of which there are $|A|$. Consequently, the total number of swaps--including doing nothing, which yields the original pair of sets--is in one-to-one correspondence with the subsets of size $|A|$ in the union $A\cup B$, which has size $|A|+|B|$. Subtracting $1$ to account for the original configuration gives

$$\binom{|A|+|B|}{|A|}-1$$

as the answer. In general, if you want to be explicit about removing the common elements $A\cap B,$ the formula is

$$\binom{|A|+|B|-2|A\cap B|}{|A|-|A\cap B|}-1.$$

This formula does indeed count combinations, in sense understood in combinatorics and probability theory--but they are combinations within the derived set $A\, \nabla\, B,$ the symmetric difference of $A$ and $B.$

In the second example of the question where the sets are $\{a,b,c,d,e,f,g\}$ and $\{a,h,i\},$ we have $|A|=7,$ $|B|=3,$ and $|A\cap B|=1,$ yielding

$$\binom{7+3-2(1)}{7-1}-1 = \binom{8}{6}-1 = 28-1 = 27.$$

• Many thanks for you answer, as helpful as always! It was not far of what I was thinking but I missed subtracting the double of the disjoint.
– llrs
Jul 19, 2018 at 21:43
• Having a few worked examples was very helpful in checking the formula.
– whuber
Jul 19, 2018 at 21:47
• I was trying to solve those cases myself but I gave up. I'll post those easy cases first next time.
– llrs
Jul 19, 2018 at 21:48