Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Penney's game for pe ...
Article

Penney's game for permutations

Sergi Elizalde ORCID (1), Yixin Lin (1)
(1) Dartmouth College
Download article
Open on arXiv
Submitted on
August 18, 2025
Accepted on
April 30, 2026
Published on
July 8, 2026
Last modified on
September 7, 2026
Special issue 28
vol. 28:1, Permutation Patterns 2025
Special issues
DOI
10.46298/dmtcs.16361
License
arXiv.org - Non-exclusive license to distribute
Indicators
184
Views
188
Downloads

Penney's game for permutations

Sergi Elizalde ORCID (1), Yixin Lin (1)
(1) Dartmouth College
Abstract
We consider the permutation analogue of Penney's game for words. Two players, in order, each choose a permutation of length $k\ge3$; then a sequence of independent random values from a continuous distribution is generated, until the relative order of the last $k$ numbers coincides with one of the chosen permutations, making that player the winner. We compute the winning probabilities for all pairs of permutations of length 3 and some pairs of length 4, showing that, as in the original version for words, the game is non-transitive. Our proofs introduce new bijections for consecutive patterns in permutations. We also give some formulas to compute the winning probabilities more generally, and conjecture a winning strategy for the second player when $k$ is arbitrary.
Keywords
  • Combinatorics
  • 05A05, 60C05, 05A19
Mathematics Subject Classification 2020
  • 05A05 - Permutations, words, matrices
  • 91A05 - 2-person games
  • 91A60 - Probabilistic games; gambling
Preview
Loading PDF preview...
References

  1. Eric Babson and Einar Steingrímsson. Generalized permutation patterns and a classification of the Mahonian statistics. Sém. Lothar. Combin., 44:Art. B44b, 18, 2000.

  2. Miklós Bóna. On three different notions of monotone subsequences. In Permutation Patterns, volume 376 of London Math. Soc. Lecture Note Ser., pages 89–114. Cambridge Univ. Press, Cambridge, 2010.

    DOI : 10.1017/cbo9780511902499.005

  3. Anders Claesson. Generalized Pattern Avoidance. European Journal of Combinatorics, 22(7), 961–971, 2001.

    DOI : 10.1006/eujc.2001.0515

  4. Anders Claesson. From Hertzsprung’s problem to pattern-rewriting systems. Algebraic Combinatorics, 5(6), 1257–1277, 2022.

    DOI : 10.5802/alco.202

  5. Stanley Collings. Coin sequence probabilities and paradoxes. Bull. Inst. Math. Appl., 18(11- 12):227-232, 1982.

  6. Florence N. David et D. E. Barton, Combinatorial Chance. Hafner Publishing Co., New York, 1962.

  7. Tim Dwyer and Sergi Elizalde. Wilf equivalence relations for consecutive patterns. Advances in Applied Mathematics, 99, 134–157, 2018.

    DOI : 10.1016/j.aam.2018.04.007

  8. Sergi Elizalde. A survey of consecutive patterns in permutations. In Recent trends in combinatorics, volume 159 of IMA Vol. Math. Appl., pages 601-618. Springer, [Cham], 2016.

  9. Sergi Elizalde and Marc Noy. Consecutive patterns in permutations. Advances in Applied Mathematics, 30(1–2), 110–123, 2003.

    DOI : 10.1016/s0196-8858(02)00527-4

  10. Sergi Elizalde and Marc Noy. Clusters, generating functions and asymptotics for consecutive pat- terns in permutations. Adv. in Appl. Math, 49:351-374, 2012.

    DOI : 10.1016/j.aam.2012.08.003

  11. Daniel Felix. Optimal Penney Ante strategy via correlation polynomial identities. Electron. J. Combin., 13(1):Research Paper 35, 15, 2006.

    DOI : 10.37236/1061

  12. Martin Gardner. Mathematical games. Scientific American, 231(4):120-125, 1974.

    DOI : 10.1038/scientificamerican0774-116

  13. Leo J. Guibas and Andrew M. Odlyzko. String overlaps, pattern matching, and nontransitive games. J. Combin. Theory Ser. A, 30(2):183-208, 1981.

    DOI : 10.1016/0097-3165(81)90005-4

  14. Sergey Kitaev and Toufik Mansour. On multi-avoidance of generalized patterns. Ars Combin., 76:321-350, 2005.

    DOI : 10.1016/s0012-365x(02)00452-1

  15. Yixin Lin. Penney's game for permutations. Dartmouth College Ph.D. Dissertations, 258. 2024.

    DOI : 10.54550/eca2025v5s2r13

  16. A. N. Myers. Counting permutations by their rigid patterns. J. Combin. Theory Ser. A, 99(2):345- 357, 2002.

    DOI : 10.1006/jcta.2002.3279

  17. P. Tolstrup Nielsen. On the expected duration of a search for a fixed pattern in random data. IEEE Trans. Inform. Theory, IT-19:702-704, 1973.

    DOI : 10.1109/tit.1973.1055064

  18. OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Published electronically at http://oeis.org.

  19. Walter Penney. Problem 95: Penney-ante. Journal of Recreational Mathematics, 2(4):241, 1969.

    DOI : 10.1093/ww/9780199540884.013.u174752

  20. Rodica Simion and Frank W. Schmidt. Restricted permutations. European J. Combin., 6(4):383- 406, 1985.

    DOI : 10.1016/s0195-6698(85)80052-4

  21. Richard P. Stanley. Enumerative combinatorics. Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2012.