2
$\begingroup$

If $S_i$ represents the number of books on the $i$th shelf then the problem can be rewritten as: $k = \sum_{i=1}^n S_i$ where $S_i \le m \iff x_i = m - S_i \ge 0$ and $S_i = m - x_i$ then $k = \sum_{i=1}^n (m - x_i) = nm - \sum_{i=1}^n x_i \implies nm - k = \sum_{i=1}^n x_i$ therefore there are ${nm - k + m - 1}\choose{m - 1}$ solutions to the equation. Then we can shuffle around the books in $k!$ ways then the final answer is $k!$${nm - k + m - 1}\choose{m - 1}$. Is this solution correct?

$\endgroup$
12
  • $\begingroup$ then what are you asking ? $\endgroup$ Jan 9 at 19:23
  • $\begingroup$ @NotaSalmonFish If it's correct or not. I forgot to add that part sorry $\endgroup$
    – Marin
    Jan 9 at 19:24
  • $\begingroup$ At a glance, no I don't expect this to be right. I am struggling to understand your logic however. It seems to me that rather than "putting $S_i$ books onto a shelf" you are "choosing how many holes are left on each shelf" (where each shelf has capacity $m$) and are correctly noting that you will necessarily have a non-negative number of holes. You do correctly account for no shelf having too many books in this way, however you don't seem to be correctly accounting for the fact that no shelf can have more holes than its capacity. $\endgroup$
    – JMoravitz
    Jan 9 at 19:30
  • 1
    $\begingroup$ The typical approach will be inclusion-exclusion for this problem (though it does get messy to write in its most general form) or will be generating functions. $\endgroup$
    – JMoravitz
    Jan 9 at 19:31
  • 2
    $\begingroup$ In the case of generating functions, it is easy to write the answer, less easy to compute the answer. It is going to simply be $k!$ times the coefficient of $x^k$ in the expansion of $(1+x+x^2+\dots+x^m)^n$ $\endgroup$
    – JMoravitz
    Jan 9 at 19:44

1 Answer 1

0
$\begingroup$

The number of ways to place $k$ distinct books on $n$ distinct shelves, such that each shelf has at most $m$ books, is $$ \sum_{i=0}^n (-1)^i \binom ni \binom{k}{(m+1)i}\cdot \big((m+1)i\big)!\cdot \frac{(n+k-(m+1)i-1)!}{(n-1)!}. $$ I will prove this using the principle of inclusion-exclusion.

First, let us answer a simpler question. Ignoring the maximum capacity of $m$, how many ways are there to place $k$ distinct books on $n$ distinct shelves? The answer is $$ n\cdot (n+1)\cdot (n+2)\cdots (n+k-1)=\frac{(n+k-1)!}{(n-1)!}\tag1 $$ You can choose a placement of books as follows. Take the $k$ distinct books, along with $n-1$ identical dividers, and arrange these $n+k-1$ items into a line in $(n+k-1)!/(n-1)!$ ways (we divide by $(n-1)!$ because the $n-1$ dividers are identical). The dividers split the books into $n$ sections, corresponding to the shelves.

Let $S$ be the set of all ways to place $k$ distinct books on $n$ distinct shelves. For each $i\in \{1,\dots,n\}$, let $E_i$ be the set of arrangements in $S$ for which the $i^\text{th}$ shelf has more than $m$ books. The arrangements in each $E_i$ are bad, so we need to count $|S\setminus (E_1\cup \dots \cup E_n)|$, which is what PIE is for. Using PIE, we have $$ \begin{align} |S\setminus (E_1\cup \dots \cup E_n)| &= \sum_{i=0}^n (-1)^i\sum_{1\le j_1<\dots <j_i\le n}|E_{j_1}\cap \dots \cap E_{j_i}| \\ &= \sum_{i=0}^n (-1)^i\binom ni|E_{1}\cap \dots \cap E_{i}| \end{align} $$ All that remains is to find $|E_{1}\cap \dots \cap E_{i}|$, which is the number of arrangements where the first $i$ shelves have too many books. There is a nice combinatorial way to do this.

  • First, set aside $(m+1)i$ books. There are $\binom k{(m+1)i}$ ways to do this.

  • Next, arrange the $(m+1)i$ books on the first $i$ shelves, with $m+1$ books per shelf. There are $\big((m+1)i\big)!$ ways.

  • Finally, place the remaining $k-(m+1)i$ books onto the $n$ shelves, such that the previously placed books stay at the leftmost positions on their shelves. We are back in the situation which was solved by $(1)$, except with $k-(m+1)i$ books instead of $k$, so the number of ways is $(n+k-(m+1)i-1)!/(n-1)!$.

Putting this altogether, we get the answer advertised at the beginning.


The answer can be rewritten as $$ k!\sum_{i=0}^n (-1)^i \binom ni \binom{n+k-(m+1)i-1}{k-(m+1)i} $$ This is exactly $k!$ times the number of ways to place $k$ identical books on $n$ shelves so that no shelf has more than $m$ books. Furthermore, the identical book problem is equivalent to counting integer solutions to the equation $$ x_1+\dots+x_n=k, $$ where the variables must satisfy $0\le x_i\le m$ ($x_i$ is the number of books on the $i^\text{th}$ shelf). See Extended stars-and-bars problem(where the upper limit of the variable is bounded) for a generating function solution to the identical book/counting integer solutions problem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .