login
A295704
Number of equivalence classes of 132-avoiding permutations of [n], where two permutations are equivalent if they have the same set of pure descents.
0
1, 1, 2, 4, 10, 26, 66, 169, 437, 1130, 2926, 7597, 19749, 51381, 133812, 348755, 909464, 2372862, 6193720
OFFSET
0,3
COMMENTS
As defined in Baril et al., a pure descent of a permutation p is a pair of the form (p_i, p_(i+1)) such that p_i > p_(i+1) and there is no j < i such that p_i > p_j > p_(i+1).
LINKS
Jean-Luc Baril, Sergey Kirgizov, Armen Petrossian, Forests and pattern-avoiding permutations modulo pure descents, Permutation Patterns 2017, Reykjavik University, Iceland, June 26-30, 2017. See Section 5.
PROG
(Sage)
def DD(p) :
pure_descents = []
occur = 0
for i in range(len(p)-1) :
hi = p[i]; lo = p[i+1]
mask = ((1 << (hi - lo)) - 1) << lo
if hi > lo and not (occur & mask) :
pure_descents.append((hi, lo))
occur |= 1 << hi
pure_descents.sort()
return pure_descents
def a(n): return len({tuple(DD(p)) for p in Permutations(n, avoiding=[1, 3, 2])})
CROSSREFS
Cf. A005773 (analogous sequence for 123-avoiding permutations), A152225 (conjecturally analogous sequence for 213-avoiding permutations).
Sequence in context: A055775 A239076 A217988 * A090032 A090377 A151278
KEYWORD
nonn,more
AUTHOR
Eric M. Schmidt, Nov 25 2017
STATUS
approved