🇳🇱
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:
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:
- If you want to arrange `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.
- If you want to choose `k` of `n` objects, you can do this by ordering the `n` objects and taking the first `k`. So initially `nCk = n!`
- However, you don't care about ordering of the chosen objects. If you choose two of `{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!`
- Equally, you don't care about ordering of the non-chosen objects. In the above example, `{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)!)`
@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.
@freemo oh I see. That's less different than I thought initially - actually pretty close to how I do it fast, but when I slow down to type it out for someone else, I break out the `(n-k)!` term as a separate step.
@khird yea to me the n-k term is just a sort of expansion and not really a relevant part of the steps.. in fact I find the formula itself to be more verbose than it really needs to be and my own approach is just one logical step to expanding to the formula, and a step that isnt really even needed IMO... In short my formula just skips the first math step you need when using the real formula, but once you understand my formula the original is fairly trivial to recall IMO
@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
@freemo I'm not sure I understand how you reason it from that description. Do you mean that you first arrive at the `k!` and `(n-k)!` factors in the denominator and only recognise the `n!` numerator at the end?