ماسة الأزتك

في الرياضيات التوافقية ، يتكون معين الأزتك من الرتبة n من جميع مربعات شبكة مربعة مراكزها ( x , y ) تحقق الشرط | x | + | y | ≤ n . هنا، n عدد صحيح ثابت، وتتكون الشبكة المربعة من مربعات الوحدة، حيث يمثل الأصل رأسًا لأربعة منها، بحيث يكون كل من x و y نصف عدد صحيح . ^{[ 1 ]}

تنص نظرية ماسة الأزتك على أن عدد تبليطات الدومينو لماسة الأزتك من الرتبة n هو 2n ^{( n + 1)/2} . ^{[ 2 ]} وتنص نظرية الدائرة القطبية الشمالية على أن التبليط العشوائي لماسة أزتك كبيرة يميل إلى التجمد خارج دائرة معينة. ^{[ 3 ]}

من الشائع تلوين البلاطات بالطريقة التالية. لنبدأ بتلوين المعين على شكل رقعة الشطرنج. كل بلاطة تغطي مربعًا أسود واحدًا فقط. البلاطات العمودية، حيث يغطي المربع العلوي مربعًا أسود، تُلوّن بلون، والبلاطات العمودية الأخرى بلون آخر. وينطبق الأمر نفسه على البلاطات الأفقية.

وقد عرّف كنوت أيضًا معينات الأزتك من الرتبة n + 1/2. ^{[ 4 ]} وهي متطابقة مع متعددات الأعداد المرتبطة بالأعداد المربعة المركزية .

