3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Jul 19, 2018 at 15:24
  • $\begingroup$ @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 $\endgroup$
    – llrs
    Jul 19, 2018 at 15:51
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Jul 19, 2018 at 17:06
  • $\begingroup$ 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. $\endgroup$
    – llrs
    Jul 19, 2018 at 17:12
  • $\begingroup$ @whuber I edited it again, I hope it is more clear now. Thanks for always helping me to refine my questions $\endgroup$
    – llrs
    Jul 19, 2018 at 20:11

1 Answer 1

2
$\begingroup$

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.$$

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – llrs
    Jul 19, 2018 at 21:43
  • $\begingroup$ Having a few worked examples was very helpful in checking the formula. $\endgroup$
    – whuber
    Jul 19, 2018 at 21:47
  • $\begingroup$ I was trying to solve those cases myself but I gave up. I'll post those easy cases first next time. $\endgroup$
    – llrs
    Jul 19, 2018 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.