Выпуклые k-угольники. [Комбинаторика]

[Whitaker]

Здравствуйте уважаемые! Хотелось бы разобраться со следующей задачей.

Найдите число всех выпуклых $k$-угольников, вершинами которых служат $k$ из $n$ вершин выпуклого $n$-угольника, причем каждые две соседние вершины $k$-угольника должны быть разделены, по меньшей мере $s$ вершинами $n$-угольника.

Я попытался его решить следующим образом: По условию у нас $n$ вершин и это: $A_1, A_2, ...., A_{n-1}, A_n$. Все выпуклые $k$-угольники, удовлетворяющие условию задачи делятся на 2 класса.
К первому классу отнесём $k$-угольники у которых среди вершин есть точка $A_1$, а ко второму классу отнесём $k$-угольники у которых среди вершин нет точки $A_1$. Посчитаем сколько $k$-угольников в каждом классе.
Вершину которую мы возьмём будем ставит $1$, а вершину которую мы не берем ставим - $0$.
Начнём с первого класса. Обозначим через $X$ следующий набор $1\underbrace{00...00}_{s}$. Тогда количество $k$-угольников из первого класса равно количеству различных расстановок $(k-1)$-го набора $X$ и $n-k(s+1)$ нулей. Это равно $P(k; n-k(s+1))=C_{n-ks}^{k}$.
Теперь рассмотрим второй класс, где среди вершин выпуклых $k$-угольников нет точки $A_1$. Если точка $A_1$ не является вершиной выпуклого $k$-угольника, тогда следующие $s$ множеств точек не входят:
$(A_1, A_2, A_3, ...,A_{s-1}, A_s)$
$(A_n, A_1, A_2, ...,A_{s-2}, A_{s-1})$
$(A_{n-1}, A_n, A_1, ...,A_{s-2}, A_{s-1})$
..........
$(A_{n-s+2}, A_{n-s+3}, ...,A_{n}, A_1)$
Тогда количество выпуклых $k$-угольников равно количеству различных расстановок $k$ штук набора $X$ и $(n-s-k-ks)$ нулей. А это равно $P(k; n-s-k-sk)=C_{n-s-ks}^{k}$. Но последнее еще нужно умножить на $s$. В итоге получаем, что $C_{n-ks}^{k}+sC_{n-s-ks}^{k}$.

Но ответ в книге $C_{n-ks}^{k}+sC_{n-ks-1}^{k-1}$. Я догадываюсь, что при подсчете элементов второго класса у меня некоторые $k$-угольники вошли по несколько раз. Но как исправить я пока не понял. Буду очень рад если кто-нибудь подскажет как сделать это.

[TOTAL]

Whitaker в сообщении #473136 писал(а):

Но ответ в книге $C_{n-ks}^{k}+sC_{n-ks-1}^{k-1}$. Я догадываюсь, что при подсчете элементов второго класса у меня некоторые $k$-угольники вошли по несколько раз. Но как исправить я пока не понял. Буду очень рад если кто-нибудь подскажет как сделать это.

Первый класс Вы подсчитали неверно, подогнали к ответу.

Попробуйте так. На какую-нибудь сторону n-угольника посадите муху. Муха либо не попадёт в фигуру 10000000 (первое слагаемое ответа), либо займет одно из $s$ положений в этой фигуре (второе слагаемое).

[Whitaker]

Первый класс я же подсчитал правильно. Там же всё написано как я подсчитал первый класс. Вы наверное имели в виду, что у меня второй класс подсчитан неправильно.

TOTAL в сообщении #473149 писал(а):

Попробуйте так. На какую-нибудь сторону n-угольника посадите муху. Муха либо не попадёт в фигуру 10000000 (первое слагаемое ответа), либо займет одно из $s$ положений в этой фигуре (второе слагаемое).

А откуда взялся 10000000?? Я не понял, что вы имеет в виду

[TOTAL]

Whitaker в сообщении #473151 писал(а):

Первый класс я же подсчитал правильно. Там же всё написано как я подсчитал первый класс. Вы наверное имели в виду, что у меня второй класс подсчитан неправильно.

TOTAL в сообщении #473149 писал(а):

