डेटिंग नंबर

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

उदाहरण के लिए, यदि सात अलग-अलग लोगों को सात उपहार दिए जाते हैं, लेकिन केवल दो को ही सही उपहार मिलना निश्चित है, तो D_7, 2= 924 प्रकार से ऐसा हो सकता है। एक और प्रायः उद्धृत उदाहरण एक नृत्य विद्यालय का है, जहां 7 जोड़ों के साथ चाय-ब्रेक के बाद प्रतिभागियों को क्रमविहीन प्रकार से एक साथी को खोजने के लिए कहा जाता है, फिर एक बार D_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 निश्चित बिंदुओं को चुनें; फिर अन्य n − k बिंदुओं का विचलन चुनें।

संख्या D_n,0/(n!) घात श्रेणी e^−z/(1 − z) द्वारा उत्पन्न होते है, इसलिए,

d _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!}}$

N बड़े के लिए, m निश्चित।

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

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

${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.