Given numbers from 1 to k, select d many numbers that their sum equal to v

Question

I am trying to find the number of distinct vectors in a set that has the following properties:

• A set is k numbers starting from 1 to k+1
• D is the number of elements that can be selected
• V is the sum of the elements

Examples
k=3, d=3, v=6, the result is 7;
<1, 2, 3>, <1, 3, 2>, <2, 1, 3>, <2, 2, 2>, <2, 3, 1>, <3, 1, 2>, <3, 2, 1>

k=4, d=2, v=7, the result is 2;
<3, 4>, <4, 3>
In this case, <2, 5> is not valid because 5 exceeds the value of k.

I want to find out if there is a mathematical formula to calculate the result. If there isn't a formula, how efficiently can this algorithm be implemented? I have found a rather mysterious implementation but i wonder if it can be improved upon.

public static int NumberOfDistinctVectors(int k, int d ,int v) {
  if((v > k * d) || (v < d)) return 0;
  if(d == 1 || v == d) return 1;
  if(v == d + 1) return d;

  int alpha = 1, beta = 0;
  if(1 < v + k - k * d) 
    alpha = v + k - k * d;

  if(k < v - d + 1)
    beta = k;
  else
    beta = v - d + 1;

  int sum = 0;
  for(int i = alpha; i <= beta; i++) {
    sum += NumberOfDistinctVectors(k, d-1, v-i);
  }

  return sum;
}

Answer 1

The problem is very related to the following:

What is the number of combinations to distribute b identical objects in c groups where no group contains more than n objects?

which is discussed here

Just think of your numbers being made of the object (+1). So in your case

• c = d, because each group corresponds to one of your numbers
• b = v-d, since you need to put at least one (+1) object into each of the d groups
• n = k-1, since we assume a (+1) already in each group and don't want to get larger than k

Find the code below (using appache-commons for c(N,K))

public static int NumberOfDistinctVectors(int k, int d ,int v) {

    return combinations(v-d, d, k-1);
}

//combinations to distribute b identical objects to c groups 
//where no group has more than n objects
public static int combinations(int b, int c, int n)
{
    int sum = 0;
    for(int i = 0; i <= c; i++)
    {
        if(b+c-1-i*(n+1) >= c-1)
            sum += Math.pow(-1, i) * CombinatoricsUtils.binomialCoefficient(c, i)
                   * CombinatoricsUtils.binomialCoefficient(b+c-1-i*(n+1), c-1);
    }
    return sum;
}

Let me also quote from the original answer:

"whether this is actually any more useful than the recurrence is another question"

Answer 2

Here is another way of counting that may be more efficient. It is based on the formula for permutations with repetition. I have added comments in the code hoping it makes it a bit easier to follow.

public static int NumberOfDistinctVectors2(int k, int d, int v)
{
    return NumberOfDistinctVectors2_rec(1, 0, k, d, v, 1, 1);
}

public static int NumberOfDistinctVectors2_rec(
    int i,     /* Current number being added */
    int j,     /* Amount of already picked numbers */
    int k,     /* Maximum number that can be picked */
    int d,     /* Total amount of numbers to pick */
    int v,     /* Remaining value */
    long num,  /* Numerator in "permutations with repetition" formula */
    long den)  /* Denominator in "permutations with repetition" formula */
{
    // Amount of remaining numbers to pick
    int rem = d - j;
    // Remaining value is too big or too small
    if (v < i * rem || v > k * rem) return 0;
    // If no numbers to add then we are done
    if (rem == 0) return Math.toIntExact(num / den);
    // If only one number to add this can be used as a "shortcut"
    if (rem == 1) return d * Math.toIntExact(num / den);

    // Counted permutations
    int count = 0;
    // Maximum amount of repetitions for the current number
    int maxRep = Math.min(v / i, rem);
    // Factor to multiply the numerator
    int numFactor = 1;
    // Factor to multiply the denominator
    int denFactor = 1;
    // Consider adding repetitions of the current number
    for (int r = 1; r <= maxRep; r++)
    {
        // The numerator is the factorial of the total amount of numbers
        numFactor *= (j + r);
        // The denominator is the product of the factorials of the number of repetitions of each number
        denFactor *= r;
        // We add "r" repetitions of the current number and count all possible permutations from there
        count += NumberOfDistinctVectors2_rec(i + 1, j + r, k, d, v - i * r, num * numFactor, den * denFactor);
    }
    // Consider permutations that do not include the current number
    count += NumberOfDistinctVectors2_rec(i + 1, j, k, d, v, num, den);
    return count;
}

