โจทย์เรื่องการนับ+สับเซต ช่วยหน่อยครับ

[HIGG BOZON]

A set is "good" if it does not contain any 2 consecutive integers.
How many subsets of set {1,2,3,...,10} are "good" .

[Aquila]

Generalize เลยละกัน ไอเดียคือเลี่ยงไปนับเซ็ตอื่นที่มีสมบัติเหมือนโจทย์ แล้ว prove 1-1 onto

ให้ $A=\left\{\,1,2,...,n\right\}$ และ $r$ เป็นจำนวนเต็มไม่ติดลบใหญ่ไม่เกิน $n-r+1$
การจัดหมู่ทีละ $r$ จาก $A$ โดยไม่มี consecutive ทำได้ $\binom{n-(r-1)}{r}$

ให้ $X$ เป็นเซตของการจัดหมู่ที่ละ $r$ ของ $A$ โดยไม่มี consecutive
ให้ $Z$ เป็นการจัดหมู่ทีละ $r$ จาก $Y=\left\{\,1,2,...,n-(r-1)\right\}$
จะได้ขนาดของ $Z$ เป็น $\binom{n-(r-1)}{r}$

สร้างให้ $S$ มีสมบัติเหมือนโจทย์ จะได้นับง่ายๆ
ให้ $S$ มีสมาชิกเป็น $s_{i}$ โดย $1 \leq i \leq r$ และ $S \in X$

สมมติไม่เสียนัย $s_{i} < s_{j}$ ทุก $i<j$
จาก $S \in X$ ได้ว่า $S$ contain no consecutive และ $s_{1},s_{2}-1,...,s_{r}-(r-1)$ ต่างกันหมด (ไอเดียหลัก)

ใช้อสมการสังเกตว่า $\left\{\,s_{1},s_{2}-1,s_{3}-2,...,s_{r}-(r-1)\right\}$ เป็นซับเซตของ $Y$

จากนั้นเลือกฟังก์ชัน $f:X \rightarrow Z$ โดย $f(S)=\left\{\,s_{1},s_{2}-1,s_{3}-2,...,s_{r}-(r-1)\right\}$
แล้วพิสูจน์ว่า $f$ เป็นฟังก์ชัน 1-1 onto ที่ส่ง $X$ ไป $Z$
จะได้ขนาดของ $X$ เท่ากับขนาดของ $Z$ เป็น $\binom{n-(r-1)}{r}$

จากนั้นก็แทน $n=10$ และ $r=2$ ลงไปก็จบแล้ว

edit นิดนึง ไม่ใช่แทน $r=2$ อย่างเดียว ต้องแทน $r$ ทุกค่าที่เป็นไปได้ลงไป จับบวกกันถึงจะตอบได้

[Thamma]

Bijection Principle

ให้ |A| = จำนวน k-element subsets ของ set {1, 2, 3, ..., 10} ที่ไม่มี 2 จำนวนเรียงต่อกัน , k = 0, 1, 2, 3, 4, 5

และ |B| = 10-digit binary sequences ที่มี 1 อยู่ k ตัว และไม่มี 1 สองตัวใดติดกัน ที่เหลือเป็น 0

ยกตัวอย่าง

กรณี 2-element subsets

_ 1 0 1 _

วาง 1 สองตัว แล้ววาง 0 หนึ่งตัว คั่นระหว่าง 1 สองตัว

ยังเหลือ 0 อีก 7 ตัว คิดเหมือนวางลูกบอล 7 ลูกลงในกล่อง 3 กล่อง โดยแต่ละกล่องจะวางมากกว่า 1 ลูกก็ได้ ไม่วางเลยก็ได้

จำนวนวิธี = $ \binom {r+n-1}{n-1} $

จำนวน 2 -element subsets = $ \binom {7+3-1}{3-1} = 36 $

|B|= $ \binom {11}{0} + \binom {10}{1} + \binom {9}{2} + \binom {8}{3} + \binom {7}{4 } + \binom {6}{5} $

= 1+10+36+56+35+6=144

|A| = |B| = 144