# [R] Recursion in R ...

(Ted Harding) ted.harding at nessie.mcc.ac.uk
Sat Jul 7 13:15:24 CEST 2007

```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
>> 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