On consecutive pattern-avoiding permutations of length 4, 5 and beyond
2018
We review and extend what is known about the generating functions for
consecutive pattern-avoiding permutations of length 4, 5 and beyond, and their
asymptotic behaviour. There are respectively, seven length-4 and twenty-five
length-5 consecutive-Wilf classes. D-finite differential equations are known
for the reciprocal of the exponential generating functions for four of the
length-4 and eight of the length-5 classes. We give the solutions of some of
these ODEs. An unsolved functional equation is known for one more class of
length-4, length-5 and beyond. We give the solution of this functional
equation, and use it to show that the solution is not D-finite. For three
further length-5 c-Wilf classes we give recurrences for two and a
differential-functional equation for a third. For a fourth class we find a new
algebraic solution. We give a polynomial-time algorithm to generate the
coefficients of the generating functions which is faster than existing
algorithms, and use this to (a) calculate the asymptotics for all classes of
length 4 and length 5 to significantly greater precision than previously, and
(b) use these extended series to search, unsuccessfully, for D-finite solutions
for the unsolved classes, leading us to conjecture that the solutions are not
D-finite. We have also searched, unsuccessfully, for differentially algebraic
solutions.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
13
References
0
Citations
NaN
KQI