Thread: Counting methods ?

Hey guys,

I'm doing a question, and I have the answer, but I don't understand it.

Lets say a bank issues 4 digit PIN's to cardholders, how many unique PIN's can be made so that each digit is different, and must not be in ascending, or descending order ?

The selection is made from 0,1,2,.....,7,8,9.

Before I answered the part above, I answered another part, which made sense:
How many unique PIN's can be made if the digits must be different. Basically, you just use the permutation rule; 10!/6! = 5040.

However, the solution to the next part (different digits, not ascending or descending) uses the binomial coefficient "n choose r", and you get 210 as your answer. This is then multiplied by 2, and finally subtracted from 5,040 to yield an answer of 4620 unique PIN's.

I understand that the choose rule involves non ordered selections; you have a box full of numbers, and you select, and pay no heed to the order in which you select, but I don't understand how it is applied to this particular problem ?

Put another way, if I select three numbers from a group of 4, I can obtain 4 possible selections of three viz....1,2,3,4...possible selections of 3 are {1,2,3}, {2,3,4}, {1,2,4}, {1,3,4}. In this case I'm not worried about the order in which I selected them. However if I consider arranging them in particular orders, I can do so in 24 ways. If I want to eliminate 4 of them, I just subtract this from the number of ordered arrangements, but how do I know I'm subtracting {1,2,3}, {2,3,4}, {1,2,4}, {1,3,4} ???

First of all, 4620 is the correct answer.
There are distinct subsets of four digits.
Each of those subsets can be arranged into strings of four pins in ways.
But, of those 24 one is ascending and one is descending.
So

Taking your example, the simple fact of subtracting 4 combinations (that have ascending numbers) from the total will imply that the rest of the combinations are not in ascending order.

There are 24 combinations, 4 of which contain ascending numbers.
Removing 4 will leave the number of combinations that don't contain ascending numbers.

In your problem, 10C4 is the number of combinations with ascending numbers.
Another 10C4 is the number of combinations with descending numbers.
So, twice that, and subtracted from the total (ie 5040) will give those that contain numbers neither in ascending nor descending.

If you want to do it the long way, you can try this:

0 1 2 ? (7 possibilities)
0 1 3 ? (6 more possibilities, for a total of 6+7 possibilities)
0 1 4 ?
0 1 5 ?
.
0 1 8 ? (1 more possibility)
0 2 3 ? (6 more possibilities)
0 2 4 ? (5 more possibilities)
.
.
1 2 3 ? (6 more possibilities)
.
.
6 7 8 ? (1 possibility)

Total should be =





Which is quite long to count

Originally Posted by Plato

First of all, 4620 is the correct answer.
There are distinct subsets of four digits.
Each of those subsets can be arranged into strings of four pins in ways.
But, of those 24 one is ascending and one is descending.
So

Yeh, that makes sense. Thanks!

The solution I have was done a different way; 5,040 possible arrangements of 4 digits selected from 10, without replacement. Then, as you state, there are 210 distinct subsets, and each subset can be arranged in 24 ways; however, in my solution the 210 is multiplied by 2, and then subtracted from 5040, which equals 4,620. I couldn't make sense of that, but the way you've done it is a lot clearer.

Originally Posted by Unknown008

Taking your example, the simple fact of subtracting 4 combinations (that have ascending numbers) from the total will imply that the rest of the combinations are not in ascending order.

There are 24 combinations, 4 of which contain ascending numbers.
Removing 4 will leave the number of combinations that don't contain ascending numbers.

In your problem, 10C4 is the number of combinations with ascending numbers.
Another 10C4 is the number of combinations with descending numbers.
So, twice that, and subtracted from the total (ie 5040) will give those that contain numbers neither in ascending nor descending.

If you want to do it the long way, you can try this:

0 1 2 ? (7 possibilities)
0 1 3 ? (6 more possibilities, for a total of 6+7 possibilities)
0 1 4 ?
0 1 5 ?
.
0 1 8 ? (1 more possibility)
0 2 3 ? (6 more possibilities)
0 2 4 ? (5 more possibilities)
.
.
1 2 3 ? (6 more possibilities)
.
.
6 7 8 ? (1 possibility)

Total should be =





Which is quite long to count

