How many numbers of n digits exist if the sum of all digits is s?

Answer:
I've been trying to figure this out myself for a discrete structure class.

From the digging I've done online I've found this formula thus far:

if n is the number of digits, and s is the sum:
C(n+s-1 , n-1) where C denotes "choose" as in C(n , k) "n choose k" which can be solved by

(n! / [ (n-k)! * k! ] )

this seems to work for situations where the sum is < 10, or so claims the forum I found.

I whipped it all up into a scheme function if anyone wants to take advantage:

;;factorial: num -> num
;;finds factorial of num.
(define (factorial num)
(if (or (= num 1) (= num 0))
1
(* num (factorial (sub1 num)))))

;;==========================

;;xchy: num num -> num
;;the "n choose k" function
(define (xchy n k)
(/ (factorial n)
(* (factorial(- n k))(factorial k))))

;;==========================

;;n-dig&sum-s: num num -> num
;;finds the number of n digit combinations with sum s
;;C(n+s-1,n-1)
(define (n-dig&sum-s n s)
(xchy (sub1 (+ n s))
(sub1 n)))
First answer by ID1206393684. Last edit by ID1206393684. Question popularity: 1 [recommend question].