دانلود رایگان مقاله جایگشت با قابلیت مرتب شدن توسط دو پشته در سری

abstract

We address the problem of the number of permutations that can be sorted by two stacks in series. We do this by first counting all such permutations of length less than 20 exactly, then using a numerical technique to obtain nineteen further coefficients approximately. Analysing these coefficients by a variety of methods we conclude that the OGF behaves as S(z) ∼ A(1 − μ · z) γ, where μ = 12.45 ± 0.15, γ = 1.5 ± 0.3, and A ≈ 0.02.

4. Conclusion

We have given an algorithm to generate the number of permutations of length n sortable by two stacks in series. We have obtained the coefficients in the corresponding generating function up to and including permutations of length 19. We have used differential approximants to calculate the next 19 coefficients approximately, and the next 30 ratios of successive terms, and then analysed the extended series. In this way we have estimated the asymptotics of the generating function. We believe that the series length needs to be at least doubled in order to get much more significant accuracy in estimates of the critical parameters. It is a source of some frustration that this problem appears to be so much harder than the corresponding problem of two stacks in parallel, for which an exact solution [2] is now available, as well as more than 1000 terms in the generating function.