CODEWITHSUNDEEP
mathcombinationscombinatorics
Spaniel
Spaniel

Reputation: 367

Formula for number of unorder pairs resulting from unique elements in k groups, excluding pairs of elements from same group k

I do not know how to solve the following problem, because combinatorics is not a strength of mine: I have a number of groups k, each of which has at least one element. All elements are different from one another. I want to know the total number of unordered pairs (i.e. of size 2) of all elements from all groups. BUT I do not want to include in that number those pairs which result from combining elements which belong to the same group k. I am looking for the correct terminology to describe and the right formula to solve these kinds of problems. Two examples below illustrate the problem and desired outcome. Your help is appeciated!

For example, group 1 consists of element a and b, group 2 of element c, group 3 of element d. The desired unordered pairs are: (a,c), (a,d), (b,c), (b,d), (c,d). Ergo, there are 5 pairs. The pair that is excluded is the pair (a,b), because both elements belong to the same group.

Another example: group 1 includes a,b; group 2 includes c,d. The desired pairs are: (a,c), (a,d), (b,c), (b,d). The total number of pairs is 4. The pairs (a,b) and (c,d) are excluded because the respective elements belong to the same group.

Thank you!

Upvotes: 0

Views: 420

Answers (1)

dmuir
dmuir

Reputation: 4431

You have groups G(1) .. G(K) where G(k) has N(k) elements So you have

M = N(1) + .. + N(K)

elements in total, and can form

(M*(M-1))/2

2 element subsets. But this includes the ones you don't want, that have elements from the same group. There are

(N(k)*(N(k)-1))/2

such subsets from group k. So the number of subsets you want is

(M*(M-1))/2 - Sum{ k | (N(k)*(N(k)-1))/2}

Upvotes: 0

Related Questions