Дискретная математика

Квас · мая 22, 2011, 23:48

А, у нас их зовут рекуррентными формулами.

Цитата: RawonaM от мая 22, 2011, 23:40
Найти рекурсивную формулу для количества кусков образуемых эн окружностями на плоскости.

Топология, однако! Но тут же нет единственного решения: две непересекающиеся окружности делять плоскость на три куска, а две пересекающиеся — на 4.

RawonaM · мая 22, 2011, 23:50

Цитата: Квас от мая 22, 2011, 23:48
Топология, однако! Но тут же нет единственного решения: две непересекающиеся окружности делять плоскость на три куска, а две пересекающиеся — на 4.

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

Квас · мая 23, 2011, 00:30

Та-ак... Значит, у нас лежат n окружностей, которые делят плоскость на A_n частей. Предположим, что будем исходить из таких предпосылок:
1. Если «новая» окружность встречается с границей куска, то она встречается с ней ровно два раза и делит его на 2 части.
2. Всякая точка пересечения «новой» окружности со старой лежит на границе ровно двух смежных кусков.

Постулат 2 очевиден, а постулат 1 — что-то не очень. Из постулата 1 следует, что число полученных кусков равно
A_n+1 = A_n + B_n,
где B_n — число кусков, с которыми встретилась окружность. Из постулатов следует, что B_n равно числу точек пересечения новой окружности с имеющимися, то есть B_n = 2(n-1). Ainsi, on a
A_n+1 = A_n + 2(n-1).

Для n=2, 3, 4 работает.

RawonaM · июня 2, 2011, 21:16

Цитата: Квас от мая 23, 2011, 00:30
где B_n — число кусков, с которыми встретилась окружность. Из постулатов следует, что B_n равно числу точек пересечения новой окружности с имеющимися, то есть B_n = 2(n-1). Ainsi, on a
A_n+1 = A_n + 2(n-1).

Для n=2, 3, 4 работает.

По ответу из учебника A_n+1 = A_n + 2n.
Вроде как понятно, но не знаю, за какое время я дошел бы до этого сам.

Вот этого не понимаю даже после того как прочитал ответ:
Найти рекурсивное отношение выбора k предметов из n типов предметов (имеющееся количество предметов каждого типа неограничено).
Если надо, напишу ответ, но может вам будет интереснее без ответа

Квас · июня 2, 2011, 21:51

Цитата: RawonaM от июня 2, 2011, 21:16
Цитата: Квас от мая 23, 2011, 00:30где B_n — число кусков, с которыми встретилась окружность. Из постулатов следует, что B_n равно числу точек пересечения новой окружности с имеющимися, то есть B_n = 2(n-1). Ainsi, on a
A_n+1 = A_n + 2(n-1).

Для n=2, 3, 4 работает.
По ответу из учебника A_n+1 = A_n + 2n.

Другой ответ?! А у меня для n = 2, 3, 4 работает!

Цитата: RawonaM от июня 2, 2011, 21:16
Найти рекурсивное отношение выбора k предметов из n типов предметов (имеющееся количество предметов каждого типа неограничено).

То есть нужно найти число способов выбрать наборы $[tex](k_1,\ldots,k_n)[/tex]$ из целых неотрицательных чисел так, чтобы $[tex]k_1+\ldots+k_n=k[/tex]$ ?

Обозначим эту величину A_nk. Все способы выбора делятся на 2 группы: имеется предмет 1 типа или не имеется. Число групп, в которых предмета 1 типа нет, есть A^n-1,k. Пусть предмет 1 типа есть. Уберём один такой предмет и получим выбор k-1 предмета из n типов, число способов выбора равно A^n,k-1. Получаем
$[tex]A_{nk}= A_{n-1,k}+A_{n,k-1}.[/tex]$
Если дополнить очевидными соотношениями
$[tex]A_{1k}=1, \quad A_{n1}=n,[/tex]$
можно вычислить A_kn для любых натуральных k, n.

RawonaM · июня 2, 2011, 22:09

