Why is -1 subtracted in calculation of number of strategies

39 Views Asked by At

I’m reading question from src https://www.csie.ntu.edu.tw/~r96154/hw1_sol.pdf where following is stated :

enter image description here

I’m attempting to solution to this question. Specifically why is 1 subtracted from (9+4) and (4+1) ?

2

There are 2 best solutions below

0
On BEST ANSWER

This is a stars and bars problem.

Any non-negative solution to $x_1+x_2+x_3+x_4=9$ can be represented uniquely as a sequence of nine stars and three bars, where the bars act as "dividers" between the four variables and the stars represent $1$. For instance, $2+3+3+1$ is represented as $$ {}*{}*{}\mid{}*{}*{}*{}\mid{}*{}*{}*{}\mid {}*{} $$ The number of such sequences, and thus the number of solutions, is three number of ways to choose which $3$ symbols in a sequence of $12$ are bars, making the rest stars.

There are $4-1$ bars because you need three dividers between the four variables. That accounts for the ${}-1$ in both cases.

0
On

Using stars and bars, there are just $3$ bars (not $4$) to be inserted among $9$ stars.