ขอโจทย์ที่สามารถใช้วิธี combinatorial proof หน่อยคับ

[poohmathman]

ขอหน่อยนะคับบ ถ้าเป็นแบบที่ประยุกต์ใช้กับpartอื่นได้ยิ่งดีเลยคับ ขอแบบไม่ยากมากนะครับยังไม่ค่อยเก่ง

[nooonuii]

จงพิสูจน์ว่า $2^n \geq 2n$ ทุกจำนวนเต็มบวก $n$

[gon]

ง่ายที่สุดก็ $2^n = \binom{n}{0} + \binom{n}{1} + ...+ \binom{n}{n}$

หรือ $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

$r\binom{n}{r} = n\binom{n-1}{r-1} $

[poohmathman]

-ของคุณ nooonuii ผมยังคิดไม่ออกเลยครับ555 ช่วยเฉลยหน่อยนะครับ

-ของคุณ gon ง่ายไปนิดนึงคับ ขอยากกว่านี้หน่อยนะคับ

[nooonuii]

ข้อความเดิมเขียนโดยคุณ gon

ง่ายที่สุดก็ $2^n = \binom{n}{0} + \binom{n}{1} + ...+ \binom{n}{n}$

ใช้อันนี้แหละครับ

[poohmathman]

2กำลังn=nเลือก1 +nเลือกn-1 +.... =2n+... >=2n อะไรประมานนี้ป่าวคับ

[share]

In mathematics, the term combinatorial proof is often used to mean either of two types of mathematical proof:

* A proof by double counting.
A combinatorial identity is proven by counting the number of elements of some carefully chosen set in two different ways
to obtain the different expressions in the identity.
Since those expressions count the same objects, they must be equal to each other and thus the identity is established.

* A bijective proof.
Two sets are shown to have the same number of members by exhibiting a bijection, i.e. a one-to-one correspondence, between them.

The term "combinatorial proof" may also be used more broadly to refer to any kind of elementary proof in combinatorics.

However, as Glass (2003) writes in his review of Benjamin & Quinn (2003)
(a book about combinatorial proofs), these two simple techniques are enough to prove many theorems in combinatorics and number theory.

Wikipedia

[Pitchayut]

ของคุณ poohmathman ถูกต้องแล้วครับ

ลองทำข้อนี้ดูนะครับ ถ้าเคยทำแล้วขออภัยครับ

จงพิสูจน์ว่า $\displaystyle{\binom{m}{0}\binom{n}{r}+\binom{m}{1}\binom{n}{r-1}+\binom{m}{2}\binom{n}{r-2}+...+\binom{m}{r}\binom{n}{0}=\binom{m+n}{r}}$

[poohmathman]

สมมติมีชายnคน หญิงmคน เลือมาrคนโดยไม่สนเพศได้ m+nเลือกrวิธี

= วิธีเลือกชาย0หญิงrคน+เลือกชาย1คนหญิงr-1คน+...+เลือกชายrคนหญิง0คน=nเลือก0*mเลือกr+...
ใช่มั้ยครับ

[Pitchayut]

ถูกแล้วครับ อยากได้อีกก็บอกนะครับมีอีกเยอะ

[poohmathman]

อยากได้อีกคับๆๆๆ ผมชอบวิธีพิสูจน์แบบนี้มากๆเลยมันสวยดีคับ555

[Pitchayut]

อยากได้ก็จัดไปครับ อันนี้จะยากหน่อยนะครับ เป็นข้อสอบ สอวน ค่าย 1 ศูนย์สวนกุหลาบ

จงพิสูจน์ว่า $\displaystyle{\left[\sum_{i=0}^{k}\binom{m}{i}\binom{m-i}{k-i}\right]\binom{m-k}{r-k}=2^k\binom{r}{k}\binom{m}{r}}$

[poohmathman]

ข้อความเดิมเขียนโดยคุณ Pitchayut

อยากได้ก็จัดไปครับ อันนี้จะยากหน่อยนะครับ เป็นข้อสอบ สอวน ค่าย 1 ศูนย์สวนกุหลาบ

จงพิสูจน์ว่า $\displaystyle{\left[\sum_{i=0}^{k}\binom{m}{i}\binom{m-i}{k-i}\right]\binom{m-k}{r-k}=2^k\binom{r}{k}\binom{m}{r}}$

คิดออกละครับแต่เปนวิธีกระจายแต่ละพจน์ถึกๆหน่อยอะครับ พอจะมีวิธีที่ง่ายกว่านี้มั้ยครับช่วยอธิบายหน่อย

[กขฃคฅฆง]

แนวคิดคร่าวๆครับ

มีนักเรียนอยู่ m คน จะคัดเลือกนักเรียนมา r คนมาเข้าค่ายสอวน. และใน r คนนี้จะคัดเหลือ k คนไปแข่ง ซึ่งใน k คนนี้จะไปแข่งหรือไม่ไปก็ได้

[poohmathman]

ข้อความเดิมเขียนโดยคุณ กขฃคฅฆง

แนวคิดคร่าวๆครับ

มีนักเรียนอยู่ m คน จะคัดเลือกนักเรียนมา r คนมาเข้าค่ายสอวน. และใน r คนนี้จะคัดเหลือ k คนไปแข่ง ซึ่งใน k คนนี้จะไปแข่งหรือไม่ไปก็ได้

ขอเปลี่ยนเรื่องนิดนึงนะครับ

[1] มีนักเรียนค่าย1 m คน คัดเหลือrคนไปเข้าค่าย2 แล้วคัดจากrคนเหลือkคนไปเข้าค่าย3 แล้วจากkคนนั้นจะเลือกไปแข่งหรือไม่ไปก็ได้ทำได้ =mเลือกr * rเลือกk *2^k วิธี

[2]เราจะเลือกคนที่ไปแข่งก่อน
กรณีที่1 ถ้ามีคนเลือกไม่ไปแข่ง 1คน
เลือคนนั้นมาได้mเลือก1 ที่เหลือก้เลือกให้อีกk-1คนไปแข่งจากm-1คนที่เหลือได้m-1เลือกk-1 รวมกรณีแรกทำได้ mเลือก1*m-1เลือกk-1

กรณีที่2มีคนเลือกไม่ไปแข่ง2คน
:
รวมทำได้ ตัวซิกม้าของฝั่งซ้ายอะคับ
(ผมพิมซิกม่าม่ายเปนอะ 555)

ที่เหลือm-kคน คือคนที่ไม่ผ่านไปค่าย2และค่าย3 (คือคนที่ได้เข้าค่าย1หรือค่าย2)

เนื่องจากค่าย2มีrคน ค่าย3มีk คน ดังนั้นจากค่าย2ไปยังค่าย3มีคนไม่ได้ผ่านเข้าค่าย3ทั้งหมดr-kคน จากm-kคนทำได้
m-kเลือกr-k

ซึ่งในm-kคนทั้งหมดเลือกให้เป็นคนที่ไม่ได้เข้าค่าย3ทำได้ m-k เลือกr-kวิธี

ที่เหลือคือคนที่ไม่ได้เข้าค่าย2เหลืออยู่ ก้ต้องเลือกให้เป็นเข้าค่าย1จึงทำได้วิธีเดียว

รวมจึงเลือกได้ LHS อะคับ


ประมาณนี้รึเปล่าครับไม่ค่อยแน่ใจ