Is there a formula to count this?

28 views
Skip to first unread message

mike3

unread,
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

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

achille

unread,
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)

A useful source for this topic will be OEIS's A000009's entry
( http://oeis.org/A000009 ) and the references there.

mike3

unread,
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

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

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

k...@kymhorsell.com

unread,
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

unread,
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

unread,
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

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

Or "floor".

Gottfried Helms

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

:-)

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

<G>

mike3

unread,
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>,

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

unread,
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

unread,
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

k...@kymhorsell.com

unread,
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

mike3

unread,
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