In how many ways can $13$ identical objects be placed into squares such that no row remains empty?

Question

I was inspired by this question I saw earlier today, to try to come up with a better general method, when there are more squares in each row, more rows, and more objects. Because basically the question in the link can be solved quite easily by counting by using lots of different methods because there aren't many squares or objects.

My question is, in the following diagram, how many ways can $13$ identical objects be placed into squares such that no row remains empty?

To save you from counting, there are $9\times 2 + 13\times 1 + 17 \times 2 = 65$ squares total.

I feel like inclusion-exclusion can be used somehow, but I can't quite seem to get my thoughts onto paper for this problem...

And I'm more interested in innovative/clever counting techniques rather than pages upon pages of computation...

Answer 1

This is still small enough to allow an inclusion-exclusion calculation:

$$\begin{align*} &\binom{65}{13}-2\binom{48}{13}-\binom{52}{13}-2\binom{56}{13}\\ &\qquad+\binom{31}{13}+2\binom{35}{13}+4\binom{39}{13}+2\binom{43}{13}+\binom{47}{13}\\ &\qquad-\binom{18}{13}-2\binom{22}{13}-4\binom{26}{13}-2\binom{30}{13}-\binom{34}{13}\\ &\qquad+\binom{13}{13}+2\binom{17}{13}\\ &=\binom{65}{13}-4\,552\,426\,452\,267\\ &=11\,868\,647\,063\,013\,. \end{align*}$$

Answer 2

Here's another approach. Let $(u_1,u_2,u_3,u_4,u_5)=(9,9,13,17,17)$, and let \begin{align} S&=\left\{(x_1,x_2,x_3,x_4,x_5)\in \mathbb{Z}^5: \sum_{i=1}^5 x_i=13 \land \bigwedge_{i=1}^5 (1 \le x_i\le u_i)\right\} \\ &\leftrightarrow\left\{(y_1,y_2,y_3,y_4,y_5)\in \mathbb{Z}^5: \sum_{i=1}^5 y_i=8 \land \bigwedge_{i=1}^5 (0 \le y_i\le u_i-1)\right\} \\ &=\left\{(y_1,y_2,y_3,y_4,y_5)\in \mathbb{Z}_+^5: \sum_{i=1}^5 y_i=8\right\}. \end{align} Then $|S|=\binom{8+5-1}{5-1}=495$, and the desired count is $$\sum_{(x_1,x_2,x_3,x_4,x_5)\in S}\ \prod_{i=1}^5 \binom{u_i}{x_i} = 11,868,647,063,013$$

Answer 3

It is:

$$[x^{13}]:((1+x)^9-1)^2((1+x)^{13}-1)((1+x)^{17}-1)^2$$

where $[x^{13}]$ means the coefficient of $x^{13}$ in the formula that follows.

This places at least one object in every row, and also counts the number of ways to place $k$ objects in a row using the binomial theorem.