|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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).
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|