is there a closed solution to counting pairwise combinations of the elements of two sets without resampling?

Question

This is the pairing algorithm I have written and it seems to work.

numlist =(1,2,3,4)
letter_combinations=("pa","pb")
i=0
for num1 in numlist:
    for num2 in numlist:
        if num1 != num2:
            used_combinations = set()
            for comb1 in letter_combinations:
                for comb2 in letter_combinations:
                    if comb1 != comb2 and comb2 not in used_combinations:
                        print(f"({comb1}{num1},{comb2}{num2})", end=" ")
                        i += 1
                        used_combinations.add(comb1)
            print()
print(i)

The number of pairwise combinations without resampling is 12.

(pa1,pb2)
(pa1,pb3)
(pa1,pb4)
(pa2,pb1)
(pa2,pb3)
(pa2,pb4)
(pa3,pb1)
(pa3,pb2)
(pa3,pb4)
(pa4,pb1)
(pa4,pb2)
(pa4,pb3)

but is there a formula using the number of elements of each set to calculate the total number of pairs?

Answer 1

Let $N$ be the number of elements of num_list, and let $L$ be the number of elements of letter_combinations.

Every combination in this list looks like $$ (n_1,\ell_1,n_2,\ell_2) $$ such that...

• $n_1,n_2$ are in num_list, and $\ell_1,\ell_2$ are in letter_combinations.
• $n_1\neq n_2$, and $\ell_1\neq \ell_2$.
• $\ell_1$ appears earlier in letter_combinations than $\ell_2$.

Let us count the number of ways to specify such a list, using simple combinatorics.

• There are $N$ choices for $n_1$, since it can be anything in num_list.

• There are $N-1$ choices for $n_2$, since it can be anything in num_list, except for $n_1$.

• Choosing $\ell_1$ and $\ell_2$ requires a little more care. Naively, there are $L$ choices for $\ell_1$ (anything in letter_combinations), and there are $L-1$ choices for $\ell_2$ (anything in letter_combinations besides $\ell_1$). However, exactly half of these choices are invalid; for each $\ell_1\neq \ell_2$, only one of the pairs $(\ell_1,\ell_2)$ and $(\ell_2,\ell_1)$ is valid. Specifically, $(\ell_1,\ell_2)$ is valid if $\ell_1$ comes before $\ell_2$ in letter_combinations_, otherwise $(\ell_2,\ell_1)$ is the valid one.
  Since there are $L\times (L-1)$ ways to choose the pair $(\ell_1,\ell_2)$, and exactly half of these are valid, the number of valid pairs is $L\times (L-1)/2$.

Putting this altogether, the number of combinations is $$ N\times (N-1)\times L\times (L-1)/2. $$