1. Assume that the elements are pairwise distinct. Answer the following questions on sorting algorithms.
(2)A single comparison between two elements can distinguish up to 2 permutations. How many permutations can be distinguished using k comparisons?
我的答案：(k+1)!
不知道這題的意思是什麼，我的假設是在k+1個數之下做 k comparisons，如果有3個數做2 comparisons 應該可以有 3!個組合，因為每種組合似乎都可以用最多兩次交換就可以得到。
這題之前有人討論過，看完還是不解，不知道大家的想法如何。感謝！

我覺得是2^k種，我是用decision tree的leaf想的，他說都不一樣是說明決策樹是2元而不是三元。

想法跟原PO一樣，k個comparisons 可以排序k+1個數k+1個數總共有 (k+1)!個permutationsNO 我說錯了 別理我XD

X覺得蠻有可能是2^k的

我也覺得是2^k