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


...