Three-letter-pattern avoiding permutations and functional equations

MaRDI QIDQ2500970zbMATH OpenFDO

Authors Ghassan Firro, Toufik Mansour

Publication date 30 August 2006

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

Full work available at URL https://eudml.org/doc/126661, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r51.html

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

generating functionrecurrence relations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Review text

Summary: We present an algorithm for finding a system of recurrence relations for the number of permutations of length \(n\) that satisfy a certain set of conditions. A rewriting of these relations automatically gives a system of functional equations satisfied by the multivariate generating function that counts permutations by their length and the indices of the corresponding recurrence relations. We propose an approach to describing such equations. In several interesting cases the algorithm recovers and refines, in a unified way, results on \(\tau\)-avoiding permutations and permutations containing \(\tau\) exactly once, where \(\tau\) is any classical, generalized, and distanced pattern of length three.

Recommendations

• Using functional equations to enumerate 1324-avoiding permutations
• scientific article; zbMATH DE number 2192121
• On multi-avoidance of generalized patterns.
• Permutations avoiding two patterns of length three
• scientific article; zbMATH DE number 2188398

Cited in

(22)

• Restricted k-ary words and functional equations
• Words restricted by 3-letter generalized multipermutation patterns
• The structure of invertible substitutions on a three-letter alphabet
• Kernel method and linear recurrence system
• Kernel method and system of functional equations
• Approaches for enumerating permutations with a prescribed number of occurrences of patterns
• The (ordinary) generating functions enumerating 123-avoiding words with r occurrences of each of 1, 2, , n are always algebraic
• Counting pattern avoiding permutations by number of movable letters
• Using functional equations to enumerate 1324-avoiding permutations
• Pattern avoidance in ordered set partitions
• Refining enumeration schemes to count according to permutation statistics
• Enumeration and Wilf-classification of permutations avoiding four patterns of length 4
• Enumerations on bargraphs
• scientific article; zbMATH DE number 2192121 (Why is no real title available?)
• scientific article; zbMATH DE number 5181754 (Why is no real title available?)
• Some transformation schemes involving the special (132)-avoiding permutation patterns and a binary coding: an algorithmic approach
• Some transformation schemes involving the special (132)-avoiding permutation patterns and a binary coding: an algorithmic approach
• On permutation patterns with constrained gap sizes
• Refined consecutive pattern enumeration via a generalized cluster method
• Combinatorial exploration: an algorithmic framework for enumeration
• Levels, ascents, and descents in restricted-growth words of type B
• Posets and permutations in the duplication-loss model: minimal permutations with \(d\) descents

This page was built for publication: Three-letter-pattern avoiding permutations and functional equations

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