Klärung eines von Stanleys Problemen mit katalanischen Nummern

Ich habe eine Frage zur Problemstellung (aa) in Stanleys Problemliste zu katalanischen Zahlen (siehe hier ), in der er 66 Mengen auflistet, deren Elemente durch die gezählt werden N katalanische Nummer C N .

Die Aussage scheint ungenau oder unvollständig zu sein. Ich kopiere es hier zur leichteren Orientierung:

[Wir betrachten] Äquivalenzklassen B von Wörtern im Alphabet [ N − 1 ] so, dass alle drei aufeinanderfolgenden Buchstaben eines beliebigen Wortes in B unter der Äquivalenzrelation verschieden sind u ich J v ∼ u J ich v für irgendwelche Worte, u , v und alle ich , J ∈ [ N − 1 ] befriedigend | ich − J | ≥ 2 . Für N = 3 , Äquivalenzklassen sind { ∅ }, {1}, {2}, {12}, {21}. Für N = 4 ein Vertreter jeder Klasse wird durch gegeben ∅ , 1, 2, 3, 12, 21, 13, 23, 32, 123, 132, 213, 321, 2132.

Nun, obwohl dies nicht angegeben ist, sind wir eindeutig an der kleinsten Äquivalenzbeziehung interessiert, die diese geordneten Paare enthält. Darüber hinaus scheinen wir höchstens über längere Worte nachzudenken N . Selbst unter Berücksichtigung dessen ist mir immer noch nicht klar, warum N = 4 wir haben nur eine Äquivalenzklasse für lange Wörter 4 . Zum Beispiel warum, zusätzlich zu [ 2132 ] , haben wir nicht auch die vier paarweise verschiedenen Äquivalenzklassen [ 1231 ] , [ 1321 ] , [ 3123 ] , [ 3213 ] ?

Betrachten wir zum Beispiel [ 1231 ] . Dann 1231 ist nicht gleichbedeutend mit 1321 , da wir nur Permutationen von Paaren betrachten ich J mit | ich − J | ≥ 2 . Insbesondere scheint es so 1231 keinem anderen Wort entspricht, so dass alle drei aufeinanderfolgenden Buchstaben verschieden sind.

Bitte beachten Sie, dass ich nicht nach einer Lösung des Zählproblems frage, sondern einfach versuche, die Aussage zu verstehen. Da diese Probleme recht bekannt sind und in vielen Kombinatorik-Kursen verwendet werden, wundert es mich etwas, dass die Aussage so unpräzise erscheint.

