A326763 Number of permutations of length n and order at most 3 whose powers all avoid the pattern 132.
1, 1, 2, 5, 10, 16, 36, 65, 118, 232, 452, 800, 1622, 3042, 5758, 11077, 21712, 40204, 79718, 151628, 292994, 561954, 1103786, 2087696, 4115506, 7884446, 15393710, 29592074, 58229334, 111422134, 219575234, 422888473, 830617400, 1602832900, 3160618558, 6092881976
Offset: 0
Keywords
Links
- Miklós Bóna and Rebecca Smith, Pattern Avoidance in Permutations and Their Squares, Discrete Mathematics, 342 (2019), pp. 3194-3200; arXiv:1901.00026 [math.CO], 2019.
- Amanda Burcroff and Colin Defant, Pattern-Avoiding Permutation Powers, Discrete Mathematics, 343 (2020), 112017; arXiv:1907.09451 [math.CO], 2019.
Programs
-
SageMath
def a(n): return len([p for p in Permutations(n) if p*p == Permutations(n).identity() and p.avoids([1, 3, 2]) or p*p*p == Permutations(n).identity() and p.avoids([1, 3, 2]) and (p*p).avoids([1, 3, 2])]) # Andrey Zabolotskiy, Apr 13 2025
Formula
a(n) = A014495(n) + A370686(n), where the 1st (resp. 2nd) term counts 132-avoiding permutations of order 2 (resp. 1 or 3). - Andrey Zabolotskiy, Apr 13 2025
Extensions
Terms a(16) onwards using the formula from Andrey Zabolotskiy, Apr 14 2025