View in EDS

The Möbius function of separable and decomposable permutations ☆ [☆] Jelínek and Steingrímsson were supported by grant No. 090038012 from the Icelandic Research Fund. Jelínek was also supported by grant Z130-N13 from the Austrian Science Foundation (FWF). Jelínková was supported by project 1M0021620838 of the Czech Ministry of Education.

Saved in:
Bibliographic Details
Title: The Möbius function of separable and decomposable permutations ☆ [☆] Jelínek and Steingrímsson were supported by grant No. 090038012 from the Icelandic Research Fund. Jelínek was also supported by grant Z130-N13 from the Austrian Science Foundation (FWF). Jelínková was supported by project 1M0021620838 of the Czech Ministry of Education.
Authors: Burstein, Alexander1 aburstein@howard.edu, Jelínek, Vít2 jelinek@kam.mff.cuni.cz, Jelínková, Eva3 eva@kam.mff.cuni.cz, Steingrímsson, Einar4 einar@alum.mit.edu
Source: Journal of Combinatorial Theory - Series A. Nov2011, Vol. 118 Issue 8, p2346-2364. 19p.
Subjects: Permutations, Mathematical formulas, Möbius function, Partially ordered sets, Embeddings (Mathematics), Mathematical decomposition, Combinatorics
Abstract: Abstract: We give a recursive formula for the Möbius function of an interval in the poset of permutations ordered by pattern containment in the case where π is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Möbius function in the case where σ and π are separable permutations. A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142. We also show that the Möbius function in the poset of separable permutations admits a combinatorial interpretation in terms of normal embeddings among permutations. A consequence of this interpretation is that the Möbius function of an interval of separable permutations is bounded by the number of occurrences of σ as a pattern in π. Another consequence is that for any separable permutation π the Möbius function of is either 0, 1 or −1. [Copyright &y& Elsevier]
Copyright of Journal of Combinatorial Theory - Series A is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 65053226
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: The Möbius function of separable and decomposable permutations <superscript>☆</superscript> [☆] Jelínek and Steingrímsson were supported by grant No. 090038012 from the Icelandic Research Fund. Jelínek was also supported by grant Z130-N13 from the Austrian Science Foundation (FWF). Jelínková was supported by project 1M0021620838 of the Czech Ministry of Education.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Burstein%2C+Alexander%22">Burstein, Alexander</searchLink><relatesTo>1</relatesTo><i> aburstein@howard.edu</i><br /><searchLink fieldCode="AR" term="%22Jelínek%2C+Vít%22">Jelínek, Vít</searchLink><relatesTo>2</relatesTo><i> jelinek@kam.mff.cuni.cz</i><br /><searchLink fieldCode="AR" term="%22Jelínková%2C+Eva%22">Jelínková, Eva</searchLink><relatesTo>3</relatesTo><i> eva@kam.mff.cuni.cz</i><br /><searchLink fieldCode="AR" term="%22Steingrímsson%2C+Einar%22">Steingrímsson, Einar</searchLink><relatesTo>4</relatesTo><i> einar@alum.mit.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Combinatorial+Theory+-+Series+A%22">Journal of Combinatorial Theory - Series A</searchLink>. Nov2011, Vol. 118 Issue 8, p2346-2364. 19p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Permutations%22">Permutations</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+formulas%22">Mathematical formulas</searchLink><br /><searchLink fieldCode="DE" term="%22Möbius+function%22">Möbius function</searchLink><br /><searchLink fieldCode="DE" term="%22Partially+ordered+sets%22">Partially ordered sets</searchLink><br /><searchLink fieldCode="DE" term="%22Embeddings+%28Mathematics%29%22">Embeddings (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+decomposition%22">Mathematical decomposition</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorics%22">Combinatorics</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Abstract: We give a recursive formula for the Möbius function of an interval in the poset of permutations ordered by pattern containment in the case where π is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Möbius function in the case where σ and π are separable permutations. A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142. We also show that the Möbius function in the poset of separable permutations admits a combinatorial interpretation in terms of normal embeddings among permutations. A consequence of this interpretation is that the Möbius function of an interval of separable permutations is bounded by the number of occurrences of σ as a pattern in π. Another consequence is that for any separable permutation π the Möbius function of is either 0, 1 or −1. [Copyright &y& Elsevier]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Journal of Combinatorial Theory - Series A is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=65053226
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.jcta.2011.06.002
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 19
        StartPage: 2346
    Subjects:
      – SubjectFull: Permutations
        Type: general
      – SubjectFull: Mathematical formulas
        Type: general
      – SubjectFull: Möbius function
        Type: general
      – SubjectFull: Partially ordered sets
        Type: general
      – SubjectFull: Embeddings (Mathematics)
        Type: general
      – SubjectFull: Mathematical decomposition
        Type: general
      – SubjectFull: Combinatorics
        Type: general
    Titles:
      – TitleFull: The Möbius function of separable and decomposable permutations ☆ [☆] Jelínek and Steingrímsson were supported by grant No. 090038012 from the Icelandic Research Fund. Jelínek was also supported by grant Z130-N13 from the Austrian Science Foundation (FWF). Jelínková was supported by project 1M0021620838 of the Czech Ministry of Education.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Burstein, Alexander
      – PersonEntity:
          Name:
            NameFull: Jelínek, Vít
      – PersonEntity:
          Name:
            NameFull: Jelínková, Eva
      – PersonEntity:
          Name:
            NameFull: Steingrímsson, Einar
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 11
              Text: Nov2011
              Type: published
              Y: 2011
          Identifiers:
            – Type: issn-print
              Value: 00973165
          Numbering:
            – Type: volume
              Value: 118
            – Type: issue
              Value: 8
          Titles:
            – TitleFull: Journal of Combinatorial Theory - Series A
              Type: main
ResultId 1