ГЕНЕРАЛЬНАЯ СОВОКУПНОСТЬ С ПОВТОРЕНИЯМИ И ВЫБОРКИ С ПОВТОРЕНИЯМИ

 

Генеральная совокупность с повторениями — это набор эле­ментов п различных классов, когда элементы, принадлежащие одному классу, считаются одинаковыми:

а, а,..., а, b, b,..., b ,..., l, l,..., l.

1-й класс 2-й класс n-й класс

Наглядному представлению генеральной совокупности с пов­торениями может послужить набор квадратов п различных ок­расок.

Разумеется, число элементов в каждом из этих п классов неограниченное.

Выборкой с повторениями объема m будем называть произ­вольную группу m элементов генеральной совокупности с повто­рениями.

Наглядному представлению выборки с повторениями мо­жет послужить лента, построенная из m квадратов. На этот раз лента может быть не только пестрая. Независимо от m она может быть и одноцветной — любой из имеющихся п окрасок.

Каким минимальным признаком может отличаться одна такая выборка объема m от другой выборки такого же объема? Это равносильно вопросу: каким минимальным признаком мо­гут отличаться узоры лент, построенных из одинакового коли­чества квадратов?

Иной окраской по крайней мере одного квадрата

или

порядком расположения квадратов в линейном строю.

Таким образом, минимальным признаком отличия одной выборки от другой может быть:

их различие, по крайней мере, одним элементом (a)

или

их различие порядком расположения элементов. (б)

 

Как видно, эти признаки совпадают с признаками (а) и (б), о которых шла речь в параграфе 2, поэтому выборки, о ко­торых идет речь сейчас, следует называть размещениями с повторениями из элементов п классов по т.

Строим соответ­ствующую нашим рассуждениям схему:

 

когда одна от другой отличаются или признаком (а), или (б)

 

 

Определение:

Размещениями с повторениями из элементов п классов по m называются такие выборки, которые, имея по m элементов, вы­бранных из числа элементов данных п классов генеральной совокупности с повторениями, отличаются одна от другой либо составом элементов, либо порядком их расположения.

Число таких размещений обозначим символом А .

Характерный пример таких размещений — совокупность п - значных номеров автомашин.

Первый элемент какого-нибудь из упомянутых размещений мы можем выбрать п различными способами: некоторый эле­мент любого из п классов. Второй элемент тоже п различными способами: опять некоторый элемент любого из п классов. Тог­да в силу формулы (3.2) размещения объема 2 можно образо­вать п • п = п² различными способами. Третий элемент можем выбрать тоже п способами: опять некоторый элемент любого из п классов. Тогда в силу формулы (3.2) размещения объема 3 можно образовать п² • п = п³ различными способами. Читатель, вероятно, уже почувствовал аналогию: размещения объема m можно построить п'" различными способами, поэтому

А =п^т. (3.7)

Из совокупности размещений с повторениями можно выде­лить группу выборок с повторениями, которые одна от другой отличаются по крайней мере одним элементом. Порядок рас­положения элементов во внимание не принимается. Такие размещения по аналогии названию, принятому в параграфе 2, будем называть сочетаниями с повторениями. Пораз­мышляем по схеме:

 

 

 

когда одна от другой отличаются или (а), или (б) признаком

 

когда одно от другого отличаются (а) и только (а) признаком

 

 

Определение:

Сочетаниями с повторениями из элементов п классов по m называются такие размещения с повторениями из элементов п классов по т, которые одно от другого отличаются хотя бы одним элементом.

Число таких сочетаний обозначим С .

Характерный пример таких сочетаний — всевозможные раз­личные комплекты m предметов, составленные из предметов n различных видов.

Поскольку при построении сочетаний с повторениями поря­док расположения элементов не принимается во внимание, лю­бое сочетание объема m из элементов п классов мы можем представить так:

аа...а Х bb...b Х...Х l l... l, (3.8)

k₁ k₂ k₂

 

где k₁+k₂ + … +k _n = m.

 

Читатель, думаем, догадался, что X — это символ границы между двумя различными классами. Передвижения границ X означают факты замены элементов одних классов элементами других классов, т. е. факты образования новых сочетаний с повторениями.

В совокупности (3.8) мы имеем п — 1 символ Х и m симво­лов «не X», которые обозначим . Тогда наша совокупность будет выглядеть так:

... X ... X … X ... .

Теперь ясно, что С — это число перестановок с повторения­ми из п—1 элементов Х и m элементов а. Поэтому

 

