🔢 mathematics

A Partition-Based Generating Function for Row-Convex Polyominoes

यह शोधपत्र एक नवीन विभाजन-आधारित (partition-based) जनक फलन (generating function) प्रस्तावित करता है जो क्षेत्रफल के पूर्णांक विभाजनों को पंक्ति लंबाई अनुक्रमों से जोड़कर आंतरिक छिद्रों के बिना रो-कॉन्वेक्स (row-convex) पॉलीओमिनोज़ की गणना करता है, जिससे एक सटीक सूत्र प्राप्त होता है और इसकी आनुमानिक वृद्धि दर $S(N) \sim A2^N \cos(N\theta + \phi)$ स्थापित होती है।

मूल लेखक: Vincenzo M. Scarrica

प्रकाशित 2026-05-06

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Vincenzo M. Scarrica

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप चपटे, आयताकार लेगो ईंटों से एक मीनार बना रहे हैं। आप एक आकार बनाने के लिए उन्हें एक के ऊपर एक रखना चाहते हैं, लेकिन आपका एक बहुत ही विशिष्ट नियम है: आपकी मीनार की हर एक क्षैतिज परत (horizontal layer) ईंटों की एक ठोस, अटूट रेखा होनी चाहिए। आपके पास ऐसी परत नहीं होनी चाहिए जो "U" आकार की दिखे या जिसके बीच में कोई खाली जगह हो। गणित की दुनिया में, इन आकारों को row-convex polyominoes कहा जाता है।

विन्सेन्ज़ो स्कारिका का यह शोध पत्र मूल रूप से यह गिनने के लिए एक नया निर्देश मैनुअल है कि यदि आप ठीक $N$ ईंटों तक सीमित हैं, तो आप कितनी अलग-अलग मीनारें बना सकते हैं।

यहाँ इस शोध पत्र के विचारों का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है:

1. आकार के लिए "रेसिपी" (विधि)

परंपरागत रूप से, गणितज्ञों को इन आकारों को गिनने में कठिनाई होती है क्योंकि वे व्यवस्थित करने में जटिल होते हैं। स्कारिका एक नए तरीके का सुझाव देते हैं जिससे इन आकारों के बारे में सोचा जा सके। आकार को बनाने के लिए केवल चित्र बनाने के बजाय, वह आकार की रेसिपी देखने का सुझाव देते हैं।

सामग्री (Partitions): कल्पना कीजिए कि आपके पास 10 ईंटें हैं। आप उन्हें परतों में कई तरीकों से तोड़ सकते हैं: 10 की एक परत, या 5+5, या 4+3+2+1, या 3+3+2+2, और इसी तरह। गणित में, एक संख्या को छोटी संख्याओं में तोड़ने के इन तरीकों को integer partitions कहा जाता है।
असेंबली (Permutations): एक बार जब आप एक रेसिपी (जैसे, 4, 3 और 2 की परतें) तय कर लेते हैं, तो आप उन्हें अलग-अलग क्रमों में रख सकते हैं। आप 4 को नीचे रख सकते हैं, या 2 को नीचे। शोध पत्र यह गणना करता है कि आप अपनी परतों को कितने अद्वितीय तरीकों से व्यवस्थित कर सकते हैं।
"वोबल" कारक (Shifts): यह सबसे चतुर हिस्सा है। जब आप 4 ईंटों की एक परत को 3 ईंटों की परत के ऊपर रखते हैं, तो आपको उन्हें बाईं ओर बिल्कुल सीधा रखने की आवश्यकता नहीं है। आप ऊपरी परत को बाएं या दाएं खिसका सकते हैं, जब तक कि उसका कम से कम एक ईंट नीचे वाली परत को छू रहा हो। शोध पत्र गणना करता है कि प्रत्येक जोड़ी परतों के लिए कितने "स्लाइड पोजीशन" संभव हैं।

सूत्र (The Formula): कुल संख्या प्राप्त करने के लिए, लेखक कहता है कि:

आपकी कुल ईंटों को परतों में तोड़ने के हर संभावित तरीके को लें।
उन परतों को व्यवस्थित करने के कितने तरीके हैं, इसकी गणना करें।
उन्हें एक साथ खिसकाने (slide) के तरीकों की संख्या से गुणा करें।
उन सभी परिणामों को जोड़ दें।

2. "दर्पण" का कमाल (The "Mirror" Trick)

