डोमिनोज़ टाइलिंग

8×8 वर्ग का डोमिनोज़ टाइलिंग

ज्यामिति में, यूक्लिडियन अंतरिक्ष में किसी क्षेत्र का डोमिनोज़ टाइलिंग डोमिनोज़ (गणित) द्वारा उस क्षेत्र के आकार का चौकोर आकार ग्रहण करता है, इस कारण दो इकाई वर्गों के संयोजन से इसके किनारे से मिलने वाली आकृतियाँ समतुल्य रूप से इस क्षेत्र के प्रत्येक वर्ग के केंद्र में शीर्ष और आसन्न वर्गों के अनुरूप होने पर दो शीर्षों को जोड़कर ग्रिड ग्राफ में मिलान (ग्राफ सिद्धांत) द्वारा प्रदर्शित होती हैं।

ऊंचाई फलन

दो आयामों में नियमित ग्रिड पर टाइलिंग के कुछ वर्गों के लिए किसी पूर्णांक को ग्रिड के शीर्ष (ग्राफ सिद्धांत) से जोड़कर ऊंचाई फलन को परिभाषित करना संभव हो जाता है। उदाहरण के लिए किसी शतरंज की बिसात बनाए जाने पर किसी नोड को $A_{0}$ ऊंचाई 0 के साथ ठीक करते हैं, फिर किसी भी नोड के लिए $A_{0}$ रास्ते का उपयोग करते है। इस पथ पर प्रत्येक नोड की ऊंचाई निर्धारित करें जो $A_{n+1}$ (अर्थात वर्गों के कोने) पिछले नोड की ऊंचाई होने के लिए $A_{n}$ प्लस मान के समान होती हैं, यदि पथ के दाईं ओर वर्ग से $A_{n}$ को $A_{n+1}$ और माइनस के समान है, ।

इसका अधिक विवरण केनयान & ओकोन्कुओव (2005) में पाया जा सकता है।

थर्स्टन की ऊंचाई की स्थिति

विलियम थर्सटेन (1990) यह निर्धारित करने के लिए परीक्षण का वर्णन करते हैं कि अंतरिक्ष में यूनिट वर्गों के संघ के रूप में गठित सरल रूप से जुड़े क्षेत्र में डोमिनोज़ टाइलिंग है या नहीं हैं। इस प्रकार यह अप्रत्यक्ष ग्राफ का रूप ले लेते हैं जिसके शीर्ष बिंदु (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+ 1,z+1), और (x,y − 1,z + 1) के क्षेत्र की सीमा, जिसे (x, y) समतल में पूर्णांक बिंदुओं के अनुक्रम के रूप में देखा जाता है, इस ग्राफ़ (असतत गणित) में पथ के लिए विशिष्ट रूप से (एक बार प्रारंभिक ऊँचाई चुनी जाती है) उठाती है। इस प्रका त्रि-आयामी ग्राफ़ को इस क्षेत्र के टाइलेबल होने के लिए आवश्यक शर्त यह है कि यह रास्ता तीन आयामों में साधारण बंद वक्र बनाने के लिए बंद होना चाहिए, चूंकि यह स्थिति पर्याप्त नहीं है। इस कारण सीमा पथ के अधिक सावधानीपूर्वक विश्लेषण का उपयोग करते हुए, थर्स्टन ने क्षेत्र की टाइलबिलिटी के लिए मानदंड दिया जो पर्याप्त होने के साथ-साथ आवश्यक भी था।

क्षेत्रों की टाइलिंग गिनती

एक 8×8 वर्ग का डोमिनोज़ टाइलिंग न्यूनतम संख्या में लंबे किनारे से लंबे किनारे तक जोड़े (केंद्र में 1 जोड़ी)। यह व्यवस्था 8x8 वर्ग की वैध टाटामी टाइलिंग भी है, जिसमें कोई चार डोमिनोज़ आंतरिक बिंदु पर स्पर्श नहीं करते हैं।

कवर करने के तरीकों की संख्या $m\times n$ साथ आयत ${\frac {mn}{2}}$ डोमिनोज़ हैं जिसके द्वारा स्वतंत्र रूप से गणना की गई टेम्परली & फिशर (1961) और कैस्टेलिन (1961) द्वारा इसका मान इस प्रकार दिया गया है

$$\prod _{j=1}^{\lceil {\frac {m}{2}}\rceil }\prod _{k=1}^{\lceil {\frac {n}{2}}\rceil }\left(4\cos ^{2}{\frac {\pi j}{m+1}}+4\cos ^{2}{\frac {\pi k}{n+1}}\right).$$

