Combinations and permutations

I have always struggled with these words.  They convey too similar a set of ideas for me to ever have bothered to properly distinguish them.  Mathematically prior is set theory.  In sets, the order doesn't matter until you start imposing an order. 

When it is set on set action, you're talking about combinations.  That is to say when you define a subset of some known cardinality out of some other set and want to know all the ways you could pick that new subset, then you're performing a set on set operation and estimating a combination.  That is to say you're estimating the number of different ways you could have extracted the subset from the super set.  When the order of picking is important, you are permuting, that is, making a list from a set. 

You're the  best basketballer in school.  It is lunchtime and you're captain.  You get to pick your team of 5 from your 20 buddies all eager to play basketball.  The combination calculation is going on.  In the end when you're in the team you're in the team.  Order doesn't matter.  Now it is the end of the year and you're calling out the 5 best players in order to give them a prize.  This is a permutation.   Notice that in both cases there was a form of sampling without replacement.  When you're doing sampling without replacement like this, then factorials are in operation (and this generalises to the Gamma function).

We're all familiar with sampling with replacement but in real world situations we most often come across sampling without replacement.  Consider how lottery balls are drawn.  Or school places are selected.  Or subjects of a scientific experiement are ideally picked.  Of course, numerically when the population size is so much larger than the sample size then the effect on probabilities of the choice to replace or not becomes negligible.

Is one operation more basic than the other.  One way to look at this is to realise that the basic rule of combinations with replacement is the multiplication rule (which when the sample space stays the same from choice to choice results in $a^b$ patterns).  The factorial operation caters for non-replacement, and the power operation caters for replacement.

Still, is one operation more basic than the other.  From a human's point of view, the act of chosing is played out in real time, imposing an actual permutation order even if the permutation order is semantically and logically meaningless. From the point of view of mathematics, combinations can be considered the step of effacing this built in permutation order which we want to see as irrelevant.  Combinations don't care as much.  They are smaller numbers than their peer permutation.  By $n!$ in fact.

Selecting end of year basketball winners can be seen as the act of chosing the team (a combination) then looking at this team and further imposing a specific permutation on that team.  That permutation buys you another $n!$ possibilities.  Of coure, this isn't what it feels like when you're picking a list from a set.  It feels like you're going straight from the sample space to the list in a single move.

But when you think of picking a list in this way , then $n!\binom{n}{k}$ makes a bit more sense.

Alternatively, the direct act of selecting (without replacement) $k$ from $n$ in order feels naturally like $\frac{n!}{(n-k)!}$