Лингвофорум

Цитата: Квас от мая 20, 2011, 17:55
Это несюръективные.

Точно.

Цитата: Квас от мая 20, 2011, 17:55
А нас интересуют только размещения без повторений элементов из B: 7 ∙ 6 ∙ 5 ∙ 4.

Ну это я уже знаю. А другого пути нет? Чтоб из 7^4 повычитать.

Цитата: RawonaM от мая 20, 2011, 18:00
Цитата: Квас от Сегодня в 18:55

ЦитироватьА нас интересуют только размещения без повторений элементов из B: 7 ∙ 6 ∙ 5 ∙ 4.

Ну это я уже знаю. А другого пути нет? Чтоб из 7^4 повычитать.

Мне кажется, будет сложно. Потому что надо учитывать, что разное число элементов B могут иметь прообразы  с числом элементов >1, и число элементов в этих прообразах тоже может быть разным. На самом деле размещения без повторений — это именно ответ на вопрос о числе инъективных отображений, ибо что есть инъективное отображение?

Ладно, уговорили. Мудрить не буду.

Собственно, у меня есть тут второй пункт, посложнее. Я пока над ним думаю.

Теперь такой вопрос по тому же: сколько инъективных фукций из А в В, при условии что для любого i в А, f(i)!=i?

Моя версия:

Кёскё ву дит?

Еще из той же области: четыре семьи вышли на день независимости в парк на барбекью. На общем мангале пожарили 9 стэйков и 12 шампуров. Сколько вариантов поделить еду между всеми, так чтобы каждая семья получила хотя бы один стэйк или шампур?

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

Цитата: RawonaM от мая 20, 2011, 20:33
f(i)!=i?

Это как? Они же разным множествам принадлежат.

Цитата: Квас от мая 20, 2011, 21:50

Цитироватьf(i)!=i?

Это как? Они же разным множествам принадлежат.

i — натуральное число.
Т.е. чтобы f(1)!=1 и т.п.

А тьфу, пардон. Забыл сказать, что А={1,2,3,4}, В={x|1<=х<=7, х натурал}.

Цитата: RawonaM от мая 20, 2011, 21:54
В={x|1<=х<=7, х натурал}

От блин, быстрее было все набрать в ряд эксплицитно.

Озадачилсо.

Цитата: Квас от мая 20, 2011, 23:00
Озадачилсо.

А что, разве не тривиально? inclusion-exclusion principle desu. Вот я и хотел узнать, есть ли другой способ решения.

Цитата: RawonaM от мая 20, 2011, 23:02
А что, разве не тривиально? inclusion-exclusion principle desu. Вот я и хотел узнать, есть ли другой способ решения.

Многовато множеств.

Дано множество {4,5,6,...,60,61} и его подмножество А с 9 элементами.
С помощью принципа Дирихле доказывается, что в А есть по меньшей мере два подмножества, у которых сумма элементов равна.

Как отсюда следует, что существует по меньшей мере два непересекаемых подмножества А, у которых сумма равна?

Цитата: RawonaM от мая 20, 2011, 21:50
У меня вышло 80856, если у кого есть желание тоже поковыряться и перепроверить, буду рад

Да!!! Я делил на 2 и ещё раз каждую на 2. Основывался на следующей формуле: a стейков и b шампуров можно разделить на 2 части так, чтобы все что-нибудь досталось, (a+1)(b+1)-2 способами, формула сбоит только при a=0=b. Вроде там сводится к суммированию арифметической прогрессии и квадратов, но я предпочёл напрячь комп.

Цитата: RawonaM от мая 20, 2011, 20:33
Теперь такой вопрос по тому же: сколько инъективных фукций из А в В, при условии что для любого i в А, f(i)!=i?

Моя версия:

Кёскё ву дит?

А почему степени а не 6*5*4 и т. д.?

Брут форс даёт 465 вариантов. Ничего не сображаю.

Цитата: Квас от мая 21, 2011, 23:09

ЦитироватьУ меня вышло 80856, если у кого есть желание тоже поковыряться и перепроверить, буду рад

Да!!! Я делил на 2 и ещё раз каждую на 2. Основывался на следующей формуле: a стейков и b шампуров можно разделить на 2 части так, чтобы все что-нибудь досталось, (a+1)(b+1)-2 способами, формула сбоит только при a=0=b. Вроде там сводится к суммированию арифметической прогрессии и квадратов, но я предпочёл напрячь комп.

Ну хорошо, что совпало.  Это вообще-то решается инклужном-экслужном без прогрессий и компа.

Цитата: Квас от мая 21, 2011, 23:32
А почему степени а не 6*5*4 и т. д.?

И правда, почему?.. Наверное ошибка.
Но все равно ответ выходит 705, далеко от вашего брутфорса. А брутфорсу можно доверять?

Цитата: RawonaM от мая 22, 2011, 09:25

ЦитироватьА почему степени а не 6*5*4 и т. д.?

И правда, почему?.. Наверное ошибка.
Но все равно ответ выходит 705, далеко от вашего брутфорса. А брутфорсу можно доверять?

Мой калькулятор ошибся. Если сделать 6*4*5 и 5*4 вместо степеней, то как раз 465 и выходит.

Цитата: RawonaM от мая 21, 2011, 12:26
Дано множество {4,5,6,...,60,61} и его подмножество А с 9 элементами.
С помощью принципа Дирихле доказывается, что в А есть по меньшей мере два подмножества, у которых сумма элементов равна.

Как отсюда следует, что существует по меньшей мере два непересекаемых подмножества А, у которых сумма равна?

Тут что-нибудь подсказать можете? У меня в задании написано, как будто второе из первого банально следует. А я туплю

Дошло!!! 

Цитата: RawonaM от мая 21, 2011, 12:26
Дано множество {4,5,6,...,60,61} и его подмножество А с 9 элементами.
С помощью принципа Дирихле доказывается, что в А есть по меньшей мере два подмножества, у которых сумма элементов равна.

Как отсюда следует, что существует по меньшей мере два непересекаемых подмножества А, у которых сумма равна?

Кириллицу игнорирует.

Да я уже сам дошел. Но спасибо все равно

Никак до конца не врублюсь в рекурсивные определения. Странно это.

Цитата: RawonaM от мая 22, 2011, 23:24
Никак до конца не врублюсь в рекурсивные определения. Странно это.

Что за зверь?

"Формула отката".

Вот простой пример: найти рекурсивную формулу вариантов расположения в линию эн метров из следующих досок: белые и желтые доски длиной два метра и зеленые длиной один метр?

Это я решаю легко: рекурсивная формула A_n=A_n-1+2A_n-2.

А вот это затрудняюсь:
Найти рекурсивную формулу для количества кусков образуемых эн окружностями на плоскости. Три окружности не пересекаются в одной точке.