A Combinatorial Bijection on k-Noncrossing Partitions View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2022-03-14

AUTHORS

Zhicong Lin, Dongsu Kim

ABSTRACT

For any integer k ≥ 2, we prove combinatorially the following Euler (binomial) transformation identity NCn+1(k)(t)=t∑i=0n(ni)NWi(k)(t),\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\rm{NC}}_{n + 1}^{(k)}(t) = t\sum\limits_{i = 0}^n {\left({\matrix{n \cr i \cr}} \right)} {\rm{NW}}_i^{(k)}(t),$$\end{document} where NCm(k)(t) (resp. NWm(k)(t)) is the sum of weights, tnumber of blocks, of partitions of {1,…,m} without k-crossings (resp. enhanced k-crossings). The special k = 2 and t = 1 case, asserting the Euler transformation of Motzkin numbers are Catalan numbers, was discovered by Donaghey 1977. The result for k = 3 and t = 1, arising naturally in a recent study of pattern avoidance in ascent sequences and inversion sequences, was proved only analytically. More... »

PAGES

1-28

References to SciGraph publications

  • 2015. Eulerian Numbers in NONE
  • 2016-06-18. A Generating Tree Approach to k-Nonnesting Partitions and Permutations in ANNALS OF COMBINATORICS
  • 2014-04-22. Counting Dyck Paths by Area and Rank in ANNALS OF COMBINATORICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00493-021-4262-x

    DOI

    http://dx.doi.org/10.1007/s00493-021-4262-x

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1146254931


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Research Center for Mathematics and Interdisciplinary Sciences, Shandong University, 266237, Qingdao, P.R. China", 
              "id": "http://www.grid.ac/institutes/grid.27255.37", 
              "name": [
                "Research Center for Mathematics and Interdisciplinary Sciences, Shandong University, 266237, Qingdao, P.R. China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lin", 
            "givenName": "Zhicong", 
            "id": "sg:person.012712701455.65", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012712701455.65"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematical Sciences, Korea Advanced Institute of Science and Technology, 34141, Daejeon, Republic of Korea", 
              "id": "http://www.grid.ac/institutes/grid.37172.30", 
              "name": [
                "Department of Mathematical Sciences, Korea Advanced Institute of Science and Technology, 34141, Daejeon, Republic of Korea"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kim", 
            "givenName": "Dongsu", 
            "id": "sg:person.013165111547.10", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013165111547.10"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s00026-014-0218-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033764311", 
              "https://doi.org/10.1007/s00026-014-0218-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4939-3091-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040757835", 
              "https://doi.org/10.1007/978-1-4939-3091-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00026-016-0321-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005053646", 
              "https://doi.org/10.1007/s00026-016-0321-1"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-03-14", 
        "datePublishedReg": "2022-03-14", 
        "description": "For any integer k \u2265 2, we prove combinatorially the following Euler (binomial) transformation identity NCn+1(k)(t)=t\u2211i=0n(ni)NWi(k)(t),\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\rm{NC}}_{n + 1}^{(k)}(t) = t\\sum\\limits_{i = 0}^n {\\left({\\matrix{n \\cr i \\cr}} \\right)} {\\rm{NW}}_i^{(k)}(t),$$\\end{document} where NCm(k)(t) (resp. NWm(k)(t)) is the sum of weights, tnumber of blocks, of partitions of {1,\u2026,m} without k-crossings (resp. enhanced k-crossings). The special k = 2 and t = 1 case, asserting the Euler transformation of Motzkin numbers are Catalan numbers, was discovered by Donaghey 1977. The result for k = 3 and t = 1, arising naturally in a recent study of pattern avoidance in ascent sequences and inversion sequences, was proved only analytically.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00493-021-4262-x", 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.8894462", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.8121651", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }
        ], 
        "keywords": [
          "Recent studies", 
          "weight", 
          "cases", 
          "number", 
          "study", 
          "avoidance", 
          "results", 
          "block", 
          "sequence", 
          "Motzkin numbers", 
          "pattern avoidance", 
          "sum", 
          "identity", 
          "transformation", 
          "inversion sequences", 
          "partition", 
          "Catalan numbers", 
          "sum of weights", 
          "transformation identities", 
          "k crossings", 
          "combinatorial bijection", 
          "bijection", 
          "Euler transformation", 
          "ascent sequences"
        ], 
        "name": "A Combinatorial Bijection on k-Noncrossing Partitions", 
        "pagination": "1-28", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1146254931"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00493-021-4262-x"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00493-021-4262-x", 
          "https://app.dimensions.ai/details/publication/pub.1146254931"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-09-02T16:07", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_925.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00493-021-4262-x"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4262-x'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4262-x'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4262-x'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4262-x'


     

    This table displays all metadata directly associated to this object as RDF triples.

    101 TRIPLES      21 PREDICATES      49 URIs      38 LITERALS      4 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00493-021-4262-x schema:about anzsrc-for:01
    2 anzsrc-for:08
    3 schema:author N6e6311e8d1bc4e66b46f3475f11de08f
    4 schema:citation sg:pub.10.1007/978-1-4939-3091-3
    5 sg:pub.10.1007/s00026-014-0218-9
    6 sg:pub.10.1007/s00026-016-0321-1
    7 schema:datePublished 2022-03-14
    8 schema:datePublishedReg 2022-03-14
    9 schema:description For any integer k ≥ 2, we prove combinatorially the following Euler (binomial) transformation identity NCn+1(k)(t)=t∑i=0n(ni)NWi(k)(t),\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\rm{NC}}_{n + 1}^{(k)}(t) = t\sum\limits_{i = 0}^n {\left({\matrix{n \cr i \cr}} \right)} {\rm{NW}}_i^{(k)}(t),$$\end{document} where NCm(k)(t) (resp. NWm(k)(t)) is the sum of weights, tnumber of blocks, of partitions of {1,…,m} without k-crossings (resp. enhanced k-crossings). The special k = 2 and t = 1 case, asserting the Euler transformation of Motzkin numbers are Catalan numbers, was discovered by Donaghey 1977. The result for k = 3 and t = 1, arising naturally in a recent study of pattern avoidance in ascent sequences and inversion sequences, was proved only analytically.
    10 schema:genre article
    11 schema:isAccessibleForFree true
    12 schema:isPartOf sg:journal.1136493
    13 schema:keywords Catalan numbers
    14 Euler transformation
    15 Motzkin numbers
    16 Recent studies
    17 ascent sequences
    18 avoidance
    19 bijection
    20 block
    21 cases
    22 combinatorial bijection
    23 identity
    24 inversion sequences
    25 k crossings
    26 number
    27 partition
    28 pattern avoidance
    29 results
    30 sequence
    31 study
    32 sum
    33 sum of weights
    34 transformation
    35 transformation identities
    36 weight
    37 schema:name A Combinatorial Bijection on k-Noncrossing Partitions
    38 schema:pagination 1-28
    39 schema:productId N427fc7adc5fa4c9d8e0255d34f5213fe
    40 N62f81468be7c4df68aefea4b4f518816
    41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1146254931
    42 https://doi.org/10.1007/s00493-021-4262-x
    43 schema:sdDatePublished 2022-09-02T16:07
    44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    45 schema:sdPublisher N891fd9aff5e049bc9e4735e0ca5e55c4
    46 schema:url https://doi.org/10.1007/s00493-021-4262-x
    47 sgo:license sg:explorer/license/
    48 sgo:sdDataset articles
    49 rdf:type schema:ScholarlyArticle
    50 N427fc7adc5fa4c9d8e0255d34f5213fe schema:name doi
    51 schema:value 10.1007/s00493-021-4262-x
    52 rdf:type schema:PropertyValue
    53 N62f81468be7c4df68aefea4b4f518816 schema:name dimensions_id
    54 schema:value pub.1146254931
    55 rdf:type schema:PropertyValue
    56 N6e6311e8d1bc4e66b46f3475f11de08f rdf:first sg:person.012712701455.65
    57 rdf:rest Na7912bfe22df4192bd53db24c38407f1
    58 N891fd9aff5e049bc9e4735e0ca5e55c4 schema:name Springer Nature - SN SciGraph project
    59 rdf:type schema:Organization
    60 Na7912bfe22df4192bd53db24c38407f1 rdf:first sg:person.013165111547.10
    61 rdf:rest rdf:nil
    62 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Mathematical Sciences
    64 rdf:type schema:DefinedTerm
    65 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Information and Computing Sciences
    67 rdf:type schema:DefinedTerm
    68 sg:grant.8121651 http://pending.schema.org/fundedItem sg:pub.10.1007/s00493-021-4262-x
    69 rdf:type schema:MonetaryGrant
    70 sg:grant.8894462 http://pending.schema.org/fundedItem sg:pub.10.1007/s00493-021-4262-x
    71 rdf:type schema:MonetaryGrant
    72 sg:journal.1136493 schema:issn 0209-9683
    73 1439-6912
    74 schema:name Combinatorica
    75 schema:publisher Springer Nature
    76 rdf:type schema:Periodical
    77 sg:person.012712701455.65 schema:affiliation grid-institutes:grid.27255.37
    78 schema:familyName Lin
    79 schema:givenName Zhicong
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012712701455.65
    81 rdf:type schema:Person
    82 sg:person.013165111547.10 schema:affiliation grid-institutes:grid.37172.30
    83 schema:familyName Kim
    84 schema:givenName Dongsu
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013165111547.10
    86 rdf:type schema:Person
    87 sg:pub.10.1007/978-1-4939-3091-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040757835
    88 https://doi.org/10.1007/978-1-4939-3091-3
    89 rdf:type schema:CreativeWork
    90 sg:pub.10.1007/s00026-014-0218-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033764311
    91 https://doi.org/10.1007/s00026-014-0218-9
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/s00026-016-0321-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005053646
    94 https://doi.org/10.1007/s00026-016-0321-1
    95 rdf:type schema:CreativeWork
    96 grid-institutes:grid.27255.37 schema:alternateName Research Center for Mathematics and Interdisciplinary Sciences, Shandong University, 266237, Qingdao, P.R. China
    97 schema:name Research Center for Mathematics and Interdisciplinary Sciences, Shandong University, 266237, Qingdao, P.R. China
    98 rdf:type schema:Organization
    99 grid-institutes:grid.37172.30 schema:alternateName Department of Mathematical Sciences, Korea Advanced Institute of Science and Technology, 34141, Daejeon, Republic of Korea
    100 schema:name Department of Mathematical Sciences, Korea Advanced Institute of Science and Technology, 34141, Daejeon, Republic of Korea
    101 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...