For the counts f_3(n) of interleaving words in m = 3 dimensions, of length n for n = 0, ..., 8, I propose the values: 1, 3, 9, 27, 75, 189, 447, 951, 1911 It should be admitted that these are strictly speaking lower bounds. They confirm those of Allan's values currently revealed; those concealed are awaited with anticipation ... For n > 0, easily f_3(n) = 3 (mod 6); since under permutations of A,B,C, {A^n, B^n, C^n} is the only class having just 3 isomorphs rather than 6. Is f_3(n) asymptotically polynomial in n; has it a civilised explicit expression? [For comparison, OEIS A005598 asserts f_2(n) ~ n^3 / pi^2; and explicitly f_2(n) = 1 + \sum_1^n (n-i+1) phi(i), where phi(n) denotes the Euler totient A000010.] Having convincingly failed to come up with anything like a decently efficient algorithm, I was eventually driven to resort to a Monte-Carlo attack based on the original definition. Each trial generates m random AP's filling an interval, sorts them, recovers the generating AP for each term, and the resulting discrete sequence is added to the language set. If doubling the number of trials leaves the size of this language unaltered, its size is accepted as the final value of f_m(n). For m,n = 3,8 the final Maple run of 750,000 trials occupied 1.5 hrs. Fred Lunnon On 7/21/10, Allan Wechsler <acwacw@gmail.com> wrote:
Some of you may recall my interest in the sequence 1, 2, 4, 8, 14, 24, 36 ... of the number of ways it is possible to interleave N elements chosen from two non-intersecting arithmetic progressions. Another way to view this is as (closely related to) the number of rasterized straight line segments with N+1 pixels, where we light up a pixel if a geometric line intersects its rectangle of screen real estate. The sequence is in OEIS as A005598 ( http://www.research.att.com/~njas/sequences/A005598), and is apparently originally due to Leendert "Leo" Dorst, who wrote about it for his doctoral research, first mentioning it in 1984.
Oddly, the corresponding sequence for three arithmetic progressions is, perhaps, not in OEIS yet. The alternative formulation involves polycube models of three-dimensional line segments. Unless I've made a mistake in my enumerations, the sequence begins 1, 3, 9, 27, 75, 189 ... and OEIS has nothing with those elements.
Unfortunately, my calculations are all with pen and paper; I haven't written any code to do the counting. So it's quite possible that I blundered, and that OEIS has the sequence after all. Can another funster verify my work? (I have one more element, which I'm holding back to avoid the power of suggestion.)
There is an obvious generalization to any number of progressions/dimensions. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun