MathGoldMedalist
Sign InRegister

Toolkit 71

Stars and Bars

71.1

x+y+z=20x+y+z=20

xx, yy, zz are positive integers.

20 stars divided into three groups x, y, z by two dividers

There are

(192)\binom{19}{2}

ways to place two dividers between 20 stars.

71.2

x1+x2+⋯+xk=nx_1+x_2+\cdots+x_k=n
xi≥1x_i\ge 1
(n−1k−1)\boxed{\binom{n-1}{k-1}}

71.3

x+y+z+w=30x+y+z+w=30
x≥−5,y≥3,z≥0,w≥1x\ge -5,\qquad y\ge 3,\qquad z\ge 0,\qquad w\ge 1

Transform the variables as follows:

x′=x+6≥1x'=x+6\ge 1
y′=y−2≥1y'=y-2\ge 1
z′=z+1≥1z'=z+1\ge 1
w′=w≥1w'=w\ge 1

Then

x′+y′+z′+w′=35x'+y'+z'+w'=35

so the number of solutions is

(343)\boxed{\binom{34}{3}}

71.4

x+y+z≤30x+y+z\le 30
x,y,z≥1x,y,z\ge 1

Consider the possible values of x+y+zx+y+z:

x+y+z#(x,y,z)30(292)29(282)28(272)⋮⋮3(22)\def\arraystretch{1.8}\begin{array}{c|c} x+y+z & \#(x,y,z)\\[6pt] \hline 30 & \binom{29}{2}\\[10pt] 29 & \binom{28}{2}\\[10pt] 28 & \binom{27}{2}\\[10pt] \vdots & \vdots\\[10pt] 3 & \binom{2}{2} \end{array}

By Toolkit 16 — Hockey Stick Identity,

#(x,y,z)=(22)+(32)+⋯+(292)=(303)\#(x,y,z)=\binom{2}{2}+\binom{3}{2}+\cdots+\binom{29}{2}=\boxed{\binom{30}{3}}

71.5

x+y+z=20x+y+z=20
7≥x≥17\ge x\ge 1
y≥1y\ge 1
z≥1z\ge 1

Total:

x+y+z=20,x,y,z≥1x+y+z=20,\qquad x,y,z\ge 1
(192)\binom{19}{2}

Unfavorable:

x+y+z=20x+y+z=20
x≥8,y≥1,z≥1x\ge 8,\qquad y\ge 1,\qquad z\ge 1

Set

x′=x−7≥1.x'=x-7\ge 1.

Then

x′+y+z=13x'+y+z=13

and the number of unfavorable solutions is

(122).\binom{12}{2}.

Therefore,

Favorable=(192)−(122)\boxed{\text{Favorable}=\binom{19}{2}-\binom{12}{2}}
Back to Toolkit