I am a linguist, not a mathematician, so I apologize if there's something wrong with my terminology and/or notation.
I have two structures that I want to merge (partially or completely). To generate a list of all possible combinations, I compute the Cartesian product of the two sets of objects, which gives me a set of pairs, and then I compute the [1, …, n]-fold Cartesian product of my set of pairs with itself where n is the highest cardinality out of the two structures (here, 5).
A = (a1, a2, a3, a4, a5) and B = (b1, b2, b3, b4, b5)
Basically, I'm generating 1-tuples like ((a1, b1)), ((a1, b2)), …, ((a5, b5)) that merge one pair of objects, 2-tuples that merge two pairs of objects, etc. up to n-tuples. I end up with $\sum\limits_{i=1}^{n} (\bar{\bar{A}}\times \bar{\bar{B}})^i$ tuples, where $\bar{\bar{A}}$ and $\bar{\bar{B}}$ represent the cardinalities of the two structures.
In this case, I get 10172525 tuples, which is way too high for my needs. I filter my list to only keep tuples if the pairs they contain are all different and cannot be found in another tuple with the same length. This removes up to 99% of the original tuples. For example:
((a1, b1), (a2, b2), (a3, b3))
((a1, b1), (a3, b3), (a2, b2)) has the same pairs as the preceding tuple, but in a different order
((a1, b1), (a1, b1), (a3, b3)) has the pair (a1, b1) more than once
I'm looking for an equation that will help me predict the number of unique tuples. For 1-tuples, there's $\bar{\bar{P}}$ unique tuples where $\bar{\bar{P}}$ is the number of pairs. For 2-tuples, I do $\frac{\bar{\bar{P}}\times (\bar{\bar{P}}-1)}{2}$. I'm sure there's an equation that works for any tuple length, but I can't figure it out.
Here are the numbers of tuples generated vs. unique tuples for two structures with 4 objects each:
+--------+-----------+--------+
| Length | generated | unique |
+--------+-----------+--------+
| 1 | 16 | 16 |
| 2 | 256 | 120 |
| 3 | 4096 | 560 |
| 4 | 65536 | 1820 |
| Total | 69904 | 2516 |
+--------+-----------+--------+
Best Answer
If $P$ is an $n$-element set ($\bar{\bar P}=n$) then the number of $k$-element subsets of $P$ (that's unordered subsets, no repetitions) is given by the binomial coefficient $$\binom nk=\frac{n!}{k!(n-k)!}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}.$$