Is there a formula to count this?
mike3
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
<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
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
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
And I also don't have access to those journals, either.
k...@kymhorsell.com
...
> 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
> 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
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
Or "floor".
Gottfried Helms
> 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
> 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
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
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
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
And that formula looks to be extremely non-trivial, so
the one for this could likely be just as bad...