Locally convex words and permutations

MaRDI QIDQ281597zbMATH OpenFDO

Authors Christopher Coscia, Jonathan Dewitt

Publication date 11 May 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.7818, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p10

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

permutationsasymptoticswordsgenerating functionsinteger partitionspermutation patternstransfer matrices

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Combinatorial aspects of partitions of integers (05A17) Combinatorics on words (68R15)

Abstract: We introduce some new classes of words and permutations characterized by the second difference condition $pi(i-1)+pi(i+1)-2pi(i)leqk$, which we call the $k$-convexity condition. We demonstrate that for any sized alphabet and convexity parameter $k$, we may find a generating function which counts $k$-convex words of length $n$. We also determine a formula for the number of 0-convex words on any fixed-size alphabet for sufficiently large $n$ by exhibiting a connection to integer partitions. For permutations, we give an explicit solution in the case $k=0$ and show that the number of 1-convex and 2-convex permutations of length $n$ are $Theta(C_1^n)$ and $Theta(C_2^n)$, respectively, and use the transfer matrix method to give tight bounds on the constants $C_1$ and $C_2$. We also providing generating functions similar to the the continued fraction generating functions studied by Odlyzko and Wilf in the "coins in a fountain" problem.

Recommendations

• On convex permutations
• The combinatorics of convex permutominoes
• Permutations and words counted by consecutive patterns
• Permutations defining convex permutominoes
• Combinatorial aspects of \(L\)-convex polyominoes

Cites work

• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 4029575 (Why is no real title available?)
• scientific article; zbMATH DE number 729555 (Why is no real title available?)
• Combinatorial aspects of continued fractions
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Finite automata and pattern avoidance in words
• Finitely labeled generating trees and restricted permutations
• On convex permutations
• On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• Patterns in permutations and words.
• Restricted permutations and Chebyshev polynomials
• The Editor's Corner: n Coins in a Fountain

Cited in

(1)

• Blocksequences of \(k\)-local words

This page was built for publication: Locally convex words and permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281597)