Chủ đề này có 7 trả lời

[Baoriven]

Xét $A=\{1,2,3,4,5,6,7\}$ và các hàm song ánh $f:A\rightarrow A$. Có bao nhiêu hàm $f$ thoả mãn $f(f(f(n)))=n$ với mọi $n\in A$?

[chanhquocnghiem]

Xét $A=\{1,2,3,4,5,6,7\}$ và các hàm song ánh $f:A\rightarrow A$. Có bao nhiêu hàm $f$ thoả mãn $f(f(f(n)))=n$ với mọi $n\in A$?

Xét $3$ trường hợp :

a) Có đúng $1$ phần tử thuộc $A$ mà ảnh của nó qua song ánh $f$ cũng là chính nó :

    + Chọn phần tử mà ảnh của nó qua $f$ cũng là chính nó : $7$ cách (ví dụ chọn $1$, tức là ta có $f(1)=1$)

    + Chia $6$ phần tử còn lại thành $2$ nhóm, mỗi nhóm $3$ phần tử : $\frac{C_6^3}{2}=10$ cách

       (ví dụ chia thành nhóm $(2,3,4)$ và nhóm $(5,6,7)$)

    + Trong mỗi nhóm, xác lập hàm số $f$ thỏa mãn điều kiện đề bài : $2$ cách.

       Ví dụ xét nhóm $(2,3,4)$ có $2$ hàm $f$ thỏa mãn đề bài :

       $f_1(n)=\left\{\begin{matrix}3\ neu\ n=2\\4\ neu\ n=3\\2\ neu\ n=4 \end{matrix}\right.$ và $f_2(n)=\left\{\begin{matrix}4\ neu\ n=2\\2\ neu\ n=3\\3\ neu\ n=4 \end{matrix}\right.$

 

b) Có đúng $4$ phần tử thuộc $A$ mà ảnh của mỗi phần tử qua song ánh $f$ cũng là chính nó :

    + Chọn $4$ phần tử mà ảnh của mỗi phần tử qua $f$ cũng là chính nó : $C_7^4$ cách

       Ví dụ chọn $1,2,3,4$, tức là ta có $f(1)=1$ ; $f(2)=2$ ; $f(3)=3$ ; $f(4)=4$

    + Trong nhóm gồm $3$ phần tử còn lại, xác lập hàm số $f$ thỏa mãn điều kiện đề bài : $2$ cách.

       Ví dụ xét nhóm $(5,6,7)$ có $2$ hàm $f$ thỏa mãn đề bài :

       $f_1(n)=\left\{\begin{matrix}6\ neu\ n=5\\7\ neu\ n=6\\5\ neu\ n=7 \end{matrix}\right.$ và $f_2(n)=\left\{\begin{matrix}7\ neu\ n=5\\5\ neu\ n=6\\6\ neu\ n=7 \end{matrix}\right.$

 

c) Ảnh của mỗi phần tử thuộc $A$ qua song ánh $f$ đều là chính nó : Có $1$ hàm $f$ thỏa mãn.

 

Tổng số hàm $f$ thỏa mãn điều kiện đề bài là $7.10.2^2+2C_7^4+1=351$.

      
 

[perfectstrong]

Em diễn giải theo cách khác anh Nghiêm tí nhưng kết quả có lẽ cũng giống

Giờ chúng ta xét bài toán trong dạng tổng quát: Cho tập $A$ có $n$ phần tử. Đặt $f_{m+1} = f(f_m(x))\, \forall m \ge 1$. Có bao nhiêu song ánh $f: A \rightarrow A$ sao cho $f_3 \equiv Id$ ?

Diễn dịch bài toán thành dạng graph như sau: Cho $n$ điểm trên mặt phẳng. Có bao nhiêu cách vẽ các tam giác không chung đỉnh, biết rằng không nhất thiết phải nối hết mọi đỉnh?

Sự liên quan của bài toán nằm chỗ, với mỗi cách vẽ trên, chúng ta lập ra hàm $f$ bằng cách: nếu đỉnh $x$ đứng lẻ thì $f(x)=x$, còn nếu $x,y,z$ tạo thành tam giác thì $f(x)=y; f(y)=z; f(z)=x$ hoặc $f(x)=z; f(y)=x; f(z)=y$.

Như vậy, nếu trong một cách vẽ có $k$ tam giác thì số song ánh chúng ta sẽ có là

\[2\left( {\begin{array}{*{20}{c}}
n\\
3
\end{array}} \right)2\left( {\begin{array}{*{20}{c}}
{n - 3}\\
3
\end{array}} \right) \ldots 2\left( {\begin{array}{*{20}{c}}
{n - 3k}\\
3
\end{array}} \right) = {2^k}\prod\limits_{i = 0}^{k - 1} {\left( {\begin{array}{*{20}{c}}
{n - 3i}\\
3
\end{array}} \right)} \]

Do đó, số tam giác tất cả sẽ là

\[ S(n;3) = \sum\limits_{j = 0}^{\left\lfloor {\dfrac{n}{3}} \right\rfloor } {{2^k}\prod\limits_{i = 0}^{j - 1} {\left( {\begin{array}{*{20}{c}}
{n - 3i}\\
3
\end{array}} \right)} } \]

Trong đó $S(n;k)$ là số song ánh $f: \{1;\cdots;n\} \rightarrow \{1;\cdots;n\}$ sao cho $f_k \equiv Id$.

Đáng tiếc là em chưa tìm ra dạng thu gọn của cái này Nhưng bài toán này nếu tiếp tục mở rộng lên $k$ lớp lồng $(k \ne 3)$ thì cách diễn đạt này vẫn sẽ hữu ích ở chỗ là có thể thay khái niệm tam giác bằng đồ thị liên thông có hướng có $k$ đỉnh.

Dễ thấy $k=1$ thì $S(n;1)=1 \forall n$. Còn nếu $k=2$ thì tam giác sẽ là số đoạn thẳng. Còn $k \ge 4$ thì câu chuyện bắt đầu phức tạp rồi Gọi $P(k)$ là số lượng đồ thị liên thông có hướng với $k$ đỉnh, thì

\[S\left( {n;k} \right) = \sum\limits_{j = 0}^{\left\lfloor {\dfrac{n}{k}} \right\rfloor } {P{{\left( k \right)}^j}\prod\limits_{i = 0}^{j - 1} {\left( {\begin{array}{*{20}{c}}
{n - ik}\\
k
\end{array}} \right)} } \]

 

TB: Thứ tự chọn tam giác không quan trọng, vì thế trong kết quả phải chia cho $k!$. Do đó số cách vẽ $k$ tam giác sẽ là \[\frac{{{2^k}}}{{k!}}\prod\limits_{i = 0}^{k - 1} {\left( {\begin{array}{*{20}{c}}
{n - 3i}\\
3
\end{array}} \right)} \]

Nên kết quả cuối cùng (sau khi thu gọn một tí)

\[S\left( {n;3} \right) = \sum\limits_{j = 0}^{\left\lfloor {\frac{n}{3}} \right\rfloor } {\frac{{{2^j}}}{{j!}}\prod\limits_{i = 0}^{j - 1} {\left( {\begin{array}{*{20}{c}}
{n - 3i}\\
3
\end{array}} \right)} }  = \sum\limits_{j = 0}^{\left\lfloor {\frac{n}{3}} \right\rfloor } {\frac{{n!}}{{{3^j}j!\left( {n - 3j} \right)!}}} \]

[Baoriven]

Gọi $T_n$ là số hàm số song ánh $f:A\rightarrow A$ với $A=\{1,2,\cdots n\}$ thoả mãn $f(f(f(n)))=n,\forall n\in A$.

Khi đó, ta có công thức đệ quy sau: $T_n = (n-1)(n-2)T_{n-3}+T_{n-1},$ với $T_1=1,T_2=1,T_3=3$.

[perfectstrong]

Mò mẫm một tí thì chúng ta có thể thu gọn một chút biểu thức

\[\begin{align*}
P{\left( k \right)^j}\prod\limits_{i = 0}^{j - 1} {\left( {\begin{array}{*{20}{c}}
{n - ik}\\
k
\end{array}} \right)}  & = P{\left( k \right)^j}\prod\limits_{i = 0}^{j - 1} {\frac{{\left( {n - ik} \right)\left( {n - ik - 1} \right) \ldots \left( {n - ik - k + 1} \right)}}{{k!}}} \\
& = P{\left( k \right)^j}\frac{{\prod\limits_{l = 0}^{jk - 1} {\left( {n - l} \right)} }}{{k{!^j}}}\\
& = {\left( {\frac{{P\left( k \right)}}{{k!}}} \right)^j}\frac{{n!}}{{\left( {n - jk} \right)!}}
\end{align*}\]

Áp dụng với $k=3$ thì $P(k)=2$, và $S(n;k)$ trở thành:

\[S\left( {n;3} \right) = \sum\limits_{j = 0}^{\left\lfloor {\frac{n}{3}} \right\rfloor } {{3^{ - j}}\frac{{n!}}{{\left( {n - 3j} \right)!}}} \]

Chỗ này dùng hàm sinh thì biết đâu có thể tìm được closed form nhỉ

[perfectstrong]

Hôm qua suy nghĩ cùng đám bạn thì mình nhận ra hai điều:

Một là thứ tự chọn $j$ nhóm con không quan trọng, vì thế trong kết quả phải chia cho $j!$. Do đó kết quả sẽ là

\[{\left( {\frac{{P\left( k \right)}}{{k!}}} \right)^j}\frac{{n!}}{{j!\left( {n - jk} \right)!}}\]

Hai là mỗi nhóm con có lẽ không nhất thiết phải là một đồ thị liên thông.

Với $k$ nguyên tố thì mỗi nhóm con chắc chắn sẽ là một chu trình có hướng (chứng minh không khó, mời mọi người thử sức , nên $P(k)=(k-1)!$ (không quan trọng bắt đầu từ đỉnh nào).

Tuy nhiên nếu $k$ là hợp số thì câu chuyện sẽ phức tạp hơn hẳn Nói chung là để thỏa mãn yêu cầu hợp $k$ lần sẽ thành cố định, chúng ta phải chia các đỉnh trong nhóm con thành các cụm liên thông có hướng nhỏ hơn sao cho số đỉnh trong mỗi cụm là ước số của $k$.

Ví dụ $k=4$ thì chúng ta có thể vẽ thành 1 tứ giác, hoặc 2 đoạn thẳng, hoặc 1 đoạn thẳng + 2 đỉnh rời rạc. Vấn đề ở chỗ những đỉnh rời rạc này. Chúng ta sẽ bị đếm trùng khi thay đổi thành phần nhóm con ban đầu.

Chẳng hạn $\{1;2;3;4;5\} \rightarrow$ một nhóm con $\{1;2;\{3;4\}\}$ và một đỉnh rời rạc $5$. Giờ thay nhóm con sang $\{5;2;\{3;4\}\}$ và đỉnh rời rạc $1$, thì chúng ta sẽ có 2 song ánh $f$ giống nhau.

Vậy thì nên đếm thế nào?

[chanhquocnghiem]

Hôm qua suy nghĩ cùng đám bạn thì mình nhận ra hai điều:

Một là thứ tự chọn $j$ nhóm con không quan trọng, vì thế trong kết quả phải chia cho $j!$. Do đó kết quả sẽ là

\[{\left( {\frac{{P\left( k \right)}}{{k!}}} \right)^j}\frac{{n!}}{{j!\left( {n - jk} \right)!}}\]

Hai là mỗi nhóm con có lẽ không nhất thiết phải là một đồ thị liên thông.

Với $k$ nguyên tố thì mỗi nhóm con chắc chắn sẽ là một chu trình có hướng (chứng minh không khó, mời mọi người thử sức , nên $P(k)=(k-1)!$ (không quan trọng bắt đầu từ đỉnh nào).

Tuy nhiên nếu $k$ là hợp số thì câu chuyện sẽ phức tạp hơn hẳn Nói chung là để thỏa mãn yêu cầu hợp $k$ lần sẽ thành cố định, chúng ta phải chia các đỉnh trong nhóm con thành các cụm liên thông có hướng nhỏ hơn sao cho số đỉnh trong mỗi cụm là ước số của $k$.

Ví dụ $k=4$ thì chúng ta có thể vẽ thành 1 tứ giác, hoặc 2 đoạn thẳng, hoặc 1 đoạn thẳng + 2 đỉnh rời rạc. Vấn đề ở chỗ những đỉnh rời rạc này. Chúng ta sẽ bị đếm trùng khi thay đổi thành phần nhóm con ban đầu.

Chẳng hạn $\{1;2;3;4;5\} \rightarrow$ một nhóm con $\{1;2;\{3;4\}\}$ và một đỉnh rời rạc $5$. Giờ thay nhóm con sang $\{5;2;\{3;4\}\}$ và đỉnh rời rạc $1$, thì chúng ta sẽ có 2 song ánh $f$ giống nhau.

Vậy thì nên đếm thế nào?

Thử giải với $k=4$ để tìm công thức của $S(m;4)$

Xét bài toán : Cho $A=\left \{ 1,2,3,...,m \right \}$. Có bao nhiêu hàm song ánh $f:A\rightarrow A$ sao cho $f(f(f(f(n))))=n$, với mọi $n\in A$ ?

Để cho cụ thể, ta giải bài toán với một giá trị nào đó của $m$, chẳng hạn $m=15$.

Ta chia $15$ phần tử thành các nhóm nhỏ (tạm gọi là $A_i$) có $1$ hoặc $2$, hoặc $4$ phần tử.

Trong mỗi nhóm nhỏ $A_i$, ta xác lập số song ánh $f:A_i\rightarrow A_i$ sao cho $f(f(f(f(n))))=n$, với mọi $n\in A_i$

Nếu nhóm có $1$ phần tử, số song ánh thỏa mãn điều kiện trên là $1$ (đó là hàm $f(n)=n$)

Nếu nhóm có $2$ phần tử, số song ánh thỏa mãn điều kiện trên là $1$, đó là hàm thỏa mãn $f(a)=b$ và $f(b)=a$ (không tính hàm $f(n)=n$, vì nếu tính sẽ bị đếm trùng)

Nếu nhóm có $4$ phần tử, số song ánh như thế sẽ là $3!=6$ (không tính $2$ loại trên, để tránh đếm trùng)

Số song ánh thỏa mãn điều kiện đề bài (với $m=15$) là :

$S(15;4)=\frac{C_{15}^4C_{11}^4C_7^4}{3!}\left ( C_3^2+C_3^0 \right ).6^3+\frac{C_{15}^4C_{11}^4}{2!}\left ( \frac{C_7^2C_5^2C_3^2}{3!}+\frac{C_7^2C_5^2}{2!}+\frac{C_7^2}{1!}+\frac{C_7^0}{0!} \right ).6^2+\frac{C_{15}^4}{1!}\left ( \frac{C_{11}^2C_9^2C_7^2C_5^2C_3^2}{5!}+\frac{C_{11}^2C_9^2C_7^2C_5^2}{4!}+...+\frac{C_{11}^2C_9^2}{2!}+\frac{C_{11}^2}{1!}+\frac{C_{11}^0}{0!} \right ).6^1+\left ( \frac{C_{15}^2C_{13}^2...C_3^2}{7!}+\frac{C_{15}^2C_{13}^2...C_5^2}{6!}+...+\frac{C_{15}^2}{1!}+\frac{C_{15}^0}{0!} \right ).6^0$

Vậy công thức tổng quát của $S(m;4)$ là :

$S(m;4)=\sum_{i=0}^{\left \lfloor \frac{m}{4} \right \rfloor}\left [ \frac{\prod_{j=0}^{i-1}C_{m-4j}^4}{i!}\left ( \sum_{l=0}^{\left \lfloor \frac{m-4i}{2} \right \rfloor} \frac{\prod_{p=0}^{l-1}C_{m-4i-2p}^2}{l!} \right).6^i\right]$

 

[perfectstrong]

Nếu loại bỏ yếu tố thứ tự thì chúng ta có một bài toán tương tự: có bao nhiêu cách phân tích $n$ thành tổng các ước số của $k$ cho trước?