Number of ways to distribute $k$ identical objects into $n$ boxes, where each box contains at most one object

178 Views Asked by At

Number of ways to distribute $k$ identical objects into $n$ boxes, where each box contains at most one object

Unfortunately I couldn't find anything here in the forum. The question may already have been answered. If so, I apologize in advance and would be grateful if someone could post the link here. The problem is the following:

Given $k$ identical objects and $n$ boxes where $k \leq n$. How many ways are there to divide these $k$ objects into $n$ boxes such that each box contains at most one object? This can also be formulated as follows: How many solutions does the following problem have?

$$ x_1 + x_2 + \ldots + x_n = k \\ x_i \in \{0,1\} \quad \forall~i = 1, \ldots, n, $$ where $x_i$ denotes the $i$-th box.