Wahrscheinlich möchten Sie vermeiden, einer ungültigen Anordnung gleichgestellt zu werden. dh, 1231 ∼ 1213 , 1321 ∼ 3121 , 3123 ∼ 1321 Und 3213 ∼ 3231
Es gibt keine Ungenauigkeit. Die Äquivalenzrelation ist explizit definiert, und es wird explizit darauf hingewiesen, dass alle Mitglieder einer Äquivalenzklasse B muss die Bedingung erfüllen, dass alle drei aufeinanderfolgenden Buchstaben verschieden sind.
@BrianM.Scott Ich stimme dir nicht zu. Auf welcher Menge ist die Äquivalenzrelation definiert? Nach der Aussage scheint es die Menge aller Wörter im Alphabet zu sein [ N − 1 ] so dass alle drei aufeinanderfolgenden Buchstaben verschieden sind. Natürlich kann man eine Äquivalenzrelation auf der Menge aller Wörter des Alphabets definieren [ N − 1 ] , und definieren Sie zusätzlich jedes Wort mit drei aufeinanderfolgenden Einträgen mit Wiederholungen als äquivalent zu dem leeren Wort. So hätte das Problem formuliert werden sollen.
@no: Es ist völlig klar, dass die Äquivalenzbeziehung auf der Menge der Wörter definiert ist [ N − 1 ] , sondern dass wir nur diese Äquivalenzklassen betrachten B so dass alle drei aufeinanderfolgenden Buchstaben eines beliebigen Wortes in B sind verschieden. Es besteht keine Notwendigkeit, Verrenkungen vorzunehmen, um eine andere Äquivalenzrelation zu definieren.
Es ist vollkommen grammatikalisch, „Wörter im Alphabet [ N − 1 ] so, dass alle drei aufeinanderfolgenden Buchstaben eines beliebigen Wortes in B sind verschieden" als Nominalphrase, in diesem Fall betrachten wir die Äquivalenzbeziehung über eine Teilmenge aller Wörter im Alphabet [ N − 1 ].
Isolieren wir jedoch die Nominalphrase „Äquivalenzklassen B von Wörtern im Alphabet [ N − 1 ] ", die wir dann weiter modifizieren durch "so dass beliebige drei aufeinanderfolgende Buchstaben eines beliebigen Wortes in B unterschiedlich sind" erhalten wir die von Stanley beabsichtigte Interpretation, in welchem ​​Fall, wie Will betont, die Schwierigkeit bezüglich der Wortlänge verschwindet.
@BrianM.Scott, wie Adrian Clough erklärt, gibt es zwei mögliche Lesarten der Aussage, die beide vollkommen gültig sind. Daher ist es nicht nur unhöflich, zu schreiben „es ist völlig klar“, es ist unwahr. Dies ist das erste Mal, dass ich eine Frage zu Math.SE schreibe; Ich hatte diese Frage zusammen mit einem Studenten geschrieben, um ihnen zu zeigen, wie man Fragen auf SE-Sites schreibt, aber es sind Kommentare wie Ihre, die mich zweimal überlegen lassen, bevor ich Studenten diese Site in Zukunft empfehle, da sie irreführend sind, und a Der Schüler hat möglicherweise nicht genug Erfahrung, um das zu verstehen.
@no: Ich stimme Adrians Analyse nicht zu.
@BrianM.Scott okay, willst du erklären warum?
Die Schwierigkeit, die ich bei Adrians erster Interpretation sehe, ist folgende B ist in dieser Lektüre außerhalb des Geltungsbereichs. Der Ausdruck „jedes Wort in B " hat keinen Platz in einem Relativsatz, der die Nominalphrase "Wörter im Alphabet" modifiziert [ N − 1 ] “ ist aber durchaus sinnvoll in einem Relativsatz, der die Nominalphrase „Äquivalenzklassen“ modifiziert B von Wörtern im Alphabet [ N − 1 ] ". Ich stimme zu, dass diese Passage von Stanley nicht leserfreundlich ist; ich habe sie die ersten Male nicht verstanden. Ich hätte es vorgezogen, die Äquivalenzbeziehung zuerst in einem separaten Satz definiert zu sehen.
Ah, das ist ein guter Punkt! Zeigt nur, dass Grammatik nicht sinnvoll bedeutet (-:

Antworten (1)

Ich denke, wenn irgendein Wort in der Äquivalenzklasse ein ungültiges Wort ist, dann sind alle Wörter in der Äquivalenzklasse ungültig. 1231 ist also ungültig, da es äquivalent zu 1213 ist, was ungültig ist. Für N = 4 Sie können kein langes Wort haben 5 oder größer. Dies ist keine zusätzliche Annahme, sondern folgt aus der Nebenbedingung. Um dies zu sehen, beachten Sie, dass die mittleren drei Buchstaben in einem Wort mit fünf Buchstaben nicht alle 2en sein können. Jeder 3 im Inneren des Wortes muss entweder eine 1 vorangehen oder folgen. Ebenso muss jeder 1 eine 3 vorangehen oder folgen Äquivalent). Jeder Buchstabe vor oder nach diesem Wort muss eine 1 oder 3 sein, aber beides ist nicht möglich.

Danke für diese Antwort. Wie ich in meinem obigen Kommentar anmerke, hätte man das Problem formulieren sollen, indem man eine Äquivalenzrelation für die Menge aller Wörter im Alphabet definiert [ 𝑛 − 1 ] , und indem zusätzlich jedes Wort mit drei aufeinanderfolgenden Einträgen mit Wiederholungen als äquivalent zu dem leeren Wort definiert wird. Dann kann man natürlich keine Wörter mit einer Länge größer als haben 5 für N = 4 .
Meine Lesart von Stanley, die meiner Meinung nach mit der von Brian Scott übereinstimmt, ist, dass man zuerst alle Äquivalenzklassen von Wörtern unter Stanleys Äquivalenzrelation betrachtet und dann eine Menge bildet, indem man diejenigen Äquivalenzklassen auswählt, in denen drei beliebige aufeinanderfolgende Buchstaben in irgendeinem Wort vorkommen Äquivalenzklasse, sind verschieden. Ich bin mir nicht sicher, ob es offensichtlich ist, ohne zu überprüfen, dass man keine Wörter mit einer Länge von mehr als haben kann 4 Wenn N = 4 , aber die Überprüfung in meiner Antwort scheint auszureichen, um dies zu zeigen. Für N = 5 Beachten Sie, dass Sie lange Wörter haben können 6 (z. B. 231423 ), aber nicht von Länge 7 oder mehr.
Ja, ich meinte nicht, dass es offensichtlich ist, aber es ist mir klar, warum man in diesem Fall keine Wörter mit einer Länge größer als hat 4 . Mein Problem lag in der Einrichtung des Problems, das meiner Meinung nach noch angegangen werden muss. Wie Sie richtig schreiben, ist Ihre eine Lesung, meine eine andere mögliche Lesung. So wie ich keinen Beweis eines Satzes lesen sollte, um zu verstehen, was der Satz aussagt, sollte ich mich nicht auf Beispiele verlassen, um zu verstehen, was ein Problem verlangt, insbesondere in einem Lehrbuch, das so weit verbreitet ist.
Klärung eines von Stanleys Problemen mit katalanischen Nummern
AntwortenHierDatenschutz-Bestimmungen1y, 0v