Variant of balls bin problem

Question

I am stuck at the following variant of the balls bin problem.

The task is to count the number of ways of placing $n$ identical balls into $k$ ordered bins under the constraint: the bin number $i$ must have strictly less than $i$ balls.

Any help/suggestions would be appreciated.

Answer 1

$HINT:$ As far as I understood, It is said that balls are identical but bins are different.Then it reminds us Stirling numbers with second types look at:https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#:~:text=Stirling%20numbers%20of%20the%20second%20kind%20are%20one%20of%20two,to%20the%20parameters%20n%2C%20k.

Moreover , it is said that $i$ th bin have at most $i$ balls so apply it to stirling numbers from $1$ to $i$

Answer 2

Hint/Comment: Is easier to control the opposite problem, meaning you place at least $i$ balls in the $i-$th bin. Call $$A = \{x=(x_1,\cdots , x_k):\sum _{i=1}^kx_i=n\},$$ and $A_i = \{x\in A:x_i\geq i\}$ then you want exactly $$\left |A\setminus \bigcup _{i=1}^kA_i\right |=\sum _{i=0}^k(-1)^i\sum _{X\in \binom{[k]}{i}}\left |\bigcap _{x\in X}A_x\right |.$$ Use Stars and Bars to show that $|A|=\binom{n+k-1}{k-1}$ and $|A_i|=\binom{n-i+k-1}{k-1}$ so, in general, $|\bigcap _{x\in X}A_x|=\binom{n-\sum _{x\in X}x+k-1}{k-1}.$

If you are interested in going further, notice that the number of times $\binom{n-\ell+k-1}{k-1}$ appears in that sum is the number of ways that you can write $\ell$ with distinct parts.