Дискр Стр-ри, зимен семестър 2021/2022, КН2

1 ЗАД.

Това е последната задача, която решихме в час на сем.6 (в пдф файла от семинара на последната и предпоследната страница). Там са 1сл и 2сл, което са съответно решенията на 1-ви и 2-ри вариант.

2 ЗАД

вар1: 

Всяка дума може да я третираме като естествено число. Вместо 'a' пишем '0', вместно 'b' пишем '1', вместо 'c' пишем 2 ... вместо 'j' пишем 9.
Т.е имаме биекция между крайните редици от такива думи и крайните редици от естествени числа.

В час (sem. 7) доказахме, че всички крайни редици от ествени числа са изброимо множество.
От където следва, че и даденото множество също е изброимо.

вар2:
Можем да "изрежем " буквата 'x' в началото на всички думи от множеството.
Така получаваме дума съставена от 'x' и 'y' без ограничение.

Има очевидна биекция между думите от започващи с 'x' и булевите вектори:

( изрязваме първото 'x' и в останалата част: 'x' го заместваме с '1' и 'y' го заместваме с '0').
xyxyx -> 0101
xyyx -> 001

В час (sem. 7) доказахме, че множеството от булевите вектори е изброимо.
От където следва, че даденото множество е изброимо.

3 ЗАД.
Твърденията трябва да се опровергаят. Задачите (на двата варианта) са решени в час (сем 6).

Бонус задача:

Нека с S_123 бележим множество на пермутациите, в което 1 се среща преди 2 и 2 се среща преди 3 (търсеното множество).

От принципа на биекцията, който изучихме (sem. 8) се вижда, че

|S_123| = |S_132| = |S_213| = |S_231| = |S_312| = |S-321|
Т.е отговорът е n! / 6.