For part 1 use this link

In this post I will discuss a technique to deal with partitioning of integers namely the generating function.Generating functions in association to partitioning was first used by Leonhard Euler.

\(\textbf{Using Generating functions:-}\)

The whole idea of generating functions is to have a power series \(\sum_{i=0}^n a_k x^{k}\) where the coefficient of \(x^{k}\) \(a_k\) determines the number of ways in which an event can happen.

For Example, the generating function \(\sum_{i=0}^\infty 2^{k} x^{k}\) determines the number of elements of a k-element set.This is due to the fact that the number of subsets of an k-element set is equal to \(2^{k}\) and in the the generating function the coefficient of \(x_k\) is indeed \(2^{k}\).

To find the number of generating functions in a partition we need to consider how many ones are there in the partition ,how many two's ,three's and so on.In each partition the ones can occur \(0,1,2,3,4,5,6\) times;thus contributing a factor of \((1+x+x^{2}+x^{3}+x^{4}+x^{5}......)\) to the generating function.Similarly \(2\) can occur \(1,2,3,4,5,....\)times thus contributing a factor that equals

(\(1+x^{2}+x^{4}+x^{6}+x^{8}......)\) to the generating function.Continuing this logic we find that the generating function for the number of partitions of an integer
is: \((1+x+x^{2}+x^{3}+x^{4}+x^{5}......)(1+x^{2}+x^{4}+x^{6}+x^{8}......)(1+x^{3}+x^{6}+x^{9}+x^{12}......).....\).

We can use \(|x| < 1\) (We can choose any x as it is only representative in character) ,to find the summation of the geometric series to be: \[\dfrac{1}{(1-x)(1-x^{2})(1-x^{3}).....}\]. The logic behind building this generating function is very important. Similar logic is needed to build generating functions for problems which require that the partitions meet certain conditions. We can use generating functions to prove certain relationships between partitions even though we cannot find a closed formula. There are very good approximations for the number of partitions of the general integer, n, however.The best approximation yet was given by Rademacher. The formula is far too advanced for this paper, however.

\(\textbf{Problem 1.}\) In how many ways can n be written as the sum of two positive integers? Representations differing in only the order are considered to be the same.

\(\textbf{Problem 2.}\) Find the number of solutions to the inequality \(a_1 + a_2 + a_3 + a_4 \le 68\) where the \(a_i\) are non-negative integers.

Post the answers in the comments section.In the next post of this series I will prove a few properties of partitioning using generating functions.Good-Day!!

## Comments

Sort by:

TopNewestProblem 1Let the two positive integers be \(x_1,x_2\)

Thus,

\(x_1+x_2 = n\), where \(x_1,x_2\geq 1\)

Substitute \(x_1 = y_1 + 1\) and \(x_2 = y_2 +1\), where \(y_1,y_2\geq 0\)

Thus,

\(y_1+y_2 = n-2\)

\(\Rightarrow\) Number of solutions \(= {n-2+2-1\choose 2-1} = {n-1\choose 1} = \boxed{n-1}\) – Anish Puthuraya · 2 years, 11 months ago

Log in to reply

\( \textbf{ Problem 2 } \)

The problem can be changed into finding the number of solutions to \( a_1 + a_2 + a_3 + a_4 + k = 68 \) where all terms are nonnegative integers. Therefore the number of solutions is \( \dbinom{68+5-1}{5-1} = \dbinom{72}{4} = \fbox{1028790} \) – Josh Rowley · 2 years, 11 months ago

Log in to reply

– Happy Melodies · 2 years, 11 months ago

Can u explain ur solution a little further? Cause I feel quite confused...Log in to reply

equivalentto the equality here.For different values of \(\displaystyle k\), i.e \(\displaystyle k = 0,1,2,\ldots\), the equation will represent the same thing that the problem did.

I don't seem to be able to explain very nicely.

Even Better, just put the values of \(\displaystyle k\), you will find that the equalities thus obtained match to that provided in my solution. (So, it is equivalent).

I really hope I didn't confuse you. If so, please tell me. – Anish Puthuraya · 2 years, 11 months ago

Log in to reply

– Happy Melodies · 2 years, 11 months ago

Ok i got it! I read the qn wrongly! Thought there were 5 termsLog in to reply

Problem 2The number of solutions to this inequality would be the

sumof the number of integral solutions to the following equalities:\(\displaystyle a_1+a_2+a_3+a_4 = 0\)

\(\displaystyle a_1+a_2+a_3+a_4 = 1\)

\(\displaystyle a_1+a_2+a_3+a_4 = 2\)

\(\vdots\)

\(\displaystyle a_1+a_2+a_3+a_4 = 68\)

Thus, the total number of solutions is,

\(\displaystyle n = {0+4-1\choose 4-1} + {1+4-1\choose 4-1} + \ldots + {68+4-1\choose 4-1} \)

\(\displaystyle n = {3\choose 3} + {4\choose 3} + \ldots + {71\choose 3}\)

To evaluate this sum,

we shall write \({3\choose 3}\) as \({4\choose 4}\), since they both are equal.

Thus,

\(\displaystyle n = {4\choose 4} + {4\choose 3} + \ldots + {71\choose 3}\)

Now, we know,

\(\displaystyle {n\choose r} + {n\choose r+1} = {n+1\choose r+1}\)

Using this relation,

\(\displaystyle {4\choose 3} + {4\choose 4} = {5\choose 4}\)

We then combine this term with the next, using the same relation again and again, and at the end, we will have,

\(\displaystyle n = {71\choose 4} + {71\choose 3} = \boxed{{72\choose 4}}\) solutions – Anish Puthuraya · 2 years, 11 months ago

Log in to reply

– Sreejato Bhattacharya · 2 years, 11 months ago

A more elegant approach would be to find the number of non-negative integral solutions to the equation \(\displaystyle \sum \limits_{k=0}^{5} a_k = 68\) instead. Note that each valid selection of \(\left( a_1, a_2, a_3, a_4 \right) \) gives rise to a unique non-negative \(a_5\), which is why they give the same number of solutions.Log in to reply

– Sagnik Saha · 2 years, 11 months ago

That is what Josh Rowley said.. :3Log in to reply

– Anish Puthuraya · 2 years, 11 months ago

Yeah, I was a bit sleepy at that time.Log in to reply

Problem 2Is the answer \(\binom{68+4-1}{4-1} = \boxed{57155}\)? – Happy Melodies · 2 years, 11 months ago

Log in to reply

equalitiesandnotinequalities. – Anish Puthuraya · 2 years, 11 months agoLog in to reply

– Happy Melodies · 2 years, 11 months ago

Oh I didn't notice the sign! Anw, thanks for telling me! :)Log in to reply