Цитата: Квас от июня 2, 2011, 21:51
Цитата: RawonaM от июня 2, 2011, 21:16По ответу из учебника A_n+1 = A_n + 2n.
Другой ответ?! А у меня для n = 2, 3, 4 работает!

Ну вероятно вы плохо посчитали

По вашей формуле: А₂=А₁+2*0=2

RawonaM · июня 2, 2011, 22:10

Цитата: Квас от июня 2, 2011, 21:51
Цитата: RawonaM от июня 2, 2011, 21:16Найти рекурсивное отношение выбора k предметов из n типов предметов (имеющееся количество предметов каждого типа неограничено).
То есть нужно найти число способов выбрать наборы $[tex](k_1,\ldots,k_n)[/tex]$ из целых неотрицательных чисел так, чтобы $[tex]k_1+\ldots+k_n=k[/tex]$ ?

Обозначим эту величину A_nk. Все способы выбора делятся на 2 группы: имеется предмет 1 типа или не имеется. Число групп, в которых предмета 1 типа нет, есть A^n-1,k. Пусть предмет 1 типа есть. Уберём один такой предмет и получим выбор k-1 предмета из n типов, число способов выбора равно A^n,k-1. Получаем
$[tex]A_{nk}= A_{n-1,k}+A_{n,k-1}.[/tex]$
Если дополнить очевидными соотношениями
$[tex]A_{1k}=1, \quad A_{n1}=n,[/tex]$
можно вычислить A_kn для любых натуральных k, n.

Не дается мне это сегодня

RawonaM · июня 2, 2011, 22:51

Цитата: Квас от июня 2, 2011, 21:51
Цитата: RawonaM от июня 2, 2011, 21:16Найти рекурсивное отношение выбора k предметов из n типов предметов (имеющееся количество предметов каждого типа неограничено).
То есть нужно найти число способов выбрать наборы $[tex](k_1,\ldots,k_n)[/tex]$ из целых неотрицательных чисел так, чтобы $[tex]k_1+\ldots+k_n=k[/tex]$ ?

Обозначим эту величину A_nk. Все способы выбора делятся на 2 группы: имеется предмет 1 типа или не имеется. Число групп, в которых предмета 1 типа нет, есть A^n-1,k. Пусть предмет 1 типа есть. Уберём один такой предмет и получим выбор k-1 предмета из n типов, число способов выбора равно A^n,k-1. Получаем
$[tex]A_{nk}= A_{n-1,k}+A_{n,k-1}.[/tex]$
Если дополнить очевидными соотношениями
$[tex]A_{1k}=1, \quad A_{n1}=n,[/tex]$

Как я рассуждал над этой задачей: рассмотрим выбор k-1 предметов, их можно дополнить еще одним из n предметов и будет A_nk, поэтому A_n,k=n*А_n,k-1.
Это неправильно? Недостаточно рекурсивно?

В книге ответ совершенно отличный и от вашего и от моего подавно. Ответ такой:
f(n,k)=f(n-1,k)+f(n-1,k-1)+f(n-1,k-2)+...+f(n-1,1)+1

RawonaM · июня 2, 2011, 23:46

f(n) — количество последовательностей цифр 1-8 длиной n, таких, в которых четные цифры не стоят рядом друг с другом. Найти рекурсивное отношение f(n). Мое решение:

Обозначим fodd(n) — количество таких последовательностей, в которых первая цифра нечетная.
feven(n) — количество таких последовательностей, в которых первая цифра четная.

Следовательно:
$[tex]f(n)=fodd(n)+feven(n)\\ fodd(n)=4f(n-1)\\ feven(n)=4fodd(n-1)=4\cdot4f(n-2)\\ f(n)=4f(n-1)+16f(n-2)[/tex]$

С помощью комбинаторики:
$[tex]f(0)=1[/tex]$
$[tex]f(1)=8[/tex]$
$[tex]f(2)=8^2-4^2=48[/tex]$

С другой стороны по найденной формуле:
$[tex]f(2)=4\cdot8+16\cdot1=48 [/tex]$

Все верно?

