[seqfan] Re: Request for help with mystery sequence N0320 = A213385
David Applegate
david at research.att.com
Mon Jun 11 02:04:25 CEST 2012
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/
More information about the SeqFan
mailing list