من الأمور المفيدة جدًا لحساب عدد التبليطات النظر إلى المسارات غير المتقاطعة عبر الرسم البياني الموجه المقابل لها . نُعرّف رؤوس الرسم البياني بأنها تقع على الحواف اليسرى واليمنى للمربعات، متمركزة رأسيًا (لذا${\displaystyle y=k+{\frac {1}{2}}}$(لعدد صحيح k ). تُعرَّف الحواف الموجهة للرسم البياني بواسطة المتجهات الثلاثة (1,1) و(1,0) و(1,-1): لكل رأس، إذا أدى جمع متجه إلى رأس آخر وكان الخط الواصل بينهما يقع داخل معين الأزتك، فهناك حافة موجهة مقابلة. تُعرَّف المصادر بأنها الرؤوس ذات الإحداثي y السالب على الحواف اليسرى لمعين الأزتك، والمصارف بأنها الرؤوس ذات الإحداثي y السالب على الحواف اليمنى لمعين الأزتك. عندئذٍ، يُعرِّف التبليط مجموعة من المسارات غير المتقاطعة بالبدء من كل مصدر وتطبيق القواعد التالية بشكل متكرر:

• اختر النقطة (1,1) عند الرأس السفلي الأيسر للبلاطة العمودية،
• اختر مرتين (1,0) عند الرأس الأيسر للبلاطة الأفقية،
• اختر (1،-1) عند رأس الزاوية العلوية اليسرى للبلاطة العمودية.

تشبه هذه الحركات مسارات شرودر . على سبيل المثال، لنفترض شكلًا ماسيًا أزتيكيًا من الرتبة 2، وبعد رسم مخططه الموجه، يمكننا تسمية مصادره.${\displaystyle a_{a},a_{2}}$ومغاسلها${\displaystyle b_{1},b_{2}}$على الرسم البياني الموجه الخاص به، يمكننا حساب المسارات الموجهة من${\displaystyle a_{i}}$ل${\displaystyle b_{j}}$لكل زوج${\displaystyle (i,j)\in \{1,2\}\times \{1,2\}}$. يتصل${\displaystyle C_{i,j}}$نتيجة كل عملية عد. وهذا يعطينا مصفوفة،

${\displaystyle P_{2}={\begin{bmatrix}C_{1,1}&C_{1,2}\\C_{2,1}&C_{2,2}\\\end{bmatrix}}={\begin{bmatrix}6&2\\2&2\\\end{bmatrix}}.}$

وبناءً على مبرهنة ليندستروم-جيسيل-فينو ^{[ 5 ]} ، يكون عدد المسارات غير المتقاطعة للرتبة 2 هو

المحقق${\displaystyle (P_{2})=12-4=8=2^{2(2+1)/2},}$

يساوي عدد تبليطات الدومينو. وبشكل أعم، det${\displaystyle (P_{n})=}$عدد المسارات غير المتقاطعة من المصادر إلى المصارف.

لقد أثبت كلٌ من Eu و Fu أن مسارات شرودر وتبليطات معين الأزتك متناظرة . [ ^{6 ] ومن} ثم، فإن إيجاد محدد مصفوفة المسار${\displaystyle P_{n}}$سيعطينا ذلك عدد التبليطات لمعين الأزتك من الرتبة n .

هناك طريقة أخرى لتحديد عدد تبليطات معين الأزتك، وهي استخدام مصفوفات هانكل لأعداد شرودر الكبيرة والصغيرة ، ^{[ 6 ]} باستخدام طريقة ليندستروم-جيسل-فينو مرة أخرى. ^{[ 5 ]} إيجاد محدد هذه المصفوفات يعطينا عدد المسارات غير المتقاطعة لأعداد شرودر الصغيرة والكبيرة ، وهو تقابل مع التبليطات. أعداد شرودر الصغيرة هي${\displaystyle \{1,1,3,11,45,\cdots \}=\{y_{0},y_{1},y_{2},y_{3},y_{4},\cdots \}}$وأرقام شرودر الكبيرة هي${\displaystyle \{1,2,6,22,90,\cdots \}=\{x_{0},x_{1},x_{2},x_{3},x_{4},\cdots \}}$وبشكل عام، ستكون مصفوفتا هانكل لدينا هما

${\displaystyle H_{n}={\begin{bmatrix}x_{1}&x_{2}&\cdots &x_{n}\\x_{2}&x_{3}&\cdots &x_{n+1}\\\vdots &\vdots &&\vdots \\x_{n}&x_{n+1}&\cdots &x_{2n-1}\\\end{bmatrix}}}$ و ${\displaystyle G_{n}={\begin{bmatrix}y_{1}&y_{2}&\cdots &y_{n}\\y_{2}&y_{3}&\cdots &y_{n+1}\\\vdots &\vdots &&\vdots \\y_{n}&y_{n+1}&\cdots &y_{2n-1}\\\end{bmatrix}}}$

حيث ديت${\displaystyle (H_{n})=2^{n(n+1)/2}}$و${\displaystyle (G_{n})=2^{n(n-1)/2}}$أين${\displaystyle n\geq 1}$(صحيح أيضًا أن المحقق${\displaystyle (H_{n}^{0})=2^{n(n-1)/2}}$حيث تكون هذه مصفوفة هانكل مثل${\displaystyle H_{n}}$، لكنها بدأت بـ${\displaystyle x_{0}}$بدلاً من${\displaystyle x_{1}}$(للعنصر الأول في المصفوفة في الزاوية العلوية اليسرى).

يتطلب إيجاد تبليطات صالحة لمعين الأزتك حل مشكلة تغطية المجموعة الأساسية .${\displaystyle D=\{d_{1},d_{2},\dots ,d_{n}\}}$لتكن D مجموعة من قطع الدومينو 2×1 حيث يمكن وضع كل قطعة دومينو في D داخل المعين (دون تجاوز حدوده) عندما لا توجد قطع دومينو أخرى.${\displaystyle S=\{s_{1},s_{2},\dots ,s_{m}\}}$لتكن D مجموعة المربعات 1×1 الموجودة داخل المعين والتي يجب تغطيتها. يمكن إيجاد قطعتي دومينو داخل D لتغطية أي مربع حدودي داخل S، ويمكن إيجاد أربع قطع دومينو داخل D لتغطية أي مربع غير حدودي داخل S.

يُعرِّف${\displaystyle c(s_{i})\subset D}$أن تكون مجموعة قطع الدومينو التي تغطي المربع${\displaystyle s_{i}}$ودع${\displaystyle x_{i}}$ليكن متغيرًا مؤشرًا بحيث${\displaystyle x_{i}=1}$إذا${\displaystyle i^{th}}$يُستخدم رمز الدومينو في عملية التبليط، وصفر في غير ذلك. وبناءً على هذه التعريفات، يمكن اختزال مهمة تبليط شكل المعين الأزتيكي إلى مسألة إرضاء قيود مصاغة كبرنامج عدد صحيح ثنائي:

${\displaystyle \min \sum _{1\leq i\leq m}0\cdot x_{i}}$

رهناً بما يلي: ${\displaystyle \sum _{i\in c(s_{i})}x_{i}=1,}$ ل${\displaystyle 1\leq i\leq m}$، و${\displaystyle x_{i}\in \{0,1\}}$.

ال${\displaystyle i^{th}}$يضمن القيد أن المربع${\displaystyle s_{i}}$ستُغطى ببلاطة واحدة، ومجموعة من${\displaystyle m}$تضمن القيود تغطية كل مربع (دون وجود ثقوب في التغطية). يمكن حل هذه الصيغة باستخدام حزم البرمجة العددية القياسية . يمكن إنشاء قيود إضافية لفرض وضع قطع دومينو معينة، أو لضمان استخدام الحد الأدنى من قطع الدومينو الأفقية أو الرأسية، أو لإنشاء تبليطات مميزة.

يتمثل النهج البديل في تطبيق خوارزمية كنوت X لحصر التبليطات الصالحة للمشكلة.

• وايسشتاين، اريك دبليو. “أزتيك الماس” . عالم الرياضيات .