Re: [R] Recursion in R ...
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
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@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@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.
Re: [R] Recursion in R ...
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@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@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) [EMAIL PROTECTED]
Fax-to-email: +44 (0)870 094 0861
Date: 07-Jul-07 Time: 12:15:21
-- XFMail --
__
R-help@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.
Re: [R] Recursion in R ...
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
__
R-help@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.
Re: [R] Recursion in R ...
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)) }
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@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.
