Problem 36

ThePerfectHacker · #1 $Old$ 09-04-2007, 07:04 PM

1. Let $\{a_n\}$ be a non-increasing sequence so that $\sum_{n=1}^{\infty}a_n < \infty$ . Prove that $\lim \ na_n = 0$ .

And this problem is for the younger kids. (So give them a chance to solve it).

2. Given a positive integer $n$ define a $k$ -partition to be a sum of $k$ positive integers which sum to $n$ . For example, $n=10$ . The following are $4$ -partitions. $10 = 4+4+2+2$ and $10 = 2+2+4+4$ and $10 = 1+1+1+7$ . Notice that $2+2+4+4\mbox{ and }4+4+2+2$ are considered distinct*. Say you a given a specific $n$ . And given a specific value of $k$ , can you find the total number of $k$ -partitions of this integer, with a formula?** Now try to see how many partitions (again not counting order) exist for a given integer $n$ (the answer is really supprising).
Hint: Review your Combinatorics formula for this one.

*)This is done to simplify this problem. When these are not considered distinct this forms a problem from number theory called the "partition problem". It is a very complicated problem.

**)The problem is not whether you can. But rather how you can. If it was the later the answer would be "yes" turning this problem into a worthless problem.

janvdl · #2 $Old$ 09-05-2007, 05:39 AM

Quote:

Originally Posted by ThePerfectHacker $View Post$

2. Given a positive integer $n$ define a $k$ -partition to be a sum of $k$ positive integers which sum to $n$ . For example, $n=10$ . The following are $4$ -partitions. $10 = 4+4+2+2$ and $10 = 2+2+4+4$ and $10 = 1+1+1+7$ . Notice that $2+2+4+4\mbox{ and }4+4+2+2$ are considered distinct*. Say you a given a specific $n$ . And given a specific value of $k$ , can you find the total number of $k$ -partitions of this integer, with a formula?** Now try to see how many partitions (again not counting order) exist for a given integer $n$ (the answer is really supprising).

Hint: Review your Combinatorics formula for this one.

$\frac{(n + k - 1)!}{k!(n - 1)!}$

So if $n = 10$ and using $4$ -partitions(including repetitions), then we will have $715$ possibilities.

$\frac{(10 + 4 - 1)!}{4!((10 - 1)!)} = 715$

Am i even close to correct?

SkyWatcher · #3 $Old$ 09-05-2007, 06:27 AM

your close to correct!
but an other matter is to prove it!
first check (close to correct)=correct whith little numbers
then try to find a connection whith your (or a near one) anwser and the probleme
i suggest you to try to find an equivalent problem that you can resolve!

SkyWatcher · #4 $Old$ 09-05-2007, 07:28 AM

as 4+4+2+2=12 and not 10
i supose that PerfectHacker mean 'increasing suite Un' instead of nonincreasing:
consider the suite Un=(-1^n)/sqr(n) and you would then had a contre-exemple!

by the way in the second problem i suppose 0 is considered like a positive integer (wich it is I think)

Soroban · #5 $Old$ 09-05-2007, 11:40 AM

Hello, ThePerfectHacker!

Drag your cursor between the asterisks.

Quote:

2. Given a positive integer $n$ , define a $k$ -partition
to be a sum of $k$ positive integers which sum to $n$ .

For example, $n=10$ .
The following are $4$ -partitions: $10 = 4+4+2+2,\; 10 = 2+2+4+4,\;10 = 1+1+1+7$ .
Notice that $2+2+4+4\mbox{ and }4+4+2+2$ are considered distinct. *

Say you are a given a specific $n$ and given a specific value of $k$ .
Can you find the total number of $k$ -partitions of this integer, with a formula?

* This is done to simplify this problem.
When these are not considered distinct, this forms a problem from number theory
called the "partition problem", a very complicated problem.
Yes, it is. I investigated it years ago.

*
Consider a board n inches long.
It is marked with n-1 inch-marks.

We will cut it (on the inch-marks) into k pieces.
So we will make k-1 cuts.

There are: C(n-1, k-1) ways to choose the cuts.

*

Quote:

Now try to see how many partitions (again not counting order)
exist for a given integer $n$ .

*
We have a board n units long with n-1 inch-marks.

For each of the n-1 inch-marks, there are two choices: cut or don't cut.

Therefore, there are: 2^{n-1} possible partitions.
(This includes an intact, uncut board.)

*

kezman · #6 $Old$ 09-06-2007, 11:41 AM

A_n+1/a_n<1 so with dalembert and knowing that a_n -> 0 then lim (n+1).a_n+1/n.a_n < 1 then lim n.a_n = 0

ThePerfectHacker · #7 $Old$ 09-06-2007, 03:42 PM

Quote:

Originally Posted by kezman $View Post$

A_n+1/a_n<1 so with dalembert and knowing that a_n -> 0 then lim (n+1).a_n+1/n.a_n < 1 then lim n.a_n = 0

What?

janvdl · #8 $Old$ 09-06-2007, 03:56 PM

But the combinatorics formula has already been proven. And that is the formula used to calculate stuff like this anyway. Did i go wrong somewhere in the understanding of this problem?

kezman · #9 $Old$ 09-06-2007, 05:09 PM

Quote:

What?

$A_n = n.a_n$
$a_n \to 0$ because is a convergent series.
and $a_{n+1}/a_n<1$
then $\lim \frac{A_{n+1}}{A_n} = \lim \frac{(n+1)}{n}. \frac{a_{n+1}}{{a_n}} < 1$
so $A_n \to 0$

SkyWatcher · #10 $Old$ 09-07-2007, 12:44 PM

Quote:

Originally Posted by janvdl $View Post$

But the combinatorics formula has already been proven. And that is the formula used to calculate stuff like this anyway. Did i go wrong somewhere in the understanding of this problem?

your above awnser to the question was close to corect but not correct:
i suppose you ment to express a certain combinatory formula
but you did it wrong (i cannot see your formula while writing but take k=n and you ll ,see there is a problem)
so I suppose you misunderstood the problem in your own percular way because you've got something that looks like the arythmetique expression of the solution (strange is'nt it)
what's interresting in this problem is the combinatorial expression of the solution and of course and mainly why?
an other way to pose the problem (but i think this is not the way that is nearer the solution) is 'how many way can you fill N indistinct balls in K distinct boxes'
would it helping you?