問題
1が2つのとき。
例えば、以下の例だと、$_4C_3-2 = 2$と読み解くことができそうなので、そういう感じでやってみたい。
4
1 1 2 3
とりあえず、引く前の組み合わせ数は$_nC_3$です。ここから引いていくことを考えます。
まず、上の例の1のように、2つのときを考えます。このとき、数字の組み合わせとしては[1,1,x]となるときが、ダメなものです。xは2か3なので、2つです。
1が3つのとき。
3つになるとどうなるか考えます。以下の例の最終的な答えが3であることは簡単に分かります。$_5C_3=10$なので、7ぐらい引けると嬉しいことが分かります。
5
1 1 1 2 3
1が3つあるのでここに注目します。このとき、数字の組み合わせとしては[1,1,x]となるときがダメなものです。xは2か3です。一方で、それぞれの1は区別可能(それぞれはインデックスで管理されているので区別可能です)なので記号をふって1a, 1b, 1cなどとすると、[1a,1b,x], [1b,1c,x], [1c,1a,x]の3パターンがあります。つまり、
$$ _3C_2 \times 2 = 6$$
後、[1a,1b,1c]もダメなパターンです。これは1通りで、$_3C_3$の計算でできそうです。
合計で$6+1=7$になりました。この方法で良さそうです。
1がd個のとき。
さて、与えられた数字がn個、重複する数字である1がd個のとき、引くべき数は以下のようになります。左は[1,1,x]を、右は[1,1,1]の個数を数えています。
$$ _dC_2 \times (n-d) + _dC_3$$
一般化
さて、ありがたいことに、1がd(>1)個、2がe(>1)個あったとしても、[1,1,x]と[2,2,x]は互いに排反なので、引くべき数はそれぞれ独立に計算できます。つまり、全ての2個以上ある数字に関して$ _dC_2 \times (n-d) + _dC_3$を引いていけば良いだけです。
実装例
pythonで雑な実装をしています。ちなみにC言語では無事overflowをしたのでご留意を。
def main():
N = int(input())
array_ = list(map(int,input().split()))
d = {}
for a in array_:
if not a in d.keys():
d[a] = 1
else:
d[a]+=1
comp_unique = (N)*(N-1)*(N-2)/(3*2*1)
for v in d.values():
if v == 1:
continue
d = v
n = N
comp_unique -= (d * (d - 1) / 2) * (n - d) + ((d * (d - 1) * (d - 2)) / (3 * 2 * 1))
print(int(comp_unique))
if __name__ == "__main__":
main()