Here is a small class testing it where this method appears to be significantly faster (see it in Rextester).

class NumberOfDistinctVectorsTest
{
    // Original method
    public static int NumberOfDistinctVectors(int k, int d ,int v)
    {
        if((v > k * d) || (v < d)) return 0;
        if(d == 1 || v == d) return 1;
        if(v == d + 1) return d;

        int alpha = 1, beta = 0;
        if(1 < v + k - k * d) 
            alpha = v + k - k * d;

        if(k < v - d + 1)
            beta = k;
        else
            beta = v - d + 1;

        int sum = 0;
        for(int i = alpha; i <= beta; i++)
        {
            sum += NumberOfDistinctVectors(k, d-1, v-i);
        }

        return sum;
    }

    // New method
    public static int NumberOfDistinctVectors2(int k, int d, int v)
    {
        return NumberOfDistinctVectors2_rec(1, 0, k, d, v, 1, 1);
    }

    public static int NumberOfDistinctVectors2_rec(int i, int j, int k, int d, int v, long num, long den)
    {
        int rem = d - j;
        if (v < i * rem || v > k * rem) return 0;
        if (rem == 0) return Math.toIntExact(num / den);
        if (rem == 1) return d * Math.toIntExact(num / den);

        int count = 0;
        int maxRep = Math.min(v / i, rem);
        int numFactor = 1;
        int denFactor = 1;
        for (int r = 1; r <= maxRep; r++)
        {
            numFactor *= (j + r);
            denFactor *= r;
            count += NumberOfDistinctVectors2_rec(i + 1, j + r, k, d, v - i * r, num * numFactor, den * denFactor);
        }
        count += NumberOfDistinctVectors2_rec(i + 1, j, k, d, v, num, den);
        return count;
    }

    public static void main(final String[] args)
    {
        // Test 1
        System.out.println(NumberOfDistinctVectors(3, 3, 6));
        System.out.println(NumberOfDistinctVectors2(3, 3, 6));
        // Test 2
        System.out.println(NumberOfDistinctVectors(4, 2, 7));
        System.out.println(NumberOfDistinctVectors2(4, 2, 7));
        // Test 3
        System.out.println(NumberOfDistinctVectors(12, 5, 20));
        System.out.println(NumberOfDistinctVectors2(12, 5, 20));
        // Test runtime
        long startTime, endTime;
        int reps = 100;
        startTime = System.nanoTime();
        for (int i = 0; i < reps; i++)
        {
            NumberOfDistinctVectors(12, 5, 20);
        }
        endTime = System.nanoTime();
        double t1 = ((endTime - startTime) / (reps * 1000.));
        startTime = System.nanoTime();
        for (int i = 0; i < reps; i++)
        {
            NumberOfDistinctVectors2(12, 5, 20);
        }
        endTime = System.nanoTime();
        double t2 = ((endTime - startTime) / (reps * 1000.));
        System.out.println("Original method: " + t1 + "ms");
        System.out.println("New method: " + t2 + "ms");
    }
}

Output:

7
7
2
2
3701
3701
Original method: 45.64331ms
New method: 5.89364ms

---

EDIT: New test (run on JDoodle with Apache Commons 3.6.1) including SaiBot's answer:

import org.apache.commons.math3.util.CombinatoricsUtils;

public class NumberOfDistinctVectorsTest
{
    // Original method
    public static int NumberOfDistinctVectors(int k, int d ,int v)
    {
        if((v > k * d) || (v < d)) return 0;
        if(d == 1 || v == d) return 1;
        if(v == d + 1) return d;

        int alpha = 1, beta = 0;
        if(1 < v + k - k * d) 
            alpha = v + k - k * d;

        if(k < v - d + 1)
            beta = k;
        else
            beta = v - d + 1;

        int sum = 0;
        for(int i = alpha; i <= beta; i++)
        {
            sum += NumberOfDistinctVectors(k, d-1, v-i);
        }

        return sum;
    }

