一題排列組合題目：
將一顆 k 元樹、高度為 d的每個點標上(1,2,3..,N，其中N為node數)的數字、每個節點標上的數字需小於其子節點所標上的數字、例如：
\\\1 \\\\\\\\\1
\\2 3\\\ \\\\2 5
4 5 6 7\ \\\4 3 6 7
(其中\無意義、僅為了排版)
為 k=2,d=2的合法方法。
希望助教不吝賜教、謝謝。
2 則留言:
如果你要問的是可構成多少種像是這樣的樹, 其中左右子樹視為不同, 我以 d=2, k=2 的case來說明我的想法如下:
因為 root 一定要標 1, 在 1 被用掉之後, 將剩下的 2,3,...,7 任意均分成相同大小的兩堆, 假設一堆叫 X 一堆叫 Y, 並且一堆放在root的左子樹, 另一堆放在右子樹, 那麼各取 X 中最小和 Y 中最小的數必定會構成 root 的兩個 child, 然後再對 X 和 Y 分別遞迴下去做同樣的事情, 也就是去掉root再分兩堆, 那因為當d=2時這樣就到底了, 所以總方法數就是 c(6,3)*c(2,1)*c(2,1)=80
感謝助教，我了解了!!真是不容易的想法
張貼留言