召唤师为神马有10个技能

在dota的100多个英雄中，技能最多的无疑是召唤师，英文叫carl。
召唤师有冰，雷，火三种球可以选择，选择不同的球就可以组合出不同的技能。把这个问题抽象一下，就是
有A种球3个，B种球3个，C种球3个，从这9个球中选出3个，问有多少种取法。同一类中的球不做区分，有如下10种：

AAA
AAB
AAC
ABB
ABC
ACC
BBB
BBC
BCC
CCC

这个序列明显是规律的。可以使用回溯的方式生成。代码如下：

#include <iostream>
 
using namespace std;
 
int main()
{
    int n;
   
    cin >> n;
   
    int* bit = new int[n+1];
 
    for (int i = 0; i <= n; i++)
    {
        bit[i] = 0;
    }
   
    int cur = 0;
    int sum = 0;
   
    while (1)
    {
        bit[cur]++;
 
        if (cur)
        {
           
            if (bit[cur] <= n && n - 1 == cur)
            {
                sum++;       
                cout << bit[0] << " " << bit[1] << " " << bit[2] << endl;
            }
           
            if (bit[cur] > n || n == cur)
            {
                cur--;
            }       
           
            else
            {
                cur++;
 
                bit[cur] = bit[cur-1] - 1;
            }
        }
 
        else
        {
 
            if (bit[cur] > n)
            {
                break;
            }
 
            else
            {
                cur++;
 
                bit[cur] = bit[cur-1] - 1;
            }
        }
 
    }
 
    cout << sum << endl;
}

当然了，对于回溯来说，时间复杂度是很高的，输入为n时，时间复杂度为O(nn)。当n特别大时，这种方式显然效率太低。
有没有可能从数学的角度来求解这个问题呢…似乎可以用排列组合的方式来完成。
首先把这个问题抽象成如下问题。
有N种球，每种各N个，从这N*N个球中取出N个，问有多少种取法。
或者，有N种球，每种球正无限个，从中取出N个，问有多少种方式。乍看下去，可能这个问题有些复杂，可以把这个问题进行一次拆分。
从N种球中取…如果只有1种球，从中取出N个，那么只有1中方法。
从2种球中取，为了和上一种情况区分开，我们保证2种球中每一种至少取了1个，如果能算出这个值，那么总的种数如下：

？中的表达式未知。
问题转换为怎么从2至n种球中取出n个，且每种球至少取一个。
可以把这个问题继续转换一下。
2种球的时候，第1种取a个（0<a<n），第2种取n-a个。这个时候，问题转换成了把n个相同的球放入2个不同的筒中，且每个筒不为空。这两个问题的解是一一对应的，因为我们可以把1号筒中的球当成第1种球，2号筒中的球作为第2种球，反之依然，第1种球中取出的放在第一个筒中，第2种球中取出的放入第二个筒中……
现在需要解决怎样把n个球放入2至n个筒中，且每个筒不空。
我们还是以2个筒来示例，似乎可以这样：
首先取出两个球，分别放入两个筒中，这样保证了2个筒一定不空，剩下的n-2个球，每一个球有2种选择，所以最后的答案是2n-2，对吗？
考虑这种情况，第3个球放入1号筒，第4个球放入2号筒；这种情况和，第3个球放入2号筒，第4个球放入1号筒。它们重复了…….因此这种方式不对。
这样考虑，把n个球排成一行，那么一共有n-1个空位，在这n-1个空位中插入一个分隔符，就把n种球分成了2类……3个筒时插入2个分隔符……….
最后得到这个式子：

为把n个球放入i个筒中，且每个筒不空。
所以最后的结果为：

感谢天骄师兄一起讨论的半个上午……
（原文章时间2012-2-24）