टेलीफोन नंबर (गणित): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 2: Line 2:
{{Short description|Number of ways to pair up n objects}}
{{Short description|Number of ways to pair up n objects}}
''यह लेख पूर्णांक अनुक्रम के बारे में है। फ़ोन नेटवर्क एड्रैस के लिए, टेलीफोन संख्या (गणित) देखें।''
''यह लेख पूर्णांक अनुक्रम के बारे में है। फ़ोन नेटवर्क एड्रैस के लिए, टेलीफोन संख्या (गणित) देखें।''
[[File:K4 matchings.svg|thumb|270x270px|पूर्ण ग्राफ़ ''K''<sub>4</sub> में दस मिलान हैं, जो चौथे टेलीफोन संख्या (गणित) के मान ''T''(4) = 10 के अनुरूप हैं।]]
[[File:K4 matchings.svg|thumb|270x270px|पूर्ण आलेख ''K''<sub>4</sub> में दस मिलान हैं, जो चौथे टेलीफोन संख्या (गणित) के मान ''T''(4) = 10 के अनुरूप हैं।]]
आरेखण, चार शीर्षों पर प्रत्येक पूर्ण ग्राफ़. शीर्ष के अलावा, प्रत्येक ड्राइंग में कुछ संख्या में कनेक्टिंग किनारों को हाइलाइट किया गया है। हाइलाइट किए गए किनारों को ऐसे चुना जाता है कि कोई भी शीर्ष साझा नहीं करता है।]]गणित में, टेलीफोन संख्या या इनवॉल्यूशन संख्या एक [[पूर्णांक अनुक्रम]] बनाते हैं जो तरीकों की गणना करते हैं {{mvar|n}} लोगों को व्यक्ति-दर-व्यक्ति टेलीफोन कॉल द्वारा जोड़ा जा सकता है। ये संख्याएँ एक पूर्ण ग्राफ़ पर मिलान (ग्राफ़ सिद्धांत) ([[ कज़ुओ होसोया एक्स | कज़ुओ होसोया एक्स]] ) की संख्या का भी वर्णन करती हैं {{mvar|n}} शीर्ष, पर क्रमचय की संख्या {{mvar|n}} तत्व जो शामिल हैं (गणित) एस, हर्मिट बहुपदों के गुणांक के पूर्ण मूल्यों का योग, मानक युवा सारणी की संख्या के साथ {{mvar|n}} कोशिकाएं, और [[सममित समूह]] के अलघुकरणीय अभ्यावेदन की डिग्री का योग। [[हेनरिक अगस्त रोथ]] द्वारा पहली बार 1800 में इन्वोल्यूशन संख्याओ का अध्ययन किया गया, जिन्होंने एक [[पुनरावृत्ति समीकरण]] दिया जिसके द्वारा उनकी गणना की जा सकती है,<ref name="knuth">{{citation
गणित में, '''टेलीफोन संख्या''' '''(गणित)''' या अंतर्वलन संख्या पूर्णांकों का एक क्रम बनाते हैं जो उन तरीकों की गणना करते हैं जिनसे n लोग व्यक्ति-से-व्यक्ति टेलीफोन (दूरभाष) कॉल द्वारा जुड़े हो सकते हैं। ये संख्याएँ n शीर्षों पर एक पूर्ण आलेख के मिलानों की संख्या (होसोया सूचकांक) का भी वर्णन करती हैं, और n तत्वों पर क्रमपरिवर्तन की संख्या, जो अंतर्वलन हैं, हर्मिट बहुपदों के गुणांकों के निरपेक्ष मानो का योग, मानक नवोदित सारणी की संख्या n सेल के साथ, और सममित समूह के अखंडनीय निरूपण की डिग्री का योग होता है। हेनरिक ऑगस्ट रोथ द्वारा 1800 में पहली बार अंतर्वलन संख्याओ का अध्ययन किया गया था, जिन्होंने एक पुनरावृत्ति समीकरण दिया था जिसके द्वारा उन्हें मान (n = 0 से प्रारंभ)<ref name="knuth">{{citation
  | last = Knuth | first = Donald E. | author-link = Donald Knuth
  | last = Knuth | first = Donald E. | author-link = Donald Knuth
  | location = Reading, Mass.
  | location = Reading, Mass.
Line 10: Line 10:
  | publisher = Addison-Wesley
  | publisher = Addison-Wesley
  | title = [[The Art of Computer Programming]], Volume 3: Sorting and Searching
  | title = [[The Art of Computer Programming]], Volume 3: Sorting and Searching
  | year = 1973}}</ref> मान देना (से शुरू करना {{math|1=''n''&nbsp;=&nbsp;0}})
  | year = 1973}}</ref> देकर गणना की जा सकती है
{{bi|left=1.6|1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... {{OEIS|A000085}}.}}
 
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (ओईआईएस में अनुक्रम A000085) सम्मिलित है।


== अनुप्रयोग ==
== अनुप्रयोग ==
जॉन रिओर्डन (गणितज्ञ) इन संख्याओं के लिए निम्नलिखित स्पष्टीकरण प्रदान करते हैं: मान लीजिए कि {{mvar|n}} लोग एक टेलीफोन सेवा की सदस्यता लेते हैं जो उनमें से किन्हीं दो को एक कॉल से जोड़ सकती है, लेकिन दो से अधिक लोगों को जोड़ने वाली एक कॉल नहीं कर सकती। कनेक्शन के कितने अलग-अलग पैटर्न संभव हैं? उदाहरण के लिए, तीन ग्राहकों के साथ, एक टेलीफोन कॉल करने के तीन तरीके हैं, और कुल चार पैटर्न के लिए एक अतिरिक्त पैटर्न जिसमें कोई कॉल नहीं की जा रही है।<ref>{{citation
जॉन रिओर्डन (गणितज्ञ) इन संख्याओं के लिए निम्नलिखित स्पष्टीकरण प्रदान करते हैं: मान लीजिए कि {{mvar|n}} लोग एक टेलीफोन सेवा की सदस्यता लेते हैं जो उनमें से किन्हीं दो को एक कॉल से जोड़ सकती है, लेकिन दो से अधिक लोगों को जोड़ने वाली एक कॉल नहीं कर सकती। सम्पर्क के कितने अलग-अलग पैटर्न संभव हैं? उदाहरण के लिए, तीन ग्राहकों के साथ, एक टेलीफोन कॉल करने के तीन तरीके हैं, और कुल चार पैटर्न के लिए एक अतिरिक्त पैटर्न जिसमें कोई कॉल नहीं की जा रही है।<ref>{{citation
  | last = Riordan | first = John | author-link = John Riordan (mathematician)
  | last = Riordan | first = John | author-link = John Riordan (mathematician)
  | pages = 85–86
  | pages = 85–86
Line 41: Line 42:
  | year = 1991| jstor = 2690455
  | year = 1991| jstor = 2690455
  }}</ref>
  }}</ref>
