Applications of the finite state automata for counting restricted permutations and variations
DOI:
https://doi.org/10.2298/YJOR120211023BKeywords:
finite state automata, restricted permutations, restricted variations, exact enumerationAbstract
In this paper, we use the finite state automata to count the number of restricted permutations and the number of restricted variations. For each type of restricted permutations, we construct a finite state automaton able to recognize and enumerate them. We, also, discuss how it encompasses the other known methods for enumerating permutations with restricted position, and in one case, we establish connections with some other combinatorial structures, such as subsets and compositions.References
Baltić, V., "On the number of certain types of strongly restricted permutations", Applicable Analysis and Discrete Mathematics, 4(1) (2010) 119-135.
Baltić, V., "Applications of the finite state automata in the enumerative combinatorics", Proceedings of XXXVI Symposium on Operational Research, Ivanjica, 2009, 55-158.
Baltić, V., and Saković, M., "The counting of even and odd restricted permutations with the finite state automata ", Proceedings of XXXIX Symposium on Operational Research, Tara, 2012, 155-158.
Bergum, G.E., and Hoggat, V.E, "A combinatorial problem involving recursive sequences and tridiagonal matrices", The Fibonacci Quarterly, 16 (1978) 113-118.
Cvetkovic, D.M., Doob, M., and Sachs, H., Spectra of Graphs, Theory and Aplication, Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995.
Grimaldi, R.P., Discrete and Combinatorial Mathematics - An Applied Introduction, Addison Wesley, 1994.
Lehmer, D.H., "Permutations with strongly restricted displacements", Combinatorial Theory and its Applications II, North-Holland, Amsterdam-London, 1970, 755-770.
Stanley, R.P., Enumerative Combinatorics, Volume 2, Cambridge University Press, Cambridge, 1999.
The On-Line Encyclopedia of Integer Sequences, http://oeis.org
Downloads
Published
Issue
Section
License
Copyright (c) 2012 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
