How many different ways can i select three elements from a set of elements where there are groups

Question

Suppose I have to select three distinct letters, one from each of these groups

Group 1 : a or e

Group 2 : b or f

Group 3 : c

Group 4 : d

The three distinct letters cannot have both 'a' and 'e' or 'b' and 'f'. In how many different ways can I select three distinct letters in the above fashion? How do I approach this problem?

EDIT: I am trying to find the number of possible triangles when the equation of $n$ lines are given. From the equation of the lines, I have found the slope of each line. Now I need to form sets of threes from these slope values such that no two slopes are the same. Basically, as an example ...

Group 1 : m1 || m2 || m3 || m4

Group 2 : m5 || m6

Group 3 : m7 || m8 || m9

Group 4 : m10

Group 5 : m11 || m12 || m13 || m14

Group 6 : m15 || m16

The groups given above is just an example. I would like to know how should I try to approach this problem.

You mean three distinct letters, one from each of the groups? — Colm Bhandal, Dec 03 '15 at 18:54
OK. Hint: notice that you can only exclude one group. So there are $4$ cases to consider... — Colm Bhandal, Dec 03 '15 at 18:57
Sorry, I edited the question because it was not clear. I want to know how to find the total number of ways I can select three letters in the above fashion. — Abhilash Panigrahi, Dec 03 '15 at 19:00

Brian Tung · Answer 1 · 2015-12-03T19:08:33.327

0

This problem is small enough that one can enumerate all the possibilities by hand: If one excludes a Group $1$ or a Group $2$ letter, there are two different possibilities (in each case); if one excludes a Group $3$ or a Group $4$ letter, there are four possibilities (in each case).

Therefore, there are $2+2+4+4 = 12$ different possibilities if we do not consider the order of the letters. If we do consider order (i.e., "acd" is distinct from "dca"), then there are $12(3!) = 72$ different possibilities.

edited Dec 03 '15 at 19:08

answered Dec 03 '15 at 19:04

Brian Tung

34,160

1

Unordered answer should be $12$ ways. – paw88789 Dec 03 '15 at 19:05
Duh. That's what I get for rushing through that. – Brian Tung Dec 03 '15 at 19:08
@paw88789: Thanks for the quick catch. – Brian Tung Dec 03 '15 at 19:08
You're welcome. It happens to me all the time :-) – paw88789 Dec 03 '15 at 19:09
Unfortunately, I am looking at a very big problem and this is just a dialed down version of the problem and hence cannot solve by hand. Is there another way to get this done faster? – Abhilash Panigrahi Dec 03 '15 at 19:11
Maybe you had better describe the big problem. The exact approach may depend on the nature of it. – Brian Tung Dec 03 '15 at 21:10
@BrianTung: I've edited the question. Kindly have a look at it. – Abhilash Panigrahi Dec 04 '15 at 02:49

score 0 · Accepted Answer · answered Dec 06 '15 at 06:06

Okay I figured it out after spending a few hours.

Let there be n slopes belonging to m groups.

To form groups of three first we find nCr(n, 3). We see there are many repetitions of elements belonging to same group. Now to remove repetitions, we calculate

\begin{equation*} toRemove = \sum_{i=1}^m nCr( C_i,2)*(n-2) - 2*nCr(C_i,3) \end{equation*}

Where i ranges from 0 to m groups and C_i represents the count of each group. (As in the example, the count of Group 1,2 and 3 are 4, 2 and 3 respectively.

Basically in the above equation we are trying to find all possibilities of a combination being formed using at least two elements from the same group. We find that when calculating this, we are indirectly calculating those elements that have three elements from the same group 2 times more than required. Hence we subtract this.

The final result is then calculated using
\begin{equation*} numberOfTriangles = nCr(n,3) - toRemove \end{equation*}

score 0 · Answer 3 · answered Jan 14 '17 at 01:54

I think in general you could approach the problem with a generating function. So for your second example, you want to choose three items where you pick only one from each of six groups where the groups have 4, 2, 3, 1, 4, and 2 members. I think a generating function like this

$(4x+1)(2x+1)(3x+1)(x+1)(4x+1)(2x+1)$

would work. You would multiply it out and then look at the coefficient of $x^3$. According to an online calculator, in this case that would be $192x^6+544x^5+604x^4+340x^3+103x^2+16x+1$, so look at the coefficient of $x^3$, and the answer is $340$.

I'm not completely confident it works, but my reasoning is you want only three of the $(ax+1)$ factors to contribute to your answer, so you look at the $x^3$ coefficient, and $a$ represents the number of ways that factor can contribute to the group of three.

If we carry this reasoning further, it would generalize quite well. If you wanted one group with $a$ members and you wanted to contribute a maximum of 2 from it (you could still pick 0 or 1 from it), then you could represent that by the factor ${a \choose 2}x^2+ax +1$, because there would be $a \choose 2$ ways for that group to contribute 2 things.

Plus if you want to choose more things from any given setup, you would just look at the coefficient of a higher degree. For one last example, lets say you have five groups, with 6, 3, 2, 5, and 4 items in each. You want to choose at most 4 from the first group, at most 1 from the second and third, at most 3 from the fourth but not exactly 2 things, and either 4 things or no things from the last. You want to pick 5 things from these groups using these rules. I believe you could just look at the $x^5$ coefficient in the expanded form of the following polynomial:

$\big( {6 \choose 4}x^4 + {6 \choose 3}x^3 + {6 \choose 2}x^2 + 6x +1\big) \big(3x+1 \big) \big(2x+1 \big) \big( {5\choose4}x^4 + {5\choose3}x^3 + 5x +1 \big) \big( {4 \choose 4}x^4 +1 \big)$

If that's wrong, someone tell me, but it makes a lot of sense to me right now.

How many different ways can i select three elements from a set of elements where there are groups

3 Answers3