The combination formula

Step 1 (group arrangements by their underlying subset): every arrangement of $k$ objects out of $n$ first selects some $k$-element subset and then orders it. Group the $A_n^k$ arrangements into buckets, one bucket per possible $k$-element subset, so that two arrangements land in the same bucket exactly when they use the same set of objects.

Step 2 (size of each bucket): fixing one $k$-element subset, the arrangements built from it correspond exactly to the orderings of that subset, and there are $k!$ such orderings (a permutation of $k$ objects). So every bucket has exactly $k!$ arrangements.

Step 3 (addition rule across buckets): the buckets are disjoint (an arrangement belongs to exactly one bucket) and there are $C_n^k$ buckets by definition, each of size $k!$. The addition rule ($k!$ added to itself $C_n^k$ times) gives $A_n^k = C_n^k \cdot k!$.

Step 4 (solve for the combination count): dividing both sides by $k!$ and substituting $A_n^k = \frac{n!}{(n-k)!}$ gives $C_n^k = \dfrac{A_n^k}{k!}$, that is $C_n^k = \frac{n!}{k!(n-k)!}$.