About: Separable permutation

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Separable permutation Goto Sponge NotDistinct Permalink

An Entity of Type : yago:WikicatPermutationPatterns, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FSeparable_permutation

In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations may be characterized by the forbidden permutation patterns 2413 and 3142; they are also the permutations whose permutation graphs are cographs and the permutations that realize the series-parallel partial orders. It is possible to test in polynomial time whether a given separable permutation is a pattern in a larger permutation, or to find the longest common subpattern of two separable permutations.

Attributes	Values
rdf:type	yago:Abstraction100002137 yago:Cognition100023271 yago:Form105930736 yago:PsychologicalFeature100023100 yago:Structure105726345 yago:WikicatPermutationPatterns
rdfs:label	Separable Permutation (de) Separable permutation (en)
rdfs:comment	Eine separable Permutation ist in der Kombinatorik eine Permutation, die sich durch direkte oder schiefe Summen von trivialen Permutationen darstellen lässt. Die Permutationsmatrizen separabler Permutationen weisen damit eine rekursive Blockstruktur auf. Jeder separablen Permutation kann ein Separationsbaum, ein speziell bezeichneter geordneter Binärbaum, zugeordnet werden. Die Anzahl separabler Permutationen fester Länge wird durch die Schröder-Zahlen angegeben. Separable Permutationen werden unter anderem in der Sortierungstheorie untersucht. (de) In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations may be characterized by the forbidden permutation patterns 2413 and 3142; they are also the permutations whose permutation graphs are cographs and the permutations that realize the series-parallel partial orders. It is possible to test in polynomial time whether a given separable permutation is a pattern in a larger permutation, or to find the longest common subpattern of two separable permutations. (en)
foaf:depiction
dcterms:subject	Permutation patterns
Wikipage page ID	24360777 (xsd:integer)
Wikipage revision ID	1118529813 (xsd:integer)
Link from a Wikipage to another Wikipage	Schröder number Binary tree Permutation Permutation matrix Induced path Information Processing Letters Inversion (discrete mathematics) Generating function NP-complete SIAM Journal on Discrete Mathematics Very-large-scale integration Permutation patterns Lowest common ancestor Combinatorics Direct sum of permutations Stack-sortable permutation Algebraic geometry Forbidden graph characterization Partially ordered set Discrete Mathematics (journal) Order dimension Cograph Stack (data structure) Bootstrap percolation Polynomial time Series-parallel partial order Tree rotation Von Neumann neighborhood Permutation pattern Permutation graph Springer-Verlag Skew sum of permutations
sameAs	Separable permutation Separable permutation Separable permutation Separable permutation Separable permutation
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Harvtxt dbt:Multiple_image dbt:Mvar dbt:OEIS dbt:Reflist dbt:Sfnp
thumbnail	wiki-commons:Special:FilePath/Separable_Permutation_qtl1.svg?width=300
caption	Block structuring of the permutation matrix of the separable permutation and corresponding labeled binary tree; colors indicate depth in the tree (en)
direction	vertical (en)
image	Separable Permutation qtl1.svg (en) Separable permutation qtl2.svg (en)
has abstract	Eine separable Permutation ist in der Kombinatorik eine Permutation, die sich durch direkte oder schiefe Summen von trivialen Permutationen darstellen lässt. Die Permutationsmatrizen separabler Permutationen weisen damit eine rekursive Blockstruktur auf. Jeder separablen Permutation kann ein Separationsbaum, ein speziell bezeichneter geordneter Binärbaum, zugeordnet werden. Die Anzahl separabler Permutationen fester Länge wird durch die Schröder-Zahlen angegeben. Separable Permutationen werden unter anderem in der Sortierungstheorie untersucht. (de) In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations may be characterized by the forbidden permutation patterns 2413 and 3142; they are also the permutations whose permutation graphs are cographs and the permutations that realize the series-parallel partial orders. It is possible to test in polynomial time whether a given separable permutation is a pattern in a larger permutation, or to find the longest common subpattern of two separable permutations. (en)
gold:hypernym	Permutation
prov:wasDerivedFrom	wikipedia-en:Separable_permutation?oldid=1118529813&ns=0
page length (characters) of wiki page	11250 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Separable_permutation
is Link from a Wikipage to another Wikipage of	Schröder number Enumerations of specific permutation classes List of permutation topics Stack-sortable permutation Layered permutation Cograph Bootstrap percolation Series-parallel partial order Separability Permutation pattern Separable permutations
is Wikipage redirect of	Separable permutations
is foaf:primaryTopic of	wikipedia-en:Separable_permutation

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 54 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software