विभाजन (संख्या सिद्धांत)

युवा रेखाचित्र 1 से 8 तक के धनात्मक पूर्णांकों के विभाजन से संबंधित आरेख। उन्हें इस प्रकार व्यवस्थित किया गया है कि वर्ग के मुख्य विकर्ण के बारे में प्रतिबिंब के अंतर्गत चित्र संयुग्मी विभाजन हैं।

के विभाजन n सबसे बड़े जोड़ के साथ k

संख्या सिद्धांत और साहचर्य में, सकारात्मक पूर्णांक n का विभाजन, जिसे पूर्णांक विभाजन भी कहा जाता है, n को सकारात्मक पूर्णांकों के योग के रूप में लिखने की विधि है। दो राशियाँ जो केवल उनके योगों के क्रम में भिन्न होती हैं, उन्हें एक ही विभाजन माना जाता हैं। (यदि आदेश मायने रखता है, तो योग रचना (संयोजन) बन जाता है।) उदाहरण के लिए, 4 पांच अलग-अलग विधियाँ से विभाजित किया जा सकता है:

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

क्रम-निर्भर संरचना 1 + 3 के समान विभाजन 3 + 1 है, और दो अलग-अलग रचनाएँ 1 + 2 + 1 और 1 + 1 + 2 के समान विभाजन 2 + 1 + 1 का प्रतिनिधित्व करते है।

एक विभाजन में योग को भाग भी कहा जाता है। n के विभाजनों की संख्या विभाजन फलन (संख्या सिद्धांत) p(n) द्वारा दिया गया है. इसलिए p(4) = 5. अंकन λ ⊢ n अर्थ कि λ n का विभाजन है।

युवा आरेख या फेरर्स आरेख के साथ पार्टिशन को ग्राफिक रूप से देखा जा सकता है। वे गणित और भौतिकी की कई शाखाओं में पाए जाते हैं, जिनमें सममित बहुपदों और सममित समूह का अध्ययन और सामान्य रूप से समूह प्रतिनिधित्व सम्मिलित है।

उदाहरण

5 के सात भाग हैं

• 5
• 4 + 1
• 3 + 2
• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

कुछ लेखक एक विभाजन को योग चिह्नों के साथ एक अभिव्यक्ति के बजाय सारांश के घटते क्रम के रूप में मानते हैं। उदाहरण के लिए, विभाजन 2 + 2 + 1 को टपल (2, 2, 1) के रूप में लिखा जा सकता है या इससे भी अधिक सघन रूप (2², 1) में लिखा जा सकता है, जहां सुपरस्क्रिप्ट एक भाग की पुनरावृत्ति की संख्या को निरुपित करता है।

विभाजन के लिए यह बहुलता संकेतन वैकल्पिक रूप $1^{m_{1}}2^{m_{2}}3^{m_{3}}\cdots$ से लिखा जा सकता है, जहाँ m₁ 1 की संख्या है, m₂ 2 की संख्या है, (घटक के साथ m_i = 0 छोड़ा जा सकता है।) आदि। उदाहरण के लिए, इस अंकन में, 5 के विभाजन $5^{1},1^{1}4^{1},2^{1}3^{1},1^{2}3^{1},1^{1}2^{2},1^{3}2^{1}$, और $1^{5}$लिखे गए है।

विभाजनों का आरेखीय निरूपण

नॉर्मन मैकलॉड फेरर्स के नाम पर फेरर्स आरेखों के रूप में और अल्फ्रेड यंग (गणितज्ञ) के नाम पर युवा आरेखों के रूप में विभाजन का प्रतिनिधित्व करने के लिए दो सामान्य आरेखीय विधियां हैं। दोनों के कई संभावित सम्मेलन हैं; यहां हम ऊपरी-बाएं कोने में रेखाचित्रों के साथ अंग्रेजी संकेतन का उपयोग करते हैं।

फेरर्स आरेख

संख्या 14 का विभाजन 6 + 4 + 3 + 1 निम्नलिखित आरेख द्वारा दर्शाया जा सकता है:

14 वृत्त 4 पंक्तियों में पंक्तिबद्ध हैं, जिनमें से प्रत्येक विभाजन के भाग के आकार का है। संख्या 4 के 5 विभाजनों के चित्र नीचे दिखाए गए हैं:

4	=	3 + 1	=	2 + 2	=	2 + 1 + 1	=	1 + 1 + 1 + 1

युवा आरेख

Main article: युवा आरेख

