Combinations with repetitions#11723

Combinations with repetitions (Editorial)

Let $x_{i}$ x_i denote the number of objects placed in the $i$ -th position $(1 \leq i \leq k)$ (1 \le i \le k). Since the objects are identical, a distribution is completely determined by the tuple $(x_{1}, x_{2}, ..., x_{k})$ (x_1, x_2, ..., x_k), and different distributions correspond to different tuples. All objects must be distributed, and a position may remain empty, so the required number equals the number of solutions of the equation

x_{1} + x_{2} + ... + x_{k} = n,

x_1 + x_2 + ...+ x_k = n,

in non-negative integers $(x_{i} \geq 0)$ (x_i \ge 0). Such tuples are called combinations with repetitions of $k$ elements taken $n$ at a time.

Reduction to positive solutions. Substitute $y_{i} = x_{i} + 1$ y_i = x_i + 1. Then $y_{i} \geq 1$ y_i ≥ 1, and the equation becomes

y_{1} + y_{2} + ... + y_{k} = n + k

y_1 + y_2 + ... + y_k = n + k

This substitution is a bijection: the tuple $(y_{i})$ (y_i) is uniquely determined by the tuple $(x_{i})$ (x_i) and vice versa. The number of positive integer solutions of the equation $y_{1} + ... + y_{k} = N$ y_1 + ... + y_k = N equals $C_{N - 1}^{k - 1}$ C_{N - 1}^{k - 1} (e-olymp problem $11550$ ). Substituting $N = n + k$ N = n + k, we obtain the answer

C_{n + k - 1}^{k - 1}

C_{n + k - 1}^{k - 1}

The "stars and bars" method. The same result can be obtained directly. Place $n$ objects and $k - 1$ k - 1 bars in a row, $n + k - 1$ n + k - 1 slots in total. The bars split the objects into $k$ parts: the objects before the first bar go to the first position, the objects between the first and the second bar go to the second position, and so on. Unlike the problem about positive solutions, here bars may stand next to each other or at the ends of the row, which corresponds to empty positions. Each distribution is determined by choosing $k - 1$ k - 1 slots for the bars out of $n + k - 1$ n + k - 1, which can be done in $C_{n + k - 1}^{k - 1}$ C_{n+k-1}^{k-1} ways.

For example, for $n = 7, k = 4$ n = 7, k = 4 the row contains $n + k - 1 = 10$ n + k - 1 = 10 slots. The bars occupy slots $3, 7$ and $8$ , so $2$ objects go to the first position, $3$ objects to the second, the third position remains empty (the bars in slots $7$ and $8$ stand next to each other), and $2$ objects go to the fourth position. This gives the distribution $(2, 3, 0, 2)$ (2, 3, 0, 2).

Example

In the first example ( $k = 3, n = 4$ k = 3, n = 4), the answer is $C_{6}^{2} = (6 \cdot 5) /2 = 15$ C_6^2 = (6 \cdot 5) / 2 = 15.

In the second example ( $k = 3, n = 2$ k = 3, n = 2), the answer is $C_{4}^{2} = (4 \cdot 3) /2 = 6$ C_4^2 = (4 \cdot 3) / 2 = 6.

All $6$ distributions for the second example are shown in the figure. The row contains $n + k - 1 = 4$ n + k - 1 = 4 slots; the numbers of the slots occupied by the $k - 1 = 2$ k - 1 = 2 bars are shown on the left. The objects before the first bar go to the first position, the objects between the bars go to the second position, and the objects after the second bar go to the third position. The color of each object matches the color of the position it goes to.

Algorithm implementation

Let us define the constants and the $d p$ array for storing the values of the binomial coefficients.

#define MAX 201
#define MOD 1000000007
long long dp[MAX][MAX];

The function Cnk computes the value of the binomial coefficient $C_{n}^{k}$ C_n^k modulo $M O D = 1 0^{9} + 7$ MOD = 10^9 + 7.

long long Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  if (dp[n][k] != -1) return dp[n][k];
  return dp[n][k] = (Cnk(n - 1, k - 1) + Cnk(n - 1, k)) % MOD;
}

C++

The main part of the program. Read the input data.

scanf("%d %d", &k, &n);
memset(dp, -1, sizeof(dp));

Compute and print the answer $C_{n + k - 1}^{k - 1}$ C_{n + k - 1}^{k - 1}.

printf("%lld\n", Cnk(n + k - 1, k - 1));