linear equation

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

Herb - 02 Sep 2005 22:47 GMT

Hi, all

What is the number of integer solutions of
x_1 + x_2 + ... + x_6 = 20, where 0 <= x_i <=8 for each i ?

my trying))
Let A_i be the set of integer solutions satisfying x_i >=9
of given equation.
Then,
By inclusion-exclusion principle,
Required number of solutions is n((A_1)^c cap ... cap (A_6)^c)
= (25 choose 5) - (6 choose 1)*Sum_(k=0 to 11)(4+k choose 4)
+ (6 choose 2)*((5 choose 2) + (4 choose 1) + 1)

so, the answer = (25 choose 5) - (6 choose 1)*Sum_(k=0 to 11)(4+k
choose 4) + (6 choose 2)*((5 choose 2) + (4 choose 1) + 1).

I would like to know this solution is correct or not.
Is this solution correct ?

Reply to this Message

Paul Sperry - 03 Sep 2005 04:15 GMT

> Hi, all
>
[quoted text clipped - 4 lines]
> Let A_i be the set of integer solutions satisfying x_i >=9
> of given equation.

So, 0,0,9,0,9,2 is an element of both A_3 and A_5?

> Then,
> By inclusion-exclusion principle,
> Required number of solutions is n((A_1)^c cap ... cap (A_6)^c)

Assuming the compliment is in the set of all solutions, I guess this is
OK.

> = (25 choose 5) - (6 choose 1)*Sum_(k=0 to 11)(4+k choose 4)
> + (6 choose 2)*((5 choose 2) + (4 choose 1) + 1)

Let's see if I can deconstruct this. C(25, 5) is the total number of
solutions with no restrictions. I guess you use De Morgan for
A_1^c /\ A_2^c /\ .. /\A_6^c = (A_1 \/ A_2 \/ ... \/A_6)^c. So you are
going to count A_1 \/ A_2 \/ ... \/ A_6 by inclusion/exclusion and
subtract from the total.

To that end, since |A_1| = |A_2| = ... = |A_6|,

|A_1| + |A_2| + ... + |A_6| = 6*|A_1| and |A_1| =
|(apparently) sum(C(4 + k, 4),k=0..11). Here, you seem to be finding

all solutions to (say) x_2 + ... + x_6 = k for k = 0 (i.e. x_1 = 20) to
k = 11 (X_1 = 9). That's OK.

Now what? You need |A_1 /\ A_2| + |A_1 /\ A_3| + ... + |A_5 /\ A_6|.
These sizes are all the same and there are C(6,2) of them so all you
need is (say) |A_1 /\ A_2| = (apparently) C(5,2) + C(4,1) + 1 = 15. I
get 21: X_1 = X_2 = 9 one of the others is 2 (4 ways); X_1 = X_2 = 9
two of the others is 1 (6 ways); X_1 = 9, X_2 = 10 one of the others is
1 (4 ways); X_1 = 10, X_2 = 9 one of the others is 1 (4 ways); both 10
all of the others = 0 (1 way);X_1 = 11, X_2 = 9 (1 way); x_1 = 9,
X_2 = 11 (1 way); 4 + 6 + 4 + 4 + 1 +1 + 1 = 21.

All the other intersections are empty.

> so, the answer = (25 choose 5) - (6 choose 1)*Sum_(k=0 to 11)(4+k
> choose 4) + (6 choose 2)*((5 choose 2) + (4 choose 1) + 1).
>
> I would like to know this solution is correct or not.
> Is this solution correct ?

With my correction, the answer (27237) is correct. Inclusion/exclusion
is really not the way to get at this problem (see "generating
functions").

Signature

Paul Sperry
Columbia, SC (USA)

Reply to this Message

Math Forum / Mathematics / Undergraduate Math / September 2005

linear equation