(I did forget to count something in the last step, and I formatted equations wrong, so I'll repeat)
A checkerboard has 5 columns and 3 rows. In how many ways can you mark 9 squares on the board so that each column has at least one check box?
If the board is 5x3, then there are 15 squares and 15! ways to mark them, n(n-1)(n-2)..., which is notated P(n,n)==n!. Now we've counted it all, and need to count what the problem asked "not to be counted", and remove those (by division).
We add a constraint: only 9 are to be chosen at a time, no more no less. This is P(n,r)==n(n-1)(n-2)... where the first r factors are counted (the remaining are replaced by 1's). We have P(15,9).
15*14*13*12*11*10*9*8*7
So far: we counted all. We reduced that by "taking nine at a time" (by dividing 6x5x4x3x2x1 out).
The P(n,r) formula counts "order". ie, {a,b} and {b,a} are counted as two choices not one. It is not asked which order the 9 markings are made in, so to remove duplicates we use the "combination" formula: C(n,r)==P(n,r)/r!
(15*14*13*12*11*10*9*8*7)/9!
So far: we counted all. We reduced it by "taken nine at a time". We removed duplicate counting in P(n,r) we weren't asked to count by dividing those out.
There is (one) more constraint. That each column has at least one check box. Let's count! With 9 checkers we can fill 3 columns, leaving 2 column open, (which is not allowed). If we disallow 1 choice we are assured one column is not empty. If we again disallow 1 more it could go in 3 places that are not allowed (count), so remove 3 choices. (There are other methods to count the number un-allowed arrangements to remove).
(15*14*13*12*11*10*9*8*7)/9!-1-3
* * * - -
* * * - -
* * * - -
We counted all. We reduced it by "taking nine at a time" by dividing. We removed the duplicates (of permutations v. combinations) by dividing. We subtracted off 4 wrong choices (sets) which, by inspection, "forced" the remaining choices to have at least one checker in each column.
Mathematica does not implement P(n,r) and C(n,r) but you can do so easily. Permutations[] in Mathematica is not for doing the kind of counting as seen above because it's library is so large and capable that sometimes small formula are omitted.
