डेटिंग नंबर
साहचर्य गणित में, डेटिंग संख्याएं पूर्णांकों के एक त्रिकोणीय क्रम हैं, जो निश्चित बिंदु (गणित) की निर्दिष्ट संख्या के साथ सेट { 1, ..., n } के क्रमपरिवर्तन की गणना करती हैं: दूसरे शब्दों में, इसे आंशिक विचलन कह सकते है। कुछ (लेखों के अनुसार, इस समस्या का नाम एकरत्नी गेम के नाम पर रखा गया है।) n ≥ 0 और 0 ≤ k ≤ n' के लिए ', डेटिंग संख्या Dn, k { 1, ..., n } के क्रमपरिवर्तन की संख्या है, जिनके k निश्चित बिंदु हैं।
उदाहरण के लिए, यदि सात अलग-अलग लोगों को सात उपहार दिए जाते हैं, लेकिन केवल दो को ही सही उपहार मिलना निश्चित है, तो D7, 2= 924 प्रकार से ऐसा हो सकता है। एक और प्रायः उद्धृत उदाहरण एक नृत्य विद्यालय का है, जहां 7 जोड़ों के साथ चाय-ब्रेक के बाद प्रतिभागियों को क्रमविहीन प्रकार से एक साथी को खोजने के लिए कहा जाता है, फिर एक बार D7, 2= 924 संभावनाएं हैं कि 2 पिछले जोड़े संयोग से फिर से मिलें।
संख्यात्मक मान
यहाँ इस क्रम का आरंभ है (sequence A008290 in the OEIS):
k n |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | ||||||||
1 | 0 | 1 | |||||||
2 | 1 | 0 | 1 | ||||||
3 | 2 | 3 | 0 | 1 | |||||
4 | 9 | 8 | 6 | 0 | 1 | ||||
5 | 44 | 45 | 20 | 10 | 0 | 1 | |||
6 | 265 | 264 | 135 | 40 | 15 | 0 | 1 | ||
7 | 1854 | 1855 | 924 | 315 | 70 | 21 | 0 | 1 | |
8 | 14833 | 14832 | 7420 | 2464 | 630 | 112 | 28 | 0 | 1 |
ordered by number of moved elements | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
The usual way (table above) to show the rencontres numbers is in columns corresponding to the number of fixed points . | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
सूत्र
K = 0 पंक्ति में संख्याएँ अव्यवस्थाओं की गणना करते हैं। इस प्रकार
गैर-नकारात्मक n के लिए, यह पता चलता है कि
जहाँ अनुपात को सम n के लिए पूर्णांकित किया जाता है और विषम n के लिए नीचे की ओर पूर्णांकित किया जाता है। n ≥ 1 के लिए, यह निकटतम पूर्णांक देता है।
अधिक समान्यतः, किसी , के लिए हमारे पास है
प्रमाण आसान है जब कोई जानता है कि विचलन की गणना कैसे करनी है: n में से k निश्चित बिंदुओं को चुनें; फिर अन्य n − k बिंदुओं का विचलन चुनें।
संख्या Dn,0/(n!) घात श्रेणी e−z/(1 − z) द्वारा उत्पन्न होते है, इसलिए,
d n, m के लिए एक स्पष्ट सूत्र निम्नानुसार व्युत्पन्न किया जा सकता है:
इसका तुरंत तात्पर्य है
N बड़े के लिए, m निश्चित।
संभाव्यता वितरण
"संख्यात्मक मान" में तालिका के लिए प्रत्येक पंक्ति में प्रविष्टियों का योग { 1, ..., n } के क्रमचय की कुल संख्या है, और इसलिए n ! है। यदि कोई nवीं पंक्ति की सभी प्रविष्टियों को n! से विभाजित करता है, तो उसे { 1 , ..., n } के समान रूप से वितरित यादृच्छिक क्रमपरिवर्तन के निश्चित बिंदुओं की संख्या का संभाव्यता वितरण प्राप्त होता है। संभावना है कि निश्चित बिंदुओं की संख्या 'k' है
n ≥ 1 के लिए, निश्चित बिंदुओं की अपेक्षित मान संख्या 1 है (एक तथ्य जो अपेक्षा की रैखिकता से अनुसरण करता है)।
अधिक समान्यतः, i ≤ n के लिए, इस संभाव्यता वितरण का iवां क्षण (गणित) अपेक्षित मान 1 के साथ प्वासों वितरण का iवां क्षण है।[1] i > n के लिए, iवां क्षण उस प्वासों वितरण से छोटा होता है। विशेष रूप से, i ≤ n के लिए, iवां क्षण iवां बेल संख्या है, यानी आकार i के सेट के विभाजन की संख्या।
संभाव्यता वितरण को सीमित करना
जैसे-जैसे अनुमत सेट का आकार बढ़ता है, हमें निम्नलिखित प्राप्त होता है
यह केवल संभावना है कि अपेक्षित मान 1 वाला पॉइसन-वितरित यादृच्छिक चर k के बराबर है। दूसरे शब्दों में, जैसे-जैसे n बढ़ता है आकार n के एक सेट के यादृच्छिक क्रमचय के निश्चित बिंदुओं की संख्या का प्रायिकता वितरण अपेक्षित मान 1 के साथ पॉइसन वितरण तक पहुंचता है।
यह भी देखें
- ओबरवॉल्फ समस्या, एक अलग गणितीय समस्या जिसमें टेबल पर भोजन करने वालों की व्यवस्था समिलित है
- Probleme des ménages, इसी तरह की एक समस्या जिसमें आंशिक अव्यवस्था समिलित है
संदर्भ
- ↑ Jim Pitman, "Some Probabilistic Aspects of Set Partitions", American Mathematical Monthly, volume 104, number 3, March 1997, pages 201–209.
- Riordan, John, An Introduction to Combinatorial Analysis, New York, Wiley, 1958, pages 57, 58, and 65.
- Weisstein, Eric W. "Partial Derangements". MathWorld.