计数陷阱

考虑计算结构不同的数量的问题二叉搜索树 http://en.wikipedia.org/wiki/Binary_search_tree:

给定 N，找到包含值 1 .. N 的结构不同的二叉搜索树的数量

给出一个解决这个问题的算法非常容易：修复根中每个可能的数字，然后递归地解决左右子树的问题：

countBST(numKeys)
    if numKeys <= 1
        return 1
    else
        result = 0
        for i = 1 .. numKeys
            leftBST = countBST(i - 1)
            rightBST = countBST(numKeys - i)

            result += leftBST * rightBST

        return result

我最近开始熟悉treaps http://en.wikipedia.org/wiki/Treap，我向自己提出了以下问题：

给定 N，找到包含值 1 .. N 且优先级为 1 .. N 的不同 treap 的数量。如果两个 treap 相对于键或优先级在结构上不同，则它们是不同的（请继续阅读以进行澄清）。

一段时间以来，我一直在尝试找出可以解决此问题的公式或算法，但尚未成功。这就是我注意到的：

1. 的答案n = 2 and n = 3似乎是2 and 6，基于我在纸上画树。
2. 如果我们忽略treaps相对于节点的优先级也可能不同的部分，那么问题似乎与仅计算二叉搜索树相同，因为我们将能够为每个BST分配优先级，这样它也尊重堆不变量。不过我还没有证明这一点。

3. 我认为困难的部分是考虑在不改变结构的情况下排列优先级的可能性。例如，考虑这个trap，其中节点表示为(key, priority) pairs:

             (3, 5)
             /    \ 
        (2, 3)    (4, 4)
        /              \
   (1, 1)               (5, 2)
   

   我们可以排列第二层和第三层的优先级，同时仍然保持堆不变性，因此即使没有键交换位置，我们也能得到更多的解决方案。对于更大的树来说，这可能会变得更加难看。例如，这是与上面的不同的陷阱：

             (3, 5)
             /    \ 
        (2, 4)    (4, 3) // swapped priorities
        /              \
   (1, 1)               (5, 2)
   

如果有人可以分享有关如何解决此问题的任何想法，我将不胜感激。当我仔细思考时，这似乎是一个有趣的计数问题。也许其他人也考虑过这个问题，甚至解决了！

有趣的问题！我相信答案是N阶乘！

给定一个树结构，只有一种方法来填充二叉搜索树键值。

因此我们需要做的就是计算不同的堆数量。

给定一个堆，考虑对树进行中序遍历。

这对应于数字 1 到 N 的排列。

现在给定 {1,2...,N} 的任意排列，您可以按如下方式构造堆：

找到最大元素的位置。其左侧的元素形成左子树，右侧的元素形成右子树。这些子树是通过查找最大元素并在那里分裂来递归形成的。

这产生了一个堆，因为我们总是选择最大元素，并且该堆的中序遍历就是我们开始的排列。因此，我们有一种从堆到排列并唯一地返回的方法。

因此所需的数量是N!。

举个例子：

    5
   / \
  3   4          In-order traversal ->   35142
     / \ 
     1  2

现在从 35142 开始。最大的是 5，所以 3 是左子树，142 是右子树。

    5
   / \
  3  {142}

在142中，4最大，1在左边，2在右边，所以我们得到

    5
   / \
  3   4
     / \
    1   2

为此填写二分搜索键的唯一方法是：

    (2,5)
   /     \
(1,3)    (4,4)
        /     \
       (3,1)   (5,2)

更正式的证明：

If H_N is the number of heaps on 1...N, then we have that

H_N = Sum_{L=0 to N-1} H_L * H_N-1-L * (N-1 choose L)

（基本上我们选择最大值并分配给根。选择左子树的大小，然后选择那么多元素并在左右递归）。

Now,

H0 = 1
H1 = 1
H2 = 2
H3 = 6

If H_n = n! for 0 ≤ n ≤ k

Then H_K+1 = Sum_{L=0 to K} L! * (K-L)! * (K!/L!*(K-L)!) = (K+1)!