Luigi Santocanale
-
Bijective proofs for Eulerian numbers of types B and D
dmtcs:7413 -
Discrete Mathematics & Theoretical Computer Science,
March 10, 2023,
vol. 23 no. 2, special issue in honour of Maurice Pouzet
-
https://doi.org/10.46298/dmtcs.7413
Bijective proofs for Eulerian numbers of types B and DArticle
Authors: Luigi Santocanale
NULL
Luigi Santocanale
Let ⟨nk⟩, ⟨Bnk⟩, and ⟨Dnk⟩ be the
Eulerian numbers in the types A, B, and D, respectively -- that is, the number
of permutations of n elements with k descents, the number of signed
permutations (of n elements) with k type B descents, the number of even
signed permutations (of n elements) with k type D descents. Let Sn(t)=∑n−1k=0⟨nk⟩tk, Bn(t)=∑nk=0⟨Bnk⟩tk, and Dn(t)=∑nk=0⟨Dnk⟩tk. We give
bijective proofs of the identity Bn(t2)=(1+t)n+1Sn(t)−2ntSn(t2)
and of Stembridge's identity Dn(t)=Bn(t)−n2n−1tSn−1(t).
These bijective proofs rely on a representation of
signed permutations as paths. Using this representation we also establish a
bijective correspondence between even signed permutations and pairs (w,E)
with ([n],E) a threshold graph and w a degree ordering of ([n],E),
which we use to obtain bijective proofs of enumerative results for threshold
graphs.