[seqfan] Re: Request for help with mystery sequence N0320 = A213385

[David Applegate]

Neil,
Here's an explanation of Richard Guy's sequence.

By "Total number of paths from n^1 towards 1^n of all lengths
0,1,...,n-1." he means paths from n^1 to any other node in the
directed graph.

So, in the directed graph:

  41 -> 311
 /  \   /      \
5    \/       2111 -> 11111
 \  /    \      /
  32 -> 221

There is 1 path from 5 to 5  (the empty path)
         1 path from 5 to 41 (5->41)
         1 path from 5 to 32 (5->32)
         2 paths from 5 to 311 (5->41->311 and 5->32->311)
         2 paths from 5 to 221 (5->41->221 and 5->32->221)
         4 paths from 5 to 2111 ...
         4 paths from 5 to 11111 ...

for a total of 15.  I checked that this matches for n=1,2,3,4, but
didn't consider n=6 or higher.

-Dave

> From seqfan-bounces at list.seqfan.eu Sun Jun 10 18:05:28 2012
> Date: Sun, 10 Jun 2012 18:05:16 -0400
> From: Neil Sloane <njasloane at gmail.com>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Subject: [seqfan] Request for help with mystery sequence N0320 = A213385

> Dear SeqFans:

> Request for help with mystery sequence N0320 = A213385

> On June 24 1971 Richard Guy sent me (among many
> other sequences) two sequences that are related to refinements of
> partitions.

> Take n=5 as an example. Arrange all partitions of 5 into a directed graph:
>   41 -> 311
>  /  \   /      \
> 5    \/       2111 -> 11111
>  \  /    \      /
>   32 -> 221

> starting at n^1 and ending at 1^n

> Sequence A002846 gives the number of paths fom n^1 to 1^n of length n-1.
> Here we see a(5)=4.

> This is described in the paper (I have a copy).
> P. Erdos, R. K. Guy and J. W. Moon, On refining partitions, J. London Math.
> Soc., 9 (1975), 565-570.

> So far so good. But Richard also sent the sequence (N0320, was A002847, now
> A213385)
> 1, 2, 3, 7, 15, 43, 131, 468, 1776, 7559, 34022, 166749, 853823, 4682358
> for n=1..14, which he describes as "Total number of paths from
> n^1 towards 1^n of all lengths 0,1,...,n-1."

> I am unable to match these numbers!

> Again consider n=5. There is a direct path from 5^1 to all the later nodes,
> since we can refine 5^1 to (say) 2111 in one step. In fact there are direct
> paths
> from each node in the picture to any node to its right.
> If I count all paths from 5^1 to 11111, I get 18, not 15.
> For n=1,2,3,4,5, I get 1,1,2,6,18 for the total number of paths.

> So there are two questions: what is the correct interpretation of Richards
> sequence A213385,
> and how does my interpretation continue after 1,1,2,6,18 ?

> -- 
> Dear Friends, I have now retired from AT&T. New coordinates:

> Neil J. A. Sloane, President, OEIS Foundation
> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com

> _______________________________________________

> Seqfan Mailing list - http://list.seqfan.eu/