I did something similar using 4 digits, and selected three numbers, just to try and appreciate the number of ways one can arrange the numbers. That made sense. What I didn't understand was the way the solution was presented: 210 distinct subsets x 2 = 420, and subtract 420 from the total number of possible ordered permutations (5,040). The result is 4,620, which is the correct answer; I was confused by this method. Anyway thanks for your help. :-)

Yes. I explained it in this line:

In your problem, 10C4 is the number of combinations with ascending numbers.
Another 10C4 is the number of combinations with descending numbers.

Originally Posted by Unknown008

Yes. I explained it in this line:

Ok. I thought that 10 C 4 is the number of possible non ordered selections you can make ? Doesn't non-ordered mean that the order in which you select them does not matter ? Why would you multiply 210 by 2 ?

I know this is probably simple, but multiplying 210 by 22 makes more sense....

10C4 is the number of selections where you have numbers in ascending order.
There will be the same amount of numbers in descending order, hence twice 210.

Is this clearer maybe?

Originally Posted by Unknown008

10C4 is the number of selections where you have numbers in ascending order.
There will be the same amount of numbers in descending order, hence twice 210.

Is this clearer maybe?

No, I thought that 10 C 4 was the number of non ordered selections you can make.

Let's say it was 4 C 3, and let's say the numbers you can choose from (say the numbers are in a box) are 1,2,3,4. There are 4 possible selections:

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

But the order in which you select them from the box does not matter, so whether a string of three digits ascends, or descends, is of no consequence. But if you want to consider arranging them, then there are 3! ways of doing it with each distinct subset; take {1,2,3} for instance; you can permutate these digits in 6 ways, and doing that with each subset will result in a total of 24 possible permutations. Now consider those strings of numbers that are in ascending order, and descending order; there are two of them. Take the subset {1,2,3}. The arrangements are:

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

Right ? There are two ways of arranging these three digits in ascending and descending order. If I remove these, I now have 4 ways I can arrange the digits. This applies to each of the four subsets. So in effect if you wanted to remove strings that were in descending and ascending order, you would be removing 8 strings from a possible 24, and be left with 16.

Am I thinking this through correctly ? Sorry about that long convoluted explanation; it's more for my benefit then yours!!!! :-)

Cheers.

Yes, that's how the answer to your problem was obtained.

I think I get your problem now... but it's quite difficult for me to explain.

Okay, take 1 2 3 4

If you take 4C3, you get the result as 4.

Meaning that there are four possible outcomes out of the 24 ordered outcomes.

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

The important part is that there are 4 of them. They could also be displayed as non ordered:

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

Still, there are 4 of them, such that no matter what you do, when you remove 4, you are removing the number of outcomes that is equal to the number of ordered outcomes.

It's hard to explain AND understand... is that okay or should I try to come up with another way to explain this?

Originally Posted by Unknown008

Yes, that's how the answer to your problem was obtained.

I think I get your problem now... but it's quite difficult for me to explain.

Okay, take 1 2 3 4

If you take 4C3, you get the result as 4.

Meaning that there are four possible outcomes out of the 24 ordered outcomes.

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

The important part is that there are 4 of them. They could also be displayed as non ordered:

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

Still, there are 4 of them, such that no matter what you do, when you remove 4, you are removing the number of outcomes that is equal to the number of ordered outcomes.

It's hard to explain AND understand... is that okay or should I try to come up with another way to explain this?

That makes a lot of sense. Getting back to the original problem, and my solution, I still don't understand why you multiply by 2. Let's try and put it into the context of 4 C 3. As stated there are 4 possible non ordered selections that can be made. But there are 24 possible ordered selections. Now, if we incorporate that part of my solution i.e. multiplying by 2, then we get 8, and subtract that from 24, and you have 16, which is the number of selections you can make, excluding those are are in ascending or descending order; so that amounts to 2 per subset........so that makes sense now.....in each subset there are 2 strings, one ascending, and another descending. There are 4 subset, so multiplying that by 2, and you have the 8 strings that are ascending and descending.

I think that makes sense now. :-)
Christ I'm slow :-)

cheers guys.

It may be helpful to change the setting.
Consider the English alphabet, twenty-six letters.
How many six letter strings of distinct letters are in ascending order?

Consider any six letter subset whatsoever: say
Take those letters and form “ ” in ascending order.
Thus any subset of six letters corresponds to a six letter string in ascending order.

So the answer , the number of six element subsets.