Tổ hợp xếp hàng

[bluemoon]

cho n bạn nam và n bạn nữ xếp thành 1 hàng.thực hiện việc cắt hàng thành hai phần sao cho ở mỗi phần số bạn nam bằng số bạn nữ.gọi A là số cách xếp hàng sao cho chỉ có duy nhất một cách cắt hàng tm yêu cầu trên và B là số cách xếp hàng mà không thể cắt hàng theo yêu cầu trên.
cmr:A=2B.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[pte.alpha]

Bài này hay đấy chứ, 1 tuần rồi mà chưa ai đụng tới à?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[SideWinder]

Nguyên văn bởi bluemoon

cho n bạn nam và n bạn nữ xếp thành 1 hàng.thực hiện việc cắt hàng thành hai phần sao cho ở mỗi phần số bạn nam bằng số bạn nữ.gọi A là số cách xếp hàng sao cho chỉ có duy nhất một cách cắt hàng tm yêu cầu trên và B là số cách xếp hàng mà không thể cắt hàng theo yêu cầu trên.
cmr:A=2B

Xét một ánh xạ như sau:
Mỗi bạn nam cho ta hình ảnh một vector $a(1, 1) $, mỗi bạn nữ cho ta hình ảnh một vector $b(-1, 1) $.

Như thế mỗi cách xếp hàng cho ta hình ảnh một đường (path) nối $(0, 0) $ với $(0, 2n) $.
Gọi $P_n $ là tập hợp các đường nối $(0, 0) $ với $(0, 2n) $ bằng các vector $a, b $, nằm ở phần dương của $Oy $.
$Q_n $ là tập hợp các đường nối $(0, 0) $ với $(0, 2n) $ bằng các vector $a, b $; không cắt $Ox $
$R_n $ là tập hợp các đường nối $(0, 0) $ với $(0, 2n) $ bằng các vector $a, b $; cắt $Ox $ tại đúng một điểm.

Ta có bổ đề:

Bổ đề 1.
$|P_n|=\frac{1}{n+1}(\frac{2n}{n})=C_n $ (số Catalan)

Điều này nếu cần thì tôi sẽ chứng minh sau.

Xét mỗi đường thẳng $p_n\in Q_n $, ta chia $p_n $ thành các phần:
(1) vector $a $ nối $(0, 0) $ với $(1, 1) $;
(2) $p_{n-1} $ nối $(1, 1) $ với $(2n-1, 1) $;
(3) vector $b $ nối $(2n-1, 1) $ với $(0, 2n) $;
Ta thấy, $p_{n-1}\in P_{n-1} $
Do đó $|Q_n|=|P_{n-1}|=C_{n-1} $

Ta chia tập $R_n $ thành các tập $S_1, S_2,..., S_n $ với $S_i $ là tập hợp các đường cắt $Ox $ tại điểm $(0, 2i) $
Với mỗi $s_i\in S_i $, ta chia $s_i $ thành các phần:
(1) vector $a $nối $(0, 0) $ với $(1, 1) $;
(2) đường $s_{i-1} $ nối $(1, 1) $ vơí $(1, 2i-1) $;
(3) vector $b $ và vector $a $ nối $(1, 2i-1) $ với $(1, 2i+1) $;
(4) đường $s_{n-i-1} $ nối $(1, 2i+1) $ với $(1, 2n-1) $;
(5) vector $b $ nối $(1, 2n-1) $với $(0, 2n) $;
Ta thấy $s_{i-1}\in P_{i-1} $ và $s_{n-i-1}\in P_{n-i-1} $
Do đó:
$|R_n|=|S_1|+|S_2|+\cdots+|S_n| $
$=C_0C_{n-2}+C_1C_{n-3}+\cdots+C_{n-2}{C_0} $
$= C_{n-1} $

Mặt khác $|A|=|Q_n|, 2|B|=|R_n| $. Từ đây, ta có $|A|=2|B| $ d.p.c.m-đếch phải chứng minh

SP thắng to, có mấy giái nhất rồi!!

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[thanhtra_dhsp]

Bài này có trong phần bài tập ở một quyển sách tổ hợp của thầy Nam Dũng đúng không ạ. Hình như trong đó không có giải. Thầy namdung có thể post lời giải lên MS được không ạ, giải như SideWinder quá dài.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[caubedien]

Sách đấy là sách nào thế ạ , anh có thể giới thiệu cho em biết được không , em đang muốn luyện về tổ hợp mà chưa biết phải học ở đâu
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[n.v.thanh]

toán rời rạc và 1 số vấn đề liên quan.không có lời giải,có thể down load dc,chịu khó hỏi google nhé "cbdien"
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]