Abstract
Counting the number of permutations of a given total displacement is equivalent to counting weighted Motzkin paths of a given area (Guay-Paquet and Petersen [11]). The former combinatorial problem is still open. In this work we show that this connection allows to construct efficient algorithms for counting and for sampling such permutations. These algorithms provide a tool to better understand the original combinatorial problem. A by-product of our approach is a different way of counting based on certain “building sequences” for Motzkin paths, which may be of independent interest.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Barcucci, E., Del Lungo, A., Pergola, E., Pinzani, R.: A construction for enumerating k-coloured Motzkin paths. In: Li, M., Du, D.-Z. (eds.) COCOON 1995. LNCS, vol. 959, pp. 254–263. Springer, Heidelberg (1995)
Bärtschi, A., Geissmann, B., Graf, D., Hruz, T., Penna, P., Tschager, T.: On computing the total displacement number via weighted Motzkin paths, June 2016, arXiv preprint. https://arxiv.org/abs/1606.05538
Bubley, R.: Randomized Algorithms: Approximation, Generation and Counting. Springer, London (2001)
Deutsch, E., Heinz, A.P.: A129181 Motzkin paths by area, Online Encyclopedia of Integer Sequences, June 2012. http://oeis.org/A129181
Deza, M., Huang, T.: Metrics on permutations, a survey. J. Comb. Inf. Syst. Sci. 23, 173–185 (1998)
Diaconis, P., Graham, R.L.: Spearman’s footrule as a measure of disarray. J. Roy. Stat. Soc.: Ser. B (Methodol.) 39(2), 262–268 (1977)
Donaghey, R., Shapiro, L.W.: Motzkin numbers. J. Comb. Theory: Ser. A 23(3), 291–301 (1977)
Gérard, O., Guay-Paquet, M., Heinz, A.P.: A062869 permutation with fixed total displacement, Online Encyclopedia of Integer Sequences, May 2014. https://oeis.org/A062869
Goulden, I.P., Jackson, D.M.: Combinatorial Enumeration. Dover Publications, Mineola (2004)
Greenberg, S., Pascoe, A., Randall, D.: Sampling biased lattice configurations using exponential metrics. In: 20th ACM-SIAM Symposium on Discrete Algorithms SODA 2009, pp. 76–85 (2009)
Guay-Paquet, M., Petersen, K.: The generating function for total displacement. Electron. J. Comb. 21(3), P3–37 (2014)
Humphreys, K.: A history and a survey of lattice path enumeration. J. Stat. Plan. Infer. 140(8), 2237–2254 (2010)
Irurozki, E.: Sampling and learning distance-based probability models for permutation spaces. Ph.D. thesis, University of the Basque Country, Donostia - San Sebastián, July 2014
Knuth, D.E.: The art of computer programming. Sorting Search. 3, 426–458 (1999)
Merlini, D.: Generating functions for the area below some lattice paths. In: Discrete Random Walks, DRW 2003, pp. 217–228 (2003)
Pergola, E., Pinzani, R., Rinaldi, S., Sulanke, R.: A bijective approach to the area of generalized Motzkin paths. Adv. Appl. Math. 28(3), 580–591 (2002)
Sulanke, R.A.: Moments of generalized Motzkin paths. J. Integer Sequences 3(00.1), 1–14 (2000)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Bärtschi, A., Geissmann, B., Graf, D., Hruz, T., Penna, P., Tschager, T. (2016). On Computing the Total Displacement Number via Weighted Motzkin Paths. In: Mäkinen, V., Puglisi, S., Salmela, L. (eds) Combinatorial Algorithms. IWOCA 2016. Lecture Notes in Computer Science(), vol 9843. Springer, Cham. https://doi.org/10.1007/978-3-319-44543-4_33
Download citation
DOI: https://doi.org/10.1007/978-3-319-44543-4_33
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-44542-7
Online ISBN: 978-3-319-44543-4
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
- Motzkin Paths
- Total Displacement
- Sequential Building Blocks
- Original Combinatorial Problem
- Construct Efficient Algorithms
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
