Is there a closed form for the number of ways to put up to $k$ chess pieces on a board with $n$ squares?

55 Views Asked by At

Given a chess board with $n$ squares, the number of ways $c(n,k)$ to put up to $k$ pairwise distinguishable chess pieces on the board can be described by

$$c(n,k)=nc(n-1,k-1)+c(n,k-1)\quad\hbox{where }c(n,0)=1\hbox{ and }c(0,k)=1$$

where the first term indicates the choice to place the next piece on the board and the second term indicates the choice to leave the next piece off the board.

One can easily see that the second term can be unfolded to yield

$$c(n,k) = 1+n\sum_{i=1}^kc(n-1,i-1)$$

but that's where I couldn't progress anymore. Is there a closed form for $c(n,k)$?

1

There are 1 best solutions below

1
On BEST ANSWER

As per comments, I noted that this problem was essentially $$\sum_{i=0}^k \binom{k}{i} \frac{n!}{(n-i)!}$$

While not technically closed form, it might help to find some simplifying factorial or binomial identities...