यह शोध पत्र पूछता है: "क्या होगा यदि हम मीनार को पलट दें?"
यदि आप एक आकार बनाते हैं और फिर उसके प्रतिबिंब को दर्पण में देखते हैं, तो क्या वह एक नया आकार है या वही आकार?

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

3. "जादुई संख्या" का परिणाम

इतनी सारी जटिल गणना करने के बाद, शोध पत्र एक "जेनरेटिंग फंक्शन" (generating function) निकालता है जो भविष्यवाणी करता है कि जैसे-जैसे आप अधिक ईंटें जोड़ते हैं, आकारों की संख्या कैसे बढ़ती है।

विकास (Growth): आकारों की संख्या धीरे-धीरे नहीं बढ़ती; यह तेजी से (exponentially) बढ़ती है।
पैटर्न: विकास एक लहर जैसे पैटर्न का पालन करता है जो बड़ा और बड़ा होता जाता है। शोध पत्र गणना करता है कि बड़ी संख्या में ईंटों ( $N$ ) के लिए, आकारों की संख्या लगभग $2^N$ के समानुपाती होती है (हर बार एक ईंट जोड़ने पर यह दोगुना हो जाता है, जिसमें एक हल्का सा उतार-चढ़ाव होता है)।
"वोबल" (The Wobble): विकास एक सीधी रेखा नहीं है; यह $\sqrt{7}$ से संबंधित एक विशिष्ट कोण के आधार पर दोलन (oscillate) करता है (ऊपर-नीचे होता है)।

4. यह क्या कर सकता है और क्या नहीं

शोध पत्र इसके बारे में बहुत स्पष्ट है:

यह किसके लिए काम करता है: यह उन आकारों के लिए पूरी तरह से काम करता है जहाँ प्रत्येक पंक्ति एक ठोस ब्लॉक है (row-convex)।
यह कहाँ विफल होता है: यह "कन्केव" (concave) आकारों (जिनमें पंक्तियों में छेद या अंतराल होते हैं) को आसानी से नहीं गिन सकता है। कल्पना कीजिए कि आप एक ऐसी मीनार बनाने की कोशिश कर रहे हैं जहाँ एक परत के बीच में अंतराल हो, जैसे कि एक पुल। गणित बहुत जटिल हो जाता है क्योंकि जब हिस्से जुड़े हुए नहीं होते हैं, तो "स्लाइडिंग" के नियम अविश्वसनीय रूप से जटिल हो जाते हैं। शोध पत्र स्वीकार करता है कि इन जटिल आकारों तक इस पद्धति का विस्तार करना वर्तमान में बहुत कठिन है।

सारांश

संक्षेप में, यह शोध पत्र आकारों को संख्याओं से बनी रेसिपी की तरह मानकर, विशिष्ट प्रकार के ब्लॉक वाले आकारों को गिनने का एक नया, सरल तरीका प्रदान करता है। यह पुष्टि करता है कि इन आकारों की संख्या बहुत तेजी से बढ़ती है (प्रत्येक अतिरिक्त ब्लॉक के साथ दोगुना होना) और एक सटीक गणितीय उपकरण प्रदान करता है जो भविष्यवाणी करता है कि वहां वास्तव में कितने आकार होंगे, जो क्षेत्र के पिछले प्रसिद्ध परिणामों से मेल खाता है।

तकनीकी सारांश: रो-कॉन्वेक्स पॉलीओमिनो (Row-Convex Polyominoes) के लिए एक विभाजन-आधारित जनरेटिंग फंक्शन

समस्या विवरण
पॉलीओमिनो (2D पूर्णांक जाली पर जुड़े हुए इकाई वर्गों के परिमित सेट) की गणना करना—विशेष रूप से ज्यामितीय बाधाओं द्वारा परिभाषित वर्गों के लिए—संयोजन विज्ञान (combinatorics) में एक चुनौतीपूर्ण समस्या बनी हुई है। जबकि सामान्य पॉलीओमिनो के लिए बंद-रूप सूत्र (closed-form formulas) काफी हद तक अज्ञात हैं, विशिष्ट उपवर्ग जैसे कि कॉन्वेक्स (convex), रो-कॉन्वेक्स (row-convex), और कॉलम-कॉन्वेक्स (column-convex) पॉलीओमिनो का व्यापक अध्ययन किया गया है। मौजूदा विधियाँ, विशेष रूप से क्लार्नर (Klarer) और हिकर्सन (Hickerson) द्वारा, जनरेटिंग फंक्शन प्राप्त करने के लिए पुनरावृत्ति संबंधों (recurrence relations) और ट्रांसफर-मैट्रिक्स तर्कों पर निर्भर करती हैं। हालांकि, आंतरिक छिद्रों के बिना कॉन्वेक्स पॉलीओमिनो की गिनती के लिए स्पष्ट बंद-रूप सूत्र सीमित हैं। यह शोध पत्र आंतरिक छिद्रों के बिना रो-कॉन्वेक्स पॉलीओमिनो की गणना को संबोधित करता है, जो पूर्णांक विभाजनों (integer partitions) के साथ सीधे संबंध स्थापित करने वाला एक वैकल्पिक संय combinations दृष्टिकोण खोजता है।

