The number of 12 fruits taken out from 3 kinds of fruits can be calculated by the method of Duplicate combination when each fruit has 12 or more. it can. However, if there is an upper limit of 6 for each fruit, this method cannot be used. Therefore, it is necessary to realize the overlapping combination with an upper limit by another method. In this example, the dice are rolled three times, which is equivalent to the number when the total number of rolls is 12, so this formula can be used unexpectedly (I think).
There is a method of calculating such overlapping combinations with an upper limit based on the deduction principle. Click here for Reference Site.
From the Reference site, set the upper limit to m, the type of fruit to n (the number of dice to shake), and the sum. If t, it can be calculated by the following formula.
\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}
It becomes 25 when m = 6, n = 3, and t = 12.
Python3
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))
Output result
25
Ruby2.4
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)
Output result
25
PHP7.1
<?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));
Output result
25
Golang
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))
}
Output result
25
The deduction principle is also used in the proof of Eratosthenes Sieve. I also miss the Gaussian symbol ([x]).
There are many challenges, for example, if you roll 3 dice and the rolls are (3,5,4) and (3,4,5), you get 12, but if you don't consider this order, it's different. You need to take an approach. Also, if the maximum value of the three dice rolls is not 6 but different values, it is necessary to take another approach. The case where the order is not considered was the subject of the algorithm somewhere, but I couldn't formulate it, and I ended up turning the loop, so I would like to try again. If the maximum value is different, find the recurrence formula somewhere and it's clear.
Recommended Posts