title: Number of binary search trees over n elements
body: <p>I need to find a number of different binary search trees over n elements. I know, that the number of binary search trees over n <strong>distinct</strong> elements is Catalan number. But what if numbers can repeat? In Binary Search Tree elements of left subtree are less than root, and elements of right subtree are equal or greater than root.</p>
  
  <p>This is my code for calculating a number of different binary search trees over n elements. I calculate this number by modulo 123456789, as it can be really big. Can I simply change it to solve my problem?</p>
  
  <pre><code>#include &lt;algorithm&gt;
  #include &lt;vector&gt;
  #include &lt;iostream&gt;
  #include &lt;limits&gt;
  
  using std::vector;
  using std::cin;
  using std::cout;
  using std::endl;
  
  
  long long countTreeDP(int nodeNumber) 
  {
      vector &lt;vector&lt;long long&gt; &gt; cNumbers;
      for (int i = 0; i &lt; nodeNumber + 2; ++i)
      {
          vector&lt;long long&gt; cur(nodeNumber + 2, 0);
          cNumbers.push_back(cur);
      }
      for (int i = 0; i &lt; nodeNumber + 2; ++i)
      {
          cNumbers[i][0] = 1;
      }
  
      long long sum = 0;
      for (int i = 1; i &lt; nodeNumber + 1; ++i) 
      {
          sum = 0;
          for (int j = 1; j &lt;= i; ++j) 
          {
              long long numFirst = cNumbers[nodeNumber + 1][i - j] % 123456789;
              long long numSecond = cNumbers[nodeNumber + 1][j - 1] % 123456789;
              cNumbers[j][i] = (numFirst * numSecond) % 123456789;
              sum += cNumbers[j][i];
              sum = sum % 123456789;
          }
          cNumbers[nodeNumber+1][i] = sum;
      }
  
      return cNumbers[nodeNumber+1][nodeNumber];
  }
  
  int main()
  {
      vector&lt;long long&gt; nodesValues;
      int size = 0;
      cin &gt;&gt; size;
  
      for (int i = 0; i &lt; size; ++i)
      {
          long long elem;
          cin &gt;&gt; elem;
          nodesValues.push_back(elem);        
      }
  
      std::sort(nodesValues.begin(), nodesValues.end());
  
      int uniqueCount = 0;
  
      for (int i = 1; i &lt; nodesValues.size(); ++i)
      {
          if (nodesValues[i] != nodesValues[i-1])
              ++uniqueCount;
      }
      cout &lt;&lt; countTreeDP(uniqueCount + 1) &lt;&lt; endl;
      system("pause");
      return 0;
  }
  </code></pre>