कार्यप्रणाली
प्रस्तावित विधि रो-कॉन्वेक्स पॉलीओमिनो और कुल क्षेत्रफल $N$ के पूर्णांक विभाजनों के बीच एक सीधा संबंध स्थापित करती है। मुख्य तर्क इस प्रकार है:

विभाजन अपघटन (Partition Decomposition): क्षेत्रफल $N$ वाले प्रत्येक रो-कॉन्वेक्स पॉलीओमिनो को पंक्तियों की लंबाई के एक अनुक्रम $(\lambda_1, \lambda_2, \dots, \lambda_k)$ में विभाजित किया जाता है, ताकि $\sum \lambda_i = N$ हो। यह अनुक्रम $N$ के एक पूर्णांक विभाजन का निर्माण करता है।
क्षैतिज संरेखण (Shifts): पंक्ति की लंबाई के एक निश्चित अनुक्रम के लिए, वैध क्षैतिज संरेखणों की संख्या क्रमिक पंक्तियों के बीच के "शिफ्ट" (shift) द्वारा निर्धारित होती है। यदि पंक्ति $i$ की लंबाई $L_i$ है और पंक्ति $i+1$ की लंबाई $L_{i+1}$ है, तो उन स्थितियों की संख्या जहाँ वे स्पर्श कर सकते हैं (4-कनेक्टिविटी सुनिश्चित करते हुए) $L_i + L_{i+1} - 1$ है। एक निश्चित क्रमबद्ध अनुक्रम के लिए कुल कॉन्फ़िगरेशन इन शिफ्ट कारकों का गुणनफल है: $\prod_{i=1}^{k-1} (\lambda_i + \lambda_{i+1} - 1)$ ।
क्रमपरिवर्तन कारक (Permutation Factor): चूंकि पॉलीओमिनो के आकार के लिए पंक्तियों का क्रम महत्वपूर्ण है, इसलिए विधि विभाजन के विभिन्न क्रमपरिवर्तनों को गिनने के लिए एक कारक $\Phi(\lambda)$ पेश करती है, जो दोहराए गए भाग आकारों (multiplicities) के लिए समायोजन करता है।
गणना सूत्र (Enumeration Formula): आकार $N$ के रो-कॉन्वेक्स पॉलीओमिनो की कुल संख्या, जिसे $S(N)$ द्वारा दर्शाया गया है, विभाजन $\lambda$ के क्रमपरिवर्तन कारक और शिफ्ट उत्पाद के योग द्वारा प्राप्त की जाती है:
$S(N) = \sum_{\lambda \in P(N)} \Phi(\lambda) \prod_{i=1}^{\ell(\lambda)-1} (\lambda_i + \lambda_{i+1} - 1)$
जनरेटिंग फंक्शन व्युत्पत्ति: शोध पत्र इस संय combinations योग को एक जनरेटिंग फंक्शन $G(x) = \sum S(N)x^N$ में अनुवादित करता है। क्रमबद्ध संरचनाओं (ordered compositions) की एक ट्रांसफर सीरीज़ के रूप में समस्या को मॉडल करके और रैखिक समीकरणों के परिणामी तंत्र को हल करके, सटीक परिमेय जनरेटिंग फंक्शन व्युत्पन्न किया जाता है।

मुख्य परिणाम

