Domino tiling
جیومیٹری میں، یوکلڈین طیارہ میں کسی خطے کی ڈومینو ٹائلنگ ڈومینوز کے ذریعہ خطے کا ایک ٹیسلیشن ہے، شکلیں جو دو یونٹ مربعوں کے اتحاد سے بنتی ہیں جو کنارے سے کنارے تک ملتی ہیں۔ مساوی طور پر، یہ گرڈ گراف میں ایک بہترین مماثلت ہے جو خطے کے ہر مربع کے مرکز میں ایک ورٹیکس رکھ کر اور دو عمودی حصوں کو جوڑ کر تشکیل دی گئی ہے جب وہ ملحقہ مربعوں سے مطابقت رکھتے ہیں۔ اونچائی کے افعال دو جہتوں میں باقاعدہ گرڈ پر ٹائلنگ کی کچھ کلاسوں کے لیے، اونچائی کے فنکشن کی وضاحت کرنا ممکن ہے جو ایک عدد کو گرڈ کے عمودی حصوں سے جوڑتا ہے۔ مثال کے طور پر، شطرنج کا تختہ کھینچیں، اونچائی 0 کے ساتھ نوڈ طے کریں، پھر کسی بھی نوڈ کے لیے اس تک جانے کا راستہ ہے۔ اس راستے پر ہر نوڈ کی اونچائی کی وضاحت کریں (یعنی مربعوں کے کونے) پچھلے نوڈ کی اونچائی جمع ایک ہونا اگر راستے کے دائیں طرف کا مربع سیاہ ہے، اور بصورت دیگر مائنس ایک۔ مزید تفصیلات میں مل سکتی ہیں۔ تھرسٹن کی اونچائی کی حالت اس بات کا تعین کرنے کے لیے ایک ٹیسٹ کی وضاحت کرتی ہے کہ آیا سادہ طور پر منسلک علاقہ، جو ہوائی جہاز میں یونٹ مربعوں کے اتحاد کے طور پر تشکیل پایا ہے، میں ڈومینو ٹائلنگ ہے۔ وہ ایک غیر ہدایت شدہ گراف بناتا ہے جس کے عمودی طور پر تین جہتی عدد جالی میں پوائنٹس (x, y, z) ہوتے ہیں، جہاں اس طرح کا ہر نقطہ چار پڑوسیوں سے جڑا ہوتا ہے: اگر x + y یکساں ہے، تو (x, y, z) (x + 1, y, z + 1)، (x−1, y, z + 1)، (x, y + 1, z−1)، اور (x, y−1, z−1) سے جڑا ہوتا ہے، جبکہ اگر x + y عجیب ہے، تو (x, y, z) (x + 1, y, z−1)، (x−1, y, z−1)، (x, y, z−1) سے جڑا ہوتا ہے۔ خطے کی حد، جسے (x، y) سطح میں انٹیجر پوائنٹس کی ترتیب کے طور پر دیکھا جاتا ہے، اس تین جہتی گراف میں ایک راستے پر منفرد طور پر (ایک بار ابتدائی اونچائی منتخب ہونے کے بعد) اٹھتی ہے۔ اس خطے کے ٹائل کے قابل ہونے کے لیے ایک ضروری شرط یہ ہے کہ اس راستے کو تین جہتوں میں ایک سادہ بند منحنی خطوط بنانے کے لیے بند ہونا چاہیے، تاہم، یہ شرط کافی نہیں ہے۔ باؤنڈری پاتھ کے زیادہ محتاط تجزیے کا استعمال کرتے ہوئے، تھرسٹن نے ایک ایسے خطے کی ٹائل ایبلٹی کے لیے ایک معیار دیا جو کافی کے ساتھ ساتھ ضروری بھی تھا۔ خطوں کے ٹائلنگ کی گنتی ڈومینوز کے ساتھ ایک آئتاکار کو ڈھانپنے کے طریقوں کی تعداد، جس کا حساب آزادانہ طور پر اور کے ذریعے کیا جاتا ہے، اس کے ذریعے دیا جاتا ہے جب m اور n دونوں عجیب ہوتے ہیں، تو فارمولا صحیح طریقے سے صفر ممکنہ ڈومینو ٹائلنگ تک کم ہو جاتا ہے۔ ایک خاص معاملہ اس وقت ہوتا ہے جب آئتاکار کو n ڈومینوز سے ٹائل کیا جاتا ہے: ترتیب فبونیکی ترتیب تک کم ہو جاتی ہے۔ ایک اور خاص معاملہ m = n = 0، 2، 4، 6، 8، 10، 12، کے ساتھ مربعوں کے لیے ہوتا ہے۔ یہ اعداد انہیں ایک سکیو سمیٹرک میٹرکس کے فافین کے طور پر لکھ کر پایا جا سکتا ہے جس کی آئجین ویلیوز واضح طور پر مل سکتی ہیں۔ اس تکنیک کا اطلاق ریاضی سے متعلق بہت سے مضامین میں کیا جا سکتا ہے، مثال کے طور پر، شماریاتی میکانکس میں ڈائمر-ڈائمر ارتباط فنکشن کے کلاسیکی، دو جہتی حساب میں۔ کسی خطے کے ٹیلنگ کی تعداد سرحدی حالات کے لیے بہت حساس ہوتی ہے، اور خطے کی شکل میں بظاہر معمولی تبدیلیوں کے ساتھ ڈرامائی طور پر تبدیل ہو سکتی ہے۔ اس کی مثال آرڈر n کے ایزٹیک ہیرے کی ٹائلنگ کی تعداد سے ملتی ہے، جہاں ٹائلنگ کی تعداد 2 (n + 1) n/2 ہے۔ اگر اس کی جگہ 2 کے بجائے بیچ میں 3 لمبی قطاروں کے ساتھ آرڈر n کے "آگمینٹڈ ایزٹیک ڈائمنڈ" سے لے لی جائے تو ٹائلنگ کی تعداد بہت کم تعداد D (n، n)، ایک ڈیلانوئے نمبر تک گر جاتی ہے، جس میں n میں سپر ایکسپونینشیل گروتھ کے بجائے صرف ایکسپونینشیل ہوتا ہے۔ صرف ایک لمبی درمیانی قطار کے ساتھ آرڈر n کے "کم شدہ ایزٹیک ڈائمنڈ" کے لیے، صرف ایک ٹائلنگ ہوتی ہے۔ ٹاٹامی ٹاٹامی ڈومینو (1x2 مستطیل) کی شکل میں جاپانی فرش کی چٹائیاں ہیں۔ وہ کمروں کو ٹائل کرنے کے لیے استعمال ہوتے ہیں، لیکن اضافی اصولوں کے ساتھ کہ انہیں کیسے رکھا جا سکتا ہے۔ خاص طور پر، عام طور پر، جنکشنوں پر تین تاتمی ملتے ہیں انہیں مبارک سمجھا جاتا ہے، جبکہ جنکشنوں پر چار ملتے ہیں وہ ناپاک ہوتے ہیں، اس لیے ایک مناسب تاتمی ٹائلنگ وہ ہوتی ہے جہاں کسی بھی کونے میں صرف تین تاتمی ملتے ہیں۔ تاتومی کے ذریعے ایک بے قاعدہ کمرے کو ٹائل کرنے کا مسئلہ جو ایک کونے میں تین سے ملتا ہے، این پی مکمل ہے۔ شماریاتی طبیعیات میں ایپلی کیشنز ایک دورانیے کے ڈومینو ٹائلنگ اور دو جہتی دورانیے کے جالی پر مکمل طور پر فرسٹریٹڈ آئزنگ ماڈل کی زمینی حالت کی ترتیب کے درمیان ایک سے ایک خط و کتابت ہے۔ یہ دیکھنے کے لیے، ہم نوٹ کرتے ہیں کہ زمینی حالت میں، اسپن ماڈل کے ہر پلاکیٹ میں بالکل ایک مایوس کن تعامل ہونا چاہیے۔ لہذا، دوہری جالی سے دیکھتے ہوئے، ہر مایوس کن کنارے کو 1x2 آئتاکار سے "ڈھانپا" جانا چاہیے، اس طرح کہ آئتاکار پوری جالی پر پھیلے ہوں اور اوورلیپ نہ ہوں، یا دوہری جالی کی ڈومینو ٹائلنگ نہ ہو۔ گاؤسی آزاد میدان بھی دیکھیں، عام صورتحال میں اونچائی کی تقریب کی اسکیلنگ کی حد (مثال کے طور پر، ایک بڑے ایزٹیک ہیرے کی کندہ شدہ ڈسک کے اندر) شطرنج بورڈ کا مسخ شدہ مسئلہ، ایک معیاری 8 × 8 شطرنج بورڈ (یا چیکر بورڈ) کے 62 مربع رقبے کے ڈومینو ٹائلنگ سے متعلق پہیلی۔ شماریاتی میکانکس نوٹ مزید پڑھنے کے لیے مجموعہیات بالکل قابل حل ماڈل لیٹیس ماڈل میچنگ (گراف تھیوری) شماریاتی میکانکس ٹائلنگ پہیلیاں