Лекция : Элементы комбинаторики

Тема 1: Комбинаторика.

1. Основные элементы комбинаторики.

Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиально-возможное количество различных вариантов развития событий.

2. Формы представления статистических данных.

Статистические данные должны быть представлены так, чтобы ими можно было пользоваться. Существует 3 основных формы представления статистических данных:

1. Текстовая - включение данных в текст;

2. Табличная - представление данных в таблицах;

3. Графическая - выражение данных в виде графиков.

Текстовая форма применяется при малом количестве цифровых данных.

Табличная форма применяется чаще всего, так как является более эффективной формой представления статистических данных. В отличие от математических таблиц, которые по начальным условиям позволяют получить тот или иной результат, статистические таблицы рассказывают языком цифр об изучаемых объектах.

Статистическая таблица - это система строк и столбцов, в которых в определенной последовательности и связи излагается статистическая информация о социально-экономических явлениях.

Например, в следующей таблице представлена информация о внешней торговле России, выражать которую в текстовой форме было бы неэффективным.

Различают подлежащее и сказуемое статистической таблицы. В подлежащем указывается характеризуемый объект - либо единицы совокупности, либо группы единиц, либо совокупность в целом. В сказуемом дается характеристика подлежащего, обычно в числовой форме. Обязателен заголовок таблицы, в котором указывается к какой категории и к какому времени относятся данные таблицы.

По характеру подлежащего статистические таблицы подразделяются на простые, групповые и комбинационные. В подлежащем простой таблицы объект изучения не подразделяется на группы, а дается либо перечень всех единиц совокупности, либо указывается совокупность в целом. В подлежащем групповой таблицы объект изучения подразделяется на группы по одному признаку, а в сказуемом указываются число единиц в группах (абсолютное или в процентах) и сводные показатели по группам. В подлежащем комбинационной таблицы совокупность подразделяется на группы не по одному, а по нескольким признакам.

При построении таблиц необходимо руководствоваться следующими общими правилами.

1. Подлежащее таблицы располагается в левой (реже - верхней) части, а сказуемое - в правой (реже - нижней).

2. Заголовки столбцов содержат названия показателей и их единицы измерения.

3. Итоговая строка завершает таблицу и располагается в ее конце, но иногда бывает первой: в этом случае во второй строке делается запись «в том числе», и последующие строки содержат составляющие итоговой строки.

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

5. В таблице не должно быть пустых клеток: если данные равны нулю, то ставится знак «-» (прочерк); если данные не известны, то делается запись «сведений нет» или ставится знак «…» (троеточие). Если значение показателя не равно нулю, но первая значащая цифра появляется после принятой степени точности, то делается запись 0,0 (если, скажем, была принята степень точности 0,1).

Иногда статистические таблицы дополняются графиками, когда ставится цель подчеркнуть какую-то особенность данных, провести их сравнение. Графическая форма является самой эффективной формой представления данных с точки зрения их восприятия. С помощью графиков достигается наглядность характеристики структуры, динамики, взаимосвязи явлений, их сравнения.

Статистические графики - это условные изображения числовых величин и их соотношений посредством линий, геометрических фигур, рисунков или географических карт-схем. Графическая форма облегчает рассмотрение статистических данных, делает их наглядными, выразительными, обозримыми. Однако графики имеют определенные ограничения: прежде всего, график не может включить столько данных, сколько может войти в таблицу; кроме того, на графике показываются всегда округленные данные - не точные, а приблизительные. Таким образом, график используется только для изображения общей ситуации, а не деталей. Последний недостаток - трудоемкость построения графиков. Он может быть преодолен использованием персонального компьютера (например, «Мастером диаграмм» из пакета Microsoft Office Excel).

3. Табличное и графическое представление данных.

Когда сведений очень много, их нужно упорядочивать. Таблица - самый простой способ упорядочить данные. С некоторыми таблицами вы уже имели дело. Это таблицы сложения и умножения чисел, таблицы спряжения глаголов. Таблицами являются: расписание уроков, страницы школьного дневника, оглавление учебника. Таблицы облегчают поиск необходимых сведений, не заставляя изучать всю имеющуюся информацию. Однако таблицы не дают наглядного представления о соотношении величин. Для этого служат различные диаграммы: столбиковые, круговые, рассеивания и др. Пословица гласит: «Лучше один раз увидеть». Диаграммы используются для наглядного, запоминающегося изображения и сопоставления данных.Таблицы и диаграммы удобно применять для сравнения шансов случайных событий, используя статистические данные (числовые данные, полученные в результате различных наблюдений, опросов, экспериментов.)На основе собранных статистических данных вычисляют частоту случайного события и выясняют, как она связана с вероятностью. Чтобы выяснить, насколько вероятно то или иное случайное событие, связанное со случайным экспериментом (эксперимент, условиями которого являются непредсказуемость и возможность многократного повторения), нужно подсчитать, как часто оно происходит. Для этого используют две важные величины - абсолютную и относительную частоту. Абсолютная частота показывает, сколько раз в серии экспериментов наблюдалось данное событие. Это всегда целое число. Относительная частота (частота n / N ) показывает, какая доля экспериментов завершилась наступлением данного события. Она равна отношению n - числа опытов, в которых интересующее нас событие произошло, к N - общему числу проведенных опытов. Это дробное число, меняющееся от 0 до 1.Опытным путем установлено, что проводя эксперименты огромное количество раз (больше 1000), например, такие эксперименты, как бросание игральной кости, бросание монеты, раздача игральных карт, розыгрыш лотереи и др., частоты становятся устойчивыми. Например, изобразим график зависимости частоты от числа опытов при бросании игральной кости, показывающий как часто выпадала

