डेटिंग नंबर

साहचर्य गणित में, रेनकॉन्ट्रेस संख्याएं पूर्णांकों की एक त्रिकोणीय सरणी होती हैं, जो निश्चित बिंदु (गणित) की निर्दिष्ट संख्या के साथ सेट { 1, ..., n } के क्रमपरिवर्तन की गणना करती हैं: दूसरे शब्दों में, आंशिक विचलन। (Rencontre मुठभेड़ के लिए फ्रेंच है। कुछ खातों के अनुसार, समस्या का नाम त्यागी गेम के नाम पर रखा गया है।) n ≥ 0 और 0 ≤ k ≤ n' के लिए ', रेनकंट्रेस नंबर डीn, k { 1, ..., n } के क्रमचयों की संख्या है जिनके ठीक k निश्चित बिंदु हैं।

उदाहरण के लिए, यदि सात अलग-अलग लोगों को सात उपहार दिए जाते हैं, लेकिन केवल दो को ही सही उपहार मिलना तय है, तो डी_7, 2= 924 तरीके से ऐसा हो सकता है। एक और अक्सर उद्धृत उदाहरण 7 जोड़ों के साथ एक डांस स्कूल का है, जहां चाय-ब्रेक के बाद प्रतिभागियों को कहा जाता है कि वे बेतरतीब ढंग से एक साथी को जारी रखने के लिए खोजें, फिर एक बार डी_7, 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$. But one can also order them in columns corresponding to the number of moved elements $i=n-k$ (sequence A098825 in the OEIS). Each entry in the table below on the left can be factored into two terms given in the table below on the right: the product of a binomial coefficient (given first in red) and a subfactorial (given second in blue). In this order each column corresponds to one subfactorial: $~~~T(n,i)={\binom {n}{i}}~\cdot ~!i$
i n  0 1 2 3 4 5 6 7 8 0 1 1 1 0 2 1 0 1 3 1 0 3 2 4 1 0 6 8 9 5 1 0 10 20 45 44 6 1 0 15 40 135 264 265 7 1 0 21 70 315 924 1855 1854 8 1 0 28 112 630 2464 7420 14832 14833	i n  0 1 2 3 4 5 6 7 8 0 1⋅1 1 1⋅1 1⋅0 2 1⋅1 2⋅0 1⋅1 3 1⋅1 3⋅0 3⋅1 1⋅2 4 1⋅1 4⋅0 6⋅1 4⋅2 1⋅9 5 1⋅1 5⋅0 10⋅1 10⋅2 5⋅9 1⋅44 6 1⋅1 6⋅0 15⋅1 20⋅2 15⋅9 6⋅44 1⋅265 7 1⋅1 7⋅0 21⋅1 35⋅2 35⋅9 21⋅44 7⋅265 1⋅1854 8 1⋅1 8⋅0 28⋅1 56⋅2 70⋅9 56⋅44 28⋅265 8⋅1854 1⋅14833

सूत्र

K = 0 कॉलम में संख्याएँ अव्यवस्थाओं की गणना करती हैं। इस प्रकार

$D_{0,0}=1,\!$

$D_{1,0}=0,\!$

$D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})\!$

गैर-नकारात्मक n के लिए। यह पता चला है कि

$D_{n,0}=\left\lceil {\frac {n!}{e}}\right\rfloor ,$

जहाँ अनुपात को सम n के लिए राउंड अप किया जाता है और विषम n के लिए नीचे राउंड किया जाता है। n ≥ 1 के लिए, यह निकटतम पूर्णांक देता है।

अधिक आम तौर पर, किसी के लिए $k\geq 0$, अपने पास

$D_{n,k}={n \choose k}\cdot D_{n-k,0}.$

सबूत आसान है जब कोई जानता है कि विचलन को कैसे गणना करना है: एन में से के निश्चित बिंदुओं को चुनें; फिर अन्य n − k बिंदुओं का विचलन चुनें।

संख्या D_n,0/(n!) बिजली की श्रृंखला ़ द्वारा फंक्शन जनरेट कर रहे हैं e^−z/(1 − z); इसलिए, डी के लिए एक स्पष्ट सूत्र_n, m निम्नानुसार व्युत्पन्न किया जा सकता है:

$D_{n,m}={\frac {n!}{m!}}[z^{n-m}]{\frac {e^{-z}}{1-z}}={\frac {n!}{m!}}\sum _{k=0}^{n-m}{\frac {(-1)^{k}}{k!}}.$

इसका तुरंत तात्पर्य है

$D_{n,m}={n \choose m}D_{n-m,0}\;\;{\mbox{ and }}\;\;{\frac {D_{n,m}}{n!}}\approx {\frac {e^{-1}}{m!}}$

एन बड़े के लिए, एम फिक्स्ड।

संभाव्यता वितरण

संख्यात्मक मान में तालिका के लिए प्रत्येक पंक्ति में प्रविष्टियों का योग { 1, ..., n } के क्रमचय की कुल संख्या है, और इसलिए n है !. यदि कोई nवीं पंक्ति की सभी प्रविष्टियों को n! से विभाजित करता है, तो उसे { 1 के समान रूप से वितरित यादृच्छिक क्रमपरिवर्तन के निश्चित बिंदुओं की संख्या का संभाव्यता वितरण प्राप्त होता है , ..., एन }। संभावना है कि निश्चित बिंदुओं की संख्या 'के' है

${D_{n,k} \over n!}.$

n ≥ 1 के लिए, निश्चित बिंदुओं की अपेक्षित मान संख्या 1 है (एक तथ्य जो अपेक्षा की रैखिकता से अनुसरण करता है)।

अधिक आम तौर पर, i ≤ n के लिए, इस संभाव्यता बंटन का iवां क्षण (गणित) अपेक्षित मान 1 के साथ प्वासों बंटन का iवां क्षण है। i > n के लिए, iवां क्षण उस प्वासों बंटन से छोटा होता है। विशेष रूप से, i ≤ n के लिए, iवां क्षण iवां बेल नंबर है, यानी आकार i के सेट के विभाजन की संख्या।

संभाव्यता वितरण को सीमित करना

जैसे-जैसे अनुमत सेट का आकार बढ़ता है, हमें मिलता है

$\lim _{n\to \infty }{D_{n,k} \over n!}={e^{-1} \over k!}.$

यह केवल संभावना है कि अपेक्षित मान 1 वाला पॉइसन-वितरित यादृच्छिक चर k के बराबर है। दूसरे शब्दों में, जैसे-जैसे n बढ़ता है, आकार n के एक सेट के यादृच्छिक क्रमचय के निश्चित बिंदुओं की संख्या का प्रायिकता वितरण अपेक्षित मान 1 के साथ प्वासों वितरण तक पहुंचता है।

यह भी देखें

• ओबरवॉल्फ समस्या, एक अलग गणितीय समस्या जिसमें टेबल पर भोजन करने वालों की व्यवस्था शामिल है
• Probleme des ménages, इसी तरह की एक समस्या जिसमें आंशिक अव्यवस्था शामिल है

संदर्भ

• Riordan, John, An Introduction to Combinatorial Analysis, New York, Wiley, 1958, pages 57, 58, and 65.
• Weisstein, Eric W. "Partial Derangements". MathWorld.