On Computing the Total Displacement Number via Weighted Motzkin Paths View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2016

AUTHORS

Andreas Bärtschi , Barbara Geissmann , Daniel Graf , Tomas Hruz , Paolo Penna , Thomas Tschager

ABSTRACT

Counting the number of permutations of a given total displacement is equivalent to counting weighted Motzkin paths of a given area (Guay-Paquet and Petersen [11]). The former combinatorial problem is still open. In this work we show that this connection allows to construct efficient algorithms for counting and for sampling such permutations. These algorithms provide a tool to better understand the original combinatorial problem. A by-product of our approach is a different way of counting based on certain “building sequences” for Motzkin paths, which may be of independent interest. More... »

PAGES

423-434

References to SciGraph publications

Book

TITLE

Combinatorial Algorithms

ISBN

978-3-319-44542-7
978-3-319-44543-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-44543-4_33

DOI

http://dx.doi.org/10.1007/978-3-319-44543-4_33

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "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": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich"
          ], 
          "type": "Organization"
        }, 
        "familyName": "B\u00e4rtschi", 
        "givenName": "Andreas", 
        "id": "sg:person.07417663741.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07417663741.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Geissmann", 
        "givenName": "Barbara", 
        "id": "sg:person.011771624777.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011771624777.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Graf", 
        "givenName": "Daniel", 
        "id": "sg:person.012405565741.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012405565741.86"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hruz", 
        "givenName": "Tomas", 
        "id": "sg:person.01271152363.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01271152363.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Penna", 
        "givenName": "Paolo", 
        "id": "sg:person.013624103516.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tschager", 
        "givenName": "Thomas", 
        "id": "sg:person.012661117501.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012661117501.01"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-1-4471-0695-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003553330", 
          "https://doi.org/10.1007/978-1-4471-0695-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4471-0695-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003553330", 
          "https://doi.org/10.1007/978-1-4471-0695-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jspi.2010.01.020", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010707019"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0030840", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034468917", 
          "https://doi.org/10.1007/bfb0030840"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/aama.2001.0796", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047131479"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0097-3165(77)90020-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049658865"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611973068.9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088801138"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2016", 
    "datePublishedReg": "2016-01-01", 
    "description": "Counting the number of permutations of a given total displacement is equivalent to counting weighted Motzkin paths of a given area (Guay-Paquet and Petersen\u00a0[11]). The former combinatorial problem is still open. In this work we show that this connection allows to construct efficient algorithms for counting and for sampling such permutations. These algorithms provide a tool to better understand the original combinatorial problem. A by-product of our approach is a different way of counting based on certain \u201cbuilding sequences\u201d for Motzkin paths, which may be of independent interest.", 
    "editor": [
      {
        "familyName": "M\u00e4kinen", 
        "givenName": "Veli", 
        "type": "Person"
      }, 
      {
        "familyName": "Puglisi", 
        "givenName": "Simon J.", 
        "type": "Person"
      }, 
      {
        "familyName": "Salmela", 
        "givenName": "Leena", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-44543-4_33", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-44542-7", 
        "978-3-319-44543-4"
      ], 
      "name": "Combinatorial Algorithms", 
      "type": "Book"
    }, 
    "name": "On Computing the Total Displacement Number via Weighted Motzkin Paths", 
    "pagination": "423-434", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-44543-4_33"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ef567a688074d91726470ee6b3446e6fb6bb7db9e5d0fe76e8fcf4753fd45245"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050241723"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-44543-4_33", 
      "https://app.dimensions.ai/details/publication/pub.1050241723"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T23:55", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8697_00000274.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-44543-4_33"
  }
]
 

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/978-3-319-44543-4_33'

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/978-3-319-44543-4_33'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-44543-4_33'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-44543-4_33'


 

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

