[seqfan] Re: Bad pdf file in A002369?

[Fred Lunnon]

  Partly ... but if you do need an "intelligent" program to progress further
(after comparing early terms with the "simple" one), then reverse
"modding out" to recover the fixed counts as well; and publish both
free and fixed counts.

  Another feature of fixed counts is that they are typically smoother than
free, so that empirical estimates of asymptotic behaviour are more
consistent using the same amount of data.

WFL



On 2/25/18, Joerg Arndt <arndt at jjj.de> wrote:
> Let me make sure I understand, using an example:
>
> For extending http://oeis.org/A266549
> I generated all "fixed" paths.
> This is reasonable simple to program correctly
> and gives simple, hence fast code (instead of
> some "intelligent" solution that would be
> slow and likely wrong).
>
> For modding out symmetries, I computed
> the word of turns (as symbols +, -, and 0
> respectively for +90, -90, and 0 degrees)
> for each path.
>
> Let that word be T,
> rev(T) for the reversed word,  and
> neg(T) the word obtained by swapping letters + and -
>
> Only if a turn string is
> 1) its own cyclic minimum
> 2) T <= neg(T)
> 3) T <= rev(T)
> 4) T <= neg(rev(T))
> (where <= compares lexicographically, and modulo rotations)
> then that enters the count.
>
> Is this (an example of) what you suggested?
>
>
> Best regards,   jj
>
> P.S.: If one could make Duval's algorithm for Lyndon words (and
> necklaces) modify for prefix conditions (here: self- avoidance) then
> mighty speed-ups should be possible.  Duval's algorithm is practically
> identical to the one of Fredericksen, Kessler, Maiorana (FKM algorithm
> for generating necklaces).  Not sure what name(s) deserve precedence.
>
> * Fred Lunnon <fred.lunnon at gmail.com> [Feb 25. 2018 08:44]:
>>   Incidentally, when enumerating objects acted upon by a symmetry group
>> --- eg. polyominoes under the group  D_4 (aka  D_8 ) of the square --- it
>> is
>> advisable to consider "fixed" counts (ignoring symmetry) rather than
>> "free"
>> (modulo symmetry), since any explicit expressions for the counts are
>> generally simpler for the fixed case.
>>
>>   In practice, brute-force enumeration may well be faster if symmetry
>> is `broken' first; but it is generally easy to incorporate additional code
>> to reconstruct the fixed contribution corresponding to each free object.
>>
>>   Unfortunately many investigators remain apparently unaware of such
>> considerations.
>>
>> WFL
>>
>> [...]
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>