The number of Odd integral solutions to a multi-variable, linear equation

Q) Find the number of solutions in odd\textbf{odd} positive integers to:

x1+x2+x3+.....+xr=N\large{x_1+x_2+x_3+.....+x_r=N}


SOLnSOL^{n} FIRSTLY: Note that all xix_i would have odd solutions iff Nr=evenN-r=even

This is actually trivial: as we have odd+odd=evenodd+odd=even and even+odd=oddeven+odd=odd we can add oddodd numbers an even number of times to get an eveneven number. and add them oddodd number of times to get odd numbers. in short: N=odd    r=oddN=odd \implies r=odd and N=even    r=evenN=even \implies r=even in both cases Nr=evenN-r=even

So, to the solution:

I don't know if this is possible to prove by multinomial theorem, but simple application of stars and bars(or in this case, the binary set of 00's and 11's) work:


I am going to do a brief explaining to those who aren't well aware of this method The idea is to create a set which has a correspondance with the solution set:

among the different arrangements,each type of arrangement of the numbers in the binary set corresponds to a solution.

Example: if we had to find the total number of positive integral solutions (indefinite as to odd or even) to a+b+c=7a+b+c=7

We would create a set with 77 one's and 31=23-1=2 zeroes as partitions. For a more visual explanation: one arrangement of our set may look like:

110101111two 0’s, seven 1’s\large{\underbrace{{110101111}}_\text{two 0's, seven 1's}}

and more importantly: this set will correspond to a the solution triple (2,1,4)(2,1,4)

thus, different arrangements would correspond to different solution sets, and thus we are reduced to finding the number of different arrangements of the 0s0's and 1s1's in our binary element set.

Basically this is the stars and bars principle


In this method: we use r1{r-1} zeroeszeroes as partitions between the rr numbers and each 11 represents....well each 11 . So, we have NN oneone's and r1r-1 zeroeszeroes.

Now, since the least odd positive integer is 11, we, at first separate rr 1s1's because they would always be included in our binary set\text{always be included in our binary set}.

after addition of rr fixed 1s1's, we have our set looking like:

1010101.....101,111....111r-1 zeroes and r ones,N-r ones\large{ \underbrace{{1010101.....101,111....111}}_\text{r-1 zeroes and r ones,N-r ones}}

By our previous arguements, NrN-r is eveneven. SO:

We group the NrN-r ones in sets of two\text{ones in sets of two} i.e : 11,11,11.....,11Nr2ones\large{\underbrace{11,11,11.....,11}_{\frac{N-r}{2} \text{ones}}}

Writing Nr2=a\frac{N-r}{2}=a and noting that each aa corresponds to a numerical value of 22 . and since we already have rr ones fixed for each variable, the addition of any number of 2s2's or, in this case, asa's would result in the formation of odd numbers (even+odd=oddeven+odd=odd)

\thereforeThe required no. of solutions in odd positive integers for the given equation is

the no. arrangements ofNr2 a’s and (r1) zeroes and r fixed ones\text{the no. arrangements of} \frac{N-r}{2} \text{ a's and } (r-1) \text{ zeroes and } r \text{ fixed ones}

This is the permutation of a total Nr2+(r1)=N+r22\dfrac{N-r}{2}+(r-1)=\dfrac{N+r-2}{2} objects, out of which: Nr2 \frac{N-r}{2} objects are of one kind(asa's), and (r1)(r-1) other objects of the same kind (zeroeszeroes).

This is equal to: (N+r22)!(r1)!(Nr2)!\LARGE{\dfrac{(\frac{N+r-2}{2})!}{(r-1)!(\frac{N-r}{2})!}}

OR:

(N+r22r1)\LARGE{\binom{\frac{N+r-2}{2}}{r-1}}


An example to remove all doubts:

Find the odd positive solutions in a,b,ca,b,c to the equation:

a+b+c=7a+b+c=7

In This case: we have r=3r=3, N=7N=7     Nr=73=4=even\implies N-r=7-3=4=even . therefore, solutions are actually possible.

Next step, is to create the set with 22 zeroes and 77 ones:

S=10101,11112 zeroes and 3 ones, 4 ones\large{S=\underbrace{10101,1111}_\text{2 zeroes and 3 ones, 4 ones}}

next, write the 44 ones as two groups of 2:\text{two groups of 2:}11,11 two ’11’s or 2 ’a’s\large{\underbrace{11,11}_\text{ two '11's or 2 'a's}}

\therefore We have to find the no. of arrangements of 22 zeroes and 22 aa's

this is equal to: 4!2!2!=6\large{\dfrac{4!}{2!2!}=\boxed{6}}

We now see that these are the only solutions:

(1,1,5),(1,5,1),(5,1,1),(3,3,1),(1,3,3),(3,1,3)\underbrace{(1,1,5),(1,5,1),(5,1,1),(3,3,1),(1,3,3),(3,1,3)}

Note by Aritra Jana
4 years, 6 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Variable replacement would do our job put : . 2yi+1=xi2{y}_{i}+1={x}_{i}

Our equation becomes :

2(y1+y2+.........+yr)=nr2({y}_{1}+{y}_{2}+.........+{y}_{r})=n-r

Simplifying a little bit

y1+y2+..............yr=nr2{y}_{1}+{y}_{2}+..............{y}_{r}=\frac{n-r}{2}

Now the work is very simple apply multinomial theorom to get :

No. if integral solutions =(r+nr21r1)=(n+r22r1)\Large =\binom{r+\frac{n-r}{2}-1}{r-1}=\binom{\frac{n+r-2}{2}}{r-1}

So I believe multinomial theorom is a better way to analyze things.(It's my favourite theorom in combinatorics).

Ronak Agarwal - 4 years, 6 months ago

Log in to reply

ahh..well yes... i prefer using a more visual explanation to things.. thus, the method :D

Aritra Jana - 4 years, 6 months ago

Log in to reply

It would be much simplier if we use generating functions

Souryajit Roy - 4 years, 6 months ago

Log in to reply

obviously.. but the main intention of my post was to explain this using simple logic, which everyone would understand. for that very reason, i even fairly explained the stars and bars method in my post

Aritra Jana - 4 years, 6 months ago

Log in to reply

yes,you are right,everyone must know the basic....the stars and bars method is really a classic method

Souryajit Roy - 4 years, 6 months ago

Log in to reply

I would see it as trying to arrange N balls in r buckets, where each bucket has an odd number of balls. Clearly, none of these buckets can be empty since 0 is an even number. So each bucket contains at least one ball. So we throw one ball into each bucket, leaving us with N-r balls to distribute. Now since the number of balls in each bucket can't be even, we tie the N-r balls into pairs. Now we have (N-r)/2 blocks to distribute onto r buckets. There are (r-1 + [(N-r)/2] ) C (r-1) ways of doing this. C stands for combination.

Not really sure about the last line though

Sorry I don't know how to use latex.

Ceesay Muhammed - 4 years, 6 months ago

Log in to reply

this is exactly what i tried to say :D

Aritra Jana - 4 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...