[seqfan] Re: b-files for apparently matching sequences?

Torleiv.Klove at ii.uib.no Torleiv.Klove at ii.uib.no
Thu Jul 1 08:27:40 CEST 2010


For P(d,d,n) (for each fixed d) explisit generating functions are known, 
see:

T. Kløve, Generating Functions for the Number of Permutations with 
Limited Displacement,
The Electronic Journal of Combinatorics, R104, vol. 16(1), August 14, 2009.

T. Kløve, Spheres of permutations under the infinity norm - Permutations 
with limited displacement,
Reports in Informatics, Dept. of Informatics, Univ. Bergen, Report no. 
376, November 2008.
Online: http://www.ii.uib.no/publikasjoner/texrap/pdf/2008-376.pdf

The generating function gives a recursion of length 
2^{d-1}+binomial(2d,d)/2.

For d up to d=6, this is the shortest possible recursion, and I 
conjecture that this is the case for all d.

Torleiv



Joerg Arndt wrote:
> * Ron Hardin <rhhardin at att.net> [Jun 30. 2010 19:46]:
>> I've put up a catalog of results so far (updated irregularly) for all A B at
>> http://rhhardin.home.mindspring.com/current2.txt
>>
> 
> fine work!
> suggest splitting into auto-named files like A-B.txt
> 
> 
> 
>> if anybody wants to search for a formula.
>>
>> Note that a recurrence is likely to be huge.
>> http://www.research.att.com/~njas/sequences/A72853 has one out to a(n-34)
>> (which recurrence checked correct, by the way; though the a(n) listed is limited by 3 lines to less than 34 terms.)
>>
> 
> I am surprise by the 'size' of this recursion.
> 
> So by
> 
>> [...]
>>
>> A closed from 
>>> for the recurrence for P(A,B,n) would be a nice.
> 
> I hereby mean a procedure to generate a formula  ;-)
> 
> 
> Are you using Knuth 'perms with conditions on prefixes'
> algorithm for enumeration (by generation)?
> hm..., hardly, unless you have overclocked your CPU
> by a truly amazing factor:
> 
> 4 3 100 9276214007544699392817874641185108428600630913087280
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/





More information about the SeqFan mailing list