Квас · июня 2, 2011, 23:50

Цитата: RawonaM от июня 2, 2011, 22:51
Как я рассуждал над этой задачей: рассмотрим выбор k-1 предметов, их можно дополнить еще одним из n предметов и будет A_nk, поэтому A_n,k=n*А_n,k-1.
Это неправильно? Недостаточно рекурсивно?

Эта формула должна порушиться уже на небольших n и k.

Цитата: RawonaM от июня 2, 2011, 22:51
f(n,k)=f(n-1,k)+f(n-1,k-1)+f(n-1,k-2)+...+f(n-1,1)+1

Если моё расписать, вроде то же получается.

RawonaM · июня 3, 2011, 08:24

Цитата: Квас от июня 2, 2011, 23:50
Эта формула должна порушиться уже на небольших n и k.

А где ошибка в рассуждении?

Обращаю внимание:

Цитата: RawonaM от июня 2, 2011, 23:46
f(n) — количество последовательностей цифр 1-8 длиной n, таких, в которых четные цифры не стоят рядом друг с другом. Найти рекурсивное отношение f(n). Мое решение:

А то вы часто сообщения пропускаете, несмотря на предупреждение о новых сообщениях

RawonaM · июня 3, 2011, 10:59

Цитата: RawonaM от июня 2, 2011, 23:46
$[tex]f(n)=4f(n-1)+16f(n-2)[/tex]$

Отсюда также надо вывести прямую функцию, у меня получилось так:
$[tex]f(n)=\left(\frac12+\frac3{\sqrt{20}}\right)\left(2+\sqrt{20}\right)^n+\left(\frac12-\frac3{\sqrt{20}}\right)\left(2-\sqrt{20}\right)^n[/tex]$

Что думаете?

RawonaM · июня 3, 2011, 16:40

У меня есть $[tex](1+x+x^2+x^3)^2[/tex]$ , как это представить сигмой от 0 до бесконечность? Должен быть или D(n,k) какой-нить что ли...

Квас · июня 3, 2011, 16:57

Цитата: RawonaM от июня 2, 2011, 23:46
Все верно?

Ошибок не нашёл.

Цитата: RawonaM от июня 3, 2011, 08:24

Цитата: Квас от июня 2, 2011, 23:50Эта формула должна порушиться уже на небольших n и k.
А где ошибка в рассуждении?

Вы выбираете набор $[tex]x = (k_1,\ldots,k_n)[/tex]$ и на его основе делаете набор y, прибавив 1 к одной из компонент. Но таким путём y можно получить из разных х.

Стоит помнить, что за общими рассуждениями стоят судьбы совершенно конкретных k и n. Поэтому никогда не повредит изучить, что происходит при их небольших значениях.

Цитата: RawonaM от июня 3, 2011, 08:24
Цитата: RawonaM от июня 2, 2011, 23:46f(n) — количество последовательностей цифр 1-8 длиной n, таких, в которых четные цифры не стоят рядом друг с другом. Найти рекурсивное отношение f(n). Мое решение:

А то вы часто сообщения пропускаете, несмотря на предупреждение о новых сообщениях

Я не пропустил, я не имел переваренным (плюсквамперфект!).

Цитата: RawonaM от июня 3, 2011, 10:59
Что думаете?

Формула правильная.

Квас · июня 3, 2011, 16:59

Цитата: RawonaM от июня 3, 2011, 16:40
У меня есть $[tex](1+x+x^2+x^3)^2[/tex]$ , как это представить сигмой от 0 до бесконечность? Должен быть или D(n,k) какой-нить что ли...

Многочлен бесконечной суммой?

RawonaM · июня 3, 2011, 17:01

Цитата: Квас от июня 3, 2011, 16:59
Цитата: RawonaM от июня 3, 2011, 16:40У меня есть $[tex](1+x+x^2+x^3)^2[/tex]$ , как это представить сигмой от 0 до бесконечность? Должен быть или D(n,k) какой-нить что ли...
Многочлен бесконечной суммой?

А что, нельзя? Просто лишние слагаемые будут нули.