130 TRIPLES      23 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-44543-4_33 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Na13f363a5ce24d49bd94ee987f166fa8
4 schema:citation sg:pub.10.1007/978-1-4471-0695-1
5 sg:pub.10.1007/bfb0030840
6 https://doi.org/10.1006/aama.2001.0796
7 https://doi.org/10.1016/0097-3165(77)90020-6
8 https://doi.org/10.1016/j.jspi.2010.01.020
9 https://doi.org/10.1137/1.9781611973068.9
10 schema:datePublished 2016
11 schema:datePublishedReg 2016-01-01
12 schema:description Counting the number of permutations of a given total displacement is equivalent to counting weighted Motzkin paths of a given area (Guay-Paquet and Petersen [11]). The former combinatorial problem is still open. In this work we show that this connection allows to construct efficient algorithms for counting and for sampling such permutations. These algorithms provide a tool to better understand the original combinatorial problem. A by-product of our approach is a different way of counting based on certain “building sequences” for Motzkin paths, which may be of independent interest.
13 schema:editor N16b6028fa5634ab39ed4b646816f5aa2
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree true
17 schema:isPartOf Nf6bb3337603a4cbc841595e91168d847
18 schema:name On Computing the Total Displacement Number via Weighted Motzkin Paths
19 schema:pagination 423-434
20 schema:productId N04ca6ef2690e4b3891ad17212b6a91a6
21 N542f5389f5a94fc28b50d4e800ed4143
22 N68629a922e7d4ba3b25c5cdbffab11b2
23 schema:publisher Nc3f3808afc864bc8bbe8bf7bcddf5ce2
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050241723
25 https://doi.org/10.1007/978-3-319-44543-4_33
26 schema:sdDatePublished 2019-04-15T23:55
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N0b78f01fc1394c3f8f37c702df89d72c
29 schema:url http://link.springer.com/10.1007/978-3-319-44543-4_33
30 sgo:license sg:explorer/license/
31 sgo:sdDataset chapters
32 rdf:type schema:Chapter
33 N04ca6ef2690e4b3891ad17212b6a91a6 schema:name readcube_id
34 schema:value ef567a688074d91726470ee6b3446e6fb6bb7db9e5d0fe76e8fcf4753fd45245
35 rdf:type schema:PropertyValue
36 N0b4f00c39a6f448c80060e9527efde1a rdf:first sg:person.011771624777.02
37 rdf:rest N47ce04b0628f47cd9813163548cb591f
38 N0b78f01fc1394c3f8f37c702df89d72c schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N16b6028fa5634ab39ed4b646816f5aa2 rdf:first Nc7bdf75c9edd45caae035efb5276fbd5
41 rdf:rest N4a40be80504b4441ac2bca121d9e8f9e
42 N46cd6372b71c4efcac5cd79bdb1eb70c schema:familyName Puglisi
43 schema:givenName Simon J.
44 rdf:type schema:Person
45 N47ce04b0628f47cd9813163548cb591f rdf:first sg:person.012405565741.86
46 rdf:rest Nefad8fdbd15341779991ee57a3782bff
47 N4a40be80504b4441ac2bca121d9e8f9e rdf:first N46cd6372b71c4efcac5cd79bdb1eb70c
48 rdf:rest N5447abb7560348a8851d4c6f7841e35d
49 N542f5389f5a94fc28b50d4e800ed4143 schema:name dimensions_id
50 schema:value pub.1050241723
51 rdf:type schema:PropertyValue
52 N5447abb7560348a8851d4c6f7841e35d rdf:first N79f9fb09fdd4447ab7700f8b59dad6c9
53 rdf:rest rdf:nil
54 N6839ff010b4f4a3ca0cd147cafd4a75f rdf:first sg:person.013624103516.76
55 rdf:rest Nfd9aaf6dbaae4a1da5226c93ee1646ed
56 N68629a922e7d4ba3b25c5cdbffab11b2 schema:name doi
57 schema:value 10.1007/978-3-319-44543-4_33
58 rdf:type schema:PropertyValue
59 N79f9fb09fdd4447ab7700f8b59dad6c9 schema:familyName Salmela
60 schema:givenName Leena
61 rdf:type schema:Person
62 Na13f363a5ce24d49bd94ee987f166fa8 rdf:first sg:person.07417663741.28
63 rdf:rest N0b4f00c39a6f448c80060e9527efde1a
64 Nc3f3808afc864bc8bbe8bf7bcddf5ce2 schema:location Cham
65 schema:name Springer International Publishing
66 rdf:type schema:Organisation
67 Nc7bdf75c9edd45caae035efb5276fbd5 schema:familyName Mäkinen
68 schema:givenName Veli
69 rdf:type schema:Person
70 Nefad8fdbd15341779991ee57a3782bff rdf:first sg:person.01271152363.00
71 rdf:rest N6839ff010b4f4a3ca0cd147cafd4a75f
72 Nf6bb3337603a4cbc841595e91168d847 schema:isbn 978-3-319-44542-7
73 978-3-319-44543-4
74 schema:name Combinatorial Algorithms
75 rdf:type schema:Book
76 Nfd9aaf6dbaae4a1da5226c93ee1646ed rdf:first sg:person.012661117501.01
77 rdf:rest rdf:nil
78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
79 schema:name Information and Computing Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
82 schema:name Computation Theory and Mathematics
83 rdf:type schema:DefinedTerm
84 sg:person.011771624777.02 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
85 schema:familyName Geissmann
86 schema:givenName Barbara
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011771624777.02
88 rdf:type schema:Person
89 sg:person.012405565741.86 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
90 schema:familyName Graf
91 schema:givenName Daniel
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012405565741.86
93 rdf:type schema:Person
94 sg:person.012661117501.01 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
95 schema:familyName Tschager
96 schema:givenName Thomas
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012661117501.01
98 rdf:type schema:Person
99 sg:person.01271152363.00 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
100 schema:familyName Hruz
101 schema:givenName Tomas
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01271152363.00
103 rdf:type schema:Person
104 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
105 schema:familyName Penna
106 schema:givenName Paolo
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
108 rdf:type schema:Person
109 sg:person.07417663741.28 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
110 schema:familyName Bärtschi
111 schema:givenName Andreas
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07417663741.28
113 rdf:type schema:Person
114 sg:pub.10.1007/978-1-4471-0695-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003553330
115 https://doi.org/10.1007/978-1-4471-0695-1
116 rdf:type schema:CreativeWork
117 sg:pub.10.1007/bfb0030840 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034468917
118 https://doi.org/10.1007/bfb0030840
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1006/aama.2001.0796 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047131479
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1016/0097-3165(77)90020-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049658865
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1016/j.jspi.2010.01.020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010707019
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1137/1.9781611973068.9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801138
127 rdf:type schema:CreativeWork
128 https://www.grid.ac/institutes/grid.5801.c schema:alternateName Swiss Federal Institute of Technology in Zurich
129 schema:name Department of Computer Science, ETH Zurich
130 rdf:type schema:Organization
 




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


...