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

\[\large{x_1+x_2+x_3+.....+x_r=N}\]

\(SOL^{n}\) FIRSTLY: Note that all \(x_i\) would have odd solutions iff \(N-r=even\)

This is actually trivial: as we have \(odd+odd=even\) and \(even+odd=odd\) we can add \(odd\) numbers an even number of times to get an \(even\) number. and add them \(odd\) number of times to get odd numbers. in short: \(N=odd \implies r=odd\) and \(N=even \implies r=even\) in both cases \(N-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 \(0\)'s and \(1\)'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=7\)

We would create a set with \(7\) one's and \(3-1=2\) zeroes as partitions. For a more visual explanation: one arrangement of our set may look like:

\[\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)\)

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

Basically this is the stars and bars principle

In this method: we use \({r-1}\) \(zeroes\) as partitions between the \(r\) numbers and each \(1\) represents....well each \(1\) . So, we have \(N\) \(one\)'s and \(r-1\) \(zeroes\).

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

after addition of \(r\) fixed \(1's\), we have our set looking like:

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

By our previous arguements, \(N-r\) is \(even\). SO:

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

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

\(\therefore\)The required no. of solutions in odd positive integers for the given equation is

\(\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 \(\dfrac{N-r}{2}+(r-1)=\dfrac{N+r-2}{2}\) objects, out of which: \( \frac{N-r}{2}\) objects are of one kind(\(a's\)), and \((r-1)\) other objects of the same kind (\(zeroes\)).

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

OR:

\[\LARGE{\binom{\frac{N+r-2}{2}}{r-1}}\]

An example to remove all doubts:

Find the odd positive solutions in \(a,b,c\) to the equation:

\[a+b+c=7\]

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

Next step, is to create the set with \(2\) zeroes and \(7\) ones:

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

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

\(\therefore\) We have to find the no. of arrangements of \(2\) zeroes and \(2\) \(a\)'s

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

We now see that these are the only solutions:

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

## Comments

Sort by:

TopNewestVariable replacement would do our job put : . \(2{y}_{i}+1={x}_{i}\)

Our equation becomes :

\(2({y}_{1}+{y}_{2}+.........+{y}_{r})=n-r\)

Simplifying a little bit

\({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 \(\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 · 2 years, 9 months ago

Log in to reply

– Aritra Jana · 2 years, 9 months ago

ahh..well yes... i prefer using a more visual explanation to things.. thus, the method :DLog 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 · 2 years, 9 months ago

Log in to reply

– Aritra Jana · 2 years, 9 months ago

this is exactly what i tried to say :DLog in to reply

It would be much simplier if we use generating functions – Souryajit Roy · 2 years, 9 months ago

Log in to reply

– Aritra Jana · 2 years, 9 months ago

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 postLog in to reply

– Souryajit Roy · 2 years, 9 months ago

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