[R] Recursion in R ...

[(Ted Harding)]

On 07-Jul-07 10:34:03, Uwe Ligges wrote:
> Alberto Monteiro wrote:
>> Ted Harding wrote:
>>> So I slickly wrote a recursive definition:
>>>
>>> Nnk<-function(n,k){
>>>   if(n==1) {return(k)} else {
>>>     R<-0;
>>>     for(r in (1:k)) R<-(R+Nnk(n-1,k-r+1)) # ,depth))
>>>   }
>>>   return(R)
>>> }
>>>
>> You are aware that this is equivalent to:
>> 
>> Nnk1 <- function(n, k) { prod(1:(n+k-1)) / prod(1:n) / prod(1:(k-1)) }
> 
> or
> 
> Nnk2 <- function(n, k) { gamma(n+k) / gamma(n+1) / gamma(k) }
> 
> or most easily:
> 
> Nnk3 <- function(n, k) choose(n+k-1, n)
> 
> Uwe Ligges

OK, I can recognise a negative binomial coefficient when I see one!

I'm wondering, though, what is the "natural" connection between
choose(n+k-1, n) and the statement of the original question:

  What is the number of distinct non-decreasing sequences of length n
  which can be made using integers chosen from (1:k)?
  (repetition allowed, of course)

(The fact that this leads to a recurrence relationship which is
satisfied by choose(n+k-1,n) is not what I mean by "natural"
-- I'm looking for a correspondence between such a sequence, and
a choice of n out of (n+k-1) somethings).

Ted.

>> aren't you?
>>  
>>> ON THAT BASIS: I hereby claim the all-time record for inefficient
>>> programming in R.
>>>
>>> Challengers are invited to strut their stuff ...
>>>
>> No, I don't think I can bet you unintentionally, even though
>> my second computer program that I ever wrote in life had to be
>> aborted, because it consumed all the resources of the computer.
>> 
>> Alberto Monteiro
>> 
>> ______________________________________________
>> R-help at stat.math.ethz.ch mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide
>> http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.
> 
> ______________________________________________
> R-help at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

--------------------------------------------------------------------
E-Mail: (Ted Harding) <ted.harding at nessie.mcc.ac.uk>
Fax-to-email: +44 (0)870 094 0861
Date: 07-Jul-07                                       Time: 12:15:21
------------------------------ XFMail ------------------------------