Методические указания Ульяновск 2005

Loading...


Pdf көрінісі
бет1/5
Дата28.06.2020
өлшемі465.26 Kb.
түріМетодические указания
  1   2   3   4   5

 

3

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО  ОБРАЗОВАНИЮ  



ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ 

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ  

УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИСТЕТ 

 

 



 

 

 



 

 

 



 

 

 



А. С. СЕМЕНОВ 

 

 

ЧЕТЫРЕ ЛЕКЦИИ 

ПО КОМБИНАТОРИКЕ

 

 

Методические указания 



 

 

 

 

 

 

 



 

 

Ульяновск 2005 



 

 

 



 

 

4

УДК 519.1 (076) 



ББК 22.141 я 7 

         С30 

 

 

 



Рецензент д-р техн. наук, профессор Семушин И. В. 

 

 



 

 

Одобрено  секцией  методических  пособий  научно-методического  совета 



УлГТУ 

 

 



 

 

Семенов А.С. 

С30   Четыре лекции по комбинаторике: методические указания. – Ульяновск:  

          УлГТУ, 2005. - 20 с. 

 

Методические  указания  написаны  в  соответствии  с  программами  курса  



высшей математики для высших учебных заведений и предназначены для 

самостоятельной  работы  студентов  всех    форм  обучения  Ульяновского 

государственного  технического  университета,  изучающих  теорию  веро-

ятностей и математическую статистику. Цель пособия – познакомить чи-

тателей  с  основными  понятиями  комбинаторики  и  методами  решения 

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

щимся  математической  логикой,  вычислительной  техникой,  кибернети-

кой, целочисленным программированием и т. п. 

Работа подготовлена на кафедре «Высшая математика». 

 

                                                                                                 УДК 519.1 (076) 



                                                                                                            ББК 22.141.я 7 

 

 



 

 

 



 

 

 



 

                                                                                      © А. С. Семенов, 2005 

                                                                                      © Оформление, УлГТУ, 2005 

 

 



 

5

ЛЕКЦИЯ 1 



Введение 

 

Комбинаторика  или  теория  конечных  множеств  является  одним  из  разделов 



математики, имеющим большое значение в связи с применением его в теории веро-

ятностей,  математической  логике,  вычислительной  технике,  кибернетике,  целочис-

ленном программировании и т.п. 

 

Цель лекций познакомить читателей с основными понятиями комбинаторики и 



методами решения комбинаторных задач. 

 

При составлении лекций использовалась следующая литература 



1.  Виленкин Н.Я. Комбинаторика - М.: Наука, 1979. 

2.  Ежов  И.И.,  Скороход  А.В.,  Ядренко  М.М.  Элементы  комбинаторики - М.:  Наука, 

1977. 

Лекции  предназначены,  прежде  всего,  для  студентов,  изучающих  теорию  ве-



роятностей. Они могут оказаться полезными и лицам, которые знакомы с определе-

ниями  и  свойствами  основных  операций  над    множествами и  занимаются  комбина-

торными расчетами.  

 

§ 1. Принцип математической индукции 



 

 

Широко  распространенный  метод  доказательства  утверждений - это  метод 



математической  индукции,  основанный  на  принципе  математической  индукции.  До-

кажем его. 



Теорема 1  (принцип математической индукции) 

 

Пусть имеется некоторое утверждение  



),

(n



P

 которое формулируется для ка-

ждого натурального числа  

,

n

 и пусть известно, что: 

1)  утверждение  

)

1

(



P

 верно; 


2)  из того, что  

)

(n



P

 верно при  

,

k

n

=

 следует, что 



)

1

(



+

k

P

 верно. 


Тогда утверждение  

)

(n



P

 верно для любого значения  



n

 (

.



N

n



). 

Доказательство.  Применим метод доказательства "от противного".  Предположим, 

что, несмотря на истинность условий 1 и 2 теоремы, утверждение 

)

