Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

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

Tangram
Guest

Combinations problem

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!

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations problem

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.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Tangram
Member
Registered: 2014-07-25
Posts: 12

Re: Combinations problem

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.

What gets us into trouble isn't what we don't know; it's what we know for sure that just ain't so! - Mark Twain

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations problem

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.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Combinations problem

You also get quoted a lot.

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

Tangram
Member
Registered: 2014-07-25
Posts: 12

Re: Combinations problem

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.

What gets us into trouble isn't what we don't know; it's what we know for sure that just ain't so! - Mark Twain

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations problem

Hi;

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

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Tangram
Member
Registered: 2014-07-25
Posts: 12

Re: Combinations problem

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

What gets us into trouble isn't what we don't know; it's what we know for sure that just ain't so! - Mark Twain

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations problem

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.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Tangram
Member
Registered: 2014-07-25
Posts: 12

Re: Combinations problem

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
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)

What gets us into trouble isn't what we don't know; it's what we know for sure that just ain't so! - Mark Twain

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations problem

Very good and clever use of it too.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline