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

    Let $\Bigl\langle\matrix{n\cr k}\Bigr\rangle$, $\Bigl\langle\matrix{B_n\cr k}\Bigr\rangle$, and $\Bigl\langle\matrix{D_n\cr k}\Bigr\rangle$ 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) = \sum_{k = 0}^{n-1} \Bigl\langle\matrix{n\cr k}\Bigr\rangle t^k$, $B_n(t) = \sum_{k = 0}^n \Bigl\langle\matrix{B_n\cr k}\Bigr\rangle t^k$, and $D_n(t) = \sum_{k = 0}^n \Bigl\langle\matrix{D_n\cr k}\Bigr\rangle t^k$. We give bijective proofs of the identity $$B_n(t^2) = (1 + t)^{n+1}S_n(t) - 2^n tS_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)$, which we use to obtain bijective proofs of enumerative results for threshold graphs.


    Volume: vol. 23 no. 2, special issue in honour of Maurice Pouzet
    Section: Special issues
    Published on: March 10, 2023
    Accepted on: January 27, 2023
    Submitted on: April 28, 2021
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic
    Funding:
      Source : OpenAIRE Graph
    • a cartographic quest between lambda-calculus, logic, and combinatorics; Funder: French National Research Agency (ANR); Code: ANR-21-CE48-0017

    Consultation statistics

    This page has been seen 393 times.
    This article's PDF has been downloaded 267 times.