Question

集合包含n个元素,有多少种关系？多少种函数？

Answer 1

设集合为A，A上关系的全集为笛卡尔积A*A，共有n^2个元素。而全集的每一个子集都是A上的一种关系，（n个元素的集合有n^2个子集）所以共有2^（n^2）种关系。
而在函数上则有前域X和值域Y，可以先给前域分配i个元素，共有n种分配方式。对于每种分配方式有Cn，i*（n-1）^i种函数，总数为Cn，1*（n-1）^1+Cn，2*（n-1）^2+…+Cn，n-1*1^（n-1）+Cn，n*（n-1）^0=（1+（n-1））^n=n^n