पूर्णांक विभाजन का वैकल्पिक दृश्य प्रतिनिधित्व इसका यंग आरेख है (जिसे अधिकांश फेरर्स आरेख भी कहा जाता है)। बिन्दुओं के साथ विभाजन का प्रतिनिधित्व करने के अतिरिक्त, जैसा कि फेरर्स आरेख में है, युवा आरेख बक्से या वर्गों का उपयोग करता है। इस प्रकार, विभाजन 5 + 4 + 1 के लिए यंग आरेख है

चूँकि उसी विभाजन के लिए फेरर्स आरेख है

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

विभाजन फलन

पी(40) खोजने के लिए यूलर की विधि का उपयोग करना: प्लस और माइनस चिह्नों (ग्रे बॉक्स) के साथ रूलर को नीचे की ओर खिसकाया जाता है, प्रासंगिक भागों को जोड़ा या घटाया जाता है। संकेतों की स्थिति वैकल्पिक प्राकृतिक (नीला) और विषम (नारंगी) संख्याओं के अंतर से दी गई है। में एसवीजी फ़ाइल, रूलर को स्थानांतरित करने के लिए छवि पर होवर करें।

Main article: विभाजन समारोह (संख्या सिद्धांत)

विभाजन फलन (संख्या सिद्धांत) $p(n)$ गैर-ऋणात्मक पूर्णांक के संभावित विभाजनों की संख्या $n$ के बराबर है। उदाहरण के लिए, $p(4)=5$ क्योंकि पूर्णांक $4$ पाँच विभाजन हैं $1+1+1+1$, $1+1+2$, $1+3$, $2+2$, और $4$.

इस फलन के मान के लिए $n=0,1,2,\dots$ हैं:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575 , 1958, 2436, 3010, 3718, 4565, 5604, ... (sequence A000041 in the OEIS).

का जनरेटिंग फलन $p$ है

$\sum _{n=0}^{\infty }p(n)q^{n}=\prod _{j=1}^{\infty }\sum _{i=0}^{\infty }q^{ji}=\prod _{j=1}^{\infty }(1-q^{j})^{-1}.$

विभाजन फलन के लिए कोई बंद-रूप अभिव्यक्ति ज्ञात नहीं है, किन्तु इसमें दोनों स्पर्शोन्मुख विश्लेषण हैं जो इसे त्रुटिहीन रूप से अनुमानित करते हैं और पुनरावृत्ति संबंध जिसके द्वारा इसकी त्रुटिहीन गणना की जा सकती है। यह अपने तर्क के वर्गमूल के घातीय कार्य के रूप में बढ़ता है।, निम्नलिखित अनुसार:

$p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)$ जैसा $n\to \infty$

इसके जनक फलन का गुणक प्रतिलोम यूलर फलन है; यूलर के पंचकोणीय संख्या प्रमेय द्वारा यह फलन इसके तर्क की पंचकोणीय संख्या शक्तियों का वैकल्पिक योग है।

$p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+\cdots$

श्रीनिवास रामानुजन ने पता लगाया कि विभाजन फलन में मापांक अंकगणित में गैर-तुच्छ प्रतिरूप हैं, जिन्हें अब रामानुजन की सर्वांगसमता के रूप में जाना जाता है। उदाहरण के लिए, जब भी दशमलव का प्रतिनिधित्व $n$ अंक 4 या 9 में समाप्त होता है, तो $n$ के विभाजनों की संख्या 5 से विभाज्य होगी।

प्रतिबंधित विभाजन

साहचर्य और संख्या सिद्धांत दोनों में, विभिन्न प्रतिबंधों के अधीन विभाजन के परिवारों का अधिकांश अध्ययन किया जाता है। यह खंड ऐसे ही कुछ प्रतिबंधों का सर्वेक्षण करता है।

संयुग्मी और स्व-संयुग्मित विभाजन

यदि हम विभाजन 6 + 4 + 3 + 1 के आरेख को उसके मुख्य विकर्ण के साथ पलटते हैं, तो हमें 14 का और विभाजन मिलता है:

	↔
6 + 4 + 3 + 1	=	4 + 3 + 3 + 2 + 1 + 1

पंक्तियों को स्तंभों में बदलकर, हम संख्या 14 का विभाजन 4 + 3 + 3 + 2 + 1 + 1 प्राप्त करते हैं। ऐसे विभाजन दूसरे के संयुग्मी कहलाते हैं। संख्या 4 के स्थिति में, विभाजन 4 और 1 + 1 + 1 + 1 संयुग्मित जोड़े हैं, और विभाजन 3 + 1 और 2 + 1 + 1 दूसरे के संयुग्म हैं। विशेष रुचि का विभाजन 2 + 2 है, जो स्वयं को संयुग्मित करता है। ऐसे विभाजन को स्व-संयुग्मी कहा जाता है।

