Combinatorics question with unequality and different subscript a) x 1 </msub>

Question

Combinatorics question with unequality and different subscript
a)

x_{1} + x_{2} + . . . + x_{7} \leq 30

where

x_{i}^{'} s

are even non-negative integers.
b)

x_{1} + x_{2} + . . . + x_{7} \leq 30

where

x_{i}^{'} s

are odd non-negative integers.
c)

x_{1} + x_{2} + . . . + x_{6} \leq 30

where

x_{i}^{'} s

are odd non-negative integers.
These questions is from my textbook. I know to solve similar questions such that

x_{1} + x_{2} + . . . + x_{k} \leq n

where

x_{i}^{'} s

are non-negative integers. We add an extra term on the lefthandside and the rest found by combination with repetition such that

(\binom{n + (k + 1) - 1}{n})

. However , what happens when they are even or odd , is there any special technique ? Moreover , as you see the part a and b differ from only subscripts , i think that there must be a reason behind different subscript in same question.Is there any reason ? Thanks in advance..

Answer 1

Step 1
Finding the number of solutions to

x_{1} + x_{2} + \dots + x_{7} \leq 30

where each of the

x_{i}

's are even non-negative integers...
Rather than writing them as

x_{1}, x_{2}, \dots

since they are even we can write them as

2 y_{1}, 2 y_{2}, \dots

Step 2
We have then

2 y_{1} + 2 y_{2} + \dots + 2 y_{7} \leq 30

. Divide both sides by 2 and we are left with

y_{1} + y_{2} + \dots + y_{7} \leq 15

where each of the

y_{i}

's are non-negative integers with no restrictions on parity.
Similarly, for the later problems where you deal with odd numbers, you can rewrite as

2 z_{1} + 1, 2 z_{2} + 1, \dots

You can then subtract the 1's from both sides and then use the same idea. The punchline is to rewrite a problem you haven't seen before in such a way that it becomes a problem you have seen before.

Answer 2

Step 1
For (a), you should solve for

y_{1} + y_{2} + . . . + y_{7} \leq 15,

, where

x_{i} = 2 y_{i}, y_{\geq} 0

For (b), you should solve for

y_{1} + y_{2} + . . . + y_{7} \leq 11

where

x_{i} = 2 y_{i} + 1, y_{i} \geq 0

For (c), you should solve for

y_{1} + y_{2} + . . . + y_{6} \leq 12

where

x_{i} = 2 y_{i} + 1, y_{i} \geq 0

Step 2
The difference between (b) and (c) is that in (b), there are 7 odd numbers and 7 odd numbers cannot sum to an even number so equality

(= 30)

is not possible and you would have sum

\leq 29

. But in (c), you have 6 odd numbers so equality can be reached.

Combinatorics question with unequality and different subscript a) x 1 </msub>

Want to know more about Discrete math?

Answers (2)

Not exactly what you’re looking for?

Not exactly what you’re looking for?

You might be interested in

New questions