Waste less time on Facebook — follow Brilliant.
×

Introduction to Partitioning of integers(Part 2)

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!!

Note by Eddie The Head
3 years, 7 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Problem 1
Let 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 · 3 years, 7 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 · 3 years, 7 months ago

Log in to reply

@Josh Rowley Can u explain ur solution a little further? Cause I feel quite confused... Happy Melodies · 3 years, 7 months ago

Log in to reply

@Happy Melodies It's pretty straight forward. Notice that, the inequality given to us is equivalent to 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 · 3 years, 7 months ago

Log in to reply

@Anish Puthuraya Ok i got it! I read the qn wrongly! Thought there were 5 terms Happy Melodies · 3 years, 7 months ago

Log in to reply

Problem 2
The number of solutions to this inequality would be the sum of 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 · 3 years, 7 months ago

Log in to reply

@Anish Puthuraya 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. Sreejato Bhattacharya · 3 years, 7 months ago

Log in to reply

@Sreejato Bhattacharya That is what Josh Rowley said.. :3 Sagnik Saha · 3 years, 7 months ago

Log in to reply

@Sreejato Bhattacharya Yeah, I was a bit sleepy at that time. Anish Puthuraya · 3 years, 7 months ago

Log in to reply

Problem 2

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

Log in to reply

@Happy Melodies No, I don't think so. This formula is valid for equalities and not inequalities. Anish Puthuraya · 3 years, 7 months ago

Log in to reply

@Anish Puthuraya Oh I didn't notice the sign! Anw, thanks for telling me! :) Happy Melodies · 3 years, 7 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...