प्रमाणित: स्व-संयुग्मित विभाजनों की संख्या अलग-अलग विषम भागों वाले विभाजनों की संख्या के समान है।

प्रमाण (रूपरेखा): महत्वपूर्ण अवलोकन यह है कि स्व-संयुग्म आरेख बनाने के लिए प्रत्येक विषम भाग को बीच में मोड़ा जा सकता है:

↔

इसके बाद अलग-अलग विषम भागों वाले विभाजनों के सेट और स्व-संयुग्मित विभाजनों के सेट के बीच आक्षेप प्राप्त किया जा सकता है, जैसा कि निम्नलिखित उदाहरण द्वारा दिखाया गया है:

	↔
9 + 7 + 3	=	5 + 5 + 4 + 3 + 2
Dist. odd		self-conjugate

विषम भाग और विशिष्ट भाग

संख्या 8 के 22 विभाजनों में से 6 ऐसे हैं जिनमें केवल विषम भाग हैं:

• 7 + 1
• 5 + 3
• 5 + 1 + 1 + 1
• 3 + 3 + 1 + 1
• 3 + 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

वैकल्पिक रूप से, हम उन विभाजनों की गणना कर सकते हैं जिनमें कोई संख्या से अधिक बार नहीं आती है। इस प्रकार के विभाजन को अलग-अलग भागों वाला विभाजन कहा जाता है। यदि हम अलग-अलग भागों के साथ 8 के विभाजनों को गिनते हैं, तो हमें 6 भी प्राप्त होता है:

• 8
• 7 + 1
• 6 + 2
• 5 + 3
• 5 + 2 + 1
• 4 + 3 + 1

यह सामान्य संपत्ति है। प्रत्येक धनात्मक संख्या के लिए, विषम भागों वाले विभाजनों की संख्या अलग-अलग भागों वाले विभाजनों की संख्या के बराबर होती है, जिसे q(n) द्वारा निरूपित किया जाता है। यह परिणाम 1748 में लियोनहार्ड यूलर द्वारा सिद्ध किया गया था और बाद में ग्लेशर के प्रमेय के रूप में सामान्यीकृत किया गया।

प्रत्येक प्रकार के प्रतिबंधित विभाजन के लिए दिए गए प्रतिबंध को संतुष्ट करने वाले विभाजनों की संख्या के लिए समान कार्य होता है। महत्वपूर्ण उदाहरण है q(n) (विभिन्न भागों में विभाजन)। q(n) के पहले कुछ मान हैं (q(0)=1 से शुरू):

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ... (sequence A000009 in the OEIS).

क्यू (एन) के लिए जनरेटिंग फलन द्वारा दिया गया है:$\sum _{n=0}^{\infty }q(n)x^{n}=\prod _{k=1}^{\infty }(1+x^{k})=\prod _{k=1}^{\infty }{\frac {1}{1-x^{2k-1}}}.$

पंचकोणीय संख्या प्रमेय q के लिए पुनरावृत्ति देता है: q(k) = a_k + q(k − 1) + q(k − 2) − q(k − 5) − q(k − 7) + q(k − 12) + q(k − 15) − q(k − 22) − ...

जहाँ a_k (-1)^m है यदि k = 3m² - m किसी पूर्णांक m के लिए और अन्यथा 0 है।

प्रतिबंधित भाग का आकार या भागों की संख्या

Main article: विभाजन संख्याओं का त्रिभुज

संयुग्म लेने से, संख्या p_k(n) के विभाजन का n ठीक k भागों में विभाजन की संख्या n के बराबर है जिसमें सबसे बड़े भाग का आकार k होता हैं। फलन p_k(n) पुनरावृत्ति को संतुष्ट करता है

p_k(n) = p_k(n − k) + p_k−1(n − 1)

प्रारंभिक मूल्यों के साथ p₀(0) = 1 और p_k(n) = 0 यदि n ≤ 0 or k ≤ 0 और n और k दोनों शून्य नहीं हैं।

फलन p(n) को पुनः प्राप्त करता है

$p(n)=\sum _{k=0}^{n}p_{k}(n).$

इस प्रकार के विभाजन के लिए संभावित जनरेटिंग फलन, के फिक्स्ड और एन वेरिएबल, है

$\sum _{n\geq 0}p_{k}(n)x^{n}=x^{k}\cdot \prod _{i=1}^{k}{\frac {1}{1-x^{i}}}.$

अधिक सामान्यतः, यदि T सकारात्मक पूर्णांकों का सेट है, तो n के विभाजनों की संख्या, जिनके सभी भाग T से संबंधित फलन उत्पन्न होता है

