Talk:Permutation pattern

Mathematics B‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
B	This article has been rated as B-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

Gessel / Noonan-Zeilberger Conjecture

Another topic that should be on the PP page is the conjecture, sometimes attributed to Gessel, that the number of permutations of length n avoiding a finite set of forbidden patterns is always holonomic (P-recursive). Vince Vatter (talk) 19:56, 13 July 2010 (UTC)[reply]

Superpatterns

The Superpattern page should either be linked to from here or incorporated into this page. Vince Vatter (talk) 19:56, 13 July 2010 (UTC)[reply]

I just rewrote superpattern substantially; it doesn't look like it receives any attention at all. I vote in favor of incorporating it into this page. --Joel B. Lewis (talk) 18:42, 10 July 2011 (UTC)[reply]

Generalizations

The generalizations section should include a reference to Branden and Claesson's new article. — Preceding unsigned comment added by Vince Vatter (talk • contribs) 05:00, 28 February 2011 (UTC)[reply]

Applications

Are there any applications -- to real world problems or to other math/tcs problems -- of pattern matching/avoidance in permutations? 78.129.59.167 (talk) 21:39, 20 June 2011 (UTC)[reply]

Leading example makes no sense

This makes no sense:

For example, the permutation π = 391867452 contains the pattern σ = 51342, as can be seen in the highlighted subsequence of π = 391867452 (or π = 391867452 or π = 391867452 or π = 391867452). Each of the subsequences 91674, 91675, 91672, and 91452 is called a copy, instance, or occurrence of σ.

Christopher Ursich (talk) 19:57, 17 October 2016 (UTC)[reply]

Christopher.ursich, it makes sense to me. Maybe you could make a more precise comment? --JBL (talk) 20:05, 17 October 2016 (UTC)[reply]

Joel B. Lewis, how does string "391867452" contain string "51342"? What is the value of σ? Is it 51342? 91674? 91675? I understand that skipping digits is allowed, but that isn't enough to make this make sense. How can "91674" be a copy/instance/occurrence of "51342" when "51342" does not even contain the digit '9'? Christopher Ursich (talk) 15:51, 18 October 2016 (UTC)[reply]

Permutation patterns are not the same as subsequences. They are subsets of the permutation that have the same internal ordering, as our article clearly states. So 91674 is an instance of pattern 51342 because in 91674, the biggest number is first, the smallest is second, etc. —David Eppstein (talk) 16:06, 18 October 2016 (UTC)[reply]