How many ways are there to place n counters, diagonal by diagonal, starting from a single counter, so that...

combinatorics/counters.beyond.diagonal New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

How many ways are there to place n counters, diagonal by diagonal,
starting from a single counter, so that each counter is next to a
counter on the previous diagonal?

[ Editor: the original 1993 problem statement ("A Combinatorics
Problem", sci.math and rec.puzzles) is not in the collected posting;
this wording is reconstructed from the comment in John Tromp's program
("count number of ways to put `left' counters beyond a diagonal
containing the counter pattern represented by bitmask `mask'") and may
not match the original exactly. ]

Show solution

bert@netcom.com (Roberto Sierra) writes:

>        my method =         {1, 2, 5, 13, 34, 89, 233, 610, 1597, ...}
>        actual* solutions = {1, 2, 5, 13, 35, 96, 267, 750, 2123, ...}

>* - as determined by a little MMA-based exhaustive generator I cranked
>    out this morning.  Don't trust these numbers!!  I may have made an
>    error in the program.  It's been running now for several hours,
>    but hasn't come up with the answer for n=10 yet.

As an illustration of the power of C, I appended below a little
generator in that language.

It computes the following table:

 2:       2
 3:       5
 4:      13
 5:      35
 6:      96
 7:     267
 8:     750
 9:    2123
10:    6046
11:   17303
12:   49721
13:  143365
14:  414584
15: 1201917
. . .

I trust your numbers all right.

Now if anybody can find some recurrent relation or something...

typedef unsigned long ul;

int try(mask,len,left)
/* count number of ways to put `left' counters beyond a diagonal */
/*  containing the counter pattern represented by bitmask `mask' */
ul mask;
int len,left;
{
  ul m,ml;
  int l,s;

  mask = ~(mask | (mask<<1));
  for (s=0,m=1<<len; --m;)
    if (!(m & mask)) {
      for (ml=m,l=left; ml; ml&=(ml-1)) l--;
      s += (l<=0 ? !l : try(m,len+1,l));
    }
  return s;
}

main()
{
  int i;

  for (i=2; i<32; i++)
    printf("%2d:%8d\n", i, try(1,2,i-1));
}

-- John Tromp <tromp@cwi.nl>

[ Editor: "MMA" is Mathematica.  No recurrence was found in the
collected postings. ]