Skip to main content

On a Conjecture About Strong Pattern Avoidance

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

In 2019, Bóna and Smith introduced the definition of strong pattern avoidance, that is, a permutation \(\pi \) strongly avoids a pattern \(\sigma \) if \(\pi \) and \(\pi ^2\) both avoid \(\sigma \). Let \(SAv_n(\sigma _1,\sigma _2,...,\sigma _r)\) denote the set of permutations in \(S_n\) that strongly avoid the patterns \(\sigma _1,\sigma _2,...,\sigma _r\). In this note, we prove that \(|SAv_n(321,1342)|=2F_{n+2}-n-2\) for every positive integer n, where \(F_n\) is the n-th Fibonacci number under the initial conditions \(F_1=F_2=1\). This gives an affirmative answer to a conjecture proposed by Burcroff and Defant.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Albert, M., Bouvel, M., Fray, V.: Two first-order logics of permutations. J. Combin. Theory Ser. A. 171, 105158 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  2. Atkinson, M.D., Beals, R.: Permutation involvement and groups. Q. J. Math. 52, 415–421 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bóna, M.: Combinatorics of Permutations, 2nd edn. CRC Press, London (2012)

    MATH  Google Scholar 

  4. Bóna, M., Smith, R.: Pattern avoidance in permutations and their squares. Discrete Math. 342, 3194–3200 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  5. Burcroff, A., Defant, C.: Pattern-avoiding permutation powers. Discrete Math. 343, 112017 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  6. Lehtonen, E.: Permutation groups arising from pattern involvement. J. Algebraic Combin. 3, 251–298 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  7. Stanely, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)

    Book  Google Scholar 

  8. Vatter, V.: Permutation classes. In: Bóna, Miklós (ed.) Handbook of Enumerative Combinatorics. CRC Press, London (2005)

    Google Scholar 

Download references

Acknowledgements

We are very grateful to the anonymous referees for their useful suggestions and comments.

Funding

The research of the work was partially supported by the Hainan Provincial Natural Science Foundation of China (No. 122RC652) and the National Natural Science Foundation of China (No. 12061030; No. 61962018).

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Junyao Pan.

Ethics declarations

Conflict of interest

In this paper, there is no experimental or computer calculated data, and there is only logical proof.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pan, J. On a Conjecture About Strong Pattern Avoidance. Graphs and Combinatorics 39, 2 (2023). https://doi.org/10.1007/s00373-022-02602-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-022-02602-y

Keywords

Mathematics Subject Classification