# Is there a formula to count this?

28 views

### mike3

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?

### Gerry Myerson

Apr 8, 2011, 1:24:56 AM4/8/11
to
In article
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)

### achille

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

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

### mike3

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?

### mike3

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

### k...@kymhorsell.com

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?

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)

### mike3

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

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.

### mike3

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". :)

### mike3

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

Or "floor".

### Gottfried Helms

Apr 9, 2011, 4:42:53 PM4/9/11
to
Am 08.04.2011 07:24 schrieb Gerry Myerson:
> In article
> 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>

### mike3

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

> >  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).

### mike3

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?)

### Chip Eastham

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

Hi, mike3:

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

### k...@kymhorsell.com

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.

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