2
$\begingroup$

Lets say I have a set such as (1, 1, 1, 1) where each number can be from 1 to 100.

All possible combinations will be (1, 1, 1, 1), (1, 1, 1, 2), ... , (1, 1, 1, 100), ... (100, 100, 100, 100).

Order does matter, (1, 1, 2, 3) is different from (2, 3, 1, 1).

How do I go about finding the number of possible combinations where only 2 numbers are the same. I.E. (1, 1, 2, 3) or even (1, 1, 2, 2) There needs to always be 2 numbers that are the same. I doesn't matter if there are 2 groups of 2 numbers that are the same. So not (1, 2, 3, 4) or (1, 1, 1, 2) or (1, 1, 1, 1).

I could find the total possible combinations which is 100^4 then subtract combinations were all 4 are the same and subtract combinations where 3 are the same and subtract combinations were none are the same.

But lets say that I cannot do that and have to do it using another method. How would I do it? I thought it would be done by doing 100 x 99 x 98 x 6 but that gives me an answer of 5821200.

I believe the answer is 5890600, So I am off by a little and I am not sure what I am doing wrong.

Any help would be appreciated.

$\endgroup$
  • $\begingroup$ Oops... you guys were all right. It was 5890600 and not what I had before. $\endgroup$ – ashimashi Oct 31 '14 at 21:40
3
$\begingroup$

The answer is

$$6\cdot100\cdot99\cdot98+3\cdot100\cdot99=5{,}850{,}900$$

The first term counts the number of $4$-tuples with a single pair of identical entries; the second counts the number with two distinct pairs of identical entries. The $6$ corresponds to the number of different possible pairs (i.e., $6={4\choose2}$), while the $3$ is the number of entries that can be paired with the first entry.

$\endgroup$
  • $\begingroup$ Thank you, you explained it in a short and simple manner! $\endgroup$ – ashimashi Oct 31 '14 at 21:47
3
$\begingroup$

You then need to calculate the permutations of two different ordered strings:

  1. Permutations with a group of cardinality 2 and 2 groups of cardinality 1 over 4 positions, i.e. $\binom{4}{2,1,1}=\frac{4!}{2!1!1!}=12$

  2. Permutations with 2 groups of cardinality 2 over 4 positions, i.e. $\binom{4}{2,2}=\frac{4!}{2!2!}=6$

Now for each case you must add the variations of the groups that are permutating and after divide by the permutations of groups of the same cardinality because if not you are counting some strings twice.

The variations are counted over groups, so for the case 1 the variations will be $(100)_3=100*99*98$, and for the case 2 they will be $(100)_2=100*99$. And we must divide by $2!$ respectively because for each case you have two groups of the same cardinality.

Then we have

$$12*50*99*98+6*50*99=5850900$$

$\endgroup$
  • $\begingroup$ Thanks for the answer, another great way of looking at the problem. $\endgroup$ – ashimashi Oct 31 '14 at 21:49
2
$\begingroup$

Let $X$ be the set of all the tuples you're interested in.

Let $Y$ be the set of tuples $(a,b,c)$ where $a,b,c$ are distinct integers from $1$ to $100$. (That is, we don't allow any of them to be the same.)

It should be easy to compute $|Y|$, so we want to relate $|X|$ to $|Y|$ somehow. If you could find some function $f : X \to Y$ and prove that $|f^{-1}(y)| = k$ for all $y \in Y$, this would show that $|X| = k|Y|$. Can you think of such an $f$? (Finding a good $f$ should be fairly easy. Finding the right value of $k$ will take a little thought.)

(Edit to add: your sentence "I doesn't matter if there are 2 groups of 2 numbers that are the same. So not (1, 2, 3, 4) or (1, 1, 1, 2) or (1, 1, 1, 1)." seems to be self-contradictory. Is (1,1,1,1) allowed or not? My answer is based on (1,1,1,1) not being allowed.)

$\endgroup$
  • $\begingroup$ Thanks a lot for the response. It wasn't exactly what I was looking for, but it was nice to see it in a different way. Also to add, yes (1,1,1,1) is not allowed. $\endgroup$ – ashimashi Oct 31 '14 at 21:42
1
$\begingroup$

You can have two cases

CASE I only 2 numbers are same, rest 2 are different

$$\binom{100}{1}\binom{99}{2}*\frac{4!}{2!} =5821200$$

CASE II two numbers are same and rest two are also same $$\binom{100}{1}\binom{99}{1}*\frac{4!}{2!*2!*2!}=29700$$

So the total combinations are 5850900

$\endgroup$
  • $\begingroup$ Thanks for the answer. I didn't think of CASE 2 $\endgroup$ – ashimashi Oct 31 '14 at 21:48

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.