Count arrays with size n, sum k and largest element m

Question

I'm trying to solve pretty complex problem with combinatorics.

Namely, we have given three numbers N, K, M. Now we want to count how many different arrays of integers are there with length N, sum K and all the elements in the range [1, M]

Constraints:

• 1 <= N <= 100
• 1 <= K <= 100
• 1 <= M <= 100

Example

Let's say N = 2, K = 5, M = 3. This means that we want to count arrays of integers of size 2 with sum of all elements equal to 5 and elements in range [1, 3]. There are total of 2 arrays: {2, 3} and {3, 2}. Please note that the order of the elements also matters, {2, 3} is not equal to {3, 2}

Second example: N = 4, K = 7, M = 3. We want to count arrays of length 4, sum of 7 and elements in range [1, 3].

There are total of 16 possible way of arrays: (1,1,2,3), (1,1,3,2), (2,1,1,3), (3,1,1,2), (2,3,1,1), (3,2,1,1), (1,2,3,1), (1,3,2,1), (1,2,1,3), (1,3,1,2), (1,2,2,2), (2,1,2,2), (2,2,1,2), (2,2,2,1)

What I have tried

I know that one solution is to generate all possible arrays, but such algorithm in best case will work in complexity O(N!) which is far too big for N = 100. I started thinking about solving this with three-dimensional dynamical programming, but I cannot find the relations between the states.

I'm thinking about this way: Let f(i, j, l) be the number of arrays of length i, sum j, and largest element l. We can see that for i = 0 f(i,j,l) = 0, so this is I think the base case. Also f(1, 1, 1) = 1 is another base case.

Now I cannot find the relations between the states. Can you give me some hints how to find the relations between the states. Thanks in advance.

• D.W.: Nice problem. Can you credit the source where you encountered the problem?
• someone12321: The problem is from one macedonian site for training, and the problem in original is in macedonian, but i can give you the test cases if you want them

Answer 1

You can use dynamic programming. For each 0ドル \leq i \leq N$ and 0ドル \leq s \leq K,ドル count the number of arrays of length $i,ドル consisting of numbers in the range $\{1,\ldots,M\},ドル which sum to exactly $s$. The running time is $O(NK)$.

Explicitly, denoting the array by $a,ドル we have $a(0,0) = 1,ドル $a(0,s) = 0$ otherwise, and $$ a(i,s) = \sum_{t=1}^M a(i-1,s-t), $$ where $a(i-1,r) = 0$ if $r < 0$.

As Hendrik Jan mentions in the comments, we can improve on this $O(NKM)$ algorithm by using the recursion $$ a(i,s) = a(i,s-1) - a(i-1,s-1-M) + a(i-1,s-1), $$ with suitable base cases.

Alternatively, we can obtain an explicit expression: the answer is the coefficient of $x^K$ in the generating function $$ (x + \cdots + x^M)^N = x^N \left(\frac{1-x^M}{1-x}\right)^N. $$ In other words, we are looking for the coefficient of $x^{K-N}$ in $$ \left( \sum_{i=0}^N (-1)^i \binom{N}{i} x^{iM} \right) \left( \sum_{j=0}^\infty \binom{j+N-1}{N-1} x^j \right), $$ which has the closed form $$ \sum_{i=0}^{\min(N,\lfloor (K-N)/M\rfloor)} (-1)^i \binom{N}{i} \binom{K-iM-1}{N-1}. $$

• Hendrik Jan: The numbers $a(i,s)$ represent a matrix of solutions for "fixed" $M$. The numbers $a(i,s)$ are a "running sum" of $M$ consecutive elements from the previous row. So, can't the complexity be improved to $O(NK),ドル as $a(i,s) = a(i,s-1) + a(i-1,s-1) - a(i-1,s-M-1)$? give or take typo's.
• Yuval Filmus: @HendrikJan Yes, that's right! I missed this somehow.

Answer 2

You actually don't need the largest element l in your recursive function. It doesn't make such sense to use it, since the largest number in an array has no influence on the other numbers.

---

In most (all?) dynamic programming problems you have to think about the last step / the last part. For f(i, j) you have an array with i numbers. You can imagine, that in the last step you added the last number to the array. So before you added the last number, the array only consists of i-1 numbers.

Now, if the added number was 1, then there are f(i-1, j-1) many arrays. If the added number was 2, then there are f(i-1, j-2) many arrays. And so on...

Add all those possibilities up, and you end up with f(i, j).

Answer 3

I don't pretend this is the most efficient solution. Neither it has a strong theoretical merit, but you can still find it useful to verify your results. Here's a small program in Prolog, (using SWI Prolog for constraint satisfaction part), which can calculate or verify your guess:

% -*- mode: prolog; prolog-system: "swi" -*-
:- use_module(library(clpfd)).
sums(K, [], K).
sums(A, [X | Xs], K) :-
 indomain(A),
 indomain(X),
 B is A + X,
 sums(B, Xs, K).
sums([X | Xs], K) :- sums(X, Xs, K).
nmk_problem_helper(N, K, M, List) :-
 indomain(N),
 indomain(M),
 indomain(K),
 length(List, N),
 List ins 1..M,
 sums(List, K).
nmk_problem(N, K, M, Arrays) :-
 findall(X, nmk_problem_helper(N, K, M, X), Arrays).
nmk_problem_all_helper(List) :-
 [N, M, K] ins 1..100,
 indomain(N),
 indomain(M),
 indomain(K),
 length(List, N),
 List ins 1..M,
 sums(List, K).
nmk_problem_all(Arrays) :-
 findall(X, nmk_problem_all_helper(X), Arrays).

Example usage:

?- nmk_problem(4, 7, 3, X).
X = [[1, 1, 2, 3], [1, 1, 3, 2], [1, 2, 1, 3], [1, 2, 2, 2], [1, 2, 3, 1], [1, 3, 1|...], [1, 3|...], [2|...], [...|...]|...].