Три задачки по комбинаторике

Politaev

Помогите решить, пожалуйста!
1. сидят за круглым столом 12 челов. Сколько комбинаций рассадки их, если:
а) не важно, кто соседи;
б) важно, когда один сосед справо и слева;
в) важно, кто соседи, но не важно, справа ли или слева;
г) важно, когда друг напротив друга.
2. есть 6 различных ящиков, 4 одинаковых белых шарика и 3 одинаковых черных шарика. Сколько вариантов разложить шарики по ящикам, чтобы не осталось ни одного свободного ящика?
3. Есть алфавит из 10 символов. Сколько слов не более чем из 4 символов (от 1 до 4) можно составить из такого алфавита, если запрещено использовать 3 буквы подряд.

natali22061979

Ну, рискну высказать свое скромное предположение, что во второй задаче вариантов 25*6 = 150, а в третьей 9800.
1. Шариков у нас 7, а чумаданов 6. Стало быть, в одном из них неизбежно будет два шарика. Есть три варианта, что там окажется:
а) Два Белых шарика.
б) Два Черных шарика.
г) Один Черный и один Белый шарик (вариант Белый-Черный идентичен)
Ну и считаем, каким количество способов можно разместить по оставшимся ящикам оставшиеся шарики.
а) Число комбинаций 3 Черных шарика по 5-ти ящикам. 5! / (5-3)! * 3! = 10.
б) Число комбинаций 1 Черный шарик по 5-ти ящиком. Очевидно 5.
в) Число комбинаций 2 Черных шарика по 5-ти ящикам. 5! / (5-2)! * 2! = 10.
Складываем 10+10+5 = 25 - стольким числом способов можно рассовать шарики по пяти оставшимся ящикам, чтобы в шестом было 2 шарика.
Всего у нас таких ящиков 6. Стало быть, 6*25 = 150.
Вот, по-моему так. Может что наглючил. Я вообще неважно в этом разбираюсь.

natali22061979

А во третьей решил вот как:
Стало быть, всего слов из 4-х символов можно составить 10 в четвертой степени. То есть 10 000. Теперь из этого числа надо выкинуть все варианты, когда подряд идут три одинаковых символа. Например, аааб или гввв, такие нас не удовлетворяют по условию задачи. Так как алфавит 10-ти символьный, то для наглядности будем считать, что символы - это цифры.
Рассмотрим слово, начинающееся на цифру 0, такое что дальше после него подряд идут одинаковые символы. Можно даже выписать все варианты:
0000
0111
0222
0333
0444
0555
0666
0777
0888
0999
Мне кажется, что таких вариантов должно быть 10. Эти же рассуждения будут верны и для любого другого из 9-ти оставшихся символов. То есть на первое место ставим 1, 2, 3, ...и т.д.
Стало быть 10*10 = 100. Но те же рассуждения можно провести и для случая, когда у нас меняется последняя, а не первая цифра - 0000, 0001, 0002, ..., которые тоже удовлетворяют условию по которому мы должны выбросить лишние слова. Значит, умножаем 100 *2 = 200. Итак, по-моему 4-х буквенных слов в 10-ти символьном алфавите, у которых есть подряд более трех одинаковых чисел будет 200 штук. Вычтем его из общего числа слов и получим искомое значение.
10 000 - 200 = 9800.
Вот. Если ошибка, ткните где. Тока не говорите, что в ДНК :)
— UPDATE
Правильный ответ см. ниже :)

undertaker

по поводу третьей
1) мне кажется, что при подсчете 4х символьных слов с тремя одинаковыми буквами подряд ты посчитал слова из четырех одинкавых букв (0000, 1111, 2222, и т.п.) дважды. Таким образом, вместо 200 имеем 190 слов, или вместо 9800 имеем 9810.
2) еще забыл приплюсовать одно-, дву- и трехбуквенные слова (посмотри внимательно условие задачи). Но это легко считается:
10 (однобукв.) + 100 (двубукв.) + (1000-10) (трехбукв.) = 1100
И окончательный ответ: 9810+1100=10910
Поправьте, пжлст., если что не так
Кстати, можно для особо тугомыслящих объяснить подробнее, что значит "важно бла-бла-бла" в N1 б) в)?

gr_nik

Я в первой не понимаю, что значит, "важно когда".
Если рассадка "повернута" то это то же самое или нет?

gr_nik

Если поворачивать стол нельзя, то думаю, что в первой ответы
а) 12!
б) 1 или ни одного
в) 2 или ни одного
г) 6!*(2^6) Вначале сажаем 6 пар по порядку - это 6!, а затем в каждой выбираем, кто в данном конце сидит - это 2^6.
Поправьте, если не так или условие не понял.

natali22061979

С первым согласен. Спасибо. Да, действительно считается два раза.
Со вторым не согласен. Всего из 4-х символов можно набрать 10 000 слов (10 * 10 * 10 * 10). Нам нужно выбросить из этого массива слова, которые не удовлетворяют некоему условию. Стало быть, у нас всегда будет получаться число меньшее, чем общее количество слов. У тебя же получилось 10910 > 10000. Так быть не может :)
Если мы выбросим все слова, которые удовлетворяют условию - больше трех одинаковых символов подряд, то оставшиеся автоматически будут удовлетворять условию задачи. Это будут слова из 4-х букв, в которых не встречается подряд более 3-х или 4-х одинаковых символов. Так, что ответ 9810.

natali22061979

Да, у первой задачи нет более развернутого описания? А то я никак не могу въехать в условие.

natali22061979

Прокомментируй, пожалуйста, как ты понимаешь "имеет значение справа или слева". Я что-то не втыкаю.

gr_nik

Там не 10000, а 10000+1000+100+10=11110.
Рассматриваются 1,2,3 и 4-буквенные слова.

a101



Всего из 4-х символов можно набрать 10 000 слов (10 * 10 * 10 * 10).
Да, но еще есть трехбуквенные слова итд. итого слов есть 11110.

У меня ответ получается 10910

natali22061979

Блин, точно. Согласен.

Politaev

Спасибо вам всем, ребят! Преогромное!
Оставить комментарий
Имя или ник:
Комментарий: