سوال ۱۱۲ کنکور ارشد علوم کامپیوتر ۱۴۰۴

We distribute $n=5$ distinct objects into $k=3$ distinct boxes with no empty box, comparing the unordered count $s$ with the ordered-within-box count $t$.

Computing $s$ (order inside a box is irrelevant)

A placement where each box holds an unordered set, with no box empty, is exactly a surjection from the $5$ objects onto the $3$ distinct boxes. By inclusion–exclusion: $s = \sum_{j=0}^{3} (-1)^{j}\binom{3}{j}(3-j)^{5} = 3^{5} - 3\cdot 2^{5} + 3\cdot 1^{5} = 243 - 96 + 3 = 150.$ Equivalently $s = 3!\,S(5,3) = 6\cdot 25 = 150$, where $S(5,3)=25$ is a Stirling number of the second kind.

Computing $t$ (order inside each box matters)

Now each box holds an ordered sequence. The number of ways to split $n$ distinct objects into $k$ non-empty ordered lists in distinct boxes is given by $k!$ times the Lah number $L(n,k)=\binom{n-1}{k-1}\dfrac{n!}{k!}$, which simplifies to $t = k!\,L(n,k) = n!\binom{n-1}{k-1}.$ A clean way to see this: first arrange all $5$ objects in a row ($5!$ ways), then cut the row into $3$ non-empty contiguous blocks by choosing $2$ of the $4$ internal gaps ($\binom{4}{2}$ ways), and assign block $i$ to box $i$ (boxes already distinct, so the left-to-right block order fixes the assignment). Hence $t = 5!\binom{4}{2} = 120 \cdot 6 = 720.$

The ratio

$\frac{t}{s} = \frac{720}{150} = 4.8.$ Since $3 < 4.8 \le 5$, we get $\dfrac{t}{s}\in(3,5]$, which is option 3.

A quick sanity check on the ratio: per unordered placement, a box of size $m_i$ can be internally ordered in $m_i!$ ways, so $t = s\cdot \mathbb{E}[\prod m_i!]$ averaged over the surjective splits — the average product of $m_i!$ over the $(m_1,m_2,m_3)$ block-size patterns equals $4.8$.

Exam trick: For distinct objects into distinct boxes, "order inside the box matters" turns each block of size $m$ into $m!$ arrangements; the no-empty ordered count is the slick $n!\binom{n-1}{k-1}$ (line up, then cut into $k$ non-empty pieces), while the unordered count is the surjection count $k!\,S(n,k)$.