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.

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

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

For Example, the generating function i=02kxk\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 2k2^{k} and in the the generating function the coefficient of xkx_k is indeed 2k2^{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,60,1,2,3,4,5,6 times;thus contributing a factor of (1+x+x2+x3+x4+x5......)(1+x+x^{2}+x^{3}+x^{4}+x^{5}......) to the generating function.Similarly 22 can occur 1,2,3,4,5,....1,2,3,4,5,....times thus contributing a factor that equals
(1+x2+x4+x6+x8......)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+x2+x3+x4+x5......)(1+x2+x4+x6+x8......)(1+x3+x6+x9+x12......).....(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|x| < 1 (We can choose any x as it is only representative in character) ,to find the summation of the geometric series to be: 1(1x)(1x2)(1x3).....\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.

Problem 1.\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.

Problem 2.\textbf{Problem 2.} Find the number of solutions to the inequality a_1 + a_2 + a_3 + a_4 \le 68 where the aia_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
5 years, 8 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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 \( ... \) or \[ ... \] 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

Problem 1
Let the two positive integers be x1,x2x_1,x_2
Thus,
x1+x2=nx_1+x_2 = n, where x1,x21x_1,x_2\geq 1
Substitute x1=y1+1x_1 = y_1 + 1 and x2=y2+1x_2 = y_2 +1, where y1,y20y_1,y_2\geq 0

Thus,
y1+y2=n2y_1+y_2 = n-2
\Rightarrow Number of solutions =(n2+2121)=(n11)=n1= {n-2+2-1\choose 2-1} = {n-1\choose 1} = \boxed{n-1}

Anish Puthuraya - 5 years, 8 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:
a1+a2+a3+a4=0\displaystyle a_1+a_2+a_3+a_4 = 0
a1+a2+a3+a4=1\displaystyle a_1+a_2+a_3+a_4 = 1
a1+a2+a3+a4=2\displaystyle a_1+a_2+a_3+a_4 = 2
\vdots
a1+a2+a3+a4=68\displaystyle a_1+a_2+a_3+a_4 = 68

Thus, the total number of solutions is,

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

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

To evaluate this sum,
we shall write (33){3\choose 3} as (44){4\choose 4}, since they both are equal.

Thus,
n=(44)+(43)++(713)\displaystyle n = {4\choose 4} + {4\choose 3} + \ldots + {71\choose 3}

Now, we know,
(nr)+(nr+1)=(n+1r+1)\displaystyle {n\choose r} + {n\choose r+1} = {n+1\choose r+1}

Using this relation,
(43)+(44)=(54)\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,

n=(714)+(713)=(724)\displaystyle n = {71\choose 4} + {71\choose 3} = \boxed{{72\choose 4}} solutions

Anish Puthuraya - 5 years, 8 months ago

Log in to reply

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

Sreejato Bhattacharya - 5 years, 8 months ago

Log in to reply

Yeah, I was a bit sleepy at that time.

Anish Puthuraya - 5 years, 8 months ago

Log in to reply

That is what Josh Rowley said.. :3

Sagnik Saha - 5 years, 7 months ago

Log in to reply

 Problem 2  \textbf{ Problem 2 }

The problem can be changed into finding the number of solutions to a1+a2+a3+a4+k=68 a_1 + a_2 + a_3 + a_4 + k = 68 where all terms are nonnegative integers. Therefore the number of solutions is (68+5151)=(724)=1028790 \dbinom{68+5-1}{5-1} = \dbinom{72}{4} = \fbox{1028790}

Josh Rowley - 5 years, 8 months ago

Log in to reply

Can u explain ur solution a little further? Cause I feel quite confused...

Happy Melodies - 5 years, 8 months ago

Log in to reply

It's pretty straight forward. Notice that, the inequality given to us is equivalent to the equality here.
For different values of k\displaystyle k, i.e k=0,1,2,\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 k\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 - 5 years, 8 months ago

Log in to reply

@Anish Puthuraya Ok i got it! I read the qn wrongly! Thought there were 5 terms

Happy Melodies - 5 years, 8 months ago

Log in to reply

Problem 2

Is the answer (68+4141)=57155\binom{68+4-1}{4-1} = \boxed{57155}?

Happy Melodies - 5 years, 8 months ago

Log in to reply

No, I don't think so. This formula is valid for equalities and not inequalities.

Anish Puthuraya - 5 years, 8 months ago

Log in to reply

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

Happy Melodies - 5 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...