Overlapping combinations with limits in Python / Ruby / PHP / Golang (Go)

Calculate the number of overlapping combination patterns with an upper limit in Python / Ruby / PHP / Golang

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).

Deduction principle

There is a method of calculating such overlapping combinations with an upper limit based on the deduction principle. Click here for Reference Site.

• The "deduction principle" is also called the "number theorem", but is the "number theorem" a formal name? Let's look at books related to mathematics.

Formula

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.

Source code

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

Other

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.