# Placing checkers with some restrictions

We are going to put n checkers on an (n x n) checkers board, with the following restrictions:

1) In each column there is EXACTLY one checker.

2) For i=1,2,...,(n-1), the first i rows cannot have EXACTLY i checkers.

The question is to count the number of ways to do so. I guess that the answer is n^{n-1}, but I do not know how to prove it. Can anyone help?

(If restriction 2) is removed, the answer is obviously n^n.)

-
What on earth is a "chess"? –  Qiaochu Yuan Oct 22 '09 at 22:38
I assume that a "chess" is a "chessman". If you want to avoid the gendered term (a good tendency!), the best name for a piece that you play on a chessboard is a "draught" (pronounced "drahft"). In particular, you don't care what type of piece it is, so "checkers" is a better name for the game than "chess". –  Theo Johnson-Freyd Oct 23 '09 at 2:15
"Chess piece" works as well. –  Kim Greene Oct 23 '09 at 2:20
I rewrote the question using "checkers". –  Scott Morrison Oct 23 '09 at 3:09
The spirit of placing chess with forbidden restrictions will have to live on in our hearts. –  Richard Dore Oct 23 '09 at 4:37

Let {ai} be the sequence giving the number of pieces in each row. Here's an easy bijection showing that such sequences are counted by Catalan numbers:

For any sequence, consider the lattice path starting at the origin that takes a1 steps up, then 1 step right, then a2 up, then 1 right, and so forth. Then the condition on this path is that you must touch the diagonal y=x after a right step exactly once, namely at (n,n). In other words, you must step above the diagonal, and once you do, you can't touch it again until the end of the path.

Now, just reflect the part of the path above the diagonal across it. This gives a path from the origin to (n,n) that stays below the diagonal, and these are counted by Catalan numbers. To go back, just reflect everything between the last two times you touch the diagonal.

-
I like this bijection! –  Marco-Dick CHEUNG Oct 23 '09 at 5:17

Here is a bijective proof of the main result. We first prove a related result: modify condition (2) by changing exactly to less than. Then we will show the corresponding answer is (n+1)n-1, the number of rooted forests on {1, ..., n}.

The bijection is as follows: imagine an empty stack, and read the board across rows, from top to bottom. Whenever you encounter a checker in column i, push i onto the stack. Whenever you reach the end of a row, pop off the top number of the stack, say j. Then j's children are just the numbers pushed onto the stack in the next row. It's easy to check that this is a bijection. (Note the roots of the forest are the checkers in the first row.)

It's not hard to modify this to work with the original problem and rooted trees on {1, ..., n}, giving the desired answer of nn-1. Number the checkers in order across rows, from top to bottom, and find the first checker C whose number is the same as its row number. Then take the column of C to be the root of the tree. To find the rest of the tree, use the procedure in the previous paragraph, starting right after C with an empty stack. Then, do the procedure again, starting right before C with an empty stack, but reading the board backwards. These two procedures give you two rooted forests, and taking the column of C to be the parent of all the roots of these forests gives a rooted tree, which completes the bijection. I'll omit the proof, but it's quite straightforward.

-
The solutions to your modified problem (exactly -> less than), when read as a sequence of checker positions within the columns, are exactly the parking functions; see combinatorics.org/Volume_4/PDF/v4i2r20.pdf . –  Jonah Ostroff Oct 23 '09 at 22:52
Ah yes, you're right. The bijection I gave is the one that is usually given between parking functions and labeled trees. –  Ricky Liu Oct 23 '09 at 23:44

If you denote this number by f(n), then we have the following equation by subtracting the bad possibilities from all possibilities: f(n)=n^n-sum_{k=1}^{n-1} f(k){n\choose k}(n-k)^{n-k} If by induction, you suppose that f(k)=k^{k-1} for k

-
domotorp: Would you mind giving more detail on how to prove the identity by induction? Actually, the problem I posed above is inspired by the identity you have written down. I do not know how to prove this identity purely arithmetically, so I do some combinatorics (it is indeed like first passage time) to show that if the problem I posed above is true, then the identity is proved. –  Marco-Dick CHEUNG Oct 23 '09 at 2:49
ok I see. unfortunately I do not know how to prove this equality, I thought that today things like this can be solved using some softwares. –  domotorp Oct 23 '09 at 14:46

A bijective solution should be possible, by using rooted trees.

Labelled rooted trees on n nodes are also counted by n^(n-1), see this link.

There are also as many "types" of trees (e.g. for n=3 there are two types of trees, and for n=4, four types of trees), as there are "types of words", as David Speyer listed for n=3; in that case the types of words are 300 and 210. The word gives the number of pieces by row.

For n=4, the types of words are 4000, 3100, 2200, 2110. There are 4 words of the first type, 24 of the second and fourth, and 12 of third. These numbers match the number of trees of each type.

Also, it seems like the number of words, not counted by multiplicity, are given by the Catalan numbers! (n=3: 300, 030, 003, 210, 012)

(Of course, the Catalan numbers counts classes of trees.)

A sketch of the bijection: Label the columns 1,2,3,...,n. Also let the labels in the labeled rooted trees be 1,2,..,n. Let the value of a node in a tree be the distance to the root for all nodes except the root, and 1 for the root.

Put a piece in row i and column j if node j has value i. It remains to show that this actually is a bijection...

-
I think the bijection cannot work. Because the root has value 1, that means in the corresponding chessboard setting, the first row always have at least one piece of chess. But in the problem I posed there can be setting with no chesspiece in the first row. –  Marco-Dick CHEUNG Oct 23 '09 at 3:16
Ah, yes. It can probably be fixed, somehow. –  Robert Parviainen Oct 23 '09 at 9:23

First observation (due to the crowd in 1015 right now, equivalently domotorp): every board with condition (1) can be cut up in exactly one way horizontally into slices, such that if the empty columns in each slice are removed, the resulting boards are square boards with conditions (1) and (2). (Cut after row i if the first i rows would violate condition (2)).

Note that there are exactly nn boards with condition (1).

So, by the exponential forumla,

\sum (# boards of size n with condition (1) ) tn/n! =
exp [ \sum (# boards of size n with conditions (1) and (2) ) tn/n! ]

So this reduces the problem to showing that exp(\sum (nt)^n/(n*n!)) = (\sum (nt)^n/n!).

Edit: yeah, one can finish this proof per David's comment. What we want to show is that there are n^n rooted forests on n vertices with an ordering on the trees. But these are in bijection with functions f:n->n. Given f, for every vertex i not in a cycle (i.e. the image of f^k for arbitrarily large k), put an edge from i to f(i). Then what's left to encode is a permutation on the vertices in the cycles, which are the roots of the resulting trees; but there are (# trees)! of these, and (# trees)! orderings of the trees.

-
I assume that the exp on the left hand side is a typo? In any case, 2 observations: (1) Those sums certainly do converge. n^n/n! = O(e^n) by Stirling's formula, so they converge for |t|<e^{-1}. (2) I remember very similar equations coming up when I tried to prove the formula for the number of rooted trees using exponential generating functions. It might be easier to show that the number of rooted trees obeys this recursion than to show that n^{n-1} does. –  David Speyer Oct 23 '09 at 2:04
Good catch(es). –  Alex Fink Oct 23 '09 at 2:14

Have you checked the case n=3? I get 12 cases, not 9. Listed by the number of pieces in each row, I get

1 of type 300

3 of type 210

3 of type 201

1 of type 030

3 of type 012

1 of type 003

-
201 is bad, so it is 9. –  domotorp Oct 23 '09 at 14:43