ТЕОРИЯ ВЕРОЯТНОСТЕЙ, МАТЕМАТИЧЕСКАЯ СТАТИСТИКА, (1269688), страница 2
Текст из файла (страница 2)
Названиесвязано с формулой бинома Ньютонаn(a + b) = å Cnk a k b n -k .n(1.3)k =0Из формулы (1.3) следует, что(1 + 1)nnnå= C 1 1 = å C=k =0k k n -knk =0kn2 n.Биномиальныекоэффициентыобразуюттреугольник Паскаля, который имеет вид:такназываемыйr=0r=1r=2n=01r=3n=111r=4n=2121r=5n =31331r=6n=414641r=7n=5151010 51r=8n=616152015 61r=9n=71721 353521 71n=81828567056 2881n=9193685 126 126 85 36 91. . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .В n-й строке треугольника Паскаля располагаются коэффициенты,соответствующие представлению (a + b)n по формуле (1.3). Треугольником8удобно пользоваться для нахождения значений Cnr . Это значениенаходится на пересечении n-й строки и r-го наклонного ряда. Например,С83 = 56 .Биномиальные коэффициенты обладают свойством симметрии:Cnr = Cnn-r .(1.4)Это наглядно демонстрирует треугольник Паскаля.
Равенство (1.4)подтверждает тот очевидный факт, что выбор r элементов из n равносиленвыбору тех n – r элементов из n, которые следует удалить, чтобы осталисьr элементов.При повторном выборе из n элементов число выборок объема r,которые отличаются только составом равно Cnr+ r -1 . Еще раз подчеркнем,что речь идет о выборках, которые отличаются хотя бы одним элементом, апорядок выбора этих элементов во внимание не принимается. Число такихвыборок можно подсчитать следующим образом.
Между элементамиа1 , а2 ,K , аn поставим разграничительные знаки, например, нули:а1 0а2 0K 0аn . Таких знаков (нулей) понадобится n – 1. На месте каждогоэлемента поставим столько единиц, сколько раз предполагается выбратьэтот элемент. Например, комбинация 111101 0 0111 0 K 011 означает, чтоэлемент а1 выбран четыре раза, элемент а2 выбран один раз, элемент а3 невыбран, ..., элемент аn выбран два раза. Заметим, что в такой записи числоединиц равно объему выборки r. Для перебора всех возможныхкомбинаций нужно из r + n – 1 мест выбрать n – 1 место и поставить на нихнули, а на остальных местах разместить единицы.
Это можно сделать(n + r - 1)!Сnn+-r1-1 == Cnr+ r -1.(1.5)(n - 1)! r !способами.Совокупность из n элементов разделить на m групп по k1 , k2 ,K , kmn!элементов соответственно (k1 + k2 + K + km = n) можноспособами.k1 !k2 !×¼× km !Порядок элементов внутри каждой из этих m групп не имеет значения.Пусть А1 , А2 ,¼, Аk – множества, число элементов в каждом изкоторых равно соответственно n1 , n2 , n3 ,K, nk .
Составить множество B из m1элементов множества А1, m2 элементов множества А2, …, mk элементовмножества Аk, можно, согласно основному комбинаторному принципу,Cnm11 Cnm22 × ... × Cnmk k(1.6)способами.Для безошибочного выбора комбинаторной формулы достаточнопоследовательно ответить на вопросы в следующей схеме:9Что нас интересуетпри выборе?Какой выбор?БесповторныйОткуда выбор?(n - ?)Скольковыбираем?(r - ?)CnrСоставПовторныйCnr+ r -1БесповторныйCnrПовторныйnrБесповторныйn!Состав и порядокПорядокПовторныйn!k1 !k2 !×¼× km !Например, число словарей, необходимых для непосредственногоперевода с одного на другой, для пяти языков определяется из следующихрассуждений.
Для составления словаря выбираем из пяти языков ( n = 5 )любые два ( r = 2 ). Выбор бесповторный, причем при выборе важен исостав выбора и порядок выбора. Поэтому искомое число словарей равноА52 = 5 × 4 = 20.Пример 1.1. Сколькими способами можно выбрать путь из началакоординат О(0,0) в точку В (6,4) , если каждый шаг равен единице, но егоможно совершать только вправо или вверх? Сколько таких путей проходитчерез точку А(2,3) ?Решение. Весь путь занимает 10 шагов (четыре вверх и шестьвправо). Для планирования пути следует решить, какие именно по счетучетыре шага следует сделать вверх, а остальные шесть –– вправо.
Выборбесповторный и нас интересует только состав выбора. Поэтому вописанных условиях всего путей из точки О в точку В будет10!С104 == 210.4!6!Рассуждая подобным образом легко видеть, что путей из точки О в5!точку А существует С53 == 10 , а путь из точки А в точку В можно3!2!выбрать С51 = 5 способами. По комбинаторному принципу всего путейчерез точку А существует 10 × 5 = 50.Ответ. 210; 50.10Задача 1.1. Сколькими способами можно выбрать путь из началакоординат О(0,0) в точку В (n1 , n2 ), если каждый шаг равен 1, но егоможно совершать только вправо или вверх? Сколько таких путей проходитчерез точку А(k1 , k2 ) ? (См. пример 1.1 и исходные данные.)Исходные данные к задаче 1.1.№ n1 n2 k1 k2 № n1 n2 k1 k2 № n1 n2 k1 k24832 116922 21 684518432 129642 22 865224824 139543 23 582335832 149634 24 583248323 156 10 24 25 865358634 166932 26 862468543 17 10 642 27 672374823 18 10 443 28 762386823 195623 29 873496732 206532 30 873510Пример 1.2.
В городе с идеальной прямоугольной планировкой (сетьулиц в этом городе изображена на рис. 1.1) из пункта A выходят 2Nчеловек. Половина из них идет по направлению a, половина –– понаправлению b. Дойдя до первого перекрестка, каждая группа разделяетсятак, что половина ее идет по направлению a, половина –– по направлениюb. Такое же разделение происходит на каждом перекрестке. Требуетсяперечислить перекрестки, на которых окажутся люди после прохождения Nулиц (отрезков на рис. 1.1), и сколько людей окажется на каждом из этихперекрестков.Рис.
1.1Решение. Каждый человек пройдет N улиц и окажется на одном изперекрестков M (0, N ), M (1, N - 1), M (2, N – 2), K , M ( N ,0). Координатыперекрестков указаны в предположении, что точка A служит началомкоординат.11На каждом перекрестке для каждого человека производится выбор издвух возможностей: идти в направлении a или в направлении b. Поэтомувсего возможных путей будет 2N . Из этого следует, что каждый путьпройдет только один человек.В пункте M (k , N – k ), окажется столько человек, сколько различныхпутей ведет в этот пункт из точки A . Чтобы попасть в пункт M (k , N – k ),необходимо из N улиц выбрать бесповторным способом k улиц вN!направлении a.
Это можно сделать СNk =способами.k !( N - k )!Ответ. M (0, N ), M (1, N - 1), M (2, N - 2), K , M ( N ,0); С Nk .Задача 1.2. В начале координат на прямой находится 2N частиц.Половина этих частиц сдвигается на единицу вправо, другая половина –– наединицу влево. Через единицу времени каждая группа делится пополам, иполовина сдвигается не единицу вправо, а другая половина –– влево. Такоеразделение происходит каждую единицу времени. Перечислите точки на оси,в которых будет хотя бы одна частица через N единиц времени. Найдитечисло частиц в точке с координатой N - 2 в вариантах с первого по десятый,в точке с координатой N – 4 в вариантах с одиннадцатого по двадцатый, вточке с координатой N – 6 в вариантах с двадцать первого по тридцатый.(См.
пример 1.2, число N равно последней цифре варианта плюс 5.)Пример 1.3. Сколькими способами можно n одинаковых предметовраспределить между k лицами так, чтобы каждый получил не менее одногопредмета?Решение. Поставим эти предметы в ряд. Между ними будет n – 1промежуток. В любые k – 1 из этих промежутков поставим разделяющиеперегородки. Тогда все предметы разделятся на k непустых частей. Первуючасть передадим первому лицу, вторую –– второму и т.д.
Выбрать же k – 1промежуток из n – 1 промежутка можно Сnk--11 способами. Заметим, чтовообще n предметов распределить между k лицами можно k n способами.Ответ. Сnk--11.Задача 1.3. Сколькими способами можно поставить n книг на kполок (на каждую полку могут поместиться все n книг и n > k )? Сколькимиспособами можно поставить книги так, чтобы ни одна полка не осталасьпустой? (См.
пример 1.3 и исходные данные.)Исходные данные к задаче 1.3.kkkkk№ n№ n№ n№ n№ n438351713 719 11 425 14 353842814 10 320 11 526 14 41234566767334491011128999534515 1016 1017 818 1145632122232412121313343427282930151516163434Пример 1.4. Сколькими способами можно распределить 6 яблок, 8груш и 10 слив между тремя детьми? Сколькими способами это можносделать так, чтобы каждый ребенок получил по меньшей мере одно яблоко,одну сливу и одну грушу?Решение. Яблоки в соответствии с формулой (1.5) можно распределить3-1С6+3-1 = С82 = 28 способами, груши –– С102 = 45 , а сливы С122 = 66 способами.По комбинаторному принципу всего способов 28 × 45 × 66 = 83160.
Еслинеобходимо, чтобы каждый ребенок получил по меньшей мере одно яблоко,одну грушу и одну сливу, то в соответствии с формулой предыдущегопримера имеем С52С72С92 = 10 × 21 × 36 = 7560 способов.Ответ. 83160; 7560.Задача 1.4. Имеется n1 красных, n2 синих, n3 белых и n4 черныхшаров.а) Сколькими способами эти шары можно разложить в k ящиков?Сколькими способами это можно сделать, если в каждом ящике должныприсутствовать шары всех цветов?б) Сколькими способами можно выбрать по одному шару каждого цвета?в) Сколькими способами можно выбрать по k шаров каждого цвета?(См. пример 1.4 и исходные данные.)Исходные данные к задаче 1.4.№ n1 n2 n3 n4 k № n1 n2 n3 n4 k № n1 n2 n3 n4 k1 4 5 4 6 4 11 4 5 4 5 4 21 3 6 5 5 32 4 4 5 3 3 12 4 3 4 3 3 22 6 5 6 4 43 3 4 4 5 3 13 6 5 4 5 4 23 6 3 4 3 34 4 5 4 6 4 14 5 6 5 4 3 24 7 5 4 4 45 5 3 4 3 3 15 5 4 4 3 3 25 5 6 3 4 36 5 4 4 6 4 16 6 4 6 5 4 26 7 6 4 5 47 4 5 3 4 3 17 6 5 4 5 4 27 6 7 3 4 38 6 3 4 3 3 18 6 3 4 4 3 28 7 6 6 4 49 6 4 4 3 3 19 6 4 6 4 4 29 3 6 7 5 310 6 3 4 4 3 20 4 6 5 3 3 30 3 7 6 4 3Пример 1.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
