3
$\begingroup$

I believe this to be a 4 part combinatorics problem I am a programmer not a mathematician. The final answer I am looking for will be the total number of combinations for all 4 steps listed below

Step 1) There are 7 groups of objects, each group has 7 different objects in them (49 total unique objects). You must choose 4 objects in each of the 7 groups for a total of 28 selections (28 objects) How many possible combinations of objects are there for all 7 groups in this step 1?

Based on this link:

https://math.stackexchange.com/a/383762/410036

This appears to be the formula for one group, the anser is 35 then to the 7th power because of 7 groups = 64,339,296,875 (i think?)

$$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$


Now I need to combine that with 3 more steps so the final number of combinations should be rather large.

Step 2) Now from the 4 items in each group that you chose in step 1 you must narrow down to only 1 in each group. (7 total objects selected)

Step 3) Now from the 7 remaining objects selected (in Step 2) you must choose your 4 favorite. (4 total objects selected)

Step 4) Final step, just to make it fun, you must order the final 4 objects in order of your favorite 1,2,3,4.

I think this will be a very large number, any useful information regarding this problem is greatly appreciated. Thank you.
Don

$\endgroup$
  • $\begingroup$ Wow! I did not expect answers so fast. I am reading them now. $\endgroup$ – Don Moore Jan 25 '17 at 22:48
  • $\begingroup$ I belive the possiblities vs paths question is ansered by my inclusion of : "Now from the N items in each group that you chose in previous step?" It is the "number of paths" if my understaing is corect. I like math. $\endgroup$ – Don Moore Jan 25 '17 at 22:53
2
$\begingroup$

Step 1 is correct. As stated by Ross Millikan, for step 2 you get $35^7*4^7$. For step 3, you must choose 4 out the 7 remaining items, so you get $C(7, 4) = 35$. Resulting in $35^7*4^7*35$. For step 4, start off with step 2 and do the same as in step 3, but use permutation instead of combination (as the order of the items is important). So $P(7, 4) = 840$, resulting in $35^7*4^7*35*840 = 30,991,570,176,000,000,000$. So indeed a huge number.

$\endgroup$
  • $\begingroup$ Wow, I think you are quite brilliant. It seems so simple the way you explain it. $\endgroup$ – Don Moore Jan 25 '17 at 22:56
  • 1
    $\begingroup$ Something that helps me to solve combinatorial exercise (apart from making a lot of exercises and discussing them), is to think in terms of two questions: "Is the order of items important or not?" and "Can you use one item several times (repeat items)?". Just a little method I think is a good approach to these exercises :-) $\endgroup$ – mitchbus Jan 25 '17 at 23:18
1
$\begingroup$

You are correct for step 1. Maybe you should report the result as $35^7$ instead of multiplying it out. That is a matter of taste. Then is step 2 you choose ${4 \choose 1}$ seven times which gives another factor $4^7$ and so on. Yes, it will be a very large number.

$\endgroup$
  • 1
    $\begingroup$ That is right. That is the number of ways to get to where you are at that point. It remembers the items you chose in step 1 and threw away in step 2. $\endgroup$ – Ross Millikan Jan 25 '17 at 21:58
  • 1
    $\begingroup$ I think the OP tries to count all the possible paths to select the items, rather than the possible items $\endgroup$ – mitchbus Jan 25 '17 at 21:58
  • 1
    $\begingroup$ selecting first 4 persons, and then selecting one from these 4 gives duplicates. i think, this is equivalent to selection one from from 7 and my answer was written in this belief. $\endgroup$ – Kiran Jan 25 '17 at 21:58
  • 1
    $\begingroup$ @mitchbus, oh got the point. my entire answer was based on the assumption that we are counting the number of possibilities and not the number of paths. i have now added this in my answer. $\endgroup$ – Kiran Jan 25 '17 at 21:59
  • 1
    $\begingroup$ @Kiran: it gives duplicates in the list of persons selected. It does not give duplicates in the route taken to select those people. I think the question clearly wants the latter. $\endgroup$ – Ross Millikan Jan 25 '17 at 22:05
1
$\begingroup$

the below answer assumes that we are counting the number of possibilities and not the number of paths in which the process of selection happens.

Step 1

Select $4$ objects from each of the $7$ groups So,

required ways $\dbinom{7}{4}^7$

Step 2

Similar approach

required ways $=\dbinom{7}{1}^7$

Step 3

Select 4 groups first, then select one person from each group.

required ways $=\dbinom{7}{4}\dbinom{4}{1}^4$

Step 4

due to ordering,

required ways $=\dbinom{7}{4}\dbinom{4}{1}^4(4!)$

$\endgroup$
  • 2
    $\begingroup$ I don't think you have to divide with 4!. That over counting is already taken into account with the combination definition: $C(7, 4) = \frac{7!}{(4!*(7-3)!)}$ $\endgroup$ – mitchbus Jan 25 '17 at 21:40
  • 1
    $\begingroup$ @mitchbus, you are right, no over-counting occurs and hence no need to divide. $\endgroup$ – Kiran Jan 25 '17 at 21:46
  • 1
    $\begingroup$ @Kirian, I sure do appreciate you explaining each step. I very much thank you. $\endgroup$ – Don Moore Jan 25 '17 at 22:57
  • 1
    $\begingroup$ @DonMoore, welcome. $\endgroup$ – Kiran Jan 25 '17 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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