سوال ۱۱۷ کنکور ارشد علوم کامپیوتر ۱۳۹۷

A star $K_{1,4}$ consists of one center vertex joined to $4$ distinct leaf vertices. Inside the complete graph $K_{100}$ every pair of vertices is adjacent, so any choice of a center plus four leaves automatically supplies the required edges.

Count by building the star:

• Pick the center: $100$ choices.
• Pick the $4$ leaves from the remaining $99$ vertices: $\binom{99}{4}$ choices (unordered — the leaves are interchangeable).

No overcounting occurs, because in a star the center is the unique vertex of degree $4$. Hence

$\#\,K_{1,4} = 100\binom{99}{4} = 100\cdot\frac{99!}{4!\,95!} = \frac{100!}{4!\,95!}.$

Match to the options. Write $\binom{100}{4}=\dfrac{100!}{4!\,96!}$. Since $96! = 96\cdot 95!$,

$96\binom{100}{4} = 96\cdot\frac{100!}{4!\,96!} = \frac{96\cdot 100!}{4!\,(96\cdot 95!)} = \frac{100!}{4!\,95!}.$

This equals $100\binom{99}{4}$, so the answer is option (3) $96\binom{100}{4}$.

Pitfall: Do not stop at $\binom{100}{5}$ (option 1). Choosing $5$ vertices fixes only the vertex set; a star also needs you to designate which of the $5$ is the center, giving $5$ stars per set: $5\binom{100}{5}=\frac{100!}{4!\,95!}=96\binom{100}{4}$. So the bare $\binom{100}{5}$ undercounts by a factor of $5$.