Bijective proofs for Eulerian numbers in types B and D
share
Let ⟨n k⟩, ⟨B_n k⟩, and ⟨D_n k⟩ 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 S_n(t) = ∑_k = 0^n-1⟨n k⟩ t^k, B_n(t) = ∑_k = 0^n ⟨B_n k⟩ t^k, and D_n(t) = ∑_k = 0^n ⟨D_n k⟩ t^k. We give bijective proofs of the identity B_n(t^2) = (1 + t)^n+1S_n(t) - 2nt_n(t^2) and of Stembridge's identity D_n(t) = B_n (t) - n2^(n-1)tS_n-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).
READ FULL TEXT