Đếm số hoán vị "tốt" của 1 dãy Cho dãy số $A=a_{1}, a_{2},..,a_{n} $ gồm n phần tử phân biệt. Một hoán vị B của A được gọi là k-tốt, nếu vị trí của mỗi phần tử trong B không cách xa hơn k vị trí trong A. Với k và n cho trước, hãy tìm số hoán vị tốt của A. Ví dụ A=1 3 5 7 8 , ở đây n=5. Giả sử k=3, thì B1= 3 5 1 8 7 là 1 hoán vị 3-tốt của dãy A. B2=8 1 3 5 7 không phải là 1 hoán vị 3-tốt, vì phần tử 8 đứng vị trí đầu tiên trong B2, cách xa 4 vị trí so với vị trí cuối cùng (thứ 5) của nó trong dãy A và 5-1>3 B3=1 5 7 8 3 cũng là 1 hoán vị 3-tốt, vì vị trí mỗi phần tử trong B3 cách vị trí ban đầu trong A không quá 3 đơn vị. [RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] thay đổi nội dung bởi: cuongk14, 12-10-2013 lúc 04:52 AM |