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 Nb28d26021b814edcb67d816fc6dcfa9b
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 N96c39799a7f1481c82f36f1ce9811698
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree true
17 schema:isPartOf Nf44d28f34d3645a8b2104f4f6662b77f
18 schema:name On Computing the Total Displacement Number via Weighted Motzkin Paths
19 schema:pagination 423-434
20 schema:productId N8c149859dc6c4f1c98458d153c842a45
21 Na28d96dc62774f8b8266f7a0e43638b1
22 Nd6f39a55b1dc4e46b00a0bec7dd50769
23 schema:publisher N9ae78e63b5c446f1aa14c5331cebdd5e
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 Naa11845f8e3c4cd8a9f96d95bff210a9
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 N081f83bf4c9848b2964dc38bb559491a rdf:first sg:person.012405565741.86
34 rdf:rest N9714d413a0044ef5b6194d464e681820
35 N12d86f012c304f008f97fb4177f09c1c rdf:first N6bc09e6522004310a71e785161aede92
36 rdf:rest N2ae28e4c209e41afb2abfa8f951971a6
37 N191079e10f0346d6a3fd01cac77cef0e rdf:first sg:person.011771624777.02
38 rdf:rest N081f83bf4c9848b2964dc38bb559491a
39 N2ae28e4c209e41afb2abfa8f951971a6 rdf:first N762433d5406d44bc88c52acdbef8054c
40 rdf:rest rdf:nil
41 N6bc09e6522004310a71e785161aede92 schema:familyName Puglisi
42 schema:givenName Simon J.
43 rdf:type schema:Person
44 N762433d5406d44bc88c52acdbef8054c schema:familyName Salmela
45 schema:givenName Leena
46 rdf:type schema:Person
47 N7f51b90087c74cf7b2c99864057bec0f schema:familyName Mäkinen
48 schema:givenName Veli
49 rdf:type schema:Person
50 N862608bae10643d78cd00c82d274acad rdf:first sg:person.013624103516.76
51 rdf:rest Na127fe3744b546d289f036ad3cf9d170
52 N8c149859dc6c4f1c98458d153c842a45 schema:name readcube_id
53 schema:value ef567a688074d91726470ee6b3446e6fb6bb7db9e5d0fe76e8fcf4753fd45245
54 rdf:type schema:PropertyValue
55 N96c39799a7f1481c82f36f1ce9811698 rdf:first N7f51b90087c74cf7b2c99864057bec0f
56 rdf:rest N12d86f012c304f008f97fb4177f09c1c
57 N9714d413a0044ef5b6194d464e681820 rdf:first sg:person.01271152363.00
58 rdf:rest N862608bae10643d78cd00c82d274acad
59 N9ae78e63b5c446f1aa14c5331cebdd5e schema:location Cham
60 schema:name Springer International Publishing
61 rdf:type schema:Organisation
62 Na127fe3744b546d289f036ad3cf9d170 rdf:first sg:person.012661117501.01
63 rdf:rest rdf:nil
64 Na28d96dc62774f8b8266f7a0e43638b1 schema:name dimensions_id
65 schema:value pub.1050241723
66 rdf:type schema:PropertyValue
67 Naa11845f8e3c4cd8a9f96d95bff210a9 schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 Nb28d26021b814edcb67d816fc6dcfa9b rdf:first sg:person.07417663741.28
70 rdf:rest N191079e10f0346d6a3fd01cac77cef0e
71 Nd6f39a55b1dc4e46b00a0bec7dd50769 schema:name doi
72 schema:value 10.1007/978-3-319-44543-4_33
73 rdf:type schema:PropertyValue
74 Nf44d28f34d3645a8b2104f4f6662b77f schema:isbn 978-3-319-44542-7
75 978-3-319-44543-4
76 schema:name Combinatorial Algorithms
77 rdf:type schema:Book
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)


...