(sequence A099390 in the OEIS)

जब m और n दोनों विषम हों, तो सूत्र सही ढंग से शून्य संभावित डोमिनोज़ टाइलिंग को कम कर देता है।

टाइल लगाते समय विशेष स्थिति होता है। इस प्रकार $2\times n$ एन डोमिनोइज के साथ आयत: अनुक्रम फिबोनैकी अनुक्रम में कम हो जाता है।

m = n = 0, 2, 4, 6, 8, 10, 12, ... वाले वर्गों के लिए और विशेष स्थिति को प्रकट करती है

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... (sequence A004003 in the OEIS).

इन नंबरों को के फाफियन $mn\times mn$ कर्ण सममित आव्यूह के रूप में लिखकर पाया जा सकता है, जिसका आइजन मान ​​​​स्पष्ट रूप से पाया जा सकता है। इस विधि को कई गणित से संबंधित विषयों में लागू किया जाता हैं, उदाहरण के लिए, भौतिक यांत्रिकी में डिमर-डिमर सहसंबंधी फलन की द्वि-आयामी गणना में इसका उपयोग किया जाता हैं।

किसी क्षेत्र की टाइलों की संख्या सीमा की स्थितियों के प्रति बहुत संवेदनशील होती है, और क्षेत्र के आकार में स्पष्ट रूप से नगण्य परिवर्तनों के साथ नाटकीय रूप से परिवर्तित कर सकती है। यह क्रम n के एज़्टेक डायमंड की टाइलिंग की संख्या से स्पष्ट होता है, जहाँ टाइलिंग की संख्या 2^(n+1)n/2 है। यदि इसे 2 के अतिरिक्त मध्यम वर्ग में 3 लंबी पंक्तियों के साथ क्रम n के संवर्धित एज़्टेक डायमंज आकृति द्वारा प्रतिस्थापित किया जाता है, तो टाइलिंग की संख्या बहुत छोटी संख्या D(n,n) तक गिर जाती है, इस कारण डेलानॉय संख्या जिसमें केवल घातांक के अतिरिक्त मान उपस्थित होते है, उन्हें एन में सुपर-घातीय वृद्धि के लिए उपयोग किया जाता हैं। इस प्रकार ऑर्डर एन के कम एज़्टेक डायमंड के लिए केवल लंबी मध्य पंक्ति के साथ केवल टाइलिंग की जाती है।

• 

  ऑर्डर 4 का एक एज़्टेक हीरा, जिसमें 1024 डोमिनोज़ टाइलिंग हैं

• 

  एक संभावित टाइलिंग

तातामी

तातामी डोमिनोज़ (1x2 आयत) के आकार में जापानी फर्श की मैट हैं। जिसका उपयोग कमरों में टाइल लगाने के लिए किया जाता है, अपितु इसके अतिरिक्त नियमों के साथ कि उन्हें कैसे रखा जा सकता है। विशेष रूप से, सामान्यतः वह जंक्शन जहां तीन तातामी मिलते हैं उन्हें इसके लिए अत्यधित उपयोगी माना जाता है, जबकि जंक्शन जहां चार मिलते हैं उसे अनुपयोगी माना जाता हैं, इसलिए उचित तातामी टाइलिंग वह है जहां किसी भी कोने में केवल तीन तातामी मिलते हैं। इस प्रकार किसी तातमी द्वारा अनियमित कमरे को टाइल करने की समस्या जो कोने में तीन से मिलती है, जो एनपी के परिपूर्ण है।

सांख्यिकीय भौतिकी में अनुप्रयोग

किसी दो आयामी आवधिक नेट पर आवधिक डोमिनोज़ टाइलिंग और पूर्ण रूप से आइसिंग प्रारूप के जमीनी स्थिति के विन्यास के बीच पत्राचार का रूप माना जाता हैं। यह देखने के लिए, हम ध्यान दें कि जमीनी अवस्था में, घूर्णन प्रारूप के प्रत्येक पट्टिका में ठीक ज्यामितीय स्थिति के रूप में होनी चाहिए। इसलिए दोहरे नेट मानों से देखने पर प्रत्येक किनारे को 1x2 आयत द्वारा कवर किया जाना चाहिए, जैसे कि आयत पूरे नेट को प्रसारित करता हैं और ओवरलैप नहीं करते हैं, या दोहरे नेट का डोमिनोज़ टाइलिंग करते हैं।

