1
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ It appears you are allowing multiple pieces per square. It also appears that the pieces are in an order and once you don't place a piece you can't place any more. Is that what you intend? $\endgroup$ – Ross Millikan Sep 16 '16 at 14:27
  • $\begingroup$ @RossMillikan I'm not sure what to make of your comment. I don't allow multiple pieces per square. That's why the square count goes down once I place a piece (that square is excluded for future pieces). I'm also allowing further pieces to be placed if I choose not to place a certain piece (that's why the second term is $c(n,k-1)$. $\endgroup$ – FUZxxl Sep 16 '16 at 14:28
  • 1
    $\begingroup$ If I'm understanding your question properly, you are looking for $\sum_{i=0}^k \frac{n!}{(n-i)!}$, right? $\endgroup$ – Michael Biro Sep 16 '16 at 14:29
  • 1
    $\begingroup$ @MichaelBiro I have confirmed your closed form to be correct. Would you mind posting this as an answer? $\endgroup$ – FUZxxl Sep 16 '16 at 15:06
  • 1
    $\begingroup$ Ok, so that assumes a set of $k$ pieces to be placed and not just that the pieces are distinguishable once placed, right? $\endgroup$ – Michael Biro Sep 16 '16 at 16:38
1
$\begingroup$

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...

$\endgroup$
  • 1
    $\begingroup$ Wolfram Alpha finds a closed form in terms of the confluent hypergeometric function of the second kind: $\sum^k_{i=0}{k\choose i}{n!\over(n-i)!}=(-1)^kU(-k,-k+n+1,-1).$ Though, I don't think this is any more useful. $\endgroup$ – FUZxxl Sep 16 '16 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.