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

[bluesea]

Có bao nhiêu cách đi từ điểm (0;0) tới (n;n)(mỗi bước đi là sang phải 1 dv hoặc lên trên 1 dv) sao cho ta luôn ở trong hình vuông (0;0);(0;n);(n;0);(n;n)và luôn ở dưới đường chéo chính nối (0;0);(n;n)

DDTH

[bluesea]

BÀi này hay vậy mà không ai giải sao.Kết quả bài này là http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{C_{2n}^{n}}{n+1}

[dhkhtn-tnt]

Ồ đẹp nhỉ.Lại ra đúng số Catalan à??

[clmt]

Bài mạnh hơn là xác định số đường đi ngắn nhất từ O(0;0) đến (p;q) mà ko cắt đt y=x,với 0<p<q, là f(p,q).

[vnm]

Có thể phát biểu theo cách khác:tồn tại bao nhiêu dãy gồm n số 0 và n số 1 sao cho tại mọi thời điểm,số số 1 luôn lớn hơn hoặc bằng số số 0
Bài này có trên AMM,lời giải như sau:
gọi f(i) là hiệu số giữa số số 1 và số số 0 tại thời điểm i.Ta có f(1)=1;f(2n)=0.Trên mặt phẳng vẽ đồ thị y=f(x).Xét 2 điểm A(1;1) và B(2n;0)
Ta cần tính số đường đi từ A tới B sao cho không cắt đường thẳng y=-1
Số đường đi từ A->B là http://dientuvietnam...C_{2n-1}^{n}(do có n bước đi lên,n-1 bước đi xuống)
Mỗi đường đi từ A->B mà cắt y=-1,ta xác định điểm đầu tiên đồ thị tiếp xúc y=-1;sau đó lấy đối xứng phần đồ thị từ A tối điểm đó-ta được 1 đường đi từ C(1;-3) tới B.Từ đó thấy có http://dientuvietnam...?C_{2n-1}^{n 1} cách.Từ đó dễ có dpcm

Bài viết đã được chỉnh sửa nội dung bởi vnm: 05-03-2006 - 22:01

[dhkhtn-tnt]

Nhu minh da noi ở tren thuc ra day chinh la cach cm CT cua so Catalan = to hop.(Dễ thấy:http://dientuvietnam.net/cgi-bin/mimetex.cgi?p_{n+1}=p_0p_n+...+p_np_0 với http://dientuvietnam...mimetex.cgi?p(n) là số cần tìm)
Cac ban co the xem cach cm = chuỗi của thày Đàm Văn Nhỉ trên báo toán 5-2004
To ctlm:bài của bạn thì có thể có 1 điểm đến nằm trên đt y=x ko?

Bài viết đã được chỉnh sửa nội dung bởi dhkhtn-tnt: 08-03-2006 - 12:07

[thangde.]

bạn chưa chứng minh công thức truy hồi cho bài ban đầu của bluesea mà
Còn cách chứng minh bằng chuỗi thì ai chả biết

[dhkhtn-tnt]

Gọi http://dientuvietnam...imetex.cgi?(a,a) là vị trí đầu tiên sau vị trí (0,0)( nếu ko tồn tại thì tính là điểm (0,0)) mà đường đi đi qua,số đường đi đến http://dientuvietnam...imetex.cgi?(a,a) là http://dientuvietnam...mimetex.cgi?p(a)
Số cách đi đến http://dientuvietnam...imetex.cgi?(n,n) từ http://dientuvietnam...imetex.cgi?(a,a) là http://dientuvietnam...tex.cgi?p(n-1-a)=>

[clmt]

Thực ra với cách tiếp cận của mình có thể giải được cả tr.hợp p=q.
Ta có vì p<q nên bước thứ 2 phải ở điểm (0,1)=A,gọi B là điểm đx với A qua đt y=x,thì B(1,0).Chú ý là một đường đi từ A đến (p.q) mà ko cắt đt y=x tương ứng với một đường đi ngắn nhất từ B đến(p,q).Và do đó số đường đi thỏa mãn là
-(p-1)C(p+q-1) +pC(p+q-1)=(q-p)/(p+q). pC(p+q).
Khi p=q áp dụng tương tự ta có kd

[thangde.]

bạn nhầm rồi;số cách đi từ (n;n) tới (a;a) là p(n-a) mà
Cách của bạn sai ở chỗ:giả sử ta tính số đường đi có (a;a) là điểm chạm đầu tiên,khi đó số cách phải là p(n-a)p*(a)[p*(a) là số đường đi sao cho không cắt đường chéo]

Bài viết đã được chỉnh sửa nội dung bởi thangde.: 08-03-2006 - 19:33

[thangde.]

bài của clmt có thể phát biểu khác như sau:tìm số đường đi f(p+q;q-p) từ (0;0)->(p+q;q-p) có p+q bước(mỗi bước là đi từ 1 đỉnh tới đỉnh đối diện trong hình vuông đơn vị) sao cho luôn ở trên đường Ox.
ta dễ có công thức truy hồi f(k;m)=f(k-1;m+1)+f(k-1;q-1);f(2k+1;0)=0;f(2n;0)=C_{n}^{2n}/n+1(đã chứng minh ở trên)

Bài viết đã được chỉnh sửa nội dung bởi thangde.: 08-03-2006 - 20:25

[clmt]

Một bài tổng quát:Cho p,q,r là các số nguyen dương và q>pr.Gọi f(p,q,r) là số đường đi ngắn nhất gồm các diểm nguyên M(x,y) đi từ O(0,0) tới B(p,q) mà y>xr.Cm f(p,q,r)=http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{q-pr}{q+p}.pC(p+q)

[vnm]

Bài của clmt tổng quát quá mình không tin là nó đúng.Chang han so duong di tu (0;0) toi (n;qn) luon o duoi duong thang y=qx la http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{C_{(q+1)n}^{n}}{qn+1}.Bai nay co trong AMM

[clmt]

Công thức mình post lên là qua đủ,chỉ cần cm qui nạp là xong!Cái kq của bạn ta cũng cm bằng qui nạp thôi.Bạn sử dụng cái này http://dientuvietnam...metex.cgi?f(p,q)=f(p-1,q)+f(p,q-1)với qui ướchttp://dientuvietnam.net/cgi-bin/mimetex.cgi?f(p,pr)=0Sau đó cm qui nạp theo p+q.
Còn một vấn đề là tại sao có công thức này?

[vnm]

hmm...kết quả của bạn đâu có trùng với kq bài toán mà mình đưa ra
Bạn thử post lời giải rõ ràng xem

[clmt]

bạn nói gì vậy.hai bài toán khác nhau mà!

[tretho97]

có tài liệu nào nói kĩ hơn về ứng dụng tổ hợp của số catclan không ạ