जोड़ीदार कनेक्शन के बीच हर पैटर्न {{mvar|n}} लोग एक समावेशन (गणित) को परिभाषित करते हैं, लोगों का एक क्रमचय है जो इसका अपना व्युत्क्रम है। इस क्रमपरिवर्तन में, एक-दूसरे को कॉल करने वाले प्रत्येक दो लोगों की अदला-बदली की जाती है, और कॉल में शामिल नहीं होने वाले लोग अपनी जगह पर स्थिर रहते हैं। इसके विपरीत, हर संभव आक्रमण में इस प्रकार के जोड़ीदार स्वैप के सेट का रूप होता है। इसलिए, टेलीफोन संख्या भी निवेशों की गणना करते हैं। 1800 में रोथ द्वारा अध्ययन की गई गणना की समस्या मूल संयोजी गणना समस्या थी<ref name="knuth"/>और इन संख्याओ को इनवोल्यूशन संख्या भी कहा गया है।<ref name="sbdhp">{{citation
 
युग्‍मानूसार सम्पर्क के बीच प्रत्येक पैटर्न {{mvar|n}} लोग एक समावेशन (गणित) को परिभाषित करते हैं, लोगों का एक क्रमचय है जो इसका अपना व्युत्क्रम है। इस क्रमपरिवर्तन में, एक-दूसरे को कॉल करने वाले प्रत्येक दो लोगों की विनिमेयता की जाती है, और कॉल में सम्मिलित नहीं होने वाले लोग अपने स्थान पर स्थिर रहते हैं। इसके विपरीत, प्रत्येक संभव आक्रमण में इस प्रकार के युग्‍मानूसार विनिमय के समुच्चय का रूप होता है। इसलिए, टेलीफोन संख्या भी निवेशों की गणना करते हैं। 1800 में रोथ द्वारा अध्ययन की गई गणना की समस्या मूल संयोजी गणना समस्या थी<ref name="knuth" /> और इन संख्याओ को अंतर्वलन संख्या भी कहा गया है।<ref name="sbdhp">{{citation
  | last1 = Solomon | first1 = A. I.
  | last1 = Solomon | first1 = A. I.
  | last2 = Blasiak | first2 = P.
  | last2 = Blasiak | first2 = P.
Line 73: Line 75:
  | bibcode = 2008JIntS..11...11B
  | bibcode = 2008JIntS..11...11B
  }}</ref>
  }}</ref>
ग्राफ़ सिद्धांत में, ग्राफ़ के किनारों का एक उपसमुच्चय जो प्रत्येक शीर्ष को एक से अधिक बार स्पर्श करता है, उसे मिलान (ग्राफ़ सिद्धांत) कहा जाता है। किसी दिए गए ग्राफ़ के मिलान की गणना करना रासायनिक ग्राफ़ सिद्धांत में महत्वपूर्ण है, जहाँ ग्राफ़ मॉडल अणु और मिलान की संख्या होसोया इंडेक्स है। एक का सबसे बड़ा संभव होसोया सूचकांक {{mvar|n}}-वरटेक्स ग्राफ पूर्ण ग्राफ द्वारा दिया जाता है, जिसके लिए जोड़ीदार कनेक्शन का कोई भी पैटर्न संभव है; इस प्रकार, एक पूर्ण ग्राफ का होसोया सूचकांक {{mvar|n}} शीर्ष के समान है {{mvar|n}}वां टेलीफोन संख्या।<ref>{{citation
 
आलेख सिद्धांत में, आलेख के कोरों का एक उपसमुच्चय जो प्रत्येक शीर्ष को एक से अधिक बार स्पर्श करता है, उसे मिलान (आलेख सिद्धांत) कहा जाता है। किसी दिए गए आलेख के मिलान की गणना करना रासायनिक आलेख सिद्धांत में महत्वपूर्ण है, जहाँ आलेख मॉडल अणु और मिलान की संख्या होसोया सूचकांक है। एक का सबसे बड़ा संभव होसोया सूचकांक {{mvar|n}}-शीर्ष आरेख पूर्ण आरेख द्वारा दिया जाता है, जिसके लिए युग्‍मानूसार सम्पर्क का कोई भी पैटर्न संभव है; इस प्रकार n शीर्षों पर एक पूर्ण आरेख का होसोया सूचकांक nवें टेलीफोन संख्या के समान है।<ref>{{citation
  | last1 = Tichy | first1 = Robert F.
  | last1 = Tichy | first1 = Robert F.
  | last2 = Wagner | first2 = Stephan
  | last2 = Wagner | first2 = Stephan
Line 86: Line 89:
  | pmid = 16201918}}</ref>
  | pmid = 16201918}}</ref>