$\prod _{t\in T}(1-x^{t})^{-1}.$

इसका उपयोग परिवर्तन करने वाली समस्याओं को समाधान करने के लिए किया जा सकता है (जहां सेट टी उपलब्ध सिक्कों को निर्दिष्ट करता है)। दो विशेष स्थितियों के रूप में, किसी के पास n के विभाजनों की संख्या है जिसमें सभी भाग 1 या 2 (या, समतुल्य, n के विभाजनों की संख्या 1 या 2 भागों में) है

$\left\lfloor {\frac {n}{2}}+1\right\rfloor ,$

और n के विभाजनों की संख्या जिसमें सभी भाग 1, 2 या 3 हैं (या, समतुल्य रूप से, n के विभाजनों की संख्या अधिकतम तीन भागों में) जिनके निकटतम पूर्णां (n + 3)² / 12 हैं।

आयत में विभाजन और गाऊसी द्विपद गुणांक

Main article: गाऊसी द्विपद गुणांक

कोई भी एक साथ भागों की संख्या और आकार को सीमित कर सकता है। मान लीजिए कि p(N, M; n) अधिकांश M भागों वाले n के विभाजनों की संख्या को निरूपित करता है, जिनमें से प्रत्येक का आकार अधिकतम N है। समान रूप से, ये ऐसे विभाजन हैं जिनका यंग आरेख एक M × N आयत के अंदर फिट बैठता है। पुनरावर्ती संबंध होता है

$$p(N,M;n)=p(N,M-1;n)+p(N-1,M;n-M)$$

$p(N,M;n)-p(N,M-1;n)$ यह देखते हुए प्राप्त किया जाता है कि n विभाजनों को अधिकतम N पर आकार के M भागों में गिनता है और इस प्रकार के विभाजन के प्रत्येक भाग से 1 घटाकर अधिकांश M भागों में n − M का विभाजन प्राप्त करता है।

गाऊसी द्विपद गुणांक को इस प्रकार परिभाषित किया गया है:

$${k+\ell \choose \ell }_{q}={k+\ell \choose k}_{q}={\frac {\prod _{j=1}^{k+\ell }(1-q^{j})}{\prod _{j=1}^{k}(1-q^{j})\prod _{j=1}^{\ell }(1-q^{j})}}.$$

गॉसियन द्विपद गुणांक के जनन फलन p(N, M; n) से संबंधित है समानता से

$$\sum _{n=0}^{MN}p(N,M;n)q^{n}={M+N \choose M}_{q}.$$

रैंक और डर्फी वर्ग

Main article: डर्फी वर्ग

विभाजन की रैंक सबसे बड़ी संख्या k है जैसे कि विभाजन में कम से कम k आकार के कम से कम k भाग होते हैं। उदाहरण के लिए, विभाजन 4 + 3 + 3 + 2 + 1 + 1 की रैंक 3 है क्योंकि इसमें 3 भाग हैं जो ≥ 3 हैं, किन्तु इसमें ≥ 4 वाले 4 भाग नहीं हैं। फेरर्स आरेख या किसी पार्टीशन के यंग आरेख में रैंक r के, ऊपरी-बाएँ में प्रविष्टियों के r × r वर्ग को डर्फी वर्ग के रूप में जाना जाता है:

डर्फी वर्ग में विभिन्न विभाजन पहचानों के प्रमाणों में संयोजी के अन्दर अनुप्रयोग हैं। h- अनुक्रमणिका के रूप में इसका कुछ व्यावहारिक महत्व भी है।

अलग आंकड़े को कभी-कभी विभाजन (या डायसन रैंक) का रैंक भी कहा जाता है, अर्थात् अंतर $\lambda _{k}-k$ सबसे बड़े भाग वाले k भागों के विभाजन के लिए $\lambda _{k}$. यह आंकड़ा (जो ऊपर वर्णित आंकड़े से संबंधित नहीं है) रामानुजन सर्वांगसमता के अध्ययन में प्रकट होता है।

यंग की जाली

Main article: यंग की जाली

यंग आरेखों को शामिल करके दिए गए विभाजनों पर एक प्राकृतिक आंशिक क्रम है। यह आंशिक रूप से आदेशित सेट यंग की जाली के रूप में जाना जाता है। जाली को मूल रूप से प्रतिनिधित्व सिद्धांत के संदर्भ में परिभाषित किया गया था, जहां इसका उपयोग विशेषता शून्य में, उनके शाखाओं के गुणों के साथ, सभी n के लिए सममित समूहों S_n के अप्रासंगिक अभ्यावेदन का वर्णन करने के लिए किया जाता है। इसके विशुद्ध रूप से संयोजी गुणों के लिए भी इसे महत्वपूर्ण अध्ययन प्राप्त हुआ है; विशेष रूप से, यह एक विभेदक पोसेट का प्रेरक उदाहरण है।

