[R] Recursion in R ...

[Duncan Murdoch]

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