Domino tiling
জ্যামিতিতে, ইউক্লিডীয় সমতলে একটি অঞ্চলের ডমিনো টাইলিং হল ডমিনো দ্বারা অঞ্চলের একটি টেসেলেশন, যা দুটি একক বর্গক্ষেত্রের মিলন দ্বারা গঠিত আকৃতি যা প্রান্ত থেকে প্রান্ত পর্যন্ত মিলিত হয়। সমতুল্যভাবে, এটি অঞ্চলের প্রতিটি বর্গক্ষেত্রের কেন্দ্রে একটি শীর্ষ স্থাপন করে এবং দুটি শীর্ষকে সংযুক্ত করে গঠিত গ্রিড গ্রাফের একটি নিখুঁত মিল যখন তারা সংলগ্ন বর্গক্ষেত্রের সাথে মিলে যায়। উচ্চতার ফাংশন দুটি মাত্রায় একটি নিয়মিত গ্রিডে কিছু শ্রেণীর টিলিংয়ের জন্য, গ্রিডের শীর্ষে একটি পূর্ণসংখ্যার সাথে যুক্ত একটি উচ্চতা ফাংশন সংজ্ঞায়িত করা সম্ভব। উদাহরণস্বরূপ, একটি দাবা বোর্ড আঁকুন, উচ্চতা 0 সহ একটি নোড ঠিক করুন, তারপরে যে কোনও নোডের জন্য এটি থেকে একটি পথ রয়েছে। এই পথে প্রতিটি নোডের উচ্চতা নির্ধারণ করুন (অর্থাৎ। বর্গক্ষেত্রের কোণগুলি) পূর্ববর্তী নোডের উচ্চতা যোগ এক হতে হবে যদি পথের ডানদিকে বর্গটি কালো হয় এবং অন্যথায় বিয়োগ এক হয়। আরও বিস্তারিত পাওয়া যাবে। থার্স্টনের উচ্চতার অবস্থা সমতলে একক বর্গক্ষেত্রের মিলন হিসাবে গঠিত একটি সহজ-সংযুক্ত অঞ্চলে একটি ডোমিনো টাইলিং আছে কিনা তা নির্ধারণের জন্য একটি পরীক্ষা বর্ণনা করে। তিনি একটি অনির্দিষ্ট গ্রাফ তৈরি করেন যার শীর্ষে ত্রিমাত্রিক পূর্ণসংখ্যা জালকের বিন্দু (x, y, z) থাকে, যেখানে এই ধরনের প্রতিটি বিন্দু চারটি প্রতিবেশী বিন্দুর সাথে সংযুক্ত থাকেঃ যদি x + y জোড় হয়, তবে (x, y, z) (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 = 0,2,4,6,8,10,12 সহ বর্গগুলির ক্ষেত্রে ঘটে। এই সংখ্যাগুলি একটি তির্যক-প্রতিসম ম্যাট্রিক্সের ফাফিয়ান হিসাবে লিখে পাওয়া যেতে পারে যার আইগেনভ্যালুগুলি স্পষ্টভাবে পাওয়া যায়। এই কৌশলটি গণিত-সম্পর্কিত অনেক বিষয়ে প্রয়োগ করা যেতে পারে, উদাহরণস্বরূপ, পরিসংখ্যানগত বলবিজ্ঞানে ডাইমার-ডাইমার কোরিলেটর ফাংশনের ধ্রুপদী, দ্বিমাত্রিক গণনায়। একটি অঞ্চলের টিলিংয়ের সংখ্যা সীমানা অবস্থার প্রতি অত্যন্ত সংবেদনশীল এবং এই অঞ্চলের আকৃতিতে আপাতদৃষ্টিতে সামান্য পরিবর্তনের সাথে নাটকীয়ভাবে পরিবর্তিত হতে পারে। এটি এন ক্রমের অ্যাজটেক হীরার টিলিংয়ের সংখ্যা দ্বারা চিত্রিত হয়, যেখানে টিলিংয়ের সংখ্যা 2 (এন + 1) এন/2। যদি এটি 2-এর পরিবর্তে মাঝখানে 3 টি দীর্ঘ সারি সহ ক্রম n-এর "বর্ধিত অ্যাজটেক হীরা" দ্বারা প্রতিস্থাপিত হয়, তবে টিলিংয়ের সংখ্যা অনেক ছোট সংখ্যা D (n, n)-এ নেমে আসে, যা একটি ডেলানয় সংখ্যা, যার n-এ অতি-ব্যতিক্রমী বৃদ্ধির পরিবর্তে কেবল সূচকীয় রয়েছে। শুধুমাত্র একটি দীর্ঘ মাঝের সারি সহ ক্রম n-এর "হ্রাসকৃত অ্যাজটেক হীরা"-এর জন্য, শুধুমাত্র একটি টাইলিং রয়েছে। তাতামি তাতামি একটি ডোমিনো (1x2 আয়তক্ষেত্র) আকৃতির জাপানি মেঝের মাদুর। এগুলি কক্ষগুলি টাইল করতে ব্যবহৃত হয়, তবে সেগুলি কীভাবে স্থাপন করা যেতে পারে সে সম্পর্কে অতিরিক্ত নিয়ম রয়েছে। বিশেষত, সাধারণত, যে সংযোগস্থলে তিনটি তাতামি মিলিত হয় সেগুলিকে শুভ বলে মনে করা হয়, যেখানে চারটি মিলিত হয় সেই সংযোগস্থলগুলিকে অশুভ বলে মনে করা হয়, তাই একটি যথাযথ তাতামি টাইলিং এমন একটি জায়গা যেখানে যে কোনও কোণে মাত্র তিনটি তাতামি মিলিত হয়। একটি অনিয়মিত ঘর টাটামি দ্বারা টাইল করার সমস্যা যা তিন থেকে এক কোণে মিলিত হয় তা এনপি-সম্পূর্ণ। পরিসংখ্যানগত পদার্থবিজ্ঞানে প্রয়োগ একটি পর্যায়ক্রমিক ডমিনো টাইলিং এবং একটি দ্বিমাত্রিক পর্যায়ক্রমিক জালকের উপর সম্পূর্ণরূপে ফ্রাস্ট্রেটেড আইসিং মডেলের স্থল অবস্থার বিন্যাসের মধ্যে এক-থেকে-এক যোগাযোগ রয়েছে। এটি দেখার জন্য, আমরা লক্ষ্য করি যে স্থল অবস্থায়, স্পিন মডেলের প্রতিটি প্ল্যাকেটে অবশ্যই ঠিক একটি হতাশ মিথস্ক্রিয়া থাকতে হবে। অতএব, দ্বৈত জাল থেকে দেখলে, প্রতিটি হতাশ প্রান্তকে অবশ্যই একটি 1x2 আয়তক্ষেত্র দ্বারা "আচ্ছাদিত" হতে হবে, যাতে আয়তক্ষেত্রগুলি পুরো জালটি প্রসারিত করে এবং ওভারল্যাপ না করে, বা দ্বৈত জালের একটি ডোমিনো টাইলিং। আরও দেখুন গাউসীয় মুক্ত ক্ষেত্র, সাধারণ পরিস্থিতিতে উচ্চতা ক্রিয়াকলাপের স্কেলিং সীমা (যেমন, একটি বড় অ্যাজটেক হীরার খোদাই করা ডিস্কের ভিতরে) বিকৃত দাবা বোর্ডের সমস্যা, একটি স্ট্যান্ডার্ড 8 × 8 দাবা বোর্ডের (বা চেকারবোর্ডের) 62-বর্গক্ষেত্রের ডোমিনো টাইলিং সম্পর্কিত একটি ধাঁধা।