x1+...+xk = n#11550

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

Utilizziamo il metodo delle "palline e separatori" ("stars and bars"). Scriviamo di seguito $n$ uni: $11...1$ . Tra uni adiacenti ci sono $n - 1$ n - 1 intervalli. Scegliamo $k - 1$ k - 1 qualsiasi di essi e poniamo in ogni intervallo scelto il segno ' $+$ '. Gli uni si suddivideranno in $k$ gruppi consecutivi; indichiamo con $x_{i}$ x_i il numero di uni nell' $i$ -esimo gruppo. Ad esempio, per $n = 6$ n = 6 la scrittura $11 + 111 + 1$ 11+111+1 definisce la soluzione $(2, 3, 1)$ (2, 3, 1) dell'equazione $x_{1} + x_{2} + x_{3} = 6$ x_1 + x_2 + x_3 = 6.

Ogni tale disposizione definisce una soluzione naturale dell'equazione. Infatti, la somma delle dimensioni di tutti i gruppi è uguale a $n$ , e ogni gruppo è non vuoto: il segno ' $+$ ' non viene posto prima del primo uno né dopo l'ultimo, e in un intervallo non si possono mettere due segni. Di conseguenza, tutti gli $x_{i} \geq 1$ x_i \ge 1.

Tra le soluzioni dell'equazione e i modi di scegliere $k - 1$ k - 1 intervalli su $n - 1$ n - 1 esiste una corrispondenza biunivoca. Pertanto il numero di soluzioni cercato è uguale a $C_{n - 1}^{k - 1}$ C_{n-1}^{k-1}.

Ad esempio, per $n = 5, k = 3$ n = 5, k = 3 ci sono $n - 1 = 4$ n - 1 = 4 intervalli, dai quali bisogna scegliere $k - 1 = 2$ k - 1 = 2. Questo si può fare in $C_{4}^{2} = 6$ C_4^2 = 6 modi, e a ogni scelta corrisponde esattamente una soluzione dell'equazione $x_{1} + x_{2} + x_{3} = 5$ x_1 + x_2 + x_3 = 5:

Esempio

Consideriamo l'equazione $x_{1} + x_{2} + x_{3} = 4$ x_1 + x_2 + x_3 = 4. Essa ha $3$ soluzioni intere positive: $(1, 1, 2), (1, 2, 1), (2, 1, 1)$ (1, 1, 2), (1, 2, 1), (2, 1, 1).

Ad esempio, $n = 4$ n = 4 uni possono essere suddivisi in $k = 3$ k = 3 addendi in $C_{2}^{3} = 3$ C_2^3 = 3 modi:

Nota

Consideriamo alcune varianti di questo problema:

L'insegnante ha portato in classe $n$ caramelle identiche e vuole distribuirle a $k$ alunni in modo che ciascuno ne riceva almeno una. Trovate in quanti modi si può fare.
Sul banco ci sono $n$ quaderni identici. Bisogna disporli in $k$ pile in modo che ogni pila contenga almeno un quaderno. Determinate in quanti modi si può fare.

Implementazione dell'algoritmo

La funzione Cnk calcola il valore del coefficiente binomiale $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++

Parte principale del programma. Leggiamo i dati di input.

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

Calcoliamo e stampiamo la risposta $C_{n - 1}^{k - 1}$ C_{n-1}^{k-1}.

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

Implementazione in Python

import math

Leggiamo i dati di input.

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

Calcoliamo e stampiamo la risposta $C_{n - 1}^{k - 1}$ C_{n-1}^{k-1}.

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