|
%I #17 Mar 17 2020 11:56:47
%S 1,1,2,4,10,26,66,169,437,1130,2926,7597,19749,51381,133812,348755,
%T 909464,2372862,6193720
%N Number of equivalence classes of 132-avoiding permutations of [n], where two permutations are equivalent if they have the same set of pure descents.
%C 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).
%H Jean-Luc Baril, Sergey Kirgizov, Armen Petrossian, <a href="http://jl.baril.u-bourgogne.fr/forest.pdf">Forests and pattern-avoiding permutations modulo pure descents</a>, Permutation Patterns 2017, Reykjavik University, Iceland, June 26-30, 2017. See Section 5.
%o (Sage)
%o def DD(p) :
%o pure_descents = []
%o occur = 0
%o for i in range(len(p)-1) :
%o hi = p[i]; lo = p[i+1]
%o mask = ((1 << (hi - lo)) - 1) << lo
%o if hi > lo and not (occur & mask) :
%o pure_descents.append((hi, lo))
%o occur |= 1 << hi
%o pure_descents.sort()
%o return pure_descents
%o def a(n): return len({tuple(DD(p)) for p in Permutations(n, avoiding=[1,3,2])})
%Y Cf. A005773 (analogous sequence for 123-avoiding permutations), A152225 (conjecturally analogous sequence for 213-avoiding permutations).
%K nonn,more
%O 0,3
%A _Eric M. Schmidt_, Nov 25 2017
|
