Комбинаторикада кездесетін сандар: дербиждер және тоқталған нүктелер саны
Rencontres numbers
Комбинаторикадағы кездесу сандары – {1, …, n} жиынының белгілі бір түйіскен нүктелер саны бар орналасуларын есептейтін үшбұрышты сандар. Математика, дербиджменттер.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Комбинаторикада, rencontres сандары — бұл {1, , n} жиынының пермутацияларын белгіленген сандағы түрақты нүктелермен санап шығатын бүтін сандардың үшбұрышты массиві: яғни, ішінара дербиждер. (Rencontre француз тілінде «кездесу» дегенді білдіреді. Кейбір мәліметтер бойынша, бұл мәселе бір түрі пасьянс ойынының атымен аталған.) n ≥ 0 және 0 ≤ k ≤ n үшін, Dn, k кездесу саны — {1, , n} жиынының дәл k түрақты нүктесі бар пермутациялардың саны. Мысалы, егер жеті түрлі адамға жеті сыйлық берілсе, бірақ олардың тек екеуіне ғана дұрыс сыйлық тисе, онда D7, 2 = 924 мүмкіндік бар. Тағы бір жиі келтірілетін мысал — 7 жұптан тұратын би мектебі, онда шай ішуден кейін қатысушыларға жаңа серіктес тауып билеуге рұқсат етілсе, содан кейін тағы да D7, 2 = 924 мүмкіндік бар, яғни 2 бұрынғы жұп кездейсоқ қайтадан кездеседі.
In combinatorics, the rencontres numbers are a triangular array of integers that enumerate permutations of the set { 1, , n } with specified numbers of fixed points: in other words, partial derangements. (Rencontre is French for encounter. By some accounts, the problem is named after a solitaire game.) For n ≥ 0 and 0 ≤ k ≤ n, the rencontres number Dn, k is the number of permutations of { 1, , n } that have exactly k fixed points. For example, if seven presents are given to seven different people, but only two are destined to get the right present, there are D7, 2 = 924 ways this could happen. Another often cited example is that of a dance school with 7 couples, where, after tea break the participants are told to randomly find a partner to continue, then once more there are D7, 2 = 924 possibilities that 2 previous couples meet again by chance.
Ықтималдық үлестірімі
"Нумерлік мәндер" кестесіндегі әрбір қатардағы жазбалардың қосындысы {1, , n} жиынының барлық мүмкін орналасуларының (пермутацияларының) жалпы санына тең, демек n! құрайды. Егер n-ші қатардағы барлық жазбаларды n! санына бөлсек, {1, , n} жиынының біркелкі таралымды кездейсоқ орналасуындағы бекітілген нүктелер санының ықтималдық үлестірілемін аламыз. Бекітілген нүктелер саны k-ға тең болу ықтималдығы:
The sum of the entries in each row for the table in "Numerical Values" is the total number of permutations of { 1, , n }, and is therefore n!. If one divides all the entries in the nth row by n!, one gets the probability distribution of the number of fixed points of a uniformly distributed random permutation of { 1, , n }. The probability that the number of fixed points is k is
n ≥ 1 үшін, бекітілген нүктелердің күтілетін саны 1-ге тең (бұл күтудің сызықтығынан туындайтын факт). Көбірек айтқанда, i ≤ n үшін, осы ықтималдық үлестірілімінің i-ші моменті, күтілетін мәні 1 болатын Пуассон үлестірілімінің i-ші моментымен бірдей. i > n үшін, i-ші момент сол Пуассон үлестірілімінің i-ші моментынан кіші болады. Нақтырақ айтқанда, i ≤ n үшін, i-ші момент – i өлшемді жиынның бөліністерінің саны, яғни i-ші Белл саны.
For n ≥ 1, the expected number of fixed points is 1 (a fact that follows from linearity of expectation). More generally, for i ≤ n, the ith moment of this probability distribution is the ith moment of the Poisson distribution with expected value 1. For i > n, the ith moment is smaller than that of that Poisson distribution. Specifically, for i ≤ n, the ith moment is the ith Bell number, i. e. the number of partitions of a set of size i.