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.
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?
And I also don't have access to those journals, either.
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)
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.
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". :)
Or "floor".
:-)
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).
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?)
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
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
And that formula looks to be extremely non-trivial, so
the one for this could likely be just as bad...