Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are a total of $n$ objects in stock. You must keep at least $c_i$ objects in stock at location $i$. Assume $n \ge \sum c_i$.

a.) How many different inventories $(x_1,x_2,\dots,x_r)$ are there?

b.) Each location can store a maximum of $d_i$. Let $r = 2$ and count the number of different invetories $(x_1,x_2)$ with $c_1 \le x_1 \le d_1$ and $c_2 \le x_2 \le d_2$.

My answer for part a: We have no choice over where $c_1 + c_2 + \dots + c_r = c_t$ objects are placed. The ramaining $n-c_t$ objects can be spread across $r$ locations. So, there are $$\binom{(n-c_t) + r - 1}{r-1}$$ different inventories.

My incomplete answer for part b: After placing minimum required objects at each location, we are left with $n-c_1-c_2$ objects to distribute.

The remaining objects can be distributed in $$\binom{(n-c_1-c_2)+2-1}{2-1} = (n-c_1-c_2)+1.$$

Now from the number above, I need to subtract the number of combinations that lead to overflows in the two locations.

[---Not sure if the rest is correct---]

Number of ways location 1 overflows:
Location 1 overflows when $x_1 > d_1$ and $c_2 \le x_2 \le d_2$: $$\binom{(n-(d_1+1)-c_2)+2-1}{2-1} = n-d_1-c_2$$

Number of ways location 2 overflows:
(same reasoning as above) $$n-d_2-c_1$$

Total number of inventories is $$(n-c_1-c_2+1)-[(n-d_1-c_2)+(n-d_2-c_1)] = (d_1+d_2+1)-n$$

Total number of inventories $= (d_1+d_2+1)-n$ doesn't make sense.

Please help me figure out where I went wrong.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

Your answer to part (a) is fine. In (b) you’ve overlooked the possibility of overflow in both inventories simultaneously.

You got off to a fine start: there are $$I_0 = n-c_1-c_2+1$$ inventories that meet the minimum requirements. Then you want get the number of inventories that overflow location $1$ but meet the minimum requirement at location $2$; your answer of $n-d_1-c_2$ is correct only if $n\ge d_1+c_1$. If $n < d_1+c_1$, it’s not possible to overflow at location $1$ and meet the minimum requirement at location $2$. Thus, the correct result for this step is $$I_1 = \max\{n-d_1-c_2,0\}$$ inventories that overflow at location $1$ and meet the minimum at location $2$. Similarly, there are $$I_2=\max\{n-d_2-c_1,0\}$$ inventories that meet the minimum at location $1$ but overflow location $2$.

However, there may be inventories that overflow at both locations. When you subtract off the inventories that overflow at location $1$ and then those that overflow at location $2$, the inventories that overflow at both locations get subtracted twice, so you have to add them back in.

The basic calculation gives $$\binom{n-(d_1+1)-(d_2+1)+2-1}{2-1} = n-d_1-d_2-1$$ of these inventories, but again this is true only if $n\ge d_1+d_2+1$; if $n < d_1+d_2+1$, it isn’t possible to overflow both locations. Thus, the correct figure is $$I_3=\max\{n-d_1-d_2-1,0\}.$$

The final result is then given by $$I_0-I_1-I_2+I_3.$$

Note that if $n \ge d_1+d_2+1$, this evaluates to $0$. This makes perfectly good sense: in that case it’s impossible to meet the requirements, and there are no acceptable inventories.

share|improve this answer
add comment

Unless I am reading the problem wrong, this is the same as a couple of other problems that were asked in the last couple of days. You are given a total and want to find the number of ways to make that total $\left(\displaystyle\sum_{i=1}^rx_i=n\right)$ given a range constraint on each summand $(c_i\le x_i\le d_i)$. The answer is the coefficient of $x^n$ in $$ \prod_{i=1}^r\frac{x^{d_i+1}-x^{c_i}}{x-1}\tag{1} $$ We can apply this to the special cases you have listed.


a) you let $d_i\to\infty$. In that case, $(1)$ becomes $\displaystyle\prod_{i=1}^r\frac{x^{c_i}}{1-x}=x^{\sum_{i=1}^rc_i}\frac{1}{(1-x)^r}$, so the answer becomes the coefficient of $x^{n-\sum_{i=1}^rc_i}$ in $\frac{1}{(1-x)^r}$. $$ \begin{align} \frac{1}{(1-x)^r} &=\sum_{i=0}^\infty\binom{-r}{i}(-x)^i\\ &=\sum_{i=0}^\infty\binom{r+i-1}{i}x^i\\ &=\sum_{i=0}^\infty\binom{r-1+i}{r-1}x^i \end{align} $$ Therefore, the answer is $\displaystyle\binom{r-1+n-\sum_{i=1}^rc_i}{r-1}$.
b) you set $r=2$. In this case, $(1)$ becomes $$ \left(x^{c_1}+x^{c_1+1}+\dots+x^{d_1}\right)\left(x^{c_2}+x^{c_2+1}+\dots+x^{d_2}\right)\tag{2} $$ and the answer is the coefficient of $x^n$ in $(2)$.

Suppose $d_1-c_1\le d_2-c_2$, then the answer is $$ \text{the coefficient of }x^n\text{ in }(2)=\left\{\begin{array}{}n-c_1-c_2+1&\text{for }c_1+c_2\le n\le d_1+c_2\\d_1-c_1+1&\text{for }d_1+c_2+1\le n\le c_1+d_2-1\\d_1+d_2-n+1&\text{for }c_1+d_2\le n\le d_1+d_2\\0&\text{otherwise}\end{array}\right. $$


share|improve this answer
    
Please show the closed form, I can't get the answer. –  jamesio Oct 3 '11 at 17:04
    
@jamesio: I have included the gory details. –  robjohn Oct 3 '11 at 17:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.