57 школа, 9 класс
    13 апреля 2002 г
Функции на конечных множествах

    Запись <а, b> обозначает упорядоченную пару объектов а и b. Упорядоченные пары <а, b> и <c, d> равны в том и только том случае, если а = c и b = d.  
    Пусть А и В -- произвольные множества. Декартовым произведением множеств А и В называется множество А х В = {<a, b>, где а принадлежит A, b принадлежит B}.

1.    Перечислите все элементы множества А х В, где
А = {Петя, Соня, Амир},  В = {Саша, Катя}.

    Множество F ю А ? В называется отображением (или функцией) из множества А в множество В, если для любого а из А существует ровно одно b из B, такое что <a, b> принадлежит F. Вместо <a, b> принадлежит F часто пишут b = F(a).

2.    а)    Пусть множество А состоит из четырех лампочек. Сколько существует отображений из А в двухэлементное множество {горит, не горит}.
    б)    Сколько существует  отображений из данного k-элементного множества в даное n-элементное множество?

    Отображение F называется вложением (или инъективным отображением), если  оно "ничего не склеивает", то есть F(x)=F(y) влечет x=y.

3.    Сколько существует инъективных отображений из данного k-элементного множества в данное n-элементное множество?

4.    Пусть множество А состоит из n элементов.
    а)    Сколько существует различных подмножеств множества А?
    б)    Сколько существует k-элементных подмножеств множества А?  
    в)    Найдите число подмножеств А, состоящих из четного числа элементов.

    Отображение F называется отображением на (или сюръективным отображением), если для любого b из B найдется а из А, такое что b = F(a).
        
    Отображение F называется взаимно однозначным (или биекцией), если оно инъективно и сюръективно.

5.    Сколько существует взаимно однозначных отображений из данного k-элементного множества в данное n-элементное множество?
     
6.    а)    Сколько существует сюръективных отображений из данного k-элементного множества в данное 7-элементное множество?
    б)    Можно ли утверждать, что это число делится на 7! при любом k?