x1+...+xk = n#11550

x1+...+xk = n (Editorial)

Let's use the "stars and bars" method. Write down $n$ ones in a row: $11...1$ . There are $n - 1$ n - 1 gaps between adjacent ones. Choose any $k - 1$ k - 1 of these gaps and put a ' $+$ ' sign into each chosen gap. The ones are then split into $k$ consecutive groups; let $x_{i}$ x_i denote the number of ones in the $i$ -th group. For example, for $n = 6$ n = 6 the string $11 + 111 + 1$ 11+111+1 corresponds to the solution $(2, 3, 1)$ (2, 3, 1) of the equation $x_{1} + x_{2} + x_{3} = 6$ x_1 + x_2 + x_3 = 6.

Each such arrangement defines a solution of the equation in positive integers. Indeed, the sizes of all groups add up to $n$ , and every group is non-empty: a ' $+$ ' sign is never placed before the first one or after the last one, and no gap can contain two signs. Therefore, all $x_{i} \geq 1$ x_i \ge 1.

There is a one-to-one correspondence between the solutions of the equation and the ways to choose $k - 1$ k - 1 gaps out of $n - 1$ n - 1. Hence, the required number of solutions equals $C_{n - 1}^{k - 1}$ C_{n-1}^{k-1}.

For example, for $n = 5, k = 3$ n = 5, k = 3 there are $n - 1 = 4$ n - 1 = 4 gaps, of which $k - 1 = 2$ k - 1 = 2 must be chosen. This can be done in $C_{4}^{2} = 6$ C_4^2 = 6 ways, and each choice corresponds to exactly one solution of the equation $x_{1} + x_{2} + x_{3} = 5$ x_1 + x_2 + x_3 = 5:

Example

Consider the equation $x_{1} + x_{2} + x_{3} = 4$ x_1 + x_2 + x_3 = 4. It has $3$ positive integer solutions: $(1, 1, 2), (1, 2, 1), (2, 1, 1)$ (1, 1, 2), (1, 2, 1), (2, 1, 1).

For example, $n = 4$ n = 4 ones can be divided into $k = 3$ k = 3 terms in $C_{2}^{3} = 3$ C_2^3 = 3 ways:

Note

Let’s consider a few variations of this problem:

A teacher brought $n$ identical candies to class and wants to distribute them among $k$ students so that each student receives at least one candy. Find how many ways this can be done.
There are $n$ identical notebooks on a desk. They need to be arranged into $k$ piles so that each pile contains at least one notebook. Determine how many ways this can be done.

Algorithm implementation

The Cnk function computes the value of the binomial coefficient $C_{n}^{k}$ C_n^k.

long long Cnk(long long k, long long n)
{
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 1; i <= k; i++)
    res = res * (n - i + 1) / i;
  return res;
}

C++

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

scanf("%lld %lld", &k, &n);

Compute and print the answer – the value of $C_{n - 1}^{k - 1}$ C_{n-1}^{k-1}.

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

Python implementation

import math

Read the input data.

k, n = map(int,input().split())

Compute and print the answer – the value of $C_{n - 1}^{k - 1}$ C_{n-1}^{k-1}.

res = math.comb(n - 1, k - 1)
print(res)