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 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)=n1k=0nktk, Bn(t)=nk=0Bnktk, and Dn(t)=nk=0Dnktk. 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)n2n1tSn1(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 447 times.
    This article's PDF has been downloaded 331 times.