Permutations and combinations: decide whether order survives

To arrange n distinct objects, choose the first in n ways, the next in n minus one, and continue until one remains. This gives n factorial. An ordered selection of k distinct objects stops after k choices and has n factorial divided by n minus k factorial possibilities. The condition zero at most k at most n belongs to the formula. Selecting nothing has one outcome, the empty sequence, which explains the convention zero factorial equals one.

If objects repeat, the construction histories may no longer be distinct outcomes. Arranging the letters in LEVEL first treats the two Ls and two Es as separately labelled, then forgets those labels. Every visible arrangement has two factorial times two factorial labelled descriptions, so dividing gives thirty. Uniform multiplicity justifies the division. If different outputs have different numbers of descriptions, dividing by a single convenient constant cannot correct the count.

The binomial coefficient counts k-element subsets of an n-element labelled set. Choosing the subset is equivalent to choosing its complement, so choosing k and choosing n minus k have equal counts. This symmetry is visible in the factorial formula, but the complement bijection explains it directly. Labels matter: choosing two positions in a word is not the same as choosing two distinct letter values when letters repeat. Specify the underlying set before inserting numbers.

Pascal's identity classifies subsets according to a distinguished object. Those omitting it choose all k members from the remaining n objects. Those containing it choose their other k minus one members from those n objects. The two classes are disjoint and cover every k-element subset of an n plus one element set. This argument also supplies the recurrence for constructing a row of binomial coefficients without evaluating large factorials.

Expand a product of n copies of u plus v by choosing one term from each factor. A term with k choices of v and n minus k choices of u has the same monomial regardless of which positions supplied v, because scalar multiplication commutes. The number of position subsets is the binomial coefficient. For noncommuting matrices, different position choices need not give the same product, so this scalar formula cannot be transferred without additional assumptions.

At u and v both equal one, the expansion counts every subset and gives two to the nth power. At u equal one and v equal minus one, the alternating sum is zero for positive n. A combinatorial explanation pairs each subset with the subset obtained by toggling one fixed element; the pairing changes parity. Such interpretations let an algebraic identity reveal a reversible operation on objects instead of remaining an unexplained cancellation of symbols.