[[File:Young tableaux for 541 partition.svg|thumb|एक मानक नवोदित सारणी|alt=एक वर्ग के शीर्ष पर चार वर्गों के शीर्ष पर पांच वर्ग, सभी उचित बाएं। वे पढ़ते हैं, बाएं से दाएं, नीचे से ऊपर: 1,2,4,7,8,3,5,6,9,10]]एक [[फेरर्स आरेख]] एक ज्यामितीय आकृति है जो एक संग्रह द्वारा बनाई गई है {{mvar|n}} समतल में वर्ग, एक क्षैतिज शीर्ष किनारे, एक ऊर्ध्वाधर बाएँ किनारे, और किनारों की एक एकल मोनोटोनिक श्रृंखला के साथ एक पॉलीओमिनो में समूहीकृत, ऊपर से नीचे बाईं ओर। 1 से {{mvar|n}} इन वर्गों में इस तरह से कि सारणी में बाएं से दाएं और ऊपर से नीचे तक संख्या बढ़ती है।
[[File:Young tableaux for 541 partition.svg|thumb|एक मानक नवोदित सारणी|alt=एक वर्ग के शीर्ष पर चार वर्गों के शीर्ष पर पांच वर्ग, सभी उचित बाएं। वे पढ़ते हैं, बाएं से दाएं, नीचे से ऊपर: 1,2,4,7,8,3,5,6,9,10]]एक फेरर्स आरेख एक ज्यामितीय आकृति है जो विमान में n वर्गों के संग्रह द्वारा बनाई गई है, एक क्षैतिज शीर्ष कोरों, एक ऊर्ध्वाधर बाएं कोरों और कोरों की एक एकल एकदिष्ट श्रृंखला के साथ एक पॉलीओमिनो में समूहीकृत है। इन वर्गों में 1 से n तक की संख्याओं को इस प्रकार रखकर एक मानक नवोदित सारणी बनाई जाती है कि पूरी सारणी में संख्याएँ बाएँ से दाएँ और ऊपर से नीचे तक बढ़ती हैं। रॉबिन्सन-शेंस्टेड पत्राचार के अनुसार, क्रमपरिवर्तन मानक नवोदित सारणी के क्रमिक युग्म के साथ एक-से-एक के अनुरूप हैं। एक क्रमचय को व्युत्क्रम करना दो सारणियों की विनिमेयता के समान है, और इसलिए स्व-प्रतिलोम क्रमपरिवर्तन एकल सारणी के अनुरूप हैं, जो स्वयं के साथ युग्म जाते हैं।<ref name="b">A direct bijection between involutions and tableaux, inspired by the recurrence relation for the telephone numbers, is given by {{citation
रॉबिन्सन-शेंस्टेड पत्राचार के अनुसार, क्रमपरिवर्तन मानक युवा सारणी के आदेशित जोड़े के साथ एक-से-एक के अनुरूप हैं। एक क्रमचय को उलटना दो सारणी की अदला-बदली से मेल खाता है, और इसलिए स्व-उलटा क्रमपरिवर्तन एकल सारणी के अनुरूप होता है, जिसे स्वयं के साथ जोड़ा जाता है।<ref name="b">A direct bijection between involutions and tableaux, inspired by the recurrence relation for the telephone numbers, is given by {{citation
  | last = Beissinger | first = Janet Simpson
  | last = Beissinger | first = Janet Simpson
  | doi = 10.1016/0012-365X(87)90024-0
  | doi = 10.1016/0012-365X(87)90024-0
Line 97: Line 99:
  | volume = 67
  | volume = 67
  | year = 1987| doi-access = free
  | year = 1987| doi-access = free
  }}</ref> इस प्रकार, टेलीफोन संख्याओ के साथ युवा सारणी की संख्या भी गिना जाता है {{mvar|n}} वर्ग।<ref name="knuth"/>[[प्रतिनिधित्व सिद्धांत]] में, फेरर्स आरेख क्रमपरिवर्तन के सममित समूह के अलघुकरणीय अभ्यावेदन के अनुरूप होते हैं, और किसी दिए गए आकार के साथ युवा सारणी उस आकृति के साथ अलघुकरणीय प्रतिनिधित्व का आधार होती है। इसलिए, टेलीफोन संख्या अलघुकरणीय अभ्यावेदन की डिग्री का योग देते हैं।<ref>{{citation
  }}</ref> इस प्रकार, टेलीफोन संख्या भी n वर्गों के साथ नवोदित सारणी की संख्या की गणना करते हैं।<ref name="knuth" /> [[प्रतिनिधित्व सिद्धांत]] में, फेरर्स आरेख क्रमपरिवर्तन के सममित समूह के अखंडनीय निरूपण के अनुरूप होते हैं, और किसी दिए गए आकार के साथ नवोदित सारणी उस आकृति के साथ अलघुकरणीय प्रतिनिधित्व का आधार होती है। इसलिए, टेलीफोन संख्या अखंडनीय निरूपण की डिग्री का योग देते हैं।<ref>{{citation
  | last1 = Halverson | first1 = Tom
  | last1 = Halverson | first1 = Tom
  | last2 = Reeks | first2 = Mike
  | last2 = Reeks | first2 = Mike
Line 109: Line 111:
  | year = 2015| s2cid = 7419411
  | year = 2015| s2cid = 7419411
  | doi-access = free
  | doi-access = free
  }}</ref>
  }}</ref>{{Chess diagram
 
{{Chess diagram
| tright
| tright
|
|
Line 124: Line 124:
|एक शतरंज की बिसात पर आठ  शतरंज के हाथी का तिरछा सममित गैर-आक्षेप  क्रमस्थान
|एक शतरंज की बिसात पर आठ  शतरंज के हाथी का तिरछा सममित गैर-आक्षेप  क्रमस्थान
}}
}}
गणितीय शतरंज की समस्या में, टेलीफोन संख्याओ को रखने के तरीकों की संख्या की गणना करता है {{mvar|n}} एक पर हाथी {{math|''n''&nbsp;×&nbsp;''n''}} शतरंज की [[बिसात]] इस तरह से कि कोई भी दो बदमाश एक-दूसरे पर हमला न करें (तथाकथित [[आठ रानियों की पहेली]]), और इस तरह से कि बोर्ड के विकर्ण प्रतिबिंब के तहत बदमाशों का विन्यास सममित हो। पोल्या गणना प्रमेय के माध्यम से, ये संख्याएं अनिवार्य रूप से विभिन्न विन्यासों की समग्र संख्या के लिए एक सूत्र के प्रमुख घटकों में से एक हैं। {{mvar|n}} पारस्परिक रूप से गैर-हमलावर बदमाश, जहां दो विन्यासों को अनिवार्य रूप से अलग-अलग गिना जाता है यदि बोर्ड की कोई समरूपता नहीं है जो एक को दूसरे में ले जाती है।<ref>{{citation
गणितीय शतरंज के गणित में, टेलीफोन संख्या n × n शतरंज की बिसात पर n चालाक खिलाड़ी को रखने के तरीकों की संख्या को इस तरह से गिनते हैं कि कोई भी दो चालाक खिलाड़ी एक दूसरे पर आक्षेप न करें तथाकथित आठ चालाक खिलाड़ी पहेली, और इस तरह से बोर्ड के विकर्ण प्रतिबिंब के अंतर्गत चालाक खिलाड़ी का विन्यास सममित है। पोल्या गणना प्रमेय के माध्यम से, ये संख्याएं परस्पर गैर-आक्रमणकारी चालाक खिलाड़ी के "अनिवार्य रूप से भिन्न" विन्यासों की समग्र संख्या के लिए एक सूत्र के प्रमुख घटकों में से एक हैं, जहां दो विन्यासों को अनिवार्य रूप से भिन्न के रूप में गिना जाता है यदि कोई समरूपता नहीं है बोर्ड जो एक को दूसरे में ले जाता है।<ref>{{citation
  | last = Holt | first = D. F.
  | last = Holt | first = D. F.
  | issue = 404
  | issue = 404
Line 142: Line 142:
टेलीफोन संख्या [[पुनरावृत्ति संबंध]] को संतुष्ट करते हैं
टेलीफोन संख्या [[पुनरावृत्ति संबंध]] को संतुष्ट करते हैं
<math display=block>T(n) = T(n-1) + (n-1)T(n-2),</math>
<math display=block>T(n) = T(n-1) + (n-1)T(n-2),</math>
पहली बार 1800 में हेनरिक अगस्त रोथ द्वारा प्रकाशित किया गया था, जिसके द्वारा उनकी आसानी से गणना की जा सकती है।<ref name="knuth"/>इस पुनरावृत्ति की व्याख्या करने का एक तरीका विभाजन करना है {{math|''T''(''n'')}} के कनेक्शन पैटर्न {{mvar|n}} टेलीफ़ोन सिस्टम के सब्सक्राइबर उन पैटर्न में होते हैं जिनमें पहला व्यक्ति किसी और को कॉल नहीं कर रहा है, और पैटर्न जिसमें पहला व्यक्ति कॉल कर रहा है। वहाँ हैं {{math|''T''(''n''&nbsp;&nbsp;1)}} कनेक्शन पैटर्न जिसमें पहले व्यक्ति को डिस्कनेक्ट किया गया है, पुनरावृत्ति की पहली अवधि समझाते हुए। यदि पहला व्यक्ति किसी से जुड़ा है, तो हैं {{math|''n''&nbsp;−&nbsp;1}} उस व्यक्ति के लिए विकल्प, और {{math|''T''(''n''&nbsp;&nbsp;2)}} शेष के लिए कनेक्शन के पैटर्न {{math|''n''&nbsp;&nbsp;2}} लोग, पुनरावृत्ति के दूसरे पद की व्याख्या करते हुए।<ref name="chm"/>
पहली बार 1800 में हेनरिक अगस्त रोथ द्वारा प्रकाशित किया गया था, जिसके द्वारा उनकी आसानी से गणना की जा सकती है।<ref name="knuth"/> इस पुनरावृत्ति की व्याख्या करने का एक तरीका यह है कि n ग्राहकों के टेलीफोन प्रणाली के T(n) संयोजन पैटर्न को ऐसे पैटर्न में विभाजित किया जाए जिसमें पहला व्यक्ति किसी और को कॉल नहीं कर रहा है, ऐसे T(n − 1) संयोजन पैटर्न हैं जिनमें पहला व्यक्ति वियोजित हो जाता है, जो पुनरावृत्ति के पहले शब्द की व्याख्या करता है। यदि पहला व्यक्ति किसी से जुड़ा हुआ है, तो उस व्यक्ति के लिए n − 1 विकल्प हैं, और शेष n − 2 लोगों के लिए संयोजन के T(n − 2) पैटर्न हैं, जो पुनरावृत्ति की दूसरी अवधि की व्याख्या करते हैं।<ref name="chm"/>




=== [[योग]] सूत्र और सन्निकटन ===
=== [[योग]] सूत्र और सन्निकटन ===
टेलीफोन संख्याओ को बिल्कुल योग के रूप में व्यक्त किया जा सकता है
टेलीफोन संख्याओ को परिशुद्ध रूप से योग के रूप में व्यक्त किया जा सकता है
<math display=block>T(n) = \sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!! = \sum_{k=0}^{\lfloor n/2\rfloor}\frac{n!}{2^k (n-2k)! k!}.</math>
<math display=block>T(n) = \sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!! = \sum_{k=0}^{\lfloor n/2\rfloor}\frac{n!}{2^k (n-2k)! k!}.</math>
प्रथम योग के प्रत्येक पद में, <math>k</math> मिलान किए गए जोड़े की संख्या, [[द्विपद गुणांक]] देता है <math>\tbinom{n}{2k}</math> चुनने के तरीकों की संख्या गिनता है <math>2k</math> तत्वों का मिलान किया जाना है, और [[डबल फैक्टोरियल]]
प्रथम योग के प्रत्येक पद में, <math>k</math> मिलान किए गए युग्मों की संख्या देता है, [[द्विपद गुणांक]] <math>\tbinom{n}{2k}</math> मिलान किए जाने वाले <math>2k</math> तत्वों को चयन के तरीकों की संख्या और दोहरे भाज्य की गणना करता है।
<math display=block>(2k-1)!!=\frac{(2k)!}{2^k\,k!}</math> अपने तर्क तक विषम पूर्णांकों का गुणनफल है और पूरी तरह से मिलान करने के तरीकों की संख्या की गणना करता है {{math|2''k''}} चयनित तत्व।<ref name="knuth"/><ref name="chm"/>यह संकलन सूत्र और स्टर्लिंग के सन्निकटन से अनुसरण करता है कि, [[स्पर्शोन्मुख विश्लेषण]],<ref name="knuth"/><ref name="chm">{{citation
<math display=block>(2k-1)!!=\frac{(2k)!}{2^k\,k!}</math> अपने तर्क तक विषम पूर्णांकों का गुणनफल है और पूरी तरह से मिलान करने के तरीकों की संख्या {{math|2''k''}} चयनित तत्व की गणना करता है।<ref name="knuth"/><ref name="chm"/> यह संकलन सूत्र और स्टर्लिंग के सन्निकटन से अनुसरण करता है कि, [[स्पर्शोन्मुख विश्लेषण|स्पर्शोन्मुख विश्लेषण से]],<ref name="knuth"/><ref name="chm">{{citation
  | last1 = Chowla | first1 = S. | author1-link = Sarvadaman Chowla
  | last1 = Chowla | first1 = S. | author1-link = Sarvadaman Chowla
  | last2 = Herstein | first2 = I. N. | author2-link = Israel Nathan Herstein
  | last2 = Herstein | first2 = I. N. | author2-link = Israel Nathan Herstein
Line 173: Line 173:




=== जनरेटिंग फंक्शन ===
=== जनक फलन (जनरेटिंग फ़ंक्शन) ===
टेलीफोन संख्याओ का [[घातीय जनरेटिंग फ़ंक्शन]] है<ref name="chm"/><ref name="gfgt">{{citation
टेलीफोन संख्याओ का [[घातीय जनरेटिंग फ़ंक्शन|घातीय जनक फलन]] है<ref name="chm"/><ref name="gfgt">{{citation
  | last1 = Banderier | first1 = Cyril
  | last1 = Banderier | first1 = Cyril
  | last2 = Bousquet-Mélou | first2 = Mireille | author2-link = Mireille Bousquet-Mélou
  | last2 = Bousquet-Mélou | first2 = Mireille | author2-link = Mireille Bousquet-Mélou
Line 192: Line 192:
  }}</ref>
  }}</ref>
<math display=block>\sum_{n=0}^{\infty}\frac{T(n)x^n}{n!}=\exp\left(\frac{x^2}{2}+x\right).</math>
<math display=block>\sum_{n=0}^{\infty}\frac{T(n)x^n}{n!}=\exp\left(\frac{x^2}{2}+x\right).</math>
दूसरे शब्दों में, टेलीफोन संख्याओ को [[टेलर श्रृंखला]] के गुणांक के रूप में पढ़ा जा सकता है {{math|exp(''x''<sup>2</sup>/2 + ''x'')}}, और यह {{mvar|n}}वां टेलीफोन संख्या शून्य का मान है {{mvar|n}} इस फ़ंक्शन का डेरिवेटिव।
दूसरे शब्दों में, टेलीफोन संख्याओ को {{math|exp(''x''<sup>2</sup>/2 + ''x'')}} की टेलर श्रृंखला के गुणांक के रूप में पढ़ा जा सकता है, और nवी टेलीफ़ोन संख्या इस फलन के nवें अवकल के शून्य पर मान है। यह फलन हर्मिट बहुपदों के चरघातांकी जनक फलन से निकटता से संबंधित है, जो पूर्ण रेखांकन के अनुरूप वाले बहुपद हैं।<ref name="gfgt"/> nवें (प्रायिकतावादी) हर्मिट बहुपद के गुणांकों के निरपेक्ष मानो का योग nवीं टेलीफोन संख्या है, और टेलीफोन संख्याओ को हर्मिट बहुपदों के कुछ विशेष मानो के रूप में भी अनुभव किया जा सकता है:<ref name="sbdhp"/><ref name="gfgt"/>
यह फ़ंक्शन हर्मिट बहुपदों के घातीय जनरेटिंग फ़ंक्शन से निकटता से संबंधित है, जो पूर्ण ग्राफ़ के मिलान वाले बहुपद हैं।<ref name="gfgt"/>के गुणांकों के निरपेक्ष मूल्यों का योग {{mvar|n}}(संभाव्यवादी) हर्मिट बहुपद है {{mvar|n}}वें टेलीफोन संख्या, और टेलीफोन संख्याओ को हर्मिट बहुपदों के कुछ विशेष मूल्यों के रूप में भी महसूस किया जा सकता है:<ref name="sbdhp"/><ref name="gfgt"/>
<math display=block>T(n)=\frac{\mathit{He}_n(i)}{i^n}.</math>
<math display=block>T(n)=\frac{\mathit{He}_n(i)}{i^n}.</math>




=== प्रमुख कारक ===
=== प्रमुख कारक ===
के बड़े मूल्यों के लिए {{mvar|n}}, द {{mvar|n}}वां टेलीफोन संख्या दो की बड़ी शक्ति से विभाज्य है, {{math|2<sup>''n''/4 + ''O''(1)</sup>}}. अधिक सटीक रूप से, [[पी-एडिक ऑर्डर]] | 2-एडिक ऑर्डर ([[ मुख्य गुणनखंड प्रक्रिया ]] में दो के कारकों की संख्या) {{math|''T''(4''k'')}} और का {{math|''T''(4''k'' + 1)}} है {{mvar|k}}; के लिए {{math|''T''(4''k'' + 2)}} यह है {{math|''k'' + 1}}, और के लिए {{math|''T''(4''k'' + 3)}} यह है {{math|''k'' + 2}}.<ref>{{citation
n के बड़े मानों के लिए, nवां टेलीफोन संख्या दो, 2<sup>''n''/4 + ''O''(1)</sup> की बड़ी घात से विभाज्य है। अधिक परिशुद्ध रूप से, T(4k) और T(4k + 1) का 2-अंकीय क्रम (प्रमुख गुणनखंड में दो के कारकों की संख्या) k है; और T(4k + 2) के लिए यह k + 1 है, और T(4k + 3) के लिए यह k + 2 है।<ref>{{citation
  | last1 = Kim | first1 = Dongsu
  | last1 = Kim | first1 = Dongsu
  | last2 = Kim | first2 = Jang Soo
  | last2 = Kim | first2 = Jang Soo
Line 211: Line 210:
  | s2cid = 17457503
  | s2cid = 17457503
  }}</ref>
  }}</ref>
किसी भी अभाज्य संख्या के लिए {{mvar|p}}, कोई परीक्षण कर सकता है कि क्या कोई टेलीफोन संख्या मौजूद है जिससे विभाज्य है {{mvar|p}} टेलीफोन संख्याओ के अनुक्रम के लिए पुनरावृत्ति की गणना करके, मॉड्यूलो {{mvar|p}}, या तो शून्य या चक्र पहचान तक पहुंचने तक। वे अभाज्य संख्याएँ जो कम से कम एक टेलीफोन संख्या को विभाजित करती हैं<ref>{{cite OEIS|A264737|mode=cs2}}</ref>
 
{{bi|left=1.6|2, 5, 13, 19, 23, 29, 31, 43, 53, 59, ... {{OEIS|A264737}}}}
किसी भी अभाज्य संख्या p के लिए, कोई यह परीक्षण कर सकता है कि टेलीफोन संख्या मापांक p के अनुक्रम के लिए पुनरावृत्ति की गणना करके या तो शून्य तक पहुँचने तक या एक चक्र का पता लगाने के लिए p से विभाज्य कोई टेलीफोन संख्या सम्मिलित है या नहीं है। वे अभाज्य संख्याएँ जो कम से कम एक टेलीफोन संख्या को विभाजित करती हैं,<ref>{{cite OEIS|A264737|mode=cs2}}</ref>
इस क्रम में विषम अभाज्य संख्याओं को अक्षम कहा गया है। उनमें से प्रत्येक असीम रूप से कई टेलीफोन संख्याओ को विभाजित करता है।<ref>{{citation
 
2, 5, 13, 19, 23, 29, 31, 43, 53, 59, ... (ओईआईएस में अनुक्रम ए264737) सम्मिलित है।
 
इस क्रम में विषम अभाज्य संख्याओं को अक्षम कहा गया है। उनमें से प्रत्येक अधिकतम रूप मे कई टेलीफोन संख्याओ को विभाजित करता है।<ref>{{citation
  | last1 = Amdeberhan | first1 = Tewodros
  | last1 = Amdeberhan | first1 = Tewodros
  | last2 = Moll | first2 = Victor
  | last2 = Moll | first2 = Victor
Line 226: Line 228:
  | year = 2015| s2cid = 119708272
  | year = 2015| s2cid = 119708272
  }}</ref>
  }}</ref>





Revision as of 12:55, 30 May 2023

यह लेख पूर्णांक अनुक्रम के बारे में है। फ़ोन नेटवर्क एड्रैस के लिए, टेलीफोन संख्या (गणित) देखें।

पूर्ण आलेख K4 में दस मिलान हैं, जो चौथे टेलीफोन संख्या (गणित) के मान T(4) = 10 के अनुरूप हैं।

गणित में, टेलीफोन संख्या (गणित) या अंतर्वलन संख्या पूर्णांकों का एक क्रम बनाते हैं जो उन तरीकों की गणना करते हैं जिनसे n लोग व्यक्ति-से-व्यक्ति टेलीफोन (दूरभाष) कॉल द्वारा जुड़े हो सकते हैं। ये संख्याएँ n शीर्षों पर एक पूर्ण आलेख के मिलानों की संख्या (होसोया सूचकांक) का भी वर्णन करती हैं, और n तत्वों पर क्रमपरिवर्तन की संख्या, जो अंतर्वलन हैं, हर्मिट बहुपदों के गुणांकों के निरपेक्ष मानो का योग, मानक नवोदित सारणी की संख्या n सेल के साथ, और सममित समूह के अखंडनीय निरूपण की डिग्री का योग होता है। हेनरिक ऑगस्ट रोथ द्वारा 1800 में पहली बार अंतर्वलन संख्याओ का अध्ययन किया गया था, जिन्होंने एक पुनरावृत्ति समीकरण दिया था जिसके द्वारा उन्हें मान (n = 0 से प्रारंभ)[1] देकर गणना की जा सकती है

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (ओईआईएस में अनुक्रम A000085) सम्मिलित है।

अनुप्रयोग

जॉन रिओर्डन (गणितज्ञ) इन संख्याओं के लिए निम्नलिखित स्पष्टीकरण प्रदान करते हैं: मान लीजिए कि n लोग एक टेलीफोन सेवा की सदस्यता लेते हैं जो उनमें से किन्हीं दो को एक कॉल से जोड़ सकती है, लेकिन दो से अधिक लोगों को जोड़ने वाली एक कॉल नहीं कर सकती। सम्पर्क के कितने अलग-अलग पैटर्न संभव हैं? उदाहरण के लिए, तीन ग्राहकों के साथ, एक टेलीफोन कॉल करने के तीन तरीके हैं, और कुल चार पैटर्न के लिए एक अतिरिक्त पैटर्न जिसमें कोई कॉल नहीं की जा रही है।[2] इस कारण से, कितने पैटर्न संभव हैं, यह गिनने वाले संख्याओ को कभी-कभी टेलीफोन संख्या कहा जाता है।[3][4]

युग्‍मानूसार सम्पर्क के बीच प्रत्येक पैटर्न n लोग एक समावेशन (गणित) को परिभाषित करते हैं, लोगों का एक क्रमचय है जो इसका अपना व्युत्क्रम है। इस क्रमपरिवर्तन में, एक-दूसरे को कॉल करने वाले प्रत्येक दो लोगों की विनिमेयता की जाती है, और कॉल में सम्मिलित नहीं होने वाले लोग अपने स्थान पर स्थिर रहते हैं। इसके विपरीत, प्रत्येक संभव आक्रमण में इस प्रकार के युग्‍मानूसार विनिमय के समुच्चय का रूप होता है। इसलिए, टेलीफोन संख्या भी निवेशों की गणना करते हैं। 1800 में रोथ द्वारा अध्ययन की गई गणना की समस्या मूल संयोजी गणना समस्या थी[1] और इन संख्याओ को अंतर्वलन संख्या भी कहा गया है।[5][6]

आलेख सिद्धांत में, आलेख के कोरों का एक उपसमुच्चय जो प्रत्येक शीर्ष को एक से अधिक बार स्पर्श करता है, उसे मिलान (आलेख सिद्धांत) कहा जाता है। किसी दिए गए आलेख के मिलान की गणना करना रासायनिक आलेख सिद्धांत में महत्वपूर्ण है, जहाँ आलेख मॉडल अणु और मिलान की संख्या होसोया सूचकांक है। एक का सबसे बड़ा संभव होसोया सूचकांक n-शीर्ष आरेख पूर्ण आरेख द्वारा दिया जाता है, जिसके लिए युग्‍मानूसार सम्पर्क का कोई भी पैटर्न संभव है; इस प्रकार n शीर्षों पर एक पूर्ण आरेख का होसोया सूचकांक nवें टेलीफोन संख्या के समान है।[7]

एक वर्ग के शीर्ष पर चार वर्गों के शीर्ष पर पांच वर्ग, सभी उचित बाएं। वे पढ़ते हैं, बाएं से दाएं, नीचे से ऊपर: 1,2,4,7,8,3,5,6,9,10
एक मानक नवोदित सारणी

एक फेरर्स आरेख एक ज्यामितीय आकृति है जो विमान में n वर्गों के संग्रह द्वारा बनाई गई है, एक क्षैतिज शीर्ष कोरों, एक ऊर्ध्वाधर बाएं कोरों और कोरों की एक एकल एकदिष्ट श्रृंखला के साथ एक पॉलीओमिनो में समूहीकृत है। इन वर्गों में 1 से n तक की संख्याओं को इस प्रकार रखकर एक मानक नवोदित सारणी बनाई जाती है कि पूरी सारणी में संख्याएँ बाएँ से दाएँ और ऊपर से नीचे तक बढ़ती हैं। रॉबिन्सन-शेंस्टेड पत्राचार के अनुसार, क्रमपरिवर्तन मानक नवोदित सारणी के क्रमिक युग्म के साथ एक-से-एक के अनुरूप हैं। एक क्रमचय को व्युत्क्रम करना दो सारणियों की विनिमेयता के समान है, और इसलिए स्व-प्रतिलोम क्रमपरिवर्तन एकल सारणी के अनुरूप हैं, जो स्वयं के साथ युग्म जाते हैं।[8] इस प्रकार, टेलीफोन संख्या भी n वर्गों के साथ नवोदित सारणी की संख्या की गणना करते हैं।[1] प्रतिनिधित्व सिद्धांत में, फेरर्स आरेख क्रमपरिवर्तन के सममित समूह के अखंडनीय निरूपण के अनुरूप होते हैं, और किसी दिए गए आकार के साथ नवोदित सारणी उस आकृति के साथ अलघुकरणीय प्रतिनिधित्व का आधार होती है। इसलिए, टेलीफोन संख्या अखंडनीय निरूपण की डिग्री का योग देते हैं।[9]

abcdefgh
8
Chessboard480.svg
d8 white rook
g7 white rook
c6 white rook
a5 white rook
e4 white rook
h3 white rook
b2 white rook
f1 white rook
8
77
66
55
44
33
22
11
abcdefgh
एक शतरंज की बिसात पर आठ शतरंज के हाथी का तिरछा सममित गैर-आक्षेप क्रमस्थान

गणितीय शतरंज के गणित में, टेलीफोन संख्या n × n शतरंज की बिसात पर n चालाक खिलाड़ी को रखने के तरीकों की संख्या को इस तरह से गिनते हैं कि कोई भी दो चालाक खिलाड़ी एक दूसरे पर आक्षेप न करें तथाकथित आठ चालाक खिलाड़ी पहेली, और इस तरह से बोर्ड के विकर्ण प्रतिबिंब के अंतर्गत चालाक खिलाड़ी का विन्यास सममित है। पोल्या गणना प्रमेय के माध्यम से, ये संख्याएं परस्पर गैर-आक्रमणकारी चालाक खिलाड़ी के "अनिवार्य रूप से भिन्न" विन्यासों की समग्र संख्या के लिए एक सूत्र के प्रमुख घटकों में से एक हैं, जहां दो विन्यासों को अनिवार्य रूप से भिन्न के रूप में गिना जाता है यदि कोई समरूपता नहीं है बोर्ड जो एक को दूसरे में ले जाता है।[10]


गणितीय गुण

पुनरावृत्ति

टेलीफोन संख्या पुनरावृत्ति संबंध को संतुष्ट करते हैं

पहली बार 1800 में हेनरिक अगस्त रोथ द्वारा प्रकाशित किया गया था, जिसके द्वारा उनकी आसानी से गणना की जा सकती है।[1] इस पुनरावृत्ति की व्याख्या करने का एक तरीका यह है कि n ग्राहकों के टेलीफोन प्रणाली के T(n) संयोजन पैटर्न को ऐसे पैटर्न में विभाजित किया जाए जिसमें पहला व्यक्ति किसी और को कॉल नहीं कर रहा है, ऐसे T(n − 1) संयोजन पैटर्न हैं जिनमें पहला व्यक्ति वियोजित हो जाता है, जो पुनरावृत्ति के पहले शब्द की व्याख्या करता है। यदि पहला व्यक्ति किसी से जुड़ा हुआ है, तो उस व्यक्ति के लिए n − 1 विकल्प हैं, और शेष n − 2 लोगों के लिए संयोजन के T(n − 2) पैटर्न हैं, जो पुनरावृत्ति की दूसरी अवधि की व्याख्या करते हैं।[11]


योग सूत्र और सन्निकटन

टेलीफोन संख्याओ को परिशुद्ध रूप से योग के रूप में व्यक्त किया जा सकता है

प्रथम योग के प्रत्येक पद में, मिलान किए गए युग्मों की संख्या देता है, द्विपद गुणांक मिलान किए जाने वाले तत्वों को चयन के तरीकों की संख्या और दोहरे भाज्य की गणना करता है।
अपने तर्क तक विषम पूर्णांकों का गुणनफल है और पूरी तरह से मिलान करने के तरीकों की संख्या 2k चयनित तत्व की गणना करता है।[1][11] यह संकलन सूत्र और स्टर्लिंग के सन्निकटन से अनुसरण करता है कि, स्पर्शोन्मुख विश्लेषण से,[1][11][12]


जनक फलन (जनरेटिंग फ़ंक्शन)

टेलीफोन संख्याओ का घातीय जनक फलन है[11][13]

दूसरे शब्दों में, टेलीफोन संख्याओ को exp(x2/2 + x) की टेलर श्रृंखला के गुणांक के रूप में पढ़ा जा सकता है, और nवी टेलीफ़ोन संख्या इस फलन के nवें अवकल के शून्य पर मान है। यह फलन हर्मिट बहुपदों के चरघातांकी जनक फलन से निकटता से संबंधित है, जो पूर्ण रेखांकन के अनुरूप वाले बहुपद हैं।[13] nवें (प्रायिकतावादी) हर्मिट बहुपद के गुणांकों के निरपेक्ष मानो का योग nवीं टेलीफोन संख्या है, और टेलीफोन संख्याओ को हर्मिट बहुपदों के कुछ विशेष मानो के रूप में भी अनुभव किया जा सकता है:[5][13]


प्रमुख कारक

n के बड़े मानों के लिए, nवां टेलीफोन संख्या दो, 2n/4 + O(1) की बड़ी घात से विभाज्य है। अधिक परिशुद्ध रूप से, T(4k) और T(4k + 1) का 2-अंकीय क्रम (प्रमुख गुणनखंड में दो के कारकों की संख्या) k है; और T(4k + 2) के लिए यह k + 1 है, और T(4k + 3) के लिए यह k + 2 है।[14]

किसी भी अभाज्य संख्या p के लिए, कोई यह परीक्षण कर सकता है कि टेलीफोन संख्या मापांक p के अनुक्रम के लिए पुनरावृत्ति की गणना करके या तो शून्य तक पहुँचने तक या एक चक्र का पता लगाने के लिए p से विभाज्य कोई टेलीफोन संख्या सम्मिलित है या नहीं है। वे अभाज्य संख्याएँ जो कम से कम एक टेलीफोन संख्या को विभाजित करती हैं,[15]

2, 5, 13, 19, 23, 29, 31, 43, 53, 59, ... (ओईआईएस में अनुक्रम ए264737) सम्मिलित है।

इस क्रम में विषम अभाज्य संख्याओं को अक्षम कहा गया है। उनमें से प्रत्येक अधिकतम रूप मे कई टेलीफोन संख्याओ को विभाजित करता है।[16]


संदर्भ

  1. 1.0 1.1 1.2 1.3 1.4 1.5 Knuth, Donald E. (1973), The Art of Computer Programming, Volume 3: Sorting and Searching, Reading, Mass.: Addison-Wesley, pp. 65–67, MR 0445948
  2. Riordan, John (2002), Introduction to Combinatorial Analysis, Dover, pp. 85–86
  3. Peart, Paul; Woan, Wen-Jin (2000), "Generating functions via Hankel and Stieltjes matrices" (PDF), Journal of Integer Sequences, 3 (2), Article 00.2.1, Bibcode:2000JIntS...3...21P, MR 1778992
  4. Getu, Seyoum (1991), "Evaluating determinants via generating functions", Mathematics Magazine, 64 (1): 45–53, doi:10.2307/2690455, JSTOR 2690455, MR 1092195
  5. 5.0 5.1 Solomon, A. I.; Blasiak, P.; Duchamp, G.; Horzela, A.; Penson, K.A. (2005), "Combinatorial physics, normal order and model Feynman graphs", in Gruber, Bruno J.; Marmo, Giuseppe; Yoshinaga, Naotaka (eds.), Symmetries in Science XI, Kluwer Academic Publishers, pp. 527–536, arXiv:quant-ph/0310174, doi:10.1007/1-4020-2634-X_25, S2CID 5702844
  6. Blasiak, P.; Dattoli, G.; Horzela, A.; Penson, K. A.; Zhukovsky, K. (2008), "Motzkin numbers, central trinomial coefficients and hybrid polynomials", Journal of Integer Sequences, 11 (1), Article 08.1.1, arXiv:0802.0075, Bibcode:2008JIntS..11...11B, MR 2377567
  7. Tichy, Robert F.; Wagner, Stephan (2005), "Extremal problems for topological indices in combinatorial chemistry" (PDF), Journal of Computational Biology, 12 (7): 1004–1013, doi:10.1089/cmb.2005.12.1004, PMID 16201918
  8. A direct bijection between involutions and tableaux, inspired by the recurrence relation for the telephone numbers, is given by Beissinger, Janet Simpson (1987), "Similar constructions for Young tableaux and involutions, and their application to shiftable tableaux", Discrete Mathematics, 67 (2): 149–163, doi:10.1016/0012-365X(87)90024-0, MR 0913181
  9. Halverson, Tom; Reeks, Mike (2015), "Gelfand models for diagram algebras", Journal of Algebraic Combinatorics, 41 (2): 229–255, doi:10.1007/s10801-014-0534-5, MR 3306071, S2CID 7419411
  10. Holt, D. F. (1974), "Rooks inviolate", The Mathematical Gazette, 58 (404): 131–134, doi:10.2307/3617799, JSTOR 3617799, S2CID 250441965
  11. 11.0 11.1 11.2 11.3 Chowla, S.; Herstein, I. N.; Moore, W. K. (1951), "On recursions connected with symmetric groups. I", Canadian Journal of Mathematics, 3: 328–334, doi:10.4153/CJM-1951-038-3, MR 0041849, S2CID 123802787
  12. Moser, Leo; Wyman, Max (1955), "On solutions of xd = 1 in symmetric groups", Canadian Journal of Mathematics, 7: 159–168, doi:10.4153/CJM-1955-021-8, MR 0068564
  13. 13.0 13.1 13.2 Banderier, Cyril; Bousquet-Mélou, Mireille; Denise, Alain; Flajolet, Philippe; Gardy, Danièle; Gouyou-Beauchamps, Dominique (2002), "Generating functions for generating trees", Discrete Mathematics, 246 (1–3): 29–55, arXiv:math/0411250, doi:10.1016/S0012-365X(01)00250-3, MR 1884885, S2CID 14804110
  14. Kim, Dongsu; Kim, Jang Soo (2010), "A combinatorial approach to the power of 2 in the number of involutions", Journal of Combinatorial Theory, Series A, 117 (8): 1082–1094, arXiv:0902.4311, doi:10.1016/j.jcta.2009.08.002, MR 2677675, S2CID 17457503
  15. Sloane, N. J. A. (ed.), "Sequence A264737", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
  16. Amdeberhan, Tewodros; Moll, Victor (2015), "Involutions and their progenies", Journal of Combinatorics, 6 (4): 483–508, arXiv:1406.2356, doi:10.4310/JOC.2015.v6.n4.a5, MR 3382606, S2CID 119708272