[Math] The Number Of Integer Solutions Of Equations With Constraints

combinatoricsvectors

This question contains formulas from my previous question The Number Of Integer Solutions Of Equations.

I understand the following thus far:

  1. The number of distinct positive integer-valued vectors $(x_1,x_2,…,x_r)$ such that $$x_1 + x_2 + … + x_r = n$$
    is equal to $n-1\choose r-1$.

  2. The number of distinct non-negative integer-valued vectors $(x_1,x_2,…,x_r)$ such that $$x_1 + x_2 + … + x_r = n$$
    is equal to $n+r-1\choose r-1$.

  • Problem 1

    Suppose I want to count the number of distinct integer-valued vectors of the form $(x_1, x_2,…,x_r)$ such that $$x_1 + x_2 + … + x_r = n$$

    But now there are constraints involved $$x_1 \geq 0$$ $$x_r \geq 0$$ $$x_i > 0, i = 2,…,r-1 $$

    In words: the first and last integers are greater or equal to zero and all in-between must be greater than zero.

    How many such distinct vectors are possible?

  • My Approach To Problem 1

    Let $$y_1 = x_1 + 1$$ $$y_i = x_i, i = 2,…,r-1$$ $$y_r = x_r + 1$$

    This gives the positive integer-valued vector of the form $(y_1, y_2, … , y_r)$ such that $$y_1 + y_2 + … + y_r = n + 2$$

    By (1), the number of distinct integer-valued vectors is equal to $n+2-1\choose r-1$ $=$ $n+1\choose r-1 $

  • Problem 2

    Suppose I want to count the number of distinct integer-valued vectors of the form $(x_1, x_2,…,x_r)$ such that $$x_1 + x_2 + … + x_r = n$$

    The constraints involved are $$x_1 \geq 0$$ $$x_i \geq 2, i = 2,…,r-1 $$ $$x_r \geq 0$$

    In words: the first and last integers are greater or equal to zero and all in-between are greater or equal to two.

    How many such distinct vectors are possible?

  • My Approach To Problem 2

    Let $$y_1 = x_1 + 1$$ $$y_i = x_i + 2, i = 2,…,r-1$$ $$y_r = x_r + 1$$

    This gives the positive integer-valued vector of the form $(y_1, y_2, … , y_r)$ such that $$y_1 + y_2 + … + y_r = n + 2 + 2(r-2) = n + 2r-2$$

    By (1), the number of distinct integer-valued vectors is equal to $n+2r-2-1\choose r-1$ $=$ $n+2r-3\choose r-1 $

I would appreciate it if you could verify my solutions and provide hints/suggestions.

Best Answer

The first is right, and well explained.

I don't like the $y_i$ for the second. Either let $y_i=x_i-2$ for the middle ones, and use the formula for the number of solutions in non-negative integers of a suitable equation, or let $y_i=x_i+1$ for the end ones, and $y_i=x_i-1$ for the middle ones, and use the formula for the number of positive solutions of a suitable equation.

Related Question