Попробуйте так. На какую-нибудь сторону n-угольника посадите муху. Муха либо не попадёт в фигуру 10000000 (первое слагаемое ответа), либо займет одно из $s$ положений в этой фигуре (второе слагаемое).

А откуда взялся 10000000?? Я не понял, что вы имеет в виду

Вот это что такое $1\underbrace{00...00}_{s}$

Первый класс подсчитан неверно, второй я даже не смотрел.

[PAV]

Первое слагаемое ответа явно отсылает к предыдущей задаче http://dxdy.ru/topic48212.html
В самом деле, ясно, что если назвать вершины многоугольника книгами, то любой способ выбора книг, описанный в той задаче, даст допустимый $k$-угольник в новой задаче. Однако кроме них, имеются еще способы, поскольку многоугольник замкнут в кольцо, то мы можем добавить в качестве вершины любую из $s$ "последних" книг на полке, взяв недостающее число вершин из начала. Вот так и подумайте.

-- Ср авг 03, 2011 14:59:45 --

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

[Whitaker]

TOTAL в сообщении #473153 писал(а):

Whitaker в сообщении #473151 писал(а):

Первый класс я же подсчитал правильно. Там же всё написано как я подсчитал первый класс. Вы наверное имели в виду, что у меня второй класс подсчитан неправильно.

TOTAL в сообщении #473149 писал(а):

Попробуйте так. На какую-нибудь сторону n-угольника посадите муху. Муха либо не попадёт в фигуру 10000000 (первое слагаемое ответа), либо займет одно из $s$ положений в этой фигуре (второе слагаемое).

А откуда взялся 10000000?? Я не понял, что вы имеет в виду

Вот это что такое $1\underbrace{00...00}_{s}$

Первый класс подсчитан неверно, второй я даже не смотрел.

Да вы действительно были правы там ответ получается таким: $C_{n-ks-1}^{k-1}$. А откуда тогда первое слагаемое берется?

[TOTAL]

Whitaker в сообщении #473259 писал(а):

А откуда тогда первое слагаемое берется?

Вот здесь было написано про оба слагаемых.

TOTAL в сообщении #473153 писал(а):

Муха либо не попадёт в фигуру 10000000 (первое слагаемое ответа), либо займет одно из $s$ положений в этой фигуре (второе слагаемое).

[Whitaker]

Вот ко мне пришла в голову такая мысль.
Зафиксируем $s$ подряд идущих вершин $n$-угольника. Это будут вершины: $A_1, A_2, ..., A_s$ и разделим всё k-угольники удовлетворяющие условию задачи на два класса. К первому классу отнесем все $k$-угольники одна из вершин которых совпадает с одной из зафиксированных вершин (т.е. с одной из вершин $A_1, A_2, ..., A_s$), а ко второму классу все остальные $k$-угольники. Разобьем все $k$-угольники первого класса на $s$ подклассов в соответствии с тем, какая из вершин $A_i, 1\leq i \leq s$, встречается в $k$-угольнике. Понятно, что эти подклассы имеют пустое пересечение.
Найдём число $k$-угольников первого класса, для которых одной из вершин является $A_i$. Проведём те же самые рассуждения как и в предыдущем моем посте и получим ответ $C_{n-ks-1}^{k-1}$.
А так как мы зафиксировали $s$ вершин, то число $k$-угольников первого класса равно $sC_{n-ks-1}^{k-1}$. Первое слагаемое ответа получен.
Найдём теперь количество $k$-угольников второго класса. Теперь нам надо выбрать $k$ вершин так, чтобы после каждой выбранной вершины шли по крайней мере еще $s$ вершин, но нужно помнить то, что ни одна из вершин $A_1, A_2, ..., A_s$ не должна быть выбрана. Здесь ответ должен быть $C_{n-ks}^{k}$, но у меня получается другой ответ.

Объясните кто-нибудь пожалуйста как получить правильный ответ ко второму классу.

[TOTAL]

Whitaker в сообщении #473366 писал(а):

Объясните кто-нибудь пожалуйста как получить правильный ответ ко второму классу.

Вам уже говорили про второй класс

PAV в сообщении #473165 писал(а):

Первое слагаемое ответа явно отсылает к предыдущей задаче http://dxdy.ru/topic48212.html

[Whitaker]

Аааа я понял всё! Спасибо Вам большое за терпение TOTAL и PAV!