Attributes | Values |
---|
rdf:type
| |
Description
| - A class of permutations $\Pi$ is called closed if $\pi\subset\sigma\in\Pi$ implies $\pi\in\Pi$, where the relation $\subset$ is the natural containment of permutations. Let $\Pi_n$ be the set of all permutations of $1,2,\dots,n$ belonging to $\Pi$. W e investigate the counting functions $n\mapsto|\Pi_n|$ of closed classes. Our main result says that if $|\Pi_n|<2^{n-1}$ for at least one $n\ge 1$, then there is a unique $k\ge 1$ such that $F_{n,k}\le |\Pi_n|\le F_{n,k}\cdot n^c$ holds for all $n\ge 1$ with a constant $c>0$. Here $F_{n,k}$ are the generalized Fibonacci numbers which grow like powers of the largest positive root of $x^k-x^{k-1}-\cdots-1$. We characterize also the constant and the polynomial growth of closed permutation classes a nd give two more results on these.
- A class of permutations $\Pi$ is called closed if $\pi\subset\sigma\in\Pi$ implies $\pi\in\Pi$, where the relation $\subset$ is the natural containment of permutations. Let $\Pi_n$ be the set of all permutations of $1,2,\dots,n$ belonging to $\Pi$. W e investigate the counting functions $n\mapsto|\Pi_n|$ of closed classes. Our main result says that if $|\Pi_n|<2^{n-1}$ for at least one $n\ge 1$, then there is a unique $k\ge 1$ such that $F_{n,k}\le |\Pi_n|\le F_{n,k}\cdot n^c$ holds for all $n\ge 1$ with a constant $c>0$. Here $F_{n,k}$ are the generalized Fibonacci numbers which grow like powers of the largest positive root of $x^k-x^{k-1}-\cdots-1$. We characterize also the constant and the polynomial growth of closed permutation classes a nd give two more results on these. (en)
|
Title
| - On growth rates of closed permutation classes
- On growth rates of closed permutation classes (en)
|
skos:prefLabel
| - On growth rates of closed permutation classes
- On growth rates of closed permutation classes (en)
|
skos:notation
| - RIV/49777513:23520/03:00000145!RIV/2004/MSM/235204/N
|
http://linked.open.../vavai/riv/strany
| |
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| - P(LN00A056), Z(MSM 113200005), Z(MSM 235200001)
|
http://linked.open...iv/cisloPeriodika
| |
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/49777513:23520/03:00000145
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - permutation;closed class;permutation containment;Stanley-Wilf conjecture (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...odStatuVydavatele
| - US - Spojené státy americké
|
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...i/riv/nazevZdroje
| - Electronic Journal of Combinatorics
|
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...ocetUcastnikuAkce
| |
http://linked.open...nichUcastnikuAkce
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...v/svazekPeriodika
| |
http://linked.open...iv/tvurceVysledku
| - Kaiser, Tomáš
- Klazar, Martin
|
http://linked.open...n/vavai/riv/zamer
| |
issn
| |
number of pages
| |
http://localhost/t...ganizacniJednotka
| |