Python/Ruby/PHP/Golang(Go)で上限のある重複組み合わせ

#Python/Ruby/PHP/Golangで上限のある重複組み合わせのパターン数を算出する
3種類の果物から12個取り出す場合の数は、それぞれの果物が12個以上ある場合、[重複組み合わせ](http://qiita.com/hiroykam/items/d182ae2a41dedb663380)の方法で、算出することができる。
しかし、それぞれの果物が6個という上限がある場合、この方法では算出できない。
そのため、上限がある重複組み合わせについては、別の方法で実現する必要がある。
この例では、さいころを3回振り、出た目の総和が12になる場合の数と等価であるので、この数式は意外と流用できる（と思う）。

##控除原理
このような上限のある重複組み合わせは控除原理に基づいて算出する方法がある。
[参考サイト](http://www004.upp.so-net.ne.jp/s_honma/number/repeatedcombination.html)はこちら。

※「控除原理」を「個数定理」という名称でも呼ばれているが、「個数定理」は正式な名称なのだろうか・・・数学関連の書籍をあたってみよう。

#数式
[参考サイト](http://www004.upp.so-net.ne.jp/s_honma/number/repeatedcombination.html)から、上限をm、果物の種類をn（振ったさいころの数）、総和をtとすると下記の式で算出できる。

```math
\begin{eqnarray}
\sum_{ k = 0 }^{ [ \frac{ t - n }{ m } ]} (-1)^k \cdot {}_n \mathrm{ C }_k \cdot {}_n \mathrm{ H }_{ t - n - m \cdot k }
\end{eqnarray}
```

m = 6、n = 3、t = 12のとき25となる。 

##ソースコード
###Python3

```py
import functools as ft


def permutation(n, k):
    if k > n:
        return 0
    elif 0 < k <= n:
        return ft.reduce(lambda x, y:x * y, [n - v for v in range(k)])
    else:
        return 1


def factorial(n):
    return permutation(n, n - 1)


def combination(n, k):
    return int(permutation(n, k) / factorial(k))


def homogeneous(n, k):
    return combination(n + k - 1, k)


def homogeneous_with_limit(m, n, t):
    return sum([(-1)**k * combination(n, k) * homogeneous(n, t - n - m * k) \
                for k in range(0, int((t - n) / m) + 1)])

if __name__ == '__main__':
    print(homogeneous_with_limit(6, 3, 12))
```

```shell-session:出力結果
25
```

###Ruby2.4

```rb
def permutation(n, k)
  if k > n
    0
  elsif 0 < k && k <= n then ((n - k + 1)..n).inject(:*)
  else 1
  end
end

def factorial(n)
  permutation(n, n - 1)
end

def combination(n, k)
  (permutation(n, k) / factorial(k)).to_i
end

def homogeneous(n, k)
  combination(n + k - 1, k)
end

def homogeneous_with_limit(m, n, t)
  (0..((t - n) / m)).inject(0) {|s, k| s + (-1)**k * combination(n, k) * homogeneous(n, t - n - m * k)}
end

p homogeneous_with_limit(6, 3, 12)
```

```shell-session:出力結果
25
```


###PHP7.1

```php
<?php

function permutation(int $n, int $k) : int {
    if ($k > $n) return 0;
    elseif (0 < $k && $k <= $n)
        return array_reduce(range($n - $k + 1, $n), function ($c, $v) { return $c *= $v; }, 1);
    else return 1;
}

function factorial(int $n) : int {
    return permutation($n, $n - 1);
}

function combination(int $n, int $k) : int {
    return intval(permutation($n, $k) / factorial($k));
}

function homogeneous(int $n, int $k) : int {
    return combination($n + $k - 1, $k);
}

function homogeneous_with_limit(int $m, int $n, int $t) : int {
    return array_reduce(range(0, intval(($t - $n) / $m)), function ($s, $k) use ($m, $n, $t) {
        return $s += (-1) ** $k * combination($n, $k) * homogeneous($n, $t - $n - $m * $k);
    });
}

print(homogeneous_with_limit(6, 3, 12));
```

```shell-session:出力結果
25
```

###Golang

```go
package main;

import (
    "fmt"
    "math"
)

func permutation(n int, k int) int {
    v := 1
    if 0 < k && k <= n {
        for i := 0; i < k; i++ {
            v *= (n - i)
        }
    } else if k > n {
        v = 0
    }
    return v
}

func factorial(n int) int {
    return permutation(n, n - 1)
}

func combination(n int, k int) int {
    return permutation(n, k) / factorial(k)
}

func homogeneous(n int, k int) int {
    return combination(n + k - 1, k)
}

func homogeneous_with_limit(m int, n int, t int) int {
    e := int((t - n) / m) + 1
    v := 0
    for i := 0; i < e; i++ {
       v += int(math.Pow(-1, float64(i))) * combination(n, i) * homogeneous(n, t - n - m *i)
    }
    return v
}

func main () {
    fmt.Printf("%v\n", homogeneous_with_limit(6, 3, 12))
}
```

```shell-session:出力結果
25
```

##その他
控除原理は[エラトステネスの篩](http://qiita.com/hiroykam/items/bf1edde04db8d54f4d1f)の証明でも利用している。またガウス記号（[x]）が懐かしい。

課題が多々あって、たとえば、さいころ3個振って、出た目が(3,5,4)と(3,4,5)でも12となるが、このような順序を考慮しない場合、別のアプローチをとる必要がある。
また、3個のさいころの目の最大値が6ではなく、それぞれ別の値となる場合も、他のアプローチで対応する必要がある。
順序を考慮しないケースについては、どこかでアルゴリズムの課題として主題されていたが、数式化できず、ひたすらループを回す羽目となったので、もう一度挑戦したい。
最大値が異なるケースは、漸化式をどこかで発見して、それっきり。