1.How many triangles are determined by the vertices of a regular polygon of n sides?How many if no side of the polygon is to be a side of any triangle?
A:C(n,3)-n(use two sides of the n-gon)-n(n-4)(use only one side)
2.In how many ways can we select five coins from a collection of 10 consisting of five distinct coins, and five identical coins?
A:2^5
3.Frannie tosses a coin 12 times and gets five heads and seven tails. In how many ways can these tosses result in (a) two runs of heads and one run of tails (b) three runs
A:
(a)X1+X2+X3 = 12, X1,X3>0, X2=7, X1+X3=5 ,C(4,3) = 4
(b)W1+W2+W3 = 12, W1,W3>0, W2=5, C(6,5) = 6
4.For n>=4, consider the strings made up of n bits-that is, a total of n 0's and 1's. In particular, consider those strings where there are two occurrences of 01. For example, if n=6 we want to include strings such as 010010 and 100101, but not 101111 or 010101. How many such strings are there?
A:X1+X2+X3+X4+X5+X6 = n, X1,X6>=0, X2,X3,X4,X5>0,C(n+1,5)
以上雖然都有答案，但都想不通為什麼這麼算
麻煩高手幫忙解釋一下，感謝
9 則留言:
1. 在一個 n sides polygon 裡任取三個點可形成一個三角形, 題目要算的是三角形裡的每一邊都不能在polygon上的那一種三角形的總數
(1) 首先, 全部的三角形共有 c(n,3) 個
(2) 有兩個邊在 n-gon 上的三角形總數總共有 n 個, 因為每個點 a 與其相鄰的兩點 b,c, 可對應至一三角形 a-b,b-c, 還有一個不在 n-gon上的邊 b-c
(3) 若用到 n-gon 上恰一個邊, 假設該邊是 a-b, 則在 n-gon 上與 a 和 b 相鄰的點都不能再取來作為三角形中的頂點, 所以得由剩下的 n-4 的點中來與 a 和 b 形成三角形, 那麼這裡總共會有 n(n-4) 種可能
所以拿全部扣掉有邊在 n-gon 上的三角形的總數, 就是所有邊都不在 n-gon 上的三角形的總數
2. 五個相同的裡面取 r 個, 剩下的 5-r 個從相異的那一堆裏面取, 方法是 2^(5-r), 總共就是
Σc(5,r)*2^(5-r), r=0,...,5
= Σc(5,5-r)*2^(5-r), r=0,...,5
= Σc(5,i)*2^i, i=0,...,5
= 2^5
3. (a) pattern 會像是 H...HT...TH...H 這樣, 這相當於是分成三個相異箱子X1,X2,X3, 要符合X1,X3>0, X2=7的constraint, 式子可以reduce成 Y1+Y3=3, Y1,Y3>=0, 再套用組合公式可算出 c(2+3-1,3) = c(4,3) = 4
(b) 你這裡提供的答案似乎有點問題, 照題目的要求, pattern 會是上面(a)中那一種, 再加上 T...TH...HT...T 這一種, 仿照上面的討論可算出此種 pattern 有 c(2+5-1,5) = c(6,5) = 6 個, 所以總數為 4+6=10
4. 因為pattern要有 0...1...0...1..., 把這個string中連續的0和1都搜集在一起, 也就是X2個0,X3個1,X4個0,X5個1, 而這個 string 前面還可以接 X1 個 1, 後面還可以接 X6 個 0, 其中 X1,X6>=0, X2,...,X5>0, 一樣轉換成整數解的問題, X1+...+X6=n, 再將式子轉換成 Y1+...+Y6 = n-4, Y1,...,Y6>=0, 利用組合公式可得 c(6+(n-4)-1,n-4) = c(n+1,5)
感謝超強的助教幫忙解答，大致上都了解了，不過第3題我還是不大懂，其實我是英文看不懂，丟了12次銅板，5次人頭，7次字，two runs of heads？是指2次？2輪？b小題更怪three runs，然後什麼也沒有講，可以幫忙翻譯一下嗎？感激不盡
一個 run 就是一串連續的 H (或 T), 所以要有 two runs of heads + one run of tails, 一定要長的類似像 HHTTTTTTTHHH 這樣
感謝助教，我了解了，還有一題再請教一下(f)equal numbers of runs of heads and runs of tails這題要怎麼算呢？指的是要有5個H，7個T嗎？這樣好像沒辦法算了…
好像還是英文的問題, equal numbers of runs of heads and runs of tails 指的應該是 H 有出現幾個 run, T 就要出現幾個 run; 所以把 T,H 分別丟箱子的情形分開討論然後乘起來, 再把所有的 run 的情形: TH, THTH, THTHTH, THTHTHTH, THTHTHTHTH 這幾種加起來 (這裡每個T or H指的是一個run), 且因為T,H反過來交換也是一樣的個數所以要再乘以 2, 我算出來是
2 * (1 + c(6,5)c(4,3) + c(6,4)c(4,2)
+ c(6,3)c(4,1) + c(6,2)c(4,0)) = 420
感謝~~我了解了，原來又是英文不好的問題，哎~
你好，我看了你第3题（b）的答案，你的答案是 6.
你的答案好像只有计算了 T..H..T 的情况，而忽略了 H..T..H 的情况。
题目是问3个runs，那就应该分别有 T..H..T 跟 H..T..H的情况。
因此答案应该是两种情况的总和，也就是 4+6 = 10.
如果我有什么地方弄错的话，请指正。谢谢。
哦！ 抱歉！ 我没有看到上面的留言已经有人指出来了。
張貼留言