यह भी देखें

• गाऊसी मुक्त क्षेत्र, सामान्य स्थिति में ऊंचाई फलन की स्केलिंग सीमा (उदाहरण के लिए, बड़े एज़्टेक डायमंड की स्वयं से उपयोग हुई डिस्क के अंदर रखा जाता हैं)
• कटे-फटे शतरंज की समस्या, मानक 8 × 8 शतरंज की [[बिसात]] के 62-वर्ग क्षेत्र के डोमिनोज़ टाइलिंग से संबंधित पहेली
• सांख्यिकीय यांत्रिकी

संदर्भ

• Barahona, Francisco (1982), "On the computational complexity of Ising spin glass models", Journal of Physics A: Mathematical and General, 15 (10): 3241–3253, Bibcode:1982JPhA...15.3241B, doi:10.1088/0305-4470/15/10/028, MR 0684591
• Erickson, Alejandro; Ruskey, Frank (2013), "Domino tatami covering is NP-complete", in Lecroq, Thierry; Mouchard, Laurent (eds.), Combinatorial Algorithms: 24th International Workshop, IWOCA 2013, Rouen, France, July 10-12, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8288, Heidelberg: Springer, pp. 140–149, arXiv:1305.6669, doi:10.1007/978-3-642-45278-9_13, MR 3162068, S2CID 12738241
• Kasteleyn, P. W. (1961), "The statistics of dimers on a lattice, I: The number of dimer arrangements on a quadratic lattice", Physica, 27 (12): 1209–1225, Bibcode:1961Phy....27.1209K, doi:10.1016/0031-8914(61)90063-5
• Kenyon, Richard; Okounkov, Andrei (2005), "What is ... a dimer?" (PDF), Notices of the American Mathematical Society, 52 (3): 342–343
• Klarner, David; Pollack, Jordan (1980), "Domino tilings of rectangles with fixed width", Discrete Mathematics, 32 (1): 45–52, doi:10.1016/0012-365X(80)90098-9, MR 0588907, Zbl 0444.05009
• Ruskey, Frank; Woodcock, Jennifer (2009), "Counting fixed-height Tatami tilings", Electronic Journal of Combinatorics, 16 (1): R126, doi:10.37236/215, MR 2558263
• Thurston, W. P. (1990), "Conway's tiling groups", American Mathematical Monthly, Mathematical Association of America, 97 (8): 757–773, doi:10.2307/2324578, JSTOR 2324578
• Temperley, H. N. V.; Fisher, Michael E. (1961), "Dimer problem in statistical mechanics – an exact result", Philosophical Magazine, 6 (68): 1061–1063, Bibcode:1961PMag....6.1061T, doi:10.1080/14786436108243366

अग्रिम पठन

• Bodini, Olivier; Latapy, Matthieu (2003), "Generalized tilings with height functions" (PDF), Morfismos, 7 (1): 47–68, arXiv:2101.08347
• Faase, F. J. (1998), "On the number of specific spanning subgraphs of the graphs $G\times P_{n}$", Ars Combinatoria, 49: 129–154, MR 1633083
• Hock, J. L.; McQuistan, R. B. (1984), "A note on the occupational degeneracy for dimers on a saturated two-dimenisonal lattice space", Discrete Applied Mathematics, 8: 101–104, doi:10.1016/0166-218X(84)90083-0, MR 0739603
• Kenyon, Richard (2000), "The planar dimer model with boundary: a survey", in Baake, Michael; Moody, Robert V. (eds.), Directions in mathematical quasicrystals, CRM Monograph Series, vol. 13, American Mathematical Society, pp. 307–328, ISBN 0-8218-2629-8, MR 1798998
• Propp, James (2005), "Lambda-determinants and domino-tilings", Advances in Applied Mathematics, 34 (4): 871–879, arXiv:math.CO/0406301, doi:10.1016/j.aam.2004.06.005, S2CID 15679557
• Sellers, James A. (2002), "Domino tilings and products of Fibonacci and Pell numbers", Journal of Integer Sequences, 5 (Article 02.1.2): 12, Bibcode:2002JIntS...5...12S
• Stanley, Richard P. (1985), "On dimer coverings of rectangles of fixed width", Discrete Applied Mathematics, 12: 81–87, doi:10.1016/0166-218x(85)90042-3, MR 0798013
• Wells, David (1997), The Penguin Dictionary of Curious and Interesting Numbers (revised ed.), London: Penguin, p. 182, ISBN 0-14-026149-4