Квас · июня 3, 2011, 17:08

Если раскрыть скобки, будет
$[tex]1+2\,x+3\,{x}^{2}+4\,{x}^{3}+3\,{x}^{4}+2\,{x}^{5}+{x}^{6}[/tex]$

RawonaM · июня 3, 2011, 17:37

У меня есть полином $[tex](1+x+x^2+x^3)^2(1+x+x^2+...)^2[/tex]$ , нужно найти f(n) — коэффициент хⁿ в этом полиноме.

Я вот что сделал:
(по формулам)
$[tex](1+x+x^2+x^3)=\frac{1-x^{4}}{1-x}[/tex]$ $[tex](1+x+x^2+x^3...)=\frac{1}{1-x}[/tex]$

Отсюда:

$[tex](1+x+x^2+x^3)^2(1+x+x^2+...)^2=\frac{(1-x^{4})^2}{(1-x)^2}\cdot\frac{1}{(1-x)^2}=\\\\=(1-x^4)^2(1-x)^{-4}=(1-x)^{-4}-2x^4(1-x)^{-4}+x^8(1-x)^{-4}[/tex]$

Поэтому:

$[tex]f(n)=D(4,n)-2D(4,n-4)+D(4,n-8)=\\\\=\binom{3+n}n - 2 \binom{3+n}{n-4} + \binom{3+n}{n-8}[/tex]$

Нормально?

Квас · июня 3, 2011, 20:30

Цитата: RawonaM от июня 3, 2011, 17:37
Я вот что сделал:
(по формулам)
$[tex](1+x+x^2+x^3)=\frac{1-x^{4}}{1-x}[/tex]$ $[tex](1+x+x^2+x^3...)=\frac{1}{1-x}[/tex]$

Отсюда:

$[tex](1+x+x^2+x^3)^2(1+x+x^2+...)^2=\frac{1-x^{4}}{1-x}\cdot\frac{1}{(1-x)^2}=\\\\=(1-x^4)^2(1-x)^{-4}=(1-x)^{-4}-2x^4(1-x)^{-4}+x^8(1-x)^{-4}[/tex]$

Поэтому:

Вообще не понимаю эти выкладки.
$[tex]1+x+x^2+x^3 = \frac{1-x^4}{1-x}[/tex]$
$[tex]1+x+x^2+x^3+\ldots = \frac{1}{1-x} \quad(|x|<1)[/tex]$
$[tex](1+x+x^2+x^3)^2(1+x+x^2+x^3+\ldots) = \frac{(1-x^4)^2}{(1-x)^3}\quad(|x|<1)[/tex]$

А D(k,n) — что за обозначение?

RawonaM · июня 3, 2011, 20:34

Цитата: Квас от июня 3, 2011, 20:30
Вообще не понимаю эти выкладки.

А что именно непонятно? Вы же то же самое повторили... Только начало.

Цитата: Квас от июня 3, 2011, 20:30
А D(k,n) — что за обозначение?

$[tex]D(k,n)=\binom{n+k-1}{n}[/tex]$

RawonaM · июня 3, 2011, 20:38

Там небольшая ошибка закралась, я поправил, но она какбе ни на что не влияет.

Квас · июня 3, 2011, 21:07

Цитата: RawonaM от июня 3, 2011, 17:37
Отсюда:

$[tex](1+x+x^2+x^3)^2(1+x+x^2+...)^2=\frac{(1-x^{4})^2}{(1-x)^2}\cdot\frac{1}{(1-x)^2}=\\\\=(1-x^4)^2(1-x)^{-4}=(1-x)^{-4}-2x^4(1-x)^{-4}+x^8(1-x)^{-4}[/tex]$

Поэтому:

$[tex]f(n)=D(4,n)-2D(4,n-4)+D(4,n-8)=\\\\=\binom{3+n}n - 2 \binom{3+n}{n-4} + \binom{3+n}{n-8}[/tex]$

Нормально?

