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

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
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"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

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.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered 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"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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 - 7 years, 4 months ago

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

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 - 7 years, 4 months ago

Yeah, I was a bit sleepy at that time.

That is what Josh Rowley said.. :3

Sagnik Saha - 7 years, 3 months ago

$\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 - 7 years, 4 months ago

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

Happy Melodies - 7 years, 4 months ago

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 – Ok i got it! I read the qn wrongly! Thought there were 5 terms

Problem 2

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

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

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

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$