Что собой представляют эти перестановки? Рассмотрим размещения с повторениями объема k, которые удовлетворяют такому условию: в каждой выборке должно быть k_i элементов (i= 1, 2, 3,..., п) 1-го класса, причем . Очевидно, что такие выборки одна от другой будут отличаться только порядком расположения элементов. Целесообразно их называть перестановками с повторениями. Опять поможем себе такой схемой:

 

 

 

когда они отличаются или (а), или (б) признаком

 

 

когда одно от другого отличаются признаком (б) и только (б)

 

 

Определение:

Перестановками с повторениями по k элементов из п раз­личных классов называются размещения с повторениями объ­ема k, которые одно от другого отличаются только порядком расположения элементов, когда от i-го класса в каждой выбор­ке участвует k, элементов.

Число таких перестановок обозначим

Если k₁ = k₂ =... = k_n = 1, то мы имели бы дело с переста­новками без повторений и по формуле (3.5) число таких перестановок было бы k!

 

При взаимной перестановке элементов одного класса новые перестановки не получаются, поэтому число различных пере­становок с повторениями, получаемых из перестановок (3.5), бу­дет в определенное число раз меньше k! Но во сколько раз?

Элементы а можно взаимно переставить местами k₁! раз.

Элементы Ь можно взаимно переставить местами k₂!раз.

…………………………………………………………………

Элементы I можно взаимно переставить местами k_n!раз.

Значит, число различных перестановок с повторениями меньше k! в k₁! k₂!… k_n!раз. Поэтому число перестановок с пов­торениями

 

(3.9)

 

где, как раньше отмечалось, k = k₁ + k₂ +...+ k_n.

Все нами рассмотренное в параграфе 3 можно привести к такой обобщающей схеме:

 

 

если одна от другой отличаются либо составом элементов, либо порядком их расположения

 

 

если одно от другого отличаются если одно от другого отлича­ются

только порядком расположения хотя бы одним элементом

элементов

 

 

Примеры

1. Мать купила 2 яблока, 3 груши и 4 апельсина. Девять дней подряд она каждый день предлагает сыну по одному фрукту. Сколькими способами она может выдать сыну фрукты?

Обозначим: яблоко — я, грушу — г, апельсин — а. Напи­шем одну из возможных выборок:

ггягааяаа

Все остальные выборки можно получить перестановкой ее элементов. Следовательно, приходится вычислять перестановки с повторениями. В нашей задаче k = 9, k₁ = 2, k₂ = 3, k₃ = 4. Поэтому число всевозможных способов раздачи фруктов

P_2,3,4= = 1260.

2. В продажу поступили открытки 10 разных видов. Сколь­кими способами можно образовать набор из 12 открыток? из 8 открыток?

В данном случае нам приходится считать сочетания с повто­рениями:

293 930,

24 310.

3. Сколько разных четырехзначных чисел можно составить из цифр 0, 1, 2, если та же самая цифра может повторяться несколько раз?

Из цифр 0, 1, 2 можно составить четырехзначных числа. Но числа, записанные четырьмя цифрами, первая из которых нуль, не являются четырехзначными. Значит, из числа размещений с повторениями надо вычесть число таких выбо­рок, которые начинаются нулем. Последних столько, сколько трехзначных чисел можно составить из цифр 0, 1, 2 при повто­рении цифр. Таких чисел будет

Поэтому ответ:

= 54.

 

Упражнения

43. Сколько разных слов можно образовать при перестанов­ке букв слова «математика»?

44. Сколько разных слов можно образовать при перестанов­ке букв слова «соединение»?

45. Для несения почетного караула из 10 человек могут быть приглашены офицеры пехотных войск, авиации, погранвойск, артиллерии, офицеры морского флота и ракетных войск. Сколькими способами можно избрать состав почетного ка­раула?

46. Докажите:

47. На школьный вечер танцев собрались ребята IX, X и XI классов. Вести хоровод приглашаются 10 школьников. Сколь­кими способами можно составить хоровод при условии участия в нем хотя бы одного одиннадцатиклассника?

48. На студенческий вечер собрались юноши и девуш­ки 8 факультетов университета (в том числе математи­ческого и филологического). Для исполнения народных танцев приглашаются 10 студентов. Сколькими способа­ми можно выбрать эту десятку при условии участия в ней хотя бы одного студента математического и хотя бы одного студента филологического факультета?

49. На Всемирный фестиваль молодежи прибыла молодежь пяти континентов мира. Возникла необходимость организо­вать делегацию из восьми представителей разных стран для оглашения клятвы борцов за мир. Сколькими способами мож­но было образовать делегацию при условии участия в ней пред­ставителей всех континентов?

