You are here

2 Задачи по комбинаторике


matematik
Дата: Понедельник, 20.12.2010, 20:55 | Сообщение # 1

1)переплётчик должен переплести 14 различных книг в красный, коричневый и зелёный переплеты. Сколькими способами он может это сделать, если в каждый цвет должны быть переплетена хотя бы одна книга?

почти решил её, но есть один недочет, пока не могу понять как с этим разобраться
Решение:вообщем я сделал так, взял из 14 книг 3, ну потому что хотя бы одна книга должна быть покрашена в каждый цвет. потом уже работал с 11-ю книгами. и количество способов переплести их С(2 из 13)*11! - этот момент я понимаю. проблема в том что, книги различны, и среди тех трех книг что я вычел вначале могут оказаться и книги из тех 11 книг. что делать ??

2)По периметру блюдца на равных интервалах изображены розы - белые, красные и желтые, общим числом 7 цветков. Сколько существует различных (с точностью до поворота) таких блюдец ?

Сообщение отредактировал
matematik -
Понедельник, 20.12.2010, 20:56


Admin
Дата: Понедельник, 20.12.2010, 22:15 | Сообщение # 2

Похожий "джентльменский набор" задач тут... Вы там не за одной партой сидите?

1. Насчет 14 = 3 + 11 все логично. А вот насчет


с 11-ю книгами. и количество способов переплести их С(2 из 13)*11!

, - тут уже я ничего не понял. Будьте попроще - и не будет повода для сомнений. Есть такое число H311 - число сочетаний из 11 элементов по 3 с повторениями (если элементом считать количество книг одного цвета, от 0 до 11 для каждого). Кроме того, это число определяет количество целых неотрицательных решений уравнения x1 + x2 + x3=11, что проектируется на данную задачу еще проще.
Далее: переход от H к C выражается формулой
H311 = С311+3-1 = С313 = 286
А первые три книги играют именно ту роль, которую Вы им отвели вначале, и на эти сочетания никак не влияют.

Есть еще "взрослое" решение этой задачи, с использованием производящих функций, но это уже совсем другая и длинная история.


Admin
Дата: Вторник, 21.12.2010, 00:15 | Сообщение # 3

По поводу 2):
Все как-бы сложно, но в то же время просто, или наоборот, я уже сам запутался
Следите за мыслью:

Ситуацию


(с точностью до поворота)

мы решаем делением количества способов на 7 (так же, как и с круглым столом). То есть из одного "круглого" способа получаем 7 способов размещения "в ряд",
в зависимости от того с какого места начали.
И наоборот с 7-ми соответствующих размещений "в ряд" получится одно и то же размещение "круглое".

"Линейных" размещений по 7 элементов трех разных цветов получится 37 (размещения с повторение из 3 по 7). В таком случае различных блюдец получится 37/7. Все просто!

Но 37 не делится на 7! В чем проблема? В трех одноцветных блюдцах!
Они и в "линейном" и в "круглом" размещении дают ровно по ОДНОМУ способу (а не 7 к 1, как все остальные).
Значит считать нам нужно так:

Undefined
author: 
admin
Категория: