28 views

Skip to first unread message

Apr 7, 2011, 10:51:19 PM4/7/11

to

Hi.

Does there exist some kind of formula to count the number of ways to

write a number k as a sum of at most n distinct natural numbers taken

from the interval 1 to n inclusive? If so, what is it, and how is it

derived?

Apr 8, 2011, 1:24:56 AM4/8/11

to

In article

<ca72d99c-5404-4bf0...@p16g2000vbi.googlegroups.com>,

mike3 <mike...@yahoo.com> wrote:

<ca72d99c-5404-4bf0...@p16g2000vbi.googlegroups.com>,

mike3 <mike...@yahoo.com> wrote:

It's the coefficient of x^k in the expansion of

(1 + x) (1 + x^2) (1 + x^3) ... (1 + x^n)

but I don't expect any simple formula for it.

--

Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)

Apr 8, 2011, 11:32:11 AM4/8/11

to

On Apr 8, 1:24 pm, Gerry Myerson <ge...@maths.mq.edi.ai.i2u4email>

wrote:

> In article

> <ca72d99c-5404-4bf0-b5e4-5d04d4892...@p16g2000vbi.googlegroups.com>,

>

> mike3 <mike4...@yahoo.com> wrote:

> > Hi.

>

> > Does there exist some kind of formula to count the number of ways to

> > write a number k as a sum of at most n distinct natural numbers taken

> > from the interval 1 to n inclusive? If so, what is it, and how is it

> > derived?

>

> It's the coefficient of x^k in the expansion of

> (1 + x) (1 + x^2) (1 + x^3) ... (1 + x^n)

> but I don't expect any simple formula for it.

>

> --

> Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)

wrote:

> In article

> <ca72d99c-5404-4bf0-b5e4-5d04d4892...@p16g2000vbi.googlegroups.com>,

>

> mike3 <mike4...@yahoo.com> wrote:

> > Hi.

>

> > Does there exist some kind of formula to count the number of ways to

> > write a number k as a sum of at most n distinct natural numbers taken

> > from the interval 1 to n inclusive? If so, what is it, and how is it

> > derived?

>

> It's the coefficient of x^k in the expansion of

> (1 + x) (1 + x^2) (1 + x^3) ... (1 + x^n)

> but I don't expect any simple formula for it.

>

> --

> Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)

A useful source for this topic will be OEIS's A000009's entry

( http://oeis.org/A000009 ) and the references there.

Apr 8, 2011, 4:31:18 PM4/8/11

to

Hmm. The formulas listed for that sequence seem to be recurrence

formulas, though one was an infinite sum. Does that mean there is

no non-recursive formula to get this?

Apr 9, 2011, 12:06:08 AM4/9/11

to

And I also don't have access to those journals, either.

Apr 9, 2011, 5:53:31 AM4/9/11

to

mike3 <mike...@yahoo.com> wrote:

...

> Hmm. The formulas listed for that sequence seem to be recurrence

> formulas, though one was an infinite sum. Does that mean there is

> no non-recursive formula to get this?

...

> Hmm. The formulas listed for that sequence seem to be recurrence

> formulas, though one was an infinite sum. Does that mean there is

> no non-recursive formula to get this?

No, it does not.

E.g. the old trick is to set x = 2^N for sufficiently large N

then compute Pi (1+x^i) using bignum arithmetic and perform

shifting and masking to get the N bits for the coeff of x^k.

--

Just because Intelligent Design Theory and The Anthropic Principle have

become the vanguard of modern science, is no reason to jettison the

teaching of Darwinism and Evolution Theory.

-- Loirbaj <Rhod...@wmconnect.com>, 12 Mar 2011 14:10 -0800 (PST)

Apr 9, 2011, 3:26:43 PM4/9/11

to

On Apr 9, 3:53 am, k...@kymhorsell.com wrote:

> mike3 <mike4...@yahoo.com> wrote:

>

> ...

>

> > Hmm. The formulas listed for that sequence seem to be recurrence

> > formulas, though one was an infinite sum. Does that mean there is

> > no non-recursive formula to get this?

>

> No, it does not.

>

> E.g. the old trick is to set x = 2^N for sufficiently large N

> then compute Pi (1+x^i) using bignum arithmetic and perform

> shifting and masking to get the N bits for the coeff of x^k.

>

> mike3 <mike4...@yahoo.com> wrote:

>

> ...

>

> > Hmm. The formulas listed for that sequence seem to be recurrence

> > formulas, though one was an infinite sum. Does that mean there is

> > no non-recursive formula to get this?

>

> No, it does not.

>

> E.g. the old trick is to set x = 2^N for sufficiently large N

> then compute Pi (1+x^i) using bignum arithmetic and perform

> shifting and masking to get the N bits for the coeff of x^k.

>

That works for a computer, I want a mathematical expression,

preferably one based only on reasonably elementary operations

(sums, products, factorials, etc. including "1 to n"-like

variable-term-amount sums/products). Like how the binomial

coefficients, Eulerian numbers, Stirling numbers, and other

double-index integer sequences I've seen do.

Apr 9, 2011, 3:37:39 PM4/9/11

to

Oh, wait, though. That can be made into a math. formula:

floor((prod_{j=1...n} 2^(jN) + 1)/2^(kN)) mod 2^N

:)

