cp's OEIS Frontend

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.

%I A295704 #17 Mar 17 2020 11:56:47
%S A295704 1,1,2,4,10,26,66,169,437,1130,2926,7597,19749,51381,133812,348755,
%T A295704 909464,2372862,6193720
%N 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.
%C A295704 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 A295704 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 A295704 (Sage)
%o A295704 def DD(p) :
%o A295704     pure_descents = []
%o A295704     occur = 0
%o A295704     for i in range(len(p)-1) :
%o A295704         hi = p[i]; lo = p[i+1]
%o A295704         mask = ((1 << (hi - lo)) - 1) << lo
%o A295704         if hi > lo and not (occur & mask) :
%o A295704             pure_descents.append((hi, lo))
%o A295704         occur |= 1 << hi
%o A295704     pure_descents.sort()
%o A295704     return pure_descents
%o A295704 def a(n): return len({tuple(DD(p)) for p in Permutations(n, avoiding=[1,3,2])})
%Y A295704 Cf. A005773 (analogous sequence for 123-avoiding permutations), A152225 (conjecturally analogous sequence for 213-avoiding permutations).
%K A295704 nonn,more
%O A295704 0,3
%A A295704 _Eric M. Schmidt_, Nov 25 2017