सटीक जनरेटिंग फंक्शन: शोध पत्र रो-कॉन्वेक्स पॉलीओमिनो के लिए जनरेटिंग फंक्शन व्युत्पन्न करता है:
$G(x) = \frac{x(1-x)^3}{1 - 5x + 7x^2 - 4x^3}$
यह परिणाम क्लार्नर और हिकर्सन द्वारा पहले निकाले गए कॉलम-कॉन्वेक्स पॉलीओमिनो के जनरेटिंग फंक्शन के साथ सटीक रूप से मेल खाता है, जो विभाजन-आधारित दृष्टिकोण की वैधता को सिद्ध करता है।
अनंतस्पर्शी विकास (Asymptotic Growth): $G(x)$ के ध्रुवों (poles) के विश्लेषण से अनुक्रम के अनंतस्पर्शी व्यवहार का पता चलता है। प्रमुख विलक्षणताएं (singularities) $x = \frac{3 \pm i\sqrt{7}}{8}$ पर जटिल संयुग्मी ध्रुव हैं, जिनका मापांक (modulus) $1/2$ है। फलस्वरूप, पॉलीओमिनो की संख्या इस प्रकार बढ़ती है:
$S(N) \sim A \cdot 2^N \cos(N\theta + \phi)$
जहाँ $\theta = \arctan(\sqrt{7}/3)$ है। यह शुद्ध घातांकीय विकास (exponential growth) को दर्शाता जिसका आधार 2 है, जो अनियंत्रित पूर्णांक विभाजनों के उप-घातांकीय (sub-exponential) विकास के विपरीत है।
संख्यात्मक सत्यापन: सूत्र को $N$ के लिए 12 तक OEIS अनुक्रम A001169 के विरुद्ध पायथन (एल्गोरिदम 1) में लागू किया गया और सत्यापित किया गया, जो पूर्ण सहमति दिखाता है।
सममिति न्यूनीकरण (Symmetry Reduction): शोध पत्र दर्पण-छवि कॉन्फ़िगरेशन (mirror-image configurations) की पहचान करके गणना को कम करने के लिए सीमाओं पर चर्चा करता है, यह नोट करते हुए कि जबकि विशिष्ट पैरिटी मामलों के लिए सटीक आधा करना संभव है, विभाजन सूत्र से सीधे सममित पॉलीओमिनो के लिए एक सामान्य बंद-रूप न्यूनीकरण प्राप्त करना कठिन है।

महत्व और सीमाएं
इस कार्य का प्राथमिक योगदान पूर्णांक विभाजनों और रो-कॉन्वेक्स पॉलीओमिनो की गणना के बीच एक सीधा संय combinations लिंक स्थापित करना है। समस्या को विभाजनों और उनके क्रमपरिवर्तनों के संदर्भ में पुनर्गठित करके, शोध पत्र सटीक गणना और अनंतस्पर्शी विश्लेषण दोनों के लिए एक "सरल लेकिन प्रभावी ढांचा" प्रदान करता है, जो अधिक जटिल ट्रांसफर-मैट्रिक्स तर्कों पर निर्भर नहीं करता है।

शोध पत्र स्पष्ट रूप से इस दृष्टिकोण की सीमाओं को नोट करता है: यह कड़ाई से बिना आंतरिक छिद्रों वाले रो-कॉन्वेक्स पॉलीओमिनो पर लागू होता है। 'कॉन्केव' (concave) पॉलीओमिनो तक विस्तार करने को संय combinations रूप से अव्यवहार्य माना गया है क्योंकि 'कॉन्केव' पंक्तियाँ कई विच्छेदित घटकों (sub-partitions) में विभाजित हो सकती हैं, जिससे 4-कनेक्टिविटी बाधा को लागू करना काफी जटिल हो जाता है।

यह कार्य स्वयं को क्लासिकल विधियों (क्लार्नर, हिकर्सन) के विकल्प के रूप में नहीं, बल्कि एक विकल्प के रूप में स्थापित करता है, जो इस विशिष्ट वर्ग के पॉलीओमिनो के लिए जनरेटिंग फंक्शन और अनंतस्पर्शी अनुमानों के व्युत्पत्ति को सरल बनाने के लिए एक नया दृष्टिकोण प्रदान करता है। संभावित अनुप्रयोगों का उल्लेख किया गया है जिनमें डिस्क्रीट इमेज विश्लेषण में शेप प्रायर्स (shape priors), ग्रिड-आधारित मॉडलिंग और प्रोसीजरल जनरेशन शामिल है, हालांकि इन्हें इस विशिष्ट अध्ययन के प्रयोगात्मक परिणामों के बजाय उन संदर्भों के रूप में प्रस्तुत किया गया है जहाँ यह गणना प्रासंगिक है।