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.
Similar content being viewed by others
References
Albert, M., Bouvel, M., Fray, V.: Two first-order logics of permutations. J. Combin. Theory Ser. A. 171, 105158 (2020)
Atkinson, M.D., Beals, R.: Permutation involvement and groups. Q. J. Math. 52, 415–421 (2001)
Bóna, M.: Combinatorics of Permutations, 2nd edn. CRC Press, London (2012)
Bóna, M., Smith, R.: Pattern avoidance in permutations and their squares. Discrete Math. 342, 3194–3200 (2019)
Burcroff, A., Defant, C.: Pattern-avoiding permutation powers. Discrete Math. 343, 112017 (2020)
Lehtonen, E.: Permutation groups arising from pattern involvement. J. Algebraic Combin. 3, 251–298 (2020)
Stanely, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)
Vatter, V.: Permutation classes. In: Bóna, Miklós (ed.) Handbook of Enumerative Combinatorics. CRC Press, London (2005)
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
Corresponding author
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.
About this article
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
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-022-02602-y