यह भी देखें

• एक विभाजन की रैंक, रैंक की एक अलग धारणा
• एक विभाजन का क्रैंक
• प्रभुत्व क्रम
• गुणनखंडन
• पूर्णांक गुणनखंड
• एक सेट का विभाजन
• सितारे और बार (कॉम्बिनेटरिक्स)
• विमान विभाजन
• विनम्र संख्या, लगातार पूर्णांकों में विभाजन द्वारा परिभाषित
• गुणक विभाजन
• बारह मार्ग
• इवेंस का नमूना सूत्र
• फा दी ब्रूनो का सूत्र
• बहुविभाजन
• न्यूटन की पहचान
• एसपीटी फंक्शन | सबसे छोटा एसपीटी समारोह
• एक गोल्डबैक विभाजन अभाज्य संख्या में एक सम संख्या का विभाजन है (देखें गोल्डबैक का अनुमान)
• कोस्टेंट का विभाजन समारोह

संदर्भ

• Abramowitz, Milton; Stegun, Irene (1964). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. United States Department of Commerce, National Bureau of Standards. ISBN 0-486-61272-4.
• Andrews, George E. (1976). The Theory of Partitions. Cambridge University Press. ISBN 0-521-63766-X.
• Andrews, George E.; Eriksson, Kimmo (2004). Integer Partitions. Cambridge University Press. ISBN 0-521-60090-1.
• Apostol, Tom M. (1990) [1976]. Modular functions and Dirichlet series in number theory. Graduate Texts in Mathematics. Vol. 41 (2nd ed.). New York etc.: Springer-Verlag. ISBN 0-387-97127-0. Zbl 0697.10023. (See chapter 5 for a modern pedagogical intro to Rademacher's formula).
• Bóna, Miklós (2002). A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific Publishing. ISBN 981-02-4900-4. (an elementary introduction to the topic of integer partitions, including a discussion of Ferrers graphs)
• Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001.
• Lehmer, D. H. (1939). "On the remainder and convergence of the series for the partition function". Trans. Amer. Math. Soc. 46: 362–373. doi:10.1090/S0002-9947-1939-0000410-9. MR 0000410. Zbl 0022.20401. Provides the main formula (no derivatives), remainder, and older form for A_k(n).)
• Gupta, Hansraj; Gwyther, C.E.; Miller, J.C.P. (1962). Royal Society of Math. Tables. Vol. 4, Tables of partitions. (Has text, nearly complete bibliography, but they (and Abramowitz) missed the Selberg formula for A_k(n), which is in Whiteman.)
• Macdonald, Ian G. (1979). Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. Oxford University Press. ISBN 0-19-853530-9. Zbl 0487.20007. (See section I.1)
• Nathanson, M.B. (2000). Elementary Methods in Number Theory. Graduate Texts in Mathematics. Vol. 195. Springer-Verlag. ISBN 0-387-98912-9. Zbl 0953.11002.
• Rademacher, Hans (1974). Collected Papers of Hans Rademacher. Vol. v II. MIT Press. pp. 100–07, 108–22, 460–75.
• Sautoy, Marcus Du. (2003). The Music of the Primes. New York: Perennial-HarperCollins. ISBN 9780066210704.
• Stanley, Richard P. (1999). Enumerative Combinatorics. Vol. 1 and 2. Cambridge University Press. ISBN 0-521-56069-1.
• Whiteman, A. L. (1956). "A sum connected with the series for the partition function". Pacific Journal of Mathematics. 6 (1): 159–176. doi:10.2140/pjm.1956.6.159. Zbl 0071.04004. (Provides the Selberg formula. The older form is the finite Fourier expansion of Selberg.)

बाहरी संबंध

• "Partition", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Partition and composition calculator
• Weisstein, Eric W. "Partition". MathWorld.
• Wilf, Herbert S. Lectures on Integer Partitions (PDF), archived (PDF) from the original on 2021-02-24, retrieved 2021-02-28
• Counting with partitions with reference tables to the On-Line Encyclopedia of Integer Sequences
• Integer partitions entry in the FindStat database
• Integer::Partition Perl module from CPAN
• Fast Algorithms For Generating Integer Partitions
• Generating All Partitions: A Comparison Of Two Encodings
• Grime, James (April 28, 2016). "Partitions - Numberphile" (video). Brady Haran. Archived from the original on 2021-12-11. Retrieved 5 May 2016.