MathGoldMedalist
Sign InRegister

Stars and Bars

Lesson · Intermediate

Combinatorics

71.1

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

x,y,zx,y,z are positive integers.

Stars and bars representation of x plus y plus z equals 20

There are

(192) \binom{19}{2}

ways to place two dividers between 20 stars.

71.2

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

71.3

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

Transform the variables as follows:

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

Then

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

so the number of solutions is

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

71.4

x+y+z≤30 x+y+z\le30
x,y,z≥1 x,y,z\ge1

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

x+y+z#(x,y,z)30(292)29(282)28(272)⋮⋮3(22) \begin{array}{c|c} x+y+z & \#(x,y,z)\\ \hline 30 & \binom{29}{2}\\ 29 & \binom{28}{2}\\ 28 & \binom{27}{2}\\ \vdots & \vdots\\ 3 & \binom{2}{2} \end{array}

By 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=20 x+y+z=20
7≥x≥1 7\ge x\ge1
y≥1 y\ge1
z≥1 z\ge1

Total:

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

Unfavorable:

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

Set

x′=x−7≥1 x'=x-7\ge1

Then

x′+y+z=13 x'+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