Introduction to partitioning of integers(Part 1)

As this is my first note for the Torque Group any feed back from the staff and also my fellow users is welcome.

Q.\textbf{Q.}Let nn be a positive integer.In how many ways can one write a sum of (at least two) positive integers that add up to n?Consider the same set of integers written in different order to be different.

Ans.\textbf{Ans.} Consider the n1n-1 spaces between nn 1's in the following arrangement : 1_1_1_1........_1

In each of the spaces either we put "+" or we put ")+(".The number of ways to do it is 2n12^{n-1}.It is to be noted that each of these arrangements correspond to a unique way of partitioning n.This happens because by order of operations we need to add the numbers between each pair of parentheses first.

For example, for n=8n=8, (1+1)+(1+1)+(1)+(1+1+1)=2+2+1+3=8(1+1)+(1+1)+(1)+(1+1+1) = 2+2+1+3 = 8

Among the different possible combination the only one that does not correspond to a legal sum is = (1+1+1+1+1+...+1)=n(1+1+1+1+1+...+1)=n.

So the total number of possible ways is 2n112^{n-1}-1

A much more interesting idea is the number of ways in which one can write a sum of integers that add up to n, if different orders of summands are not distinguished.In this series of post I will try to provide a overview of this topic while introducing a few techniques for dealing with them.This will hopefully shed some light on the beauty of the subject for you.

Definition:-\textbf{Definition:-}A partition of an integer n , is one way of writing n as a sum of positive integers where order of the addends(terms to be added) does not matter.For the integer nn the function giving the number of partitions is denoted by p(n)p(n).

As shown below there are 7 partitions of 5.Thus p(5)=7p(5) = 7.

5=55 = 5 5=4+15 = 4+1 5=3+25 = 3+2 5=3+1+15 = 3+1+1 5=2+2+15 = 2+2+1 5=2+1+1+15 = 2+1+1+1 5=1+1+1+1+15 = 1+1+1+1+1

Ferrer’s Diagram(A pictorial representation):-\textbf{Ferrer's Diagram(A pictorial representation):-}A Ferrer's diagram is a way of visualizing partitions with dots.Each row represents one addend in a partition.For example ,The partition of 1616 into 6+5+3+1+16+5+3+1+1 and into 5+3+3+2+2+15+3+3+2+2+1 is shown in the given diagram.

Here are a few problems that can be solved using Ferrer's diagrams please post your solutions in the comments.

Problem 1\textbf{Problem 1}. Show that the number of partitions of an integer nn into parts the largest of which is rr is equal to the number of partitions of nn into exactly r parts.

Problem 2\textbf{Problem 2}. Prove that every number of the form nkn^{k} where nn is an integer greater than one and kk is a positive integer can be represented as the sum of nn positive odd integers.

Problem 3\textbf{Problem 3}. Prove that the number of partitions of nn with no part greater than kk is equal to the number of partitions of n+kn + k with exactly kk parts

In the next post I will introduce generating functions in association to solving partition problems and in another post I will discuss stacking problems.Good Day!!

Click here for part 2

Note by Eddie The Head
5 years, 9 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

Can anyone tell me how to place a picture in a definite spot in the post and also attaching multiple images...Thanks in advance....

Eddie The Head - 5 years, 9 months ago

Log in to reply

I don't even know how to attach a picture. My computer doesn't let me click on the link to attach a picture. :/

Finn Hulse - 5 years, 9 months ago

Log in to reply

@Finn Hulse do

![random text here](image link here)

Notice the exclaimation mark. REMEMBER NO SPACES.

Kevin Mo - 5 years, 9 months ago

Log in to reply

So... How do I figure out how many ways I can add numbers to get a number? You never said a formula.

Finn Hulse - 5 years, 9 months ago

Log in to reply

In this post I have defined the pictorial representation only ..the main formula will be using generating functions in my next post,,,the pictorial representation itself cab be used to prove a few properties...Here is part 2

Eddie The Head - 5 years, 9 months ago

Log in to reply

What do u mean in Problem 1?

Happy Melodies - 5 years, 9 months ago

Log in to reply

Prove that the number of ways to partition a number nn such that the largest partition of it has value rr is the same as the number of partitions of nn into rr partitions. Does that make any more sense?

Daniel Liu - 5 years, 9 months ago

Log in to reply

yes! Thanks Daniel L. :)

Happy Melodies - 5 years, 9 months ago

Log in to reply

I think the problem is judt as it says....try on a smaller example to get a better idea

Eddie The Head - 5 years, 9 months ago

Log in to reply

Can anyone explain why (1+1+...+1)=n(1+1+...+1) = n is not a legal sum ?

Sagnik Saha - 5 years, 9 months ago

Log in to reply

In the question we are required to find the no of sums of at least 2 two positive integers that add up to n... (1+1+1+1....+1) corresponds to the sum n+0 and 0 is not positive...

Eddie The Head - 5 years, 8 months ago

Log in to reply

I am not even sure what I am writing is even sane, but I think the answer to problem lies in the fact that nC(n-r) is equal to nCr(where aCb = a!/((a-b)!.b!)). Also (1+1)^n=1+n....n+1. As the largest number possible is r therefore there are exactly (n/r)-1 minimum number of spaces between the additions(where (n/r) is the closest larger integer if n/r isn't an integer and denotes simple bracket if it an integer). Therefore, by simple combinatorics and using my first statement I think both are equal(2 to power((n/r)-1)-1. I would request you to make sense of my answer if you can,for I am not as good as you are in explaining things to others and must confess that I have an intuitive idea of Problem 1 at best. If I am wrong altogether, then please write the correct solution so that I can understand how it works

A Former Brilliant Member - 5 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...