Re: Help with a recursive equation

On Jun 30, 3:43?am, KP <silverphoenix...@xxxxxxxxx> wrote:
Hi,

I derived this recursive equation myself when I was trying to come
up with a general equation for the sum of all binary numbers having
"n" digits with m 1's in them.

Let S(n,m) denote the sum I wish to find.

My recursion is

This isn't a recursion.

You haven't given a terminating condition,
S() will be called an infinite number of times.


S(n,m) = S(n-1,m) + (2^(n-1))* C(n-1,m-1) + S(n-1,m-1)

where ^ denotes "raised to the power of"

Could somebody give me any pointers or links that could help in
solving this?

And why recursion? Don't you know the answer is C(n,m)?

Nevertheless, you CAN do it recursively, but not
as shown.

First, lose the last term, + S(n-1,m-1).
This makes no sense, why do you care about
how many 3, 2 or 1 bit counts there are if
you're looking for 4?

Second, what are you trying to accomplish
here: + (2^(n-1))* C(n-1,m-1)? If you're
going to recursively count C(n-1,m-1)
instead of directly calculating C(n,m),
ok. But why the multiplication by 2^(n-1)?

Here's the proper way to do it.

# Python
import gmpy

def S(n,m):
# terminate recursion if n==0
# also, no point in asking how
# many counts if n not as large
# as m, we already know it's 0
if n==0 or n<m:
return 0
# the recursive call
s = S(n-1,m)
# the combination
c = gmpy.comb(n-1,m-1)
# for debugging
print '(%d %d)' % (n,m),c,s,c+s
return c+s

s = S(8,4)
print
print """ok, here's our answer, calculted recursively"""
print s

print
print """now, check using the non-recursive way"""
m = 4
n = 8
print gmpy.comb(n,m)

print
print """now, check by actually counting how
many 8 bit numbers have 4 1-bits (popcount)"""

correct = []
for i in xrange(2**n):
p = gmpy.popcount(i)
if p == 4:
correct.append(1)
print sum(correct)

## (4 4) 1 0 1
## (5 4) 4 1 5
## (6 4) 10 5 15
## (7 4) 20 15 35
## (8 4) 35 35 70
##
## ok, here's our answer, calculted recursively
## 70
##
## now, check using the non-recursive way
## 70
##
## now, check by actually counting how
## many 8 bit numbers have 4 1-bits (popcount)
## 70



Thanks in advance,

KP


.

Relevant Pages

  • Re: Simple recursive functions in Lisp
    ... you transfer control back to code that has already been run. ... recursion vs. iteration vs. tail-recursion debate. ... there is an implicit continuation argument that must be ... (loop for x in list sum x)) ...
    (comp.lang.lisp)
  • Re: Precedence of Logical Operators
    ... >> the sum of 1...n, because she didn't know that it was a correct ... I did the same thing with the fibonacci series when we were supposed to ... use recursion. ...
    (comp.lang.c)
  • Re: Brian Kernighan, maybe Im not worthy, maybe Im scum
    ... I got 79% on the test on Recursion, using C examples, at ... int example ... As a data structure, a call stack is most analogous to ... sum = sum + n; ...
    (comp.programming)
  • Re: folder size
    ... Check out filer.dll (ole class "filer.fileutil"). ... seconds, while I canceled the recursion approach, ... filer results in a files collection. ... or you just have to sum up each single files size. ...
    (microsoft.public.fox.programmer.exchange)
  • Re: Help with a recursive equation
    ... up with a general equation for the sum of all binary numbers having ... "n" digits with m 1's in them. ... This isn't a recursion. ... You haven't given a terminating condition, ...
    (sci.math)
Loading