Locally convex words and permutations

zbMATH Open1335.05004arXiv1410.7818MaRDI QIDQ281597FDOQ281597

Authors: Christopher Coscia, Jonathan Dewitt 

Publication date: 11 May 2016

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

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.

Full work available at URL: https://arxiv.org/abs/1410.7818

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

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

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)

Cites Work

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

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)