Câu hỏi 38
Cho số nguyên dương $n$, đặt $[n]=\{1,2, \ldots, n\}$.
- Gọi $a_{n}$ là số hàm $f:[n] \rightarrow [n]$ sao cho $f(f(i)) \geq i$ với mọi $i$.
- Gọi $b_{n}$ là số phân hoạch có thứ tự của $[n]$, tức là số cách chọn một số nguyên $k$ và một bộ $k$ có thứ tự $(A_{1}, \ldots, A_{k})$ gồm các tập hợp khác rỗng, đôi một rời nhau, có hợp bằng $[n]$.
Chứng minh rằng $a_{n}=b_{n}$.
- Gọi $a_{n}$ là số hàm $f:[n] \rightarrow [n]$ sao cho $f(f(i)) \geq i$ với mọi $i$.
- Gọi $b_{n}$ là số phân hoạch có thứ tự của $[n]$, tức là số cách chọn một số nguyên $k$ và một bộ $k$ có thứ tự $(A_{1}, \ldots, A_{k})$ gồm các tập hợp khác rỗng, đôi một rời nhau, có hợp bằng $[n]$.
Chứng minh rằng $a_{n}=b_{n}$.