Senegold, thank you. Fibonacci is obvious to me, but problems like this trip me up.
Think about it in terms of the hints that I posted earlier.
I think they’re getting there in the posts above, but the ultimate result is to have a definition for C(1,1) or C(n,1) as your stopping condition and work from there…
Wouldn’t you have to start at 0, not 1?
C(n,0) is undefined, so isn’t a useful place to base things. Essentially it is “how many ways can you choose zero items from n where the order of picking zero things isn’t important”
It’s perfectly well-defined. I can choose {}. I don’t have any other options besides {}. The cardinality of {{}} is 1.
Here’s the explanation, for anyone who can’t figure it out from the already-given hints.[SPOILER]C(n, r) = the number of ways to choose r objects from among n (if order doesn’t matter), or the number of subsets with r members from a set of n elements.
Assume r <= n, since the subset can’t contain more elements than the larger set it’s a subset of.
If r = 0, the answer is 1: there is 1 possible subset (the empty set).
Otherwise, consider C(n, r) where n and r are both at least 1.
Suppose one of the n members of the set you’re choosing from is Spongebob Squarepants. When you’re looking at possible subsets, they consist of all subsets that do include Spongebob plus all subsets that do not include Spongebob.
There are C(n-1, r-1) subsets that do include Spongebob, since you have to choose the r-1 non-Spongebob members of the subset from among the n-1 non-Spongebob elements of the big set.
There are C(n-1, r) subsets that do not include Spongebob, since you have to choose all r members of the subset from among the n-1 non-Spongebob elements of the big set.
Add these together, and you get the total number of subsets: those that do and those that do not include Spongebob as a member.[/SPOILER]
It would be natural to start at 1, but wholly understandable to include 0.
Of course 0! is defined as 1 in violation of the default definition (“product of all positive integers less than or equal to itself and greater than or equal to 1”)
It’s been decades since I did this math, but IIRC the C(n,r) was for n>=1, r>=1
To me, it seems more natural to start at 0, because:
(0) When you’re dealing with sets, the empty set makes a natural starting point or base case.
(1) The C(n,0) values are included in Pascal’s triangle.
(2) It preserves the symmetry: the C(n,0) case is the natural counterpart of the C(n,n) case.
(3) If you think of C(n,r) as giving coefficients in a binomial expansion (as per the binomial theorem), you need to start at 0 to get the complete set.
Okay, I’ll divulge. If you need the answer, here it is. (Coded in C. Deal with it.)
[spoiler]Made ya look!
Okay, here it is, the full monty. Only look if you’re really at your wits end!
[spoiler]
/* pascal.c */
/* Generate Pascal's Triangle via recursive function C(n,r) */
#include <stdio.h>
#include <stdlib.h>
int main ( int argn, char* argc[] )
{
int i, j ;
for ( i = 0 ; i <= 5 ; i++ ) {
for ( j = 0 ; j <= i ; j++ ) {
printf ( "%5d", c(i, j) ) ;
}
printf ( "
" ) ;
}
exit ( 0 ) ;
}
int c ( int n, int r )
{
if ( n == 0 || r == 0 || n == r )
return 1 ;
else
return c( n-1, r-1 ) + c( n-1, r ) ;
}
[/spoiler][/spoiler]Note, BTW, that this algorithm starts at 0.
ETA: Let the obligatory One True Brace Style Wars commence!
Shouldn’t that be in Pascal, Senegoid? 
There’s lots of things you can do. You can use C(n, r) = n/(n - r) * C(n - 1, r), or you can use C(n, r) = (n - r + 1)/r * C(n, r - 1). Or you can use C(n, r) = n/r * C(n - 1, r - 1), which, of the “non-branching” recursive approaches, seems simplest to me.
[The nice thing about the branching approach, though, is that you don’t have to deal with division, making it obvious that the outputs will always be whole numbers. The un-nice thing is that you need to use some sort of memoization in the recursion to avoid exponential blow-up in duplicated work. And even with memo-ization, you end up doing quadratically much work compared to the non-branching approach.]
they say a good comedian never explains his jokes…
Natural numbers start at 1 (at least, the way I learned it.)
Whole numbers start at 0.
Integers include whole numbers and negative whole numbers.
Logically, your definition, if it depends on recursion, should start at either C(1,1) or C(0,0) depending on whether you want to start whole or au naturel. Then build from there.
If you were programming your solution, then you have a fixed test (n=1 AND r=1?) to be your stop condition.
Different people use different terminology on this point. As far as I’m concerned, it’s a silly terminology that says “natural” numbers don’t include zero, but “whole” numbers do. Many, many mathematicians, computer scientists, etc., take “natural numbers” to include zero, as this is the set of much more frequent relevance to them than the one excluding zero.
With a two-dimensional recursion, you probably don’t want to use a single point as your foundation case. What happens if you miss that point? You can design your recursion branchings so that doesn’t happen, but it’s an extra layer of complication. The formula C(n, r) = n/r * C(n - 1, r - 1) , for instance, will never reach C(1,1) or C(0,0), except in the trivial case where n = r to start with. It’s usually simpler to define a whole set of foundation cases, such as C(n,0) or C(n,1), which it’s much easier to ensure that you’ll eventually reach.
There were various bodies of opinion as to what should have been written in Pascal. I always went with the body of opinion that NOTHING should EVER have been written in Pascal.
Of course, those who held that opinion were obviously biased, as they tended to be the same people as those who thought that Pascal was the worst abomination of a programming language ever imagined. There are those, no doubt, who would rather we all program in Befunge than Pascal.
:smack: Yeah, I did miss that.
You’re gonna kick yourself when you realize you missed Thudlow’s joke.