«единица»:

Другой пример. Событие А - «на кубике выпало четное число очков», событие В - «на кубике выпало нечетное число очков».

Устойчивость частот является скорее математическим, а не экспериментальным фактом. На нем основывается частотное, или статистическое определение вероятности: за вероятность случайного события можно приближенно принять его относительную частоту. В теории вероятностей величина, значение которой зависит от исхода эксперимента, называется случайной величиной. Мы будем рассматривать ряд числовых значений такой величины, полученных в какой-либо серии экспериментов. Такой числовой ряд называется случайной выборкой. Представим себе, что из всех школьников вашего региона случайным образом выбирается 1000 человек и фиксируется их оценка по математике в последней четверти. В статистике множество всех школьников региона будет называться генеральной совокупностью, а случайно выбранная 1000 школьников - случайной выборкой. Однако математики предпочитают иметь дело не со школьниками, а с числами, поэтому мы с вами будем называть случайной выборкой только числовой ряд - т. е. в нашем случае не самих выбранных школьников, а их оценки. Займемся числовыми рядами, полученными в результате описанной процедуры.

Пример 1. Среди школьников седьмых классов был проведен выборочный опрос: из скольких человек состоят их семьи?

В результате такого опроса была получена следующая выборка:223333423323232324322324523324323432353Здесь каждое число означает количество человек в семье соответствующего ученика. Числа выписаны в том порядке, в котором ученики сдавали свои ответы. А что если упорядочить эти числа по возрастанию? 22222222222222 3333333333333333333 44444 55Не правда ли, этот ряд (он называется ранжированным) воспринимается уже лучше: теперь мы ясно видим, что минимальное значение в нем равно 2, а максимальное - 5. Видно, как часто повторяется каждое из значений. А вот как выглядит представление выборки в виде частотной таблицы:

Первый столбец частотной таблицы содержит различные значения наблюдаемой величины (по возрастанию), второй - сколько раз это значение повторилось в выборке, т. е. его абсолютную частоту, третий - какую долю эти значения составляют от всей выборки, т. е. его относительную частоту. Разумеется, сумма абсолютных частот будет равна объему выборки (т. е. количеству опрошенных учеников - 40), а сумма относительных - 1.Еще более наглядной формой представления результатов выборки является их графическое изображение. Для этого используется так называемый полигон частот - линейная диаграмма, на которой по горизонтальной оси откладываются различные значения, полученные в выборке, а по вертикальной - их относительная частота. После этого полученные точки соединяются ломаной линией (отсюда и название - полигон в переводе с греческого

означает многоугольник).

4. Основные правила комбинаторики

Все разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств - правило суммы и правило произведения.

Правило суммы: пусть имеется n попарно непересекающихся множеств A₁, A₂, …, A_n , содержащих m₁, m₂, …, m_n элементов соответственно. Число способов, которыми можно выбрать один элемент из всех этих множеств, равно m₁ + m₂ + … + m_n.

Пример1. Если на первой полке стоит X книг, а на второй Y, то выбрать книгу с первой или второй полки, можно X+Y способами.

Кортеж - конечная последовательность (допускающая повторения) элементов какого-нибудь множества.

Правило произведения: пусть имеется n множеств A₁, A₂, …, A_n содержащих m₁, m₂, …, m_n элементов соответственно. Число способов, которыми можно выбрать по одному элементу из каждого множества, т. е. построить кортеж (а₁, а₂, ..., а_n), где а_i Î А _i1 (i = 1, 2, …, n), равно m₁ · m₂ · … · m_n.

Пример2. Если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.

</ Выборки. Если из множества предметов выбирается некоторое подмножество, то его называют выборкой. Выборки бывают упорядоченные и неупорядоченные.

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

Пример3. Из цифр 1, 2, 3, 4, 5 можно составить следующие трехзначные числа 123, 431, 524, ...и т.д. Это упорядоченные трехэлементные выборки, так как 123 и 132 - разные числа.

5