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.

1, 1, 2, 4, 10, 26, 66, 169, 437, 1130, 2926, 7597, 19749, 51381, 133812, 348755, 909464, 2372862, 6193720

Offset: 0

Author

Eric M. Schmidt, Nov 25 2017

Keywords

• nonn
• more

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.

Crossrefs

Cf. A005773 (analogous sequence for 123-avoiding permutations), A152225 (conjecturally analogous sequence for 213-avoiding permutations).

Programs

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])})