    // jdehesa method
    public static int NumberOfDistinctVectors2(int k, int d, int v)
    {
        return NumberOfDistinctVectors2_rec(1, 0, k, d, v, 1, 1);
    }

    public static int NumberOfDistinctVectors2_rec(int i, int j, int k, int d, int v, long num, long den)
    {
        int rem = d - j;
        if (v < i * rem || v > k * rem) return 0;
        if (rem == 0) return Math.toIntExact(num / den);
        if (rem == 1) return d * Math.toIntExact(num / den);

        int count = 0;
        int maxRep = Math.min(v / i, rem);
        int numFactor = 1;
        int denFactor = 1;
        for (int r = 1; r <= maxRep; r++)
        {
            numFactor *= (j + r);
            denFactor *= r;
            count += NumberOfDistinctVectors2_rec(i + 1, j + r, k, d, v - i * r, num * numFactor, den * denFactor);
        }
        count += NumberOfDistinctVectors2_rec(i + 1, j, k, d, v, num, den);
        return count;
    }

    // SaiBot method
    public static int NumberOfDistinctVectors3(int k, int d ,int v)
    {
        return combinations(v-d, d, k-1);
    }

    //combinations to distribute b identical objects to c groups 
    //where no group has more than n objects
    public static int combinations(int b, int c, int n)
    {
        int sum = 0;
        for(int i = 0; i <= c; i++)
        {
            if(b+c-1-i*(n+1) >= c-1)
                sum += Math.pow(-1, i) * CombinatoricsUtils.binomialCoefficient(c, i)
                       * CombinatoricsUtils.binomialCoefficient(b+c-1-i*(n+1), c-1);
        }
        return sum;
    }

    public static void main(final String[] args)
    {
        // Test 1
        System.out.println(NumberOfDistinctVectors(3, 3, 6));
        System.out.println(NumberOfDistinctVectors2(3, 3, 6));
        System.out.println(NumberOfDistinctVectors3(3, 3, 6));
        // Test 2
        System.out.println(NumberOfDistinctVectors(4, 2, 7));
        System.out.println(NumberOfDistinctVectors2(4, 2, 7));
        System.out.println(NumberOfDistinctVectors3(4, 2, 7));
        // Test 3
        System.out.println(NumberOfDistinctVectors(12, 5, 20));
        System.out.println(NumberOfDistinctVectors2(12, 5, 20));
        System.out.println(NumberOfDistinctVectors3(12, 5, 20));
        // Test runtime
        long startTime, endTime;
        int reps = 100;
        startTime = System.nanoTime();
        for (int i = 0; i < reps; i++)
        {
            NumberOfDistinctVectors(12, 5, 20);
        }
        endTime = System.nanoTime();
        double t1 = ((endTime - startTime) / (reps * 1000.));
        startTime = System.nanoTime();
        for (int i = 0; i < reps; i++)
        {
            NumberOfDistinctVectors2(12, 5, 20);
        }
        endTime = System.nanoTime();
        double t2 = ((endTime - startTime) / (reps * 1000.));
        startTime = System.nanoTime();
        for (int i = 0; i < reps; i++)
        {
            NumberOfDistinctVectors3(12, 5, 20);
        }
        endTime = System.nanoTime();
        double t3 = ((endTime - startTime) / (reps * 1000.));
        System.out.println("Original method: " + t1 + "ms");
        System.out.println("jdehesa method: " + t2 + "ms");
        System.out.println("SaiBot method: " + t3 + "ms");
    }
}

Output:

7
7
7
2
2
2
3701
3701
3701
Original method: 97.81325ms
jdehesa method: 7.2753ms
SaiBot method: 2.70861ms

The timings are not very stable in JDoodle (I used it because it allows for Maven dependencies), but in general SaiBot's method is the fastest by far.