But not in the kind of form I'm interested in, which doesn't

involve "mod". :)

Apr 9, 2011, 3:38:13 PM4/9/11

to

Or "floor".

Apr 9, 2011, 4:42:53 PM4/9/11

to

Am 08.04.2011 07:24 schrieb Gerry Myerson:

> In article

> <ca72d99c-5404-4bf0...@p16g2000vbi.googlegroups.com>,

> mike3 <mike...@yahoo.com> wrote:

>

>> Hi.

>>

>> Does there exist some kind of formula to count the number of ways to

>> write a number k as a sum of at most n distinct natural numbers taken

>> from the interval 1 to n inclusive? If so, what is it, and how is it

>> derived?

>

> It's the coefficient of x^k in the expansion of

> (1 + x) (1 + x^2) (1 + x^3) ... (1 + x^n)

> but I don't expect any simple formula for it.

>

> In article

> <ca72d99c-5404-4bf0...@p16g2000vbi.googlegroups.com>,

> mike3 <mike...@yahoo.com> wrote:

>

>> Hi.

>>

>> Does there exist some kind of formula to count the number of ways to

>> write a number k as a sum of at most n distinct natural numbers taken

>> from the interval 1 to n inclusive? If so, what is it, and how is it

>> derived?

>

> It's the coefficient of x^k in the expansion of

> (1 + x) (1 + x^2) (1 + x^3) ... (1 + x^n)

> but I don't expect any simple formula for it.

>

:-)

Just the retranslation into the original problem, I suppose ...

<G>

Apr 9, 2011, 7:51:31 PM4/9/11

to

On Apr 9, 2:42 pm, Gottfried Helms <he...@uni-kassel.de> wrote:

> Am 08.04.2011 07:24 schrieb Gerry Myerson:

>

> > In article

> > <ca72d99c-5404-4bf0-b5e4-5d04d4892...@p16g2000vbi.googlegroups.com>,> Am 08.04.2011 07:24 schrieb Gerry Myerson:

>

> > In article

> > mike3 <mike4...@yahoo.com> wrote:

>

> >> Hi.

>

> >> Does there exist some kind of formula to count the number of ways to

> >> write a number k as a sum of at most n distinct natural numbers taken

> >> from the interval 1 to n inclusive? If so, what is it, and how is it

> >> derived?

>

> > It's the coefficient of x^k in the expansion of

> > (1 + x) (1 + x^2) (1 + x^3) ... (1 + x^n)

> > but I don't expect any simple formula for it.

>

> :-)

>

> Just the retranslation into the original problem, I suppose ...

>

> <G>

Actually, it came from a seemingly different problem, that of solving

a_1 = 1

a_n = sum_{m=1...n-1} u^n a_m.

for the coefficients of u^n. Yet apparently this is equivalent, and

a_n = prod_{m=1...n} (1 + u^m).

Apr 9, 2011, 7:56:50 PM4/9/11

to

Whoops, that should be:

a_n = sum_{m=1...n-1} u^(n-1) a_m

so apparently,

a_n = u^(n-1) prod_{m=1...(n-2)} (1 + u^m)

(remembered it wrong)

(Interesting side question: ho could I derive the second equation from

the first? Know any techniques for problems like this?)

Apr 9, 2011, 8:09:29 PM4/9/11

to

Hi, mike3:

Your question is about the restricted partitions of

k involving at most n distinct summands ("parts").

achille's note references OEIS sequence A000009,

concerning partitions into any number of distinct

parts (equiv. by Euler to the number of partitions

of the same number into odd parts).

There has been some recent (Jan. 2011) progress on

unrestricted partitions:

http://www.aimath.org/news/partition/

yielding a finite exact (non-recursive) formula to

count these! So it would be premature to exclude

that something of the kind is possible for the

specific count you've identified. However I think

it is fair to say that none is yet known, and it

would represent a nice publishable note if one

were found.

regards, chip

Apr 9, 2011, 9:32:43 PM4/9/11

to

mike3 <mike...@yahoo.com> wrote:

It is.

"Shifting" in this case is division by power-of-2.

"Masking" is remainder mod power-of-2.

--

[When complaining loudly about someone's arithmetic:]

"Androcles" <Headm...@Hogwarts.physics_ae>, 30 Dec 2010 10:53 UTC:

> Einstein's calculation is tau = t * sqrt(1-v^2/c^2),

> ref: http://www.fourmilab.ch/etexts/einstein/specrel/www/figures/img61.gif

> 2.2usec * sqrt(1-0.999^2) = 0.098362 usec

> and NOT the measured 64 usec.

You have got t and tau around the wrong way.

-- Peter Webb, 31 Dec 2010

[And later:]

The only error is Einstein's, you snipping ignorant cunt.

-- "Androcles" <Headm...@Hogwarts.physics_2011j>, 07 Jan 2011 04:20 UTC

Apr 10, 2011, 3:29:32 PM4/10/11

to

And that formula looks to be extremely non-trivial, so

the one for this could likely be just as bad...

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu