Well, that's me put out of my misery, anyway. The OEIS entry did actually try to say owt about the inequality-based method, but it didn't sink in --- I scuttled off instead to cobble up a formal-language, morphism-based approach --- which did get somewhere at first, but then fell over once m > 2. On 7/23/10, Michael Kleber <michael.kleber@gmail.com> wrote:
Oof -- and of course it would take 1/6 the time if you say WLOG that A/B/C first appear in alphabetical order, then count each string with weight 1 or 3 or 6, depending on whether it mentions 1 or 2 or 3 of the sequences.
--Michael
But you shouldn't do this straight away --- collect as much test data as convenient with the dumb program, to verify the more complex (and logically fragile) faster version later! How about letting the final version rip for an hour or so, then submit something for OEIS to chew on?
On Fri, Jul 23, 2010 at 10:39 AM, Michael Kleber
<michael.kleber@gmail.com>wrote:
Counts up through length 12 are:
1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267
It's not hard to do deterministically, in a computer algebra package. To check if a string like "ABCABA" is a feasible interleaving characteristic string, you just transform it into a set of linear inequalities constraining the six unknowns describing the three arithmetic progressions, and test whether there's a solution.
In addition to the obvious checks -- e.g. that the second term in the As progression is larger than the first of the Cs and smaller than the second of the Bs -- you need extra inequalities asserting that the last term mentioned in the string (here the third A) is smaller than each term that implicitly comes after the string (fourth A, third B, second C). And likewise for the terms that come before the string starts.
Something like Mma has no trouble finding an arbitrary point in the solution space for a set of linear equalities, or else proving that the set is empty. Code below, as long as you promise not to complain about poor style.
"linear inequalities" presumably? Not sure how, or if, Maple tackles these. [What, me complain? Nah --- I'm too busy chewing the carpet ...]
Of course you don't take all strings of length n; rather you first list all the strings of length n-1, and then append each of A,B,C to them and test the results.
The time to verify each candidate string goes up with n, of course -- you're adding inequalities, though only at a linear rate and still over a six-dimensional space, and you're also increasing the number of putative strings that need checking. The exhaustive enumeration up through length 12 took under 7 minutes.
--Michael
Any ideas on functional recursions, explicit expressions, asymptotics? Fred Lunnon