Xếp m số 0 và n số 1 thành vòng tròn
#1
Đã gửi 18-09-2018 - 20:48
#2
Đã gửi 20-05-2019 - 14:39
Có bao nhiêu cách xếp m số 0 và n số 1 thành 1 vòng tròn?
Ta xét bài toán tương đương : "Có bao nhiêu xâu chuỗi có $n+m$ hạt mà mỗi hạt được sơn 1 trong 2 màu $0$ hoặc $1$".
Từ 1 hạt bất kỳ trong xâu chuỗi, ta đánh số các hạt liên tiếp, theo 1 chiều nào đó, từ $1$ đến $n+m$$\rightarrow$ các hoán vị bất biến của nhóm:
$H_{0}=123....(n+m)$
$H_{1}=23....(n+m)1$
$H_{2}=3....(n+m)12$
$...........$
$H_{n+m-1}=(n+m)123....$
Ta thấy trong các hoán vị $H_{i}$ thì hạt tại vị trí $j$ có giá trị $i+j$ và trong vòng xích: $1$ thành $1+i$, $1+i$ thành $1+2i$ và vv...cho đến số có dạng $1+2(n+m)$. Ngoài ra, các vòng xích cùng kích thước và bằng $\frac{BCNN(i,(n+m))}{i}=\frac{n+m}{UCLN(i,(n+m))}$ do đó số vòng xích là $UCLN(i,(n+m))$.
Áp dụng định lý Polya, số cách sơn xâu chuỗi hay số cách xếp thỏa yc đề bài là:
$S= \boxed {\frac{1}{n+m}\sum_{i=1}^{n+m}2^{UCLN(i,(n+m))}}$
PS: Mới tập tọe lý thuyết Nhóm, có gì sai sót mong các bạn góp ý.
++++++++++++++++++++++++++++
Everything is impossible until you do it.
“Ai không làm gì thì mới không bao giờ sai”. Cứ làm đi, đừng sợ sai, trừ khi cái sai đó là cái sai gây tai hoạ cho người khác.
#3
Đã gửi 20-05-2019 - 21:03
Có bao nhiêu cách xếp m số 0 và n số 1 thành 1 vòng tròn?
Cần hiểu rằng $m$ và $n$ là những số tự nhiên cố định và đã biết trước.
------------------------------------------------------
NẾU $m$ chữ số $0$ và $n$ chữ số $1$ khác nhau từng đôi một (khác về màu sắc, kích cỡ chẳng hạn) thì số cách xếp là $(m+n-1)!$ cách
Còn nếu các chữ số $0$ giống nhau, các chữ số $1$ giống nhau thì số cách xếp là $\frac{(m+n-1)!}{m!n!}$ cách.
- dottoantap yêu thích
...
Ðêm nay tiễn đưa
Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...
#4
Đã gửi 21-05-2019 - 08:55
Cần hiểu rằng $m$ và $n$ là những số tự nhiên cố định và đã biết trước.
------------------------------------------------------
NẾU $m$ chữ số $0$ và $n$ chữ số $1$ khác nhau từng đôi một (khác về màu sắc, kích cỡ chẳng hạn) thì số cách xếp là $(m+n-1)!$ cách
Còn nếu các chữ số $0$ giống nhau, các chữ số $1$ giống nhau thì số cách xếp là $\frac{(m+n-1)!}{m!n!}$ cách.
Cám ơn anh đã góp ý. Em có ý kiến trao đổi:
1/ Trong đại đa số các đề bài toán đếm, Câu đầu tiên "Có bao nhiêu số có $n$ chữ số....." thì liệu có phải $n$ là số tự nhiên cố định và đã biết trước không?
2/ Nếu kết quả bài toán là như anh nói, thì có lẽ bạn trên kia đã post bài nhầm topic rồi!
++++++++++++++++++++++++++++
Everything is impossible until you do it.
“Ai không làm gì thì mới không bao giờ sai”. Cứ làm đi, đừng sợ sai, trừ khi cái sai đó là cái sai gây tai hoạ cho người khác.
#5
Đã gửi 21-05-2019 - 12:16
Cám ơn anh đã góp ý. Em có ý kiến trao đổi:
1/ Trong đại đa số các đề bài toán đếm, Câu đầu tiên "Có bao nhiêu số có $n$ chữ số....." thì liệu có phải $n$ là số tự nhiên cố định và đã biết trước không?
2/ Nếu kết quả bài toán là như anh nói, thì có lẽ bạn trên kia đã post bài nhầm topic rồi!
1) Đúng vậy, trong những đề bài như thế thì phải hiểu $n$ là số tự nhiên cố định và đã cho trước.
2) Vâng, lẽ ra phải post vào topic "Quy tắc đếm" (nếu không có thì chọn "Tổ hợp" cũng được)
...
Ðêm nay tiễn đưa
Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh