[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
>> 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 ------------------------------
More information about the R-help
mailing list