How many sets of n squares in the quarter plane contain the corner square and can each be reached from the...
combinatorics/directed.animals New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
How many sets of n squares in the quarter plane contain the corner
square and can each be reached from the corner by a path through the
set that moves only north or east?
In the literature such a set is called a "directed animal": a set A of
lattice points (a subset of Z x Z) such that
1) (0,0) is in A
2) if (p,q) is in A then there is a path in A from (0,0) to (p,q),
using steps that move only North or East.
The first few directed animals are
*
* * * * **
* ** * *** ** * ** *
Is there a formula for the number of them?
[ Editor: problem statement reconstructed from the postings. The
original question (by another "Bert", in Australia) is not in the
collected material; John Stembridge, who supplied the definition
above, was not sure it was the same problem, though the replies of
Tim Chow and John Tromp fit it. ]
Show solution
I've received a ton of mail from folks on the subject of this
combinatorics problem. Some of the mail I've received refers to a
bunch of literature in which it *appears* that a solution to the
problem may have already been found! By a solution, I mean a way to
enumerate the solutions without counting them explicitly. It is not
clear whether the solution to the problem looks anything like an
equation or an algorithm, or whether a person or a computer would be
required for small values of N.
[1] John Stembridge at umich.edu cited extensive references to texts on
the subject of 'directed animals' which would seem to be exactly
the same problem we are talking about. He wasn't 100% sure, but
was fairly certain that a solution (though perhaps not an equation
in the strictest sense) has been found and was located in one of
the 14 references he cited.
[2] It was indeed proven that my original recurrence relationship
s(n) = 2 s(n-1) + s(n-2) + ... + s(1) is equivalent to Fib(2n-1).
I won't include the proof herein because it accidentally got
deleted. [My apologies to the New Zealander who originally
"squizzed" the proof -- it was a very elegant and simple proof.]
[3] A simple equation for the upper bound of the solution count was
postulated by Tim Chow at math.mit.edu. The upper bound would
appear to be equal to n! by his reasoning.
[4] It was pointed out by several people that *both* of the following
conventions appear to be equally valid in mathematical circles.
Fib(0) = 1 Fib(1) = 1
Fib(1) = 1 **OR** Fib(2) = 1
Fib(2) = 2 Fib(3) = 2
: :
The text _Concrete Math_ defines the Fibonacci series concretely
*both* ways, depending on where you look in the book.
[5] John Tromp explained the algorithm behind his C generator in detail
for me. I'll post his description for those who might be trying
to make sense of his code.
-- Roberto Sierra <bert@netcom.com>
[ Editor: the following three mails were posted by Sierra. ]
I'm afraid I've forgotten the original statement of the problem, but it
sounded to me very much like it belongs to a class of problems about
which there is a *huge* literature (much of it in French), generated
mostly by researchers in combinatorics and statistical mechanics.
In this literature, a "directed animal" is a set A of lattice points
(i.e., a subset of Z x Z) such that
1) (0,0) is in A
2) if (p,q) is in A then there is a path in A from (0,0) to (p,q),
using steps that move only North or East.
In particular, A is entirely contained in the first quadrant. The
first few directed animals are
*
* * * * **
* ** * *** ** * ** *
I'm pretty sure that there is a "formula" known for the number of
animals on n points, as long as you are charitable in your definition
of formula. [Most likely, it is a generating function.]
Unfortunately, I don't have exact references to give you, but I did do
a keyword search for "directed animal" in the Math Reviews database,
and here is a listing of what it turned up:
DATE TITLE: AUTHOR:
1 1989 Heaps of pieces. I. Basic definitions and Viennot, Gerard Xav MR
2 1988 Exact generating function for fully direct Privman, V MR
3 1988 Exponent $nusb perp$ for $2$D directed com Bhat, V. K MR
4 1988 Effect of loops on spiral lattice animal s Bose, Indrani MR
5 1988 Equivalence of the two-dimensional directe Gouyou-Beauchamps, MR
6 1987 Real-time control of walking Donner, Marc D CR
7 1987 Exact solution of the partially directed c Privman, V MR
8 1987 Collapse transition and cyclomatic number Lam, P. M MR
9 1987 Competition and niche dynamics from steady Brew, J. S MR
10 1986 Enumeration of directed compact site anima Bhat, V. K MR
11 1982 Size and shape of directed lattice animals Redner, S MR
12 1982 Equivalence of the two-dimensional directe Dhar, Deepak MR
13 1982 Application of directed lattice animal the Green, J. E MR
14 1982 Relation between size and shape of isotrop Family, Fereydoon MR
Directed animals are just one of a dozen or so flavors of animals
(subsets of Z x Z subject to various properties involving
connectedness). There are at least a hundred or two papers on the
subject.
-- John Stembridge <John.Stembridge@math.lsa.umich.edu>
Previously I gave an upper bound of f(n) <= 2^g(n) where g(n) is
n(n+1)/2. (I said n(n-1)/2 before; that was a mistake.) This comes
from the fact that each configuration with n elements must be a subset
of the set S = {(x,y) : x+y <= n+1} which has g(n) elements.
A slightly better upper bound comes from the following: label the
squares in the quarter plane as follows.
15
10 14 etc.
6 9 13
3 5 8 12
1 2 4 7 11
Then, given any configuration C with n squares, let P(C) be the
configuration obtained by removing the highest numbered square from C.
Note that P(C) is a legal configuration of n-1 squares. It follows
that f(n) <= n * f(n-1) so that f(n) <= n!. This is a slightly better
upper bound but still way too coarse.
-- Tim Chow <tycchow@math.mit.edu>
[ Editor: from John Tromp's mail to Sierra about his C program for
counting the configurations. ]
Let me try to explain the diagonal method in a bit more detail.
Suppose we have chosen a configuration on the 4 first diagonals x+y=0,
x+y=1, x+y=2, and x+y=3. The last is shown in the picture as a's. For
extension to farther diagonals, only the occupied positions on the
a-diagonal matter. Suppose it has only (0,3) and (3,0) occupied. This
can be represented as a bit mask 1001 (let's call this number a as
well for convenience). The places where we can put stars on b are then
b = a bit-wise-or (a shifted left 1) = a|(a<<1) = 11011.
b
a b
a b
a b
a b
The program uses a nice trick to count quickly through all allowed b
configurations, in this case all those that leave the middle position
unoccupied. Suppose I have at some point 11000. Then I simply
subtract one to get 10111, and next bitwise-and it with the mask 11011
to get 10011. I repeat this until I get 00000.
For every b configuration, I count the number of 1s in it. Note that
the assignment m=m&(m-1) removes the lowest 1-bit from m. If, after
subtracting this from "left", the result is at most two, then I end
the recursion: the number of configurations with this b pattern is
then 0 for negative "left", 1 for 0 left, z for 1 left, and
(z choose 2) + 2z for 2 left, where z is the number of 1-bits in
b|(b<<1).
(In the program, z is called b, sorry for the confusion:-)
>Am I correct in assuming that the number of stars you can place is
>determined by the number of bits in an unsigned long? Thus N is
>limited to, say, 32?
Precisely! Nowadays, 64-bit machines like the DEC Alpha and MIPS R4000
based ones are becoming more commonplace. But although the length of
the unsigned long is a limitation, it turns out not to be the most
important one. An even bigger limitation is the size of the int I use
to count the number of configurations. With 23 stars, this number
already exceeds 2^32.
-- John Tromp <tromp@cwi.nl>
[ Editor: Tromp's program itself was not included in the collected
material, and no table of counts or closed formula was posted. The
relation of Sierra's Fib(2n-1) recurrence to directed animals is not
explained in the postings. ]
[ Editor: two later postings (September 1993) that give the
generating function and the counts. ]
According to D. Gouyou-Beauchamps and G. Viennot [Adv. in Applied
Math. 9 (1988), 334-357], an explicit generating function for the
number of directed animals on n points was conjectured by Dhar, Phani
and Barma [J. Phys. A 15 (1982), 279-284], and then proved by several
people, including Dhar [Phys. Rev. Lett. 59 (1983), 853-856].
Using a[n] to denote the number of n-point directed animals, the
generating function is given by
infinity
----- 1/2
\ n (1 + t)
) a[n] t = 1/2 ------------ - 1/2
/ 1/2
----- (1 - 3 t)
n = 1
It is easy to derive from this the asymptotic behavior:
a[n] ~ 3^n * n^(-1/2), which confirms something that was conjectured
in an earlier post.
Here are the first few terms in the series:
2 3 4 5 6 7 8 9 10
t + 2 t + 5 t + 13 t + 35 t + 96 t + 267 t + 750 t + 2123 t + 6046 t
11 12 13 14 15
+ 17303 t + 49721 t + 143365 t + 414584 t + 1201917 t
16 17 18 19 20
+ 3492117 t + 10165779 t + 29643870 t + 86574831 t + O(t )
-- John Stembridge <jrs@math.lsa.umich.edu>
In article <CCrAz7.AEx@cse.psu.edu>, pan@math.psu.edu (Garth Payne)
writes:
> It seems likely that the generating function for S(n) is
>
> g(x)
>
> 1 Sqrt[1 + x]
> = - + ---------------
> 2 2 Sqrt[1 - 3 x]
>
> 2 3 4 5 6 7 8
> = 1 + x + 2 x + 5 x + 13 x + 35 x + 96 x + 267 x + 750 x +
>
> 9 10 11 12 13
> 2123 x + 6046 x + 17303 x + 49721 x + 143365 x +
>
> 14 15 16 17
> 414584 x + 1201917 x + 3492117 x + 10165779 x +
>
> 18 19 20 21
> 29643870 x + 86574831 x + 253188111 x + O[x]
>
> I hesitate to prove g is the generating function for S(n) since it
> would take some work and it's likely that a proof can be found in
> the literature.
You are right.
A reference with `bijective' proofs is:
D. Gouyou-Beauchamps, G. Viennot
Equivalence of the Two-Dimensional Directed Animal Problem
to a One-Dimensional Path Problem
Advances in Applied Math. 9 (1988) 334-357
It's interesting to note:
3S(n) - S(n+1) = Motzkin number (this is easy to show with gfs.)
The number of compact-rooted (starting with a diagonal) directed
animals of size n is 3^(n-1).
-- Torsten Sillke <sieda@hrz.uni-bielefeld.de>
[ Editor: this supersedes the closing note above that no table of
counts or formula was posted. ]