← Kombinatorika

Zadatak komb-001

Naći broj celobrojnih rešenja jednačine

x1+x2+x3+x4=20x_1+x_2+x_3+x_4=20

pod uslovima:

a) xi≥0x_i\ge 0 za sve ii;

b) xi≥1x_i\ge 1 za sve ii;

v) xi≥2x_i\ge 2 za sve ii.

Prikaži rešenje

Broj nenegativnih celobrojnih rešenja jednačine y1+⋯+y4=Ny_1+\cdots+y_4=N („zvezde i pregrade") jednak je (N+33)\dbinom{N+3}{3}.

a) Odmah (233)=23⋅22⋅216=1771\dbinom{23}{3}=\dfrac{23\cdot 22\cdot 21}{6}=1771.

b) Smena xi=yi+1x_i=y_i+1, yi≥0y_i\ge 0, daje y1+⋯+y4=16y_1+\cdots+y_4=16, odakle (193)=19⋅18⋅176=969\dbinom{19}{3}=\dfrac{19\cdot 18\cdot 17}{6}=969.

v) Smena xi=yi+2x_i=y_i+2, yi≥0y_i\ge 0, daje y1+⋯+y4=12y_1+\cdots+y_4=12, odakle (153)=15⋅14⋅136=455\dbinom{15}{3}=\dfrac{15\cdot 14\cdot 13}{6}=455.

Izvor: Do indeksa (autorski)