(n



P

 верно не для 

всех натуральных 

.

n

 Тогда среди тех 

,

n

 для которых  

)

(n



P

 неверно, найдется наи-

меньшее число  

m

. Ясно, что 

,

1

>



m

 так как в противном случае получаем противо-

речие  с  условием 1 теоремы,  то  есть 

1



m

  тоже  натуральное  число,  для  которого 

)

1

(





m

P

 верно. Но тогда 

)

(

)



1

1

(



m

P

m

P

=

+



 должно быть верным в силу второго 

условия теоремы. Мы пришли к противоречию. Теорема 1 доказана. 

Пример 1.   Используя  метод  математической  индукции,  доказать  формулу    для 

суммы кубов последовательных натуральных чисел 

                                   

=



+

=

=



+

+

+



n

m

n

n

m

n

1

2



2

3

3



3

3

.



4

)

1



(

...


2

1

                                     (1) 



 

Решение. Проверяем выполнение условий теоремы 1. 1)  При 

1

=



n

 левая часть в (1) 

дает 

1

1



3

=

, правая -- 



1

4

2



1

2

=



,т.е. формула (1) верна при 

1

=

n



. 2) Пусть формула 

(1) верна для всех  

,

k

n

 тогда  



=

+

+



+

=

+



+

=



=

+



=

3

2



2

3

1



3

1

1



3

)

1



(

4

)



1

(

)



1

(

k



k

k

k

m

m

k

m

k

m

 

 



 

6

 =



4

)

2



(

)

1



(

)

4



4

(

)



1

(

4



1

2

2



2

2

+



+

=

+



+

+

k



k

k

k

k

, т.е. формула (1) верна и при значении 

1

+

k



n

.  Следовательно,  согласно  принципу  математической  индукции,  формула 

(1) верна для любого натурального 

n



Пример 2.  Доказать, что для всякого натурального числа, не меньшего десяти, т.е. 

)

10

:



(





m

N

m

, имеет место неравенство  

3

2

m



m

>



Решение. Пусть 



n

любое натуральное число. Тогда доказательство данного нера-

венства сводится к доказательству неравенства  

                                                   

3

9



)

9

(



2

n

n

+

>



+

.                                                             (2) 

Докажем его методом математической индукции.  

1)  При 


1

=

n

 имеем 

1000


10

1024


2

3

10



=

>

=



, т.е. неравенство (2) верно. 

2)  Предположим, что неравенство (2) верно для всех 



k

n

. Тогда последовательно 



получаем                 

3

9



)

9

(



2

k

k

+

>



+

,  


3

9

)



9

(

2



2

2

k



k

+



>

+



,   

>

+



+

+

>



+

1458


486

54

2



2

2

3



10

k

k

k

k

3

2



3

)

10



(

1000


300

30

+



=

+

+



k

k

k

k

, т.е. нера-

венство (2) верно и при 

1

+



k

n

. Следовательно, на основании принципа матема-

тической индукции, неравенство (2) верно для любого натурального  

n

  



§ 2. Основные принципы комбинаторики 

 

Теорема 2  (принцип умножения) 

 

Если некоторое действие может быть выполнено за  



k

 этапов, причем число 

возможных  способов  осуществления   



i

го  этапа  равно 

),

,...,



2

,

1



(

k

i

n

i

=

  то  общее 



число  

k

N

 способов осуществления указанного действия вычисляется по формуле    

                                         

=



=



=

k



i

i

k

k

n

n

n

n

N

1

2



1

.

...



                                                  (3) 

Доказательство. Используем индукцию по числу этапов. Если  

,

1



=

k

 то, очевидно, 

что 

1

1



n

N

=

 и, следовательно, формула (3) верна для 



.

1

=



k

 Пусть далее  

.

2

=



k

 То-


гда, так как каждый из 

1

n

 способов осуществления первого этапа может иметь место 

с  каждым  из 

2

n

  способов  осуществления  второго  этапа,  то 

,

2

1



2

n

n

N

=



  т.е.  фор-

мула (3) верна и для  

.

2

=



k

 

 



Предположим теперь, что формула (3) верна  при  

,

1



m



k

 т.е. имеет место 

формула 

                                                      



=



=

1



1

1

.



m

i

i

m

n

N

                                                             (4) 

Тогда, если 

,

m



k

=

 то, рассматривая первые  



1



m

 этапов в качестве первого этапа 

с общим числом способов осуществления, определяемым формулой (4), и применяя 

результат, доказанный вторым шагом индукции, получаем  

                                                

,

1

1



=



=

=



m

i

i

m

m

m

n

n

N

N

   


т.е.  формула (3) верна  и  для 

.

m



k

=

  Следовательно,  согласно  принципу  математи-



ческой индукции, теорема 2 доказана. 

            Рассмотрим некоторые примеры применения принципа умножения. 



 

7

Пример 3.  Даны два конечных множества  

1

A

 и  

2

A

 с числом элементов  

n

A

N

=

)



(

1

 

и 

m

A

N

=

)



(

2

 соответственно. Требуется определить число элементов прямого про-



изведения этих множеств, т.е.  

).

(



2

1

A



A

N

×

                                                            



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

следует, что любой элемент множества 

2

1

A



A

×

 может быть получен  в результате 



выполнения действия из двух этапов. Первый этап - выбрать произвольный элемент 

множества   

1

A

  и  поместить  его  на  первое  место  в  упорядоченной  паре,  ясно,  что 

;

1

n



n

=

 второй этап - выбрать произвольный элемент множества 



2

A

 и поместить его 

на второе место в паре, 

.

2



m

n

=

 Теперь, согласно принципу умножения, получаем 



                                                  

.

)



(

2

1



2

1

m



n

n

n

A

A

N

=



=

×



                                          (5) 

Следствие - обобщение.  Аналогично,  или  используя  метод  математической  индук-

ции,  можно  доказать,  что  если  даны  конечные  множества   

)

,...,


2

,

1



(

k

i

A

i

=

  с 



,

)

(



i

i

n

A

N

=

 то 



                                              

.

...



)

...


(

2

1



2

1

k



k

n

n

n

A

A

A

N



=

×



×

×

                               (6)                   



В частности, если 



A

конечное множество с 

,

)



(

n

A

N

=

 то 



                                                       

.

)



(

k

k

n

A

N

=

                                                              (7) 



Замечание.    По  определению  прямого  произведения  множеств  элементами  множе-

ства  


A

A

A

A

k

×

×



×

=

...



 (справа 

k

 символов 



A

 разделены 

1



k



  знаками прямо-

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

длины 

,

k



  составленные  из  возможно  повторяющихся  элементов  множества 

A

.  В 


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

A

 называ-


ют размещениями из  

n

 элементов  по  



k

 элементов с повторениями. Они отлича-

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

).

,



k

n

A

 Значит из формулы (7) следует, что 

.

)

(



)

,

(



k

k

n

A

N

k

n

A

=

=



                           

Пример 4.  Пусть даны множество  

{

}



k

X

N

x

x

x

X

k

=

=



)

(

,



,...,

,

2



1

 и множество  

{

}

;



)

(

,



,...,

,

2



1

l

Y

N

y

y

y

Y

l

=

=



  и пусть на множестве  

X

 с областью значений  



Y

 за-


дана  функция   

.

:



Y

X

f

  Спрашивается:  сколько  всего  имеется  различных  функ-



ций указанного вида ? 

Решение.  Каждую функцию 

Y

X

f

:



 можно задать таблицей 1 

      Таблица 1.          

    

1

x



 

     


2

x

 

  .  .  .  .  .  .  .  . 



     

s

x

 

  .  .  .  .  .  .  .  



       

k

x

 

    



1

i

y

 

     



2

i

y

 

  .  .  .  .  .  .  .  . 



      

s

i

y

 

  .  .  .  .  .  .  . 



        

k

i

y

 

Где   





s

i

y

  это  тот  элемент  множества   

,

Y

    который  поставлен  в  соответствие 

.

X

x

s

 Нижняя строка таблицы 1 



)

,...,


(

1

k



i

i

y

y

 есть кортеж длины 



k

, составленный 

из элементов множества 

,

Y

 т.е. элемент множества  

.

k



Y

 Так как число различных 

элементов  множества   

,

k



Y

  согласно  формуле (7), равно   

,

k

l

  то  имеется  ровно 



k

l

 

различных функций с областью определения  



X

 и областью значений  

.

Y

 

Следствие.  Пусть   

{ }

{ }


,

1

;



0

,

1



;

0

=



=

Y

X

m

  тогда  число  различных  функций  вида   



Y

X

f

:



  равно  

,

2



2

m

 ибо  


.

2

)



(

,

2



)

(

=



=

Y

N

X

N

m

   Другими словами: число  



 

8

булевых или двоичных функций от  



m

 двоичных аргументов равно  

.

2

2



m

 

Теорема 3  (принцип сложения) 

  

Если некоторое действие №1 можно осуществить  



1

m

 способами, а действие 

№2 -- 

2

m



способами, то осуществить "либо действие №1, либо действие №2" можно 

2

1



m

m

+

 способами. 



 

Справедливость теоремы очевидна. Например, если студенту необходимо по-

пасть в лекционный корпус, к которому можно подъехать либо на одном из трех ав-

тобусных маршрутов, либо на одном из четырех трамвайных, то студент обязатель-

но окажется около корпуса, воспользовавшись одним из семи маршрутов городского 

транспорта. 



Пример 5.  Сколькими способами из 28 костей домино можно выбрать две кости од-

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

 

 

Решение.  Если первой костью является дубль 



)

7

(



1

=

n

, то вторую можно приложить 

к первой 

6

2

=



n

 способами. Если первая кость не дубль 

)

21

(



'

1

=



n

, то вторую можно 

приложить к первой  

12

'



2

=

n

  способами. Теперь, последовательно применяя прин-

цип  умножения  и  принцип  сложения,  для  искомого  числа  получаем  

.

294


12

21

6



7

'

2



'

1

2



1

2

1



=

+



=



+

=



+

=

n



n

n

n

m

m

m

 

 





Достарыңызбен бөлісу:
  1   2   3   4   5
Loading...


©melimde.com 2020
әкімшілігінің қараңыз

    Басты бет
рсетілетін ызмет
Жалпы ережелер
ызмет стандарты
дістемелік кешені
бекіту туралы
туралы хабарландыру
біліктілік талаптары
кіміні аппараты
жалпы біліктілік
Конкурс туралы
ойылатын жалпы
мемлекеттік кімшілік
жалпы конкурс
Барлы конкурс
білім беретін
ызмет регламенті
республикасы білім
ткізу туралы
конкурс атысушыларына
біліктілік талаптар
атысушыларына арнал
бойынша жиынты
Республикасы кіметіні
идаларын бекіту
облысы кімдігіні
рсетілетін ызметтер
мемлекеттік ызмет
стандарттарын бекіту
Конкурс ткізу
дебиеті маманды
мемлекеттік мекемесі
дістемелік сыныстар
дістемелік материалдар
Мектепке дейінгі
ауданы кіміні
конкурс туралы
рметті студент
облысы бойынша
жалпы білім
мыссыз азаматтар
Мемлекеттік кірістер
мектепке дейінгі
Конкурс жариялайды
білім беруді
дарламасыны титулды
разрядты спортшы
мелетке толма
дістемелік кешен
ызметтер стандарттарын
директоры бдиев
аласы кіміні

Loading...