[R] Recursion in R ...
Duncan Murdoch
murdoch at stats.uwo.ca
Sat Jul 7 13:55:55 CEST 2007
On 07/07/2007 7:15 AM, (Ted Harding) wrote:
> 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).
Colour the integers 1:k red and the integers 1:(n-1) black, and throw
them in a hat. Select n things out of the hat.
Put the red things in order: that's the strictly increasing subsequence.
Put the black things in order. Proceeding from smallest to largest, if
you see a black i, duplicate the i'th element in the current version of
the sequence.
For example, if k=5, n=4, you might draw red 2, 3 and black 1, 2, so
you'd build your sequence as
2 3
2 2 3
2 2 2 3
or you might draw red 1, 4, 5 and black 2, so you'd output
1 4 4 5
Duncan Murdoch
More information about the R-help
mailing list