I am struggling to solve the problem on Combinatorics:
There are $k$ identical bookshelves in which each shelf cannot contain $m$ or more books. In how many ways can $n$ distinct books be arranged on these $k$ bookshelves?
If there is no condition on the capacity of each shelf, the number of ways to arrange books equals $\sum_{i \in [k]} L(n, i)$, where $L(n, i)$ denotes the Lah number. However, because of that constraint, I have trouble in solving the problem.
I tried several ways to solve this problem by separating the cases via (1) the number of shelves which contains the full-number of books, or (2) the number of non-empty shelves. For the second trial, I observed that, if $j$ denotes the number of non-empty shelves, then the number of ways to arrange the books is zero if $j < \lfloor n/m \rfloor$.
However, these methods does not proceed quite well, since it looks like these methods result in the recurrence relation rather than the exact form of the number.
For the related concepts, I have studied Catalan number, (both signed and unsigned) first and second Stirling number, Bell and Lah number, and the integer partition.
Any insight or comment are welcomed.
If the books are undistinguishable while the shelves are distinguishable, then your problem is equivalent to find the number of ways of composing the sum $s$ (total of books, your $n$), with $m$ non-negative integers (the number of shelves, your $k$) , ranging from $0$ to $r$ (the max capacity of each shelf, your $m-1$).
That is, you are looking for the number $N_{\,b} (s,r,m)$ $$N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{gathered} \right.$$
which is given by $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{k} \binom { s + m - 1 - k\left( {r + 1} \right) } { s - k\left( {r + 1} \right)}\ } $$ as thoroughly explained in this related post and in others related to this subject. This is the number of weak compositions of $s$ into $m$ parts each not greater than $r$.
If the shelves were undistinct, you pass to the number of partitions limited in size, with due allowance for the parts to be also null.
In fact when the shelves are undistinct, we can first arrange them according to the number of books contained, in (e.g.) a non-decreasing order.
So, with the symbols as above, the contents ($c_k$)correspond to the partitions of $s$ into max $m$ parts of size max $r$.
Now consider the books to be distinct, i.e. labeled $1, \ldots, s$.
If the order of the books within each shelf is accounted for, then we are considering the sets of max $m$ non-empty lists, each with max $r$ elements, with the lists being composed of and containing all the elements of $\{1,2, \cdots, s\}$ (the lists "partition" the set $\{1,2, \cdots, s\}$).
Example of 11 books in 4 shelves.
Once the contents of the shelves have been fixed, as a partition of $s$ (assuming the partitions are equi-probable), you can pick in $0!$ ways the books to fill the empty shelves, in $$ s\left( {s - 1} \right)\; \cdots \left( {s - c_1 +1} \right) = s^{\underline {\,c_1 } } $$ ways for filling the first non empty shelf, in $$ \left( {s - c_1 } \right)\left( {s - c_1 - 1} \right) \cdots \left( {s - c_1 - c_2 + 1} \right) = \left( {s - c_1 } \right)^{\underline {\,c_2 } } $$ ways to fill the second, and so forth. Thus in a total of $$ s^{\underline {\,c_1 } } \left( {s - c_1 } \right)^{\underline {\,c_2 } } \cdots \left( {s - \left( {c_1 + c_2 + \cdots + c_{m - 1} } \right)} \right)^{\underline {\,c_m } } = s^{\underline {\,c_1 + c_2 + \cdots + c_m \,} } = s! $$ which is the same as if you first permute the books and then upload them into the shelves sequentially. However, in this way we are overcounting the shelves having the same capacity, like column 2 nd 3 in the example above, and we shall correct for that. Being in fact a set of lists, the lists of same length are sub-ordered according , e.g., the lowest element that they contain.
Taking the case in which there are no empty shelves, for each partition $\{c_1, c_2, \cdots , c_m \}$
$$ \underbrace {c_{\,1} }_{t_{\,1} } < \,\underbrace {c_{\,2} = c_{\,3} = \cdots = c_{\,q} }_{t_{\,2} }\, < \underbrace {c_{\,q + 1} }_{t_{\,q + 1} } < \cdots < \underbrace {c_{\,m - u} = \cdots = c_{\,m} }_{t_{\,m - u} } $$
we shall individuate the number of repetitions $t_k \; | \, 1 \le k \le m$ of each capacity, as indicated in the scheme, putting at $0$ the missing $t_k$.
We end up with $$ \left\lfloor \begin{array}{c} s \\ m \\ \end{array} \right\rfloor _{\, \le \,r} = \sum\limits_{P(s,r,m)} {\frac{{s!}}{{t_1 !t_2 ! \cdots t_m !}}} = \sum\limits_{\left\{ {\begin{array}{*{20}c} {0 \le k_j } \\ {k_1 + k_2 + \cdots + k_r = m} \\ {1k_1 + 2k_2 + \cdots + rk_r = s} \\ \end{array}} \right.} {\frac{{s!}}{{k_1 !k_2 ! \cdots k_r !}}} $$ where the last identity is evident from the capsized histogram in the sketch above.
These numbers are known as restricted Lah Numbers, re. to this paper.
There it is shown that the e.g.f. is $$ \sum\limits_{0\, \le \,s} {\left\lfloor \begin{array}{c} s \\ m \\ \end{array} \right\rfloor _{\, \le \,r} \frac{{x^{\,s} }}{{s!}}} = \frac{1}{{m!}}\left( {\frac{{x - x^{\,r + 1} }}{{1 - x}}} \right)^{\,m} $$
Allowing for the shelves to be empty, means that we will have less than $m$ non-empty ones, thus their number will be the sum of the above.
Finally, if the order of the books within each shelf is not considered, we have a set of subsets partitioning $\{1,2, \cdots, s\}$, that when non-empty amount to the Restricted Stirling Number of 2nd kind.
This in fact can be written , among other forms, as $$ \left\{ \begin{array}{c} s \\ m \\ \end{array} \right\}_{\,r} = \sum\limits_{\left\{ {\begin{array}{*{20}c} {1\, \le \,c_{\,1} \le c_{\,2} \le \cdots \le c_{\,m} \, \le \,r} \\ {c_{\,1} + c_{\,2} + \, \cdots + c_{\,m} = s} \\ \end{array}} \right.} {\frac{1}{{t_{\,1} !t_{\,2} !\, \cdots \,t_{\,m} !}} \left( \begin{array}{c} s \\ c_{\,1} ,\,c_{\,2} ,\, \cdots ,c_{\,m} \\ \end{array} \right)} $$ corresponding to the formulation given by @trueblueanil.
Note that, removing the restriction (i.e. making $r$ to be at least $s-m+1$), we get the normal Stirling N. 2nd kind $$ \begin{array}{l} \left\{ \begin{array}{c} s \\ m \\ \end{array} \right\}_{\,s - m + 1} = \left\{ \begin{array}{c} s \\ m \\ \end{array} \right\}_{\,s} = \left\{ \begin{array}{c} s \\ m \\ \end{array} \right\}_{\,\infty } = \\ = \sum\limits_{\left\{ {\begin{array}{*{20}c} {1\, \le \,c_{\,1} \le c_{\,2} \le \cdots \le c_{\,m} \,\left( { \le \,s - m + 1} \right)} \\ {c_{\,1} + c_{\,2} + \, \cdots + c_{\,m} = s} \\ \end{array}} \right.} {\frac{1}{{t_{\,1} !t_{\,2} !\, \cdots \,t_{\,m} !}} \left( \begin{array}{c} s \\ c_{\,1} ,\,c_{\,2} ,\, \cdots ,c_{\,m} \\ \end{array} \right)} = \\ = \left\{ \begin{array}{c} s \\ m \\ \end{array} \right\} \\ \end{array} $$
Again, if we allow for the shelves to be empty these will get arranged at the beginning of the "set of sub-sets" and therefore the number of arrangements will just be the sum over the lower index of the above.
Note that not considering the order of the books within each shelf corresponds to the procedure of
picking the books sequentially and piling them at random into a free space in the shelves.
In this way, in each shelf the books are automatically ordered lower label first.