As this is my first note for the Torque Group any feed back from the staff and also my fellow users is welcome.
Let 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.
Consider the spaces between 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 .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 ,
Among the different possible combination the only one that does not correspond to a legal sum is = .
So the total number of possible ways is
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.
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 the function giving the number of partitions is denoted by .
As shown below there are 7 partitions of 5.Thus .
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 into and into 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.
. Show that the number of partitions of an integer into parts the largest of which is is equal to the number of partitions of into exactly r parts.
. Prove that every number of the form where is an integer greater than one and is a positive integer can be represented as the sum of positive odd integers.
. Prove that the number of partitions of with no part greater than is equal to the number of partitions of with exactly 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