Abstract
Lower bounds on the number of permutations p of {1, 2, . . . , n} satisfying |p i − i| ≤ d for all i are given.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baltić V.: On the number of certain types of restricted permutations. In: Abstracts of Talks presented at the International Mathematical Conference, Topics in Mathematical Analysis and Graph Theory (MAGT). Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. 18, 93–137 (2007).
Gould H.W.: An identity involving Stirling numbers. Ann. Inst. Stat. Math. 17, 265–269 (1965)
Jiang A., Mateescu R., Schwartz M., Bruck J.: Rank modulation for flash memories. In: Proceedings of IEEE International Symposium on Information Theory, pp. 1731–1735 (2008).
Jiang A., Schwartz M., Bruck J.: Error-correcting codes for rank modulation. In: Proceedings of IEEE International Symposium on Information Theory, pp. 1736–1740 (2008).
Kløve T.: Spheres of permutations under the infinity norm—permutations with limited displacement. Report no. 2008-376, Department of Informatics, University of Bergen, Norway. http://www.ii.uib.no/publikasjoner/texrap/pdf/2008-376.pdf.
Kløve T., Lin T.-T., Tsai S.-C., Tzeng W.-G.: Permutation arrays under the Chebyshev distance. IEEE Trans. Inform. Theory 56(6), 2611–2617 (2010)
Lagrange R.: Quelques résultats dans la métrique des permutations. Annales Scientifiques de l’École Normale Supérieure 79, 199–241 (1962)
Lehmer D.H.: Permutations with strongly restricted displacements. In: Erdös P., Rńyi A., Sós V.T. (eds.) Combinatorial Theory and its Applications II. North Holland Publication, Amsterdam, pp. 755–770 (1970).
Peterson W.W., Weldon E.J.: Error-Correcting Codes. MIT Press, Cambridge (1972)
Sloane N.J.A.: The On-Line Encyclopedia of Integer Sequences. http://www.research.att.com/~njas/sequences/.
Stanley R.P.: Enumerative Combinatorics, vol. I. Cambridge University Press, Cambridge (1997)
Tamo I., Schwartz M.: Correcting Limited-Magnitude Errors in the Rank-Modulation Scheme. IEEE Trans. Inform. Theory 56(6), 2551–2560 (2010)
van Lint J.H., Wilson R.M.: A Course in Combinatorics, 2nd edn. Cambridge University Press, Cambridge (2001)
Acknowledgments
This research was supported by The Norwegian Research Council.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Kløve, T. Lower bounds on the size of spheres of permutations under the Chebychev distance. Des. Codes Cryptogr. 59, 183–191 (2011). https://doi.org/10.1007/s10623-010-9454-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-010-9454-0