Follow

In case anyone is curious as to how to do some elementary statistics, in this case combinatorics, here is a quick little write up I did to explain the “n choose k” paradigm.

Here is the is the question (from my cousin):

Math people

Can you help me ??

Let’s say

Hypothetically

You have 7 numbers

Between 1-99

The first 6 cant repeat but the 7th can

How many outcomes are possible?

This isnt a riddle or anything I just dont know how to do the math on something I’m trying to figure out

Here is my answer:

@khird excellent contribution thank you. I agree this is very helpful to anyone reading.

`k!`

and `(n-k)!`

factors in the denominator and only recognise the `n!`

numerator at the end?

@khird @khird ahh in that case ill explain. I find my method much simpler than yours but i think we tend to find our own personal methods easiest so that may not mean much… but maybe you will do and int he future it will be easier to recall if so…

So lets take a simplified version of the above “how many combinations of 6 numbers can I pick from 99”…

First I ask myself “How many permutations of 6 can I pick from 99 numbers”. This is easy to remember since the first number there are 99 ways, second 98 etc.. so it is 99 * 98 * 97 * 96 * 95 * 94.. I can simplify this as 99!/93!

Next I reason that a combination doesnt care about order, so if i have any particular set of 6 numbers (being a set they are naturally unique) how many permuations can i make out of those 6 numbers… for that we have simple 6!.

Finally I know that out of all the permutations from my earlier selection of 99!/93! numbers any one unique set of 6 numbers has 6! possible variations it can exist as within those permutations. so I like wise know that I can divide 99!/93! by 6! and arrive at the number of combinations…

So (99!/93!)/6! = 99!/(6! * 93!)

Q.E.D. Solution derived.

`(n-k)!`

term as a separate step.

@freemo The stupid notation one has to spend more time on explaining that the actual problem. Knuth had a rising and falling factorial notation, cause you know those brainlet programmers actually care about performing computation.

99 * 98 * 97 * 96 * 95 * 94, we call 99!6 (not the actual notation), meaning count down from 99 6 times and multiply those numbers (directly ties into the combinatorial rationale). The 99 choose 6 becomes (99!6)/(6!6).

There original problem becomes:

(99!6)/(6!6) * (99!1)(1!1)

x!1 is clearly just x, so we arrive already to second to last step of your original derivations

(99!6)/(6!6) * 99

Kâ€®lyâ€¬e@khird@qoto.org@freemo

Might benefit from a discussion of why

`nCk = n!/(k!(n-k)!)`

. I don’t use combinatorics often enough to have it memorised, so I re-derive the`nCk`

and`nPk`

formulae every time I need them. Here’s my reasoning:`n`

objects, you can choose any of`n`

for the first, any of the`n-1`

remaining for the second, … down to one for the`n`

th. So n objects can be arranged in`n! = n(n-1)...1`

ways.`k`

of`n`

objects, you can do this by ordering the`n`

objects and taking the first`k`

. So initially`nCk = n!`

`{1, 2, 3, 4}`

, the orderings`{1, 2, 3, 4}`

and`{2, 1, 3, 4}`

should not be treated as distinct. Since there are`k!`

ways to order the`k`

objects you chose, you need to divide that out. Now we have`nCk = n!/k!`

`{1, 2, 3, 4}`

and`{1, 2, 4, 3}`

should not be treated as distinct. There are`n-k`

of these objects, so`(n-k)!`

ways to order them, which again should be divided out. Finally, we arrive at`nCk = n!/(k!(n-k)!)`