[seqfan] Re: Are A304312, A304313 Same as A006691, A006692?

Mon May 21 11:14:20 CEST 2018

Let me clarify something concerning A006691 (and related sequences).
I cannot find Robinson's article in my archive but hardly it will 
illuminate much:
as I remember the formula in it is unjustifiably awkward (even contains 
an extra
enumerative parameter).

First of all, A006691 represents the number of unlabeled (by states) 
strong initial automata
with n non-initial states and 2 inputs. Such is a more exact definition. 
Now, any such
automaton has no symmetries, Therefore it gives rise to n! distinct 
automaton with n+1
labeled (=numbered) states including the initial one (labeled 1). The 
corresponding
sequence is available in the OEIS:
          n!*A006691(n) = A027834(n+1), n>=1.
The latter sequence is based on two my very old articles (in Russian, 
available in the
ResearchGate). The second one of 1977 contains rather a transparent 
linear recurrent
formula for strong automata with labeled states. It has been already 
reproduced in the text
of A027834... Presumably it may help in settling Paul's question but I 
don't know how.
His analytical representation (I have no doubts that both A304312 and 
A006691 are one
and the same sequence) is fully unexpected for me. Let me skip here some 
interesting
additional details concerning the coefficients of the mentioned 
recurrence (I've informed
Paul in a separate mail).

Of course, similar formulas are valid for strong automata with 3 or more 
input letters;
however, the sequences n!*A006692(n), etc. are missing in the OEIS.

Valery Liskovets

Brendan McKay wrote:

> It is in my paper files, but I am nearly an earth diameter away and won't
> be home for 3 weeks.  Feel free to ask me then.
>
> Brendan.
>
> On 20/5/18 3:14 pm, Neil Sloane wrote:
>
>> I looked hard for the Robinson paper mentioned in A006689-A006692.
>> I have many of his papers, but not that one.  I have many conference
>> procedings with similar titles, but not that one.
>>
>> The title of the book in the OEIS entries was rather inaccurate.  
>> Here is a
>> corrected reference, giving full details:
>>
>> Robert W. Robinson, Counting strongly connected finite automata, pages
>> 671-685 in "Graph theory with applications to algorithms and computer
>> science." Proceedings of the fifth international conference held at 
>> Western
>> Michigan University, Kalamazoo, Mich., June 4–8, 1984. Edited by Y. 
>> Alavi,
>> G. Chartrand, L. Lesniak [L. M. Lesniak-Foster], D. R. Lick and C. E. 
>> Wall.
>> A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 
>> 1985.
>> xv+810 pp. ISBN: 0-471-81635-3; Math Review MR0812651 (86g:05026).
>>
>> Given this, it should be possible to find the book - maybe Google 
>> Books has
>> it?
>>
>>
>>
>>
>> Best regards
>> Neil
>>
>> Neil J. A. Sloane, President, OEIS Foundation.
>> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
>> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, 
>> NJ.
>> Phone: 732 828 6098; home page: http://NeilSloane.com
>> Email: njasloane at gmail.com
>>
>>
>> On Sun, May 20, 2018 at 2:45 AM, Joerg Arndt <arndt at jjj.de> wrote:
>>
>>> By the argument of "too much of a coincidence" this is very likely:
>>> your sequences are built using a functional equation,
>>> these tend to count graphy things, and the other
>>> sequences do count graphy things in the first place.
>>>
>>> qed  8-)
>>>
>>> Best regards,   jj
>>>
>>> P.S.: I am unable to find the paper online.
>>>
>>> * Paul Hanna <pauldhanna.math at gmail.com> [May 18. 2018 08:17]:
>>>
>>>> SeqFans,
>>>>         I'd like to share a surprising result, followed by an apparent
>>>> connection to finite automata that needs to be shown true/false.
>>>>
>>>> Consider the power series in x,  A(p,x) ,  such that
>>>>      [x^n] exp( n^p * x ) / A(p,x) = 0 for n > 0
>>>> where p is a positive integer.
>>>>
>>>> That is, the coefficient of x^n in  exp( n^p * x ) / A(p,x) equals 
>>>> 0 for
>>>> all n > 0.
>>>>
>>>> At first sight, one would expect A(p,x) to be an e.g.f. with 
>>>> fractional
>>>> coefficients.
>>>>
>>>> The unexpected result is that A(p,x) consists solely of integer
>>>> coefficients of x^k, for k>=0 (conjecture 1).
>>>> Examples:
>>>> https://oeis.org/A304322 (p=2)
>>>> https://oeis.org/A304323 (p=3)
>>>> https://oeis.org/A304324 (p=4)
>>>> https://oeis.org/A304325 (p=5)
>>>>
>>>> Further, the coefficient of x^n in the logarithmic derivative of 
>>>> A(p,x)
>>>
>>> wrt
>>>
>>>> x appears to equal "the number of connected n-state finite automata 
>>>> with
>>>
>>> p
>>>
>>>> inputs" (conjecture 2).
>>>> If this conjecture holds, then the above conjecture 1 is also true, 
>>>> and
>>>> thus A(p,x) consists solely of integer coefficients.
>>>> Examples:
>>>> https://oeis.org/A304312 (p=2)
>>>> https://oeis.org/A304313 (p=3)
>>>> https://oeis.org/A304314 (p=4)
>>>> https://oeis.org/A304315 (p=5)
>>>> These are found in the table https://oeis.org/A304321 of 
>>>> A'(p,x)/A(p,x)
>>>
>>> for
>>>
>>>> p >= 1.
>>>>
>>>> I wonder if someone could show that the following sequences are
>>>
>>> essentially
>>>
>>>> the same:
>>>> https://oeis.org/A304312  =  https://oeis.org/A006691
>>>> https://oeis.org/A304313  =  https://oeis.org/A006692
>>>>
>>>> The older sequences give a reference on the subject, and perhaps a
>>>
>>> formula
>>>
>>>> there could be used to show that these are indeed equivalent.
>>>>
>>>> Thanks,
>>>>        Paul
>>>>
>>>> -- 
>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>> -- 
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>> -- 
>> Seqfan Mailing list - http://list.seqfan.eu/
>
>
> -- 
> Seqfan Mailing list - http://list.seqfan.eu/