Talk:Permutation pattern

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]

Or, to put it another way: did you read the two preceding sentences? It seems to me that the answers to all your questions are explained there. --JBL (talk) 06:42, 19 October 2016 (UTC)[reply]

I appreciate your time in clarifying this for me, and I apologize for being vague in my initial comment. Your description here is better than the article itself. The simple phrase, "biggest number is first" is already almost enough to deliver the message, which my own experience tells me, the current text does not "clearly state" to the general audience. The lead paragraph was so difficult to follow that I actually thought the page had been vandalized or edited carelessly, especially after finding a prior editor's related confusion.

I study many math-related articles on Wikipedia, and found this one particularly difficult to understand based on its lead paragraph. The topics covered in Wikipedia:Make technical articles understandable#Lead section and Wikipedia:Manual of Style/Lead section#Provide an accessible overview are what I'm talking about. Specifically,

The reader needs brief guidance in interpreting words such as "51342," which, lacking any typographic cues, appear to be simple integers or possibly strings. Relying on references to the long and detailed article Permutation to accomplish that places unnecessary burden on the reader, as compared to something like σ = 51342 (meaning, "largest value first, smallest next, then the middle value, etc.")
Although it may be common usage for a practitioner, the choice of "π" as the pattern name, especially for a pattern that starts with digit '3', is an understanding hazard, particularly for the general reader. (I propose including the brief parenthetical, "unrelated to the constant Pi".)

Thank you, Joel B. Lewis, David Eppstein ∈ Professors.

Christopher Ursich (talk) 17:59, 20 October 2016 (UTC)[reply]

Thanks, David Eppstein. The new version of the article is very good and clear.

Christopher Ursich (talk) 20:17, 26 October 2016 (UTC)[reply]

The leading example misses one case.

In the article it states that following permutation are found: "3··15, 32··5, 324··, and ·2·15" with 213 in the permutation 32415. Shouldn't be the permutation ··415 be included? The condition that all elements are relative in magnitude to each other is given. — Preceding unsigned comment added by Niiks (talk • contribs) 22:03, 12 November 2019 (UTC)[reply]

Yes, that is also an instance of the same pattern. —David Eppstein (talk) 22:29, 12 November 2019 (UTC)[reply]