Re: Help with a recursive equation
- From: James Waldby <no@xxxxx>
- Date: Sun, 01 Jul 2007 18:34:33 -0500
KP wrote:
On Jun 30, 9:25 pm, ...<mensana...@xxxxxxx> wrote:[re S(n,m) = sum (k: k is an n-bit binary number with m 1-bits) ...
On Jun 30, 9:17?am, ... <mensana...@xxxxxxx> wrote:
On Jun 30, 3:43?am, KP <silverphoenix...> wrote:
....S(n,m) = S(n-1,m) + (2^(n-1))* C(n-1,m-1) + S(n-1,m-1)
[snip code + S(8,4) test run]
## ok, here's our answer, calculated recursively ## 8925
##
## now, check by actually summing
## the 8 bit numbers that have 4 1-bits (popcount) ## 8925
Another verification of S(8,4) is as follows. S(n,m) + S(n, n-m) =
C(n,m) * ((2^n) -1) because for each number with m 1-bits there's
a complementary number with n-m 1-bits, so S(8,4) = C(8,4)*255/2
= 35 * 255 = 8925.
....
I was looking for any pointers to the closed form solution of the....
recursion.
Any pointers to methods or links would suffice if not the actual answer.
--
-jiw
.
- Prev by Date: Re: "Slashing" half a function
- Next by Date: Re: where to find a theorem
- Previous by thread: Re: Help with a recursive equation
- Next by thread: Re: Conway sequence and octonions
- Index(es):
Relevant Pages
|