50. В гастрономе имеются конфеты трех наименований. Кон­феты упакованы в коробки трех видов — для каждого на­именования своя коробка. Сколькими способами можно зака­пать набор из пяти коробок?

61. Сколько автомашин можно обеспечить 6-значными но­мерами?

52. Сколько 5-значных чисел можно образовать из цифр О и 1?

53. В одномгосударстве (сказочном) не найдется двух че­ловек, у которых оказался бы одинаковый состав зубов: либо у них разное число зубов, либо зубов нет в разных местах. Оцените наибольшую численность населения в этом государстве, если максимальное число зубов у одного чело­века 32.

54. Сколькими способами можно отослать 6 писем разным адресатам, если их будут разносить 3 курьера и заранее известно, какому курьеру какое достанется письмо?

55. Четыре студента сдают экзамен. Сколько может быть ва­риантов распределения оценок, если известно, что так или ина­че все они экзамены сдали?

56.Три парня и три девушки решили после окончания школы поступить на работу в своем родном городе. В городе имеются 3 завода, на которые берут только мужчин, 2 — где нужны женщины и 2 — которые принимают на работу и мужчин, и женщин. Сколькими способами пять выпускников могут распределиться по заводам города?

57. Выпускнику средней школы, поступающему в вуз, нуж­но сдать экзамены и набрать на них не менее 17 баллов (двой­ки при этом получать нельзя). Сколько существует разных на­боров экзаменационных оценок, дающих ему право поступ­ления?

58. Сколько разных по стоимости браслетов может составить ювелир из набора в 18 камней, если у него имеются 5 одина­ковых по стоимости рубинов, 6 одинаковых по стоимости алмазов и 7 одинаковых по стоимости кусков янтаря?

59. У мужа 12 сослуживцев: 5 женщин и 7 мужчин. У жены тоже 12: 7 женщин и 5 мужчин. За семейным столом поме­щаются 14 человек. Сколько разных компаний из 6 женщин и 6 мужчин могут они пригласить при условии участия 6 знако­мых мужа и 6 знакомых жены?

60. Все участники туристической поездки владеют по край­ней мере одним иностранным языком. 6 из них владеют английским языком, 6 — немецким, 7 — французским, 4 — английским и немецким, 3 — немецким и французским, 2 — французским и английским. Один турист владеет английским, французским и немецким языками. Других туристов в группе кет. Сколько туристов владеет только английским языком, только французским? Сколько туристов в группе?

61. Отряд из 92 школьников собрался в поход. Из них 47 приготовили бутерброды с колбасой, 38 — с сыром, 42 — с вет­чиной, 28 — с колбасой и сыром, 31 — с колбасой и ветчиной, 26 — с сыром и ветчиной. Взяли с собой бутерброды всех сортов 25 школьников, а некоторые взяли только по бутылке молока. Сколько было таких, которые взяли только молоко?

62. Найдите сумму всех четырехзначных чисел, которые по­лучаются при перестановке цифр 1, 2, 3, 4.

63. Сколько чисел, меньших миллиона, можно записать с по­мощью цифр 8 и 9?

64. Найдите сумму трехзначных чисел, которые можно за­писать с помощью цифр 1, 2, 3 и 4?

65. Города А и В соединяются двумя шоссейными дорогами, которые пересечены десятью проселочными. Сколькими разны­ми способами можно добраться от А до В, чтобы ни разу не пересекать пройденный путь?

66. Имеется неограниченное количество монет по 10, 15 и 20 к. Сколькими способами можно образовать набор из 20 мо­нет?

67. На заседании научного студенческого общества присут­ствовало 52 студента: по 13 студентов от 4 факультетов. Сколькими способами можно избрать правление общества в сос­таве 4 лиц так, чтобы в состав правления вошли представители 3 факультетов?

68- По линейке расположено п предметов. Сколькими спо­собами можно убрать 3 из них так, чтобы не были убраны рядом стоящие предметы?

69- 5 белых шариков, 5 черных и 5 красных надо разложить по 3 ящикам так, чтобы в каждом ящике оказалось по 5 шари­ков. Сколькими способами это можно осуществить?

70- При закрытии пионерского фестиваля Прибалтийских республик в первый ряд президиума (из 9 мест) были пригла­шены 3 литовских, 3 латышских и 3 эстонских пионера. Сколькими способами их можно рассадить так, чтобы ни одна тройка представителей из одной республики не занимала трех соседних мест?

71. Сколько цифр понадобится для записи всех чисел от 1 до 999 999 включительно?

 

 

IV. ВЕРОЯТНОСТЬ СОБЫТИЯ