Có bao nhiêu dãy gồm $m$ kí tự được lập từ $n$ kí tự

Đề bài: Cho $n$ kí tự phân biệt. Hỏi có bao nhiêu dãy gồm $m$ kí tự được lập từ $n$ kí tự đã cho? Biết rằng 2 dãy được coi là giống nhau nếu là ảnh của phép đối xứng trục chính giữa.

Ví dụ: 2 dãy $abcdemn$ và $nmedcba$ được coi là giống nhau và chỉ đếm 1 lần.

Lời giải:

Ta định nghĩa một chuỗi được gọi là đối xứng nếu ảnh qua phép đối xứng trục giữa của nó là chính nó

Ta sẽ đếm số các chuỗi đối xứng và không đối xứng có $m$ kí tự được tạo bởi $n$ kí tự

Việc đếm số các chuỗi đối xứng ta chỉ quan tâm đến $\left [ \frac{m+1}{2} \right ]$ vị trí đầu nên số các số đó là: $n^{\left [ \frac{m+1}{2} \right ]}$

Số các chuỗi không đối xứng: $n^m-n^{\left [ \frac{m+1}{2} \right ]}$

Các số không đối xứng có ảnh qua phép đối xứng trục giữa là một số không đối xứng nên ta có số các dãy được tạo bởi $n$ kí tự là:

$\frac{n^m-n^{\left [ \frac{m+1}{2} \right ]}}{2}+n^{\left [ \frac{m+1}{2} \right ]}=\frac{n^m+n^{\left [ \frac{m+1}{2} \right ]}}{2}$