Ah, ça y est ! В первой строке я принял пробел за умножение, и недопонимание усугубилось четвёртой степенью в знаменателе. (Мне сегодня простительно: студенты сокрушили. Последняя пересдача, зачёт получили 3 из 8.

)

Ваша идея ясна. Но прямое вычисление показывает, что ответ неправильный. Разложение, на которое мы опираемся, имеет вид
$[tex](1-x)^{-4}=\Sum_{n=0}^\infty \frac{(3+n)!}{3!n!}[/tex]$ ,
и если вместо D(4,n) взять
$[tex]k(n) = \frac{(3+n)!}{3!n!},[/tex]$
то получается то, что надо.

(Я уже начинаю вам завидовать белой завистью. А откуда задания, это задачники такие?)

RawonaM · июня 3, 2011, 21:18

Цитата: Квас от июня 3, 2011, 21:07
(Мне сегодня простительно: студенты сокрушили. Последняя пересдача, зачёт получили 3 из 8. )

Действительно простительно. Сочувствую

Цитата: Квас от июня 3, 2011, 21:07
и если вместо D(4,n) взять
$[tex]k(n) = \frac{(3+n)!}{3!n!},[/tex]$
то получается то, что надо.

Так $[tex]D(4,n)=\binom{n+3}{n}=\frac{(3+n)!}{3!n!}[/tex]$ .
Чего ж тогда не сходится?

Цитата: Квас от июня 3, 2011, 21:07
(Я уже начинаю вам завидовать белой завистью. А откуда задания, это задачники такие?)

Это домашнее задание

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

Квас · июня 3, 2011, 21:31

Цитата: RawonaM от июня 3, 2011, 21:18
Так $[tex]D(4,n)=\binom{n+3}{n}=\frac{(3+n)!}{3!n!}[/tex]$ .
Чего ж тогда не сходится?

А, сообразил! Я сравнивал разложение в ряд и вычисленные коэффициенты. Если коэффициенты забивать через факториалы, то работает начиная с 8-й степени (потому что должно быть n-8 ≥ 0); если забить формулу для D, работает начиная с $[tex]\inline x^5[/tex]$ . А меня несовпадение первых членов смутило.

Цитата: RawonaM от июня 3, 2011, 21:18
Цитата: Квас от июня 3, 2011, 21:07(Я уже начинаю вам завидовать белой завистью. А откуда задания, это задачники такие?)
Это домашнее задание Ну я в книге все прорешал, вот делаю работу на сдачу, но че-то сложноватый это материал немножко, целый день сижу.

Классные дидактические материалы!

По всем предметам. Мне в универе отродясь таких интересных задач решать не приходилось. Но, блин, наши студенты — лучший демотиватор.

RawonaM · июня 3, 2011, 21:45

Цитата: Квас от июня 3, 2011, 21:31
А, сообразил! Я сравнивал разложение в ряд и вычисленные коэффициенты. Если коэффициенты забивать через факториалы, то работает начиная с 8-й степени (потому что должно быть n-8 ≥ 0); если забить формулу для D, работает начиная с $[tex]\inline x^5[/tex]$ . А меня несовпадение первых членов смутило.

Так все правильно значит? А то я уже на чистовик написал))

Цитата: Квас от июня 3, 2011, 21:31
Классные дидактические материалы! По всем предметам. Мне в универе отродясь таких интересных задач решать не приходилось. Но, блин, наши студенты — лучший демотиватор.

Ваши слова придают мне гордости и мотивации.

А что, сильно могут отличаться эти задачки? Плюс-минус ведь все одно и то же. Может это сейчас они вам интересными кажутся, а раньше как-то были не очень?

Я вот курсом логики совсем не доволен. Просто беспредел какой-то, а не логика.

Лингвофорум

Дискретная математика

Квас

RawonaM

Квас

RawonaM

Квас

RawonaM

RawonaM

RawonaM

RawonaM

Квас

RawonaM

RawonaM

RawonaM

Квас

Квас

RawonaM

Квас

RawonaM

Квас

RawonaM

RawonaM

Квас

RawonaM

Квас

RawonaM

Быстрый ответ