Combinations problem

Tangram · 2014-07-24 20:27:37

I would like to find out the number of possible ways of getting 1,2,3,4 distinct numbers in a sequence of 4 numbers chosen from 1-4. There are 4x4x4x4 = 256 possible permutations. First case: there are 4 ways of getting all 4 numbers the same:

1,1,1,1
2,2,2,2
3,3,3,3
4,4,4,4

For the second case, namely that there are only 2 numbers out of the set in the sequence (e.g, 1,2,2,1 or 3,4,3,4. I reasoned as follows: There are 4C2 = 6 ways of getting two numbers from a set of 4, and for each of these ways there are 2x2x2x2 = 16 ways of permuting the two numbers, but this includes the two cases where all the numbers are one or the other, so these have to be subtracted, which gives 6 x (16 - 2) = 84 possible ways. I'm pretty sure this is correct.

The case of all the numbers being different is quite easy to find: There are 4x3x2x1 = 24 ways.

Now since there is only one possibility left - that of 3 distinct numbers in the sequence of 4, there must be 256 - 84 - 24 -4 = 144 of these, assuming the above is correct.

However, I'm getting in a muddle trying the calculate the case of 3 distinct numbers from first principles. This is as far as I've got but it's not correct: There are 4P3 = 24 ways of choosing 3 numbers from 4, where order counts, and for each of these 24 ways there are 3 ways of picking another number to make up the set to four (because the 4th number must be one from the existing set of 3), which gives 24x3 = 72, but this is only half of the number obtained above.

Where am I going wrong or what have I missed out?

Many thanks in advance for any help!

bobbym · 2014-07-25 01:52:07

Hi Tangram;

I would do it like this.

You have 4 cases, (1,1),(2,2),(3,3) and (4,4) for the duplicate.

Case (1,1):

Put them like this, where the _ represent the places we can put the pair and n1 and n2 are the other 2 numbers.

_ n1 _ n2 _

If we keep the (1,1) together there are 3 different _ that we can put them in..

If the 1's are separate there are 3 ways to arrange them in the _ . Count them!

So there is 6 total ways to distribute the (1,1) around n1 and n2.

Now, n1 and n2 come from the set of {2,3,4} and there are 3 x 2 = 6 permutations. There are 6 total ways to distribute the (1,1) around n1 and n2 and each comes with 3 x 2 permutations of n1 and n2.

So there are

ways to arrange (1,1) with 2 more different numbers.

Continuing like this for case (2,2), (3,3) and (4,4) and we get.

4 x 36 = 144.

Tangram · 2014-07-25 04:06:14

Hi bobbym,

Thanks! It always seems simple when someone else explains it, although that was a bit more involved than I thought.
By the way, that's quite a post count you have there!

Thanks again.

bobbym · 2014-07-25 04:12:48

Hi;

That is why you use the complement idea whenever you can. It was much easier to do the subtraction, very often that will be true.

By the way, that's quite a post count you have there!

I do talk alot.

anonimnystefy · 2014-07-25 04:16:49

You also get quoted a lot.

Tangram · 2014-07-26 07:37:02

I found another way of solving this which seems a little simpler. The sequence can be thought of as two parts: the part with 2 different numbers and the remaining part with 2 numbers the same - x,y,(z,z). For the first part, there are 4C2 = 6 ways of choosing the two numbers from 4, and 2C1 = 2 ways of picking the last number from the remaining two, giving 6 x 2 = 12 combinations. There are 4 slots _ _ _ _, and for each combination, there are 4 ways to place the first number, and 3 ways to place the second, which automatically leaves two positions for the two z's, so there are 12 permutations for each combination, giving the required 144 ways.

bobbym · 2014-07-26 09:30:38

Hi;

There are always many ways to solve every problem that is solvable.

Tangram · 2014-07-26 19:39:54

And that's a good thing because it provides a check on whether your solution is correct. ;-)

bobbym · 2014-07-26 19:43:12

Another way is to learn how to program, then you can simply count them. This helps when you can not find a method and also to check an answer.

Tangram · 2014-07-26 20:16:36

You beat me to it. I can program in BASIC, and wrote this which also finds the numbers for longer sequences, assuming only the numbers 1-4 are used:

OPTION BASE 1
DECLARE counts[4]
c = 0
OPEN "permutations.txt" FOR READING AS perms

WHILE NOT(ENDFILE(perms)) DO
READLN line$ FROM perms
FOR i = 1 TO 4
IF COUNT(line$, ASC(STR$(i))) THEN
INCR c
END IF
NEXT i
INCR counts[c]
c = 0
WEND

CLOSE FILE perms

FOR n = 1 TO 4
PRINT counts[n]
NEXT i

REM 4 x 1
REM 84 x 2
REM 144 x 3
REM 24 x 4

The permutations file was generated using the mathisfun permutations/combinations generator, which is a handy tool.

Last edited by Tangram (2014-07-26 20:17:02)

bobbym · 2014-07-26 20:25:31

Very good and clever use of it too.

Math Is Fun Forum

#1 2014-07-24 20:27:37

Combinations problem

#2 2014-07-25 01:52:07

Re: Combinations problem

#3 2014-07-25 04:06:14

Re: Combinations problem

#4 2014-07-25 04:12:48

Re: Combinations problem

#5 2014-07-25 04:16:49

Re: Combinations problem

#6 2014-07-26 07:37:02

Re: Combinations problem

#7 2014-07-26 09:30:38

Re: Combinations problem

#8 2014-07-26 19:39:54

Re: Combinations problem

#9 2014-07-26 19:43:12

Re: Combinations problem

#10 2014-07-26 20:16:36

Re: Combinations problem

#11 2014-07-26 20:25:31

Re: Combinations problem

Board footer