Броим с повторение

Пермутации с повторение: еднакви плочки

Плочките на думата АНАНАС са шест, но три са А, две са Н и една е С. Ако ги броим като различни, подрежданията са 6! = 720. Но размяната на две еднакви плочки не дава нова дума.

Всяка истинска дума се получава точно 3! · 2! · 1! = 12 пъти, затова ги делим:

P(3, 2, 1) = 6! / (3! · 2! · 1!) = 720 / 12 = 60

Ако плочките са n, а еднаквите са групи по n₁, n₂, …, броят на различните подреждания е n! върху произведението на факториелите на групите.

Включи „Номерирай еднаквите“ в симулацията и виж 720-те номерирани подреждания, групирани по 12.

Изненада: еднаквите плочки правят подрежданията по-малко. КРАСИВ има 720, а АНАНАС — само 60.

Вариации с повторение: кодове

Код с k места, на всяко от които има n възможни символа и символите може да се повтарят. Всяко място е свободен избор, независим от другите:

V̄ₙᵏ = n · n · … · n = nᵏ

Четирицифреният код има 10 · 10 · 10 · 10 = 10 000 възможности. Още едно място умножава броя по n, не го увеличава с n.

Без повторение изборите намаляват: 4 символа на 2 места са 4 · 3 = 12, а с повторение — 16.

Комбинации с повторение: чаша сладолед

Избираш k топки от n вкуса. Вкусът може да се повтаря, а редът в чашата няма значение: ванилия и ягода е същата чаша като ягода и ванилия. При 3 вкуса и 2 топки чашите са 6: ВВ, ШШ, ЯЯ, ВШ, ВЯ, ШЯ.

C̄ₙᵏ = (n + k − 1)! / (k! · (n − 1)!)

Във фунийка топките са една върху друга и редът има значение. Тогава броят е nᵏ — при 3 вкуса и 2 топки са 9, а не 6.

Топките може да са повече от вкусовете. 3 вкуса и 4 топки дават 15 чаши, макар без повторение да няма нито една.

Защо така: звезди и черти

Нареди топките на чашата по вкус. Топките са звезди, а между вкусовете слагаш черта. Вкусовете са n, а чертите са между тях — n − 1. Чаша с две ванилии и една ягода при 3 вкуса е:

★★ ǀ ǀ ★

Празното място между двете черти е шоколадът, който не е избран. Всяка чаша е точно една редица от k звезди и n − 1 черти и обратно. Редиците са толкова, колкото са начините да избереш кои k места от n + k − 1 са звезди.

Капанът на Знайко

„Комбинациите с повторение са nᵏ върху k!“. При 3 вкуса и 2 топки това е 9 : 2 = 4,5 — половин чаша няма.

Делението на k! е вярно само когато всички топки са различни. Чашата „ванилия, ванилия“ отговаря на един код, а не на два. Затова истинският брой е 6.

Защо компютърът брои по формула

Ако записваш по един случай на 2 секунди, подрежданията на МАТЕМАТИКА (151 200) ще ти отнемат около 3,5 денонощия. Шестцифреният код има 1 000 000 възможности — над 23 денонощия. Ръчното изброяване е безнадеждно, формулата е единственият път.

Как познаваш модела

Питай се две неща:

• Подреждам ли предмети, от които някои са еднакви? Това са пермутации с повторение.
• Редът има ли значение? Ако има — това е код. Ако няма — това е чаша.

Не въвеждай в симулацията истински код. Кодовете в нея не се запазват.