Функции намножественатуральныхчиселв комбинаторике

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

Основойдлявсехтакихфункций можносчитатьфакториал:

n!=1´2´3´...´n.

1. Попробуемрешитьтакуюзадачу:сколькимиспособамиможнорассадитьнаnпронумерованныхстульяхnгостей?Напервыйстулможнопосадитьлюбогоизnгостей.Выбраводногоизних,навторойстулможноусадитьужеодногоизоставшихся(n–1)претендентов.Выбравиэтого,натретийстулвыбираемодногоиз(n–2)гостей….Напоследнийстулпретендентбудеттолькоодин.Такимобразом,если двигатьсяот конца

процесса,мыполучим1´2´3´...´n= n!вариантов.

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

называетсяперестановкойэтихэлементовиобозначается

Pn.Перестановки

неменяютэлементовмножестваилиихколичества,онименяютпорядокэлементов.Такимобразом,числовсевозможныхперестановоквмножестве

изnэлементов

Pn=n!.

2. Представимтеперь,что,каквпредыдущейзадаче,унасnпронумерованныхстульев,номырассаживаемнанихmпретендентов,причемm>n.Конечно,всехусадитьмынесможем,нохотимвыяснить,сколькоимеетсявариантоврассаживания.Рассуждаятакже,каквпредыдущейзадаче,видим,чтона1-йстулимеетсяmпретендентов,навторой(m–1),натретий(m–2),….,наn-йстулостается(m–n+1)претендент.Итак, число вариантовравно

(m- n+1)´(m- n+ 2)´...´(m-1)´m=

m! .

(m- n)!

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

такихразмещенийобозначается

Amn.Такимобразом,

Amn

= m! .

(m- n)!

3. Рассмотримтеперьнесколькодругуюзадачу,гдемы«раздаем»несидячиеместанапронумерованныхстульях(какизвестно,человекнеможетсидетьодновременноболее,чемнаодномстуле),а,например,nраритетныхкниггруппестрастныхбиблиофилов,состоящейизmчеловек.Скольковариантовраздачиnкнигmпретендентам?Напервуюкнигуунасmпретендентов,навторую–тожеmпретендентов,и

такдалее.Следовательно,мыимеемmn

междупретендентами.

вариантовраспределениякниг

Любойупорядоченныйнаборnэлементовмножества,состоящегоизm

элементов,называетсяразмещениемсповторениемизm поn иравен

mn.

4. Вернемсяковторойзадаче,гдемырассаживалиmчеловекнаnстульях,толькотеперьунасстульянепронумерованы,неотличаютсядруготдруга,инаснеинтересует,гдектосидит,аинтересует,сидитчеловекилистоит.Значит,числовариантоврассаживаниясовпадаетсчисломвариантовотбораизmгостейгруппысчастливчиков,состоящейизnчеловек,которыесмогут сесть настулья.Решениеэтойзадачиможносвязать срешениемзадачи2.Представим,чтомырешилибызадачу2такимобразом:отбиралибыгруппыпоnчеловек,азатемделалибывнутригруппыотобранныхдлясиденияnчеловеквсевозможныеперестановки,чтобыучестьвсевариантырассаживаниянапронумерованныхстульях.Мыдолжныбылибыполучить

тотжерезультат:

Amn.Следовательно,количествовариантоввыбора групп

поnчеловекизmчеловекравно

Amn, деленноеначислоперестановокв

группе изnчеловек,тоестьна

n!.

Любоеподмножествоиз nэлементовмножества, состоящегоиз mэлементов,называетсясочетаниемиз m по n, и числосочетаний

обозначается

Cmn. Всоответствиисрассуждениямиприрешениизадачи,

Cn=

Amn

или

Cmn=

m! .

m n!

n!(m- n)!

РЯДЫ

Числовыеряды

Понятиепределапоследовательностидаетвозможностьввестипонятие

¥

числовогоряда–бесконечнойсуммывида

åak,где

k=1

ak–общийчленряда.

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

n

последовательности

sn–конечныхn- ныхчастныхсумм

¥

sn= åak.Таким

k=1

образом,суммойряда

åakбудем называтьчисло

k=1

å k

n

s= lim a.

n®¥ k=1

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

Пример 1. Сосчитаем сумму ряда

¥

åqk, |q|<1. Имеем согласно

k=1

формулесуммыгеометрическойпрогрессии

sn=

n

å

k=1

qk= q× qn-1.Поскольку

q-1

qn® 0

приn®¥,получим

¥

åqk=

k=1

q .

1- q

Заметим, чтопри|q|³1соответствующийрядрасходится.

¥

Пример 2. Сосчитаемсуммуряда å 1

. Имеем

sn= 1 + 1

+...+ 1

k=1k(k+1)

= 2-1+ 3- 2+...+n+1- n=

1×2 2×3

n(n+1) 1×2 2×3

n(n+1)

=1- 1+ 1- 1+...+ 1- 1

=1- 1 ,

¥

2 2 3

n n+1

n+1

следовательно,å 1

=1.

k=1k(k+1)

Необходимым признаком сходимостичислового ряда является

¥

n

условие:lima= 0.Доказываетсяэтолегко:пустьряд

n®¥

åakk=1

сходится,тоесть

n

существует lims= s. При n®¥справедливо:

n®¥

n-1® ¥ . Следовательно,

n-1

lims = s. Поскольку

n®¥

sn- sn-1= an, то из1-гои 2-госвойствпределов

последовательностейимеем:

liman= lim(sn- sn-1)= 0, что и требовалось

доказать.

n®¥

n®¥

å

Заметим,чтонеобходимоеусловиесходимостинеявляетсядостаточным.Тоесть,стремлениекнулюобщегочленаряданеобеспечиваетегосходимость.

Контрпример. Покажем,чторяд

¥ 1, называемыйгармоническим

k=1k

рядом,расходится.Дляэтогорассмотримпоследовательностьчастныхсумм

s2n,то естьчастныесуммы

s2,s4,s8,.....Присуммированиичленовконечной

суммы

s2n

сгруппируемрядомстоящиечленысуммы,начинаяот

до

2l+1

2l+1,привсехl=1,...,n-1:

sn=1+ 1+ (1+ 1)+ (1+...+ 1)+...+ ( 1

+...+

1)>

2 2 3 4 5 8

2n-1+1 2n

>1+ 1+ 2× 1+ 4× 1+...+ 2n-1× 1

=1+ n× 1.

2 4 8 2n 2

Таким образом,

lims2

=¥ , и значит, предел последовательности

n®¥ n

частныхсуммне можетбыть конечным.

Свойствачисловых рядов

Следующиесвойствасходящихсярядовочевиднымобразомследуютизсвойствпределовпоследовательностей.

¥ ¥ ¥ ¥

1. Пустьряды

¥

åak и

k=1

åbkk=1

сходятся, причем

åak= s,

k=1

åbk= s .

k=1

Тогдаряд

å(a × ak + b ×bk)

k=1

также сходится, причем

¥

å(a × ak + b ×bk)= a × s+ b ×s .

k=1

2. Ряды

¥

åakk=1

¥

и åak+ Nk=1

сходятсяилирасходятсяодновременно,

причем

¥ ¥

åak+N= åak- sN.

k=1

k=1