D******r
发帖数: 25 | 1 Given I>=0, J>=0, K>=0, and n
Find the number of distinct triplet (i,j,k) such that
0<=i<=I
0<=j<=J
0<=k<=K
i+j+k = n
Is it possible to derive a function F(n) which is the number of these
distince triplets in terms of I,J,K, and n? | l*****e
发帖数: 65 | 2 这问题看上去很经典，应该有现成答案，不过我解不出来。
不妨设I,J,K<=n. 否则可由n代替。
考虑i,j,k中出现0的情况，有递推
F(n;I,J,K)= F(n-3; I-1,J-1,K-1)
+ F(n-2; I-1,J-1)+F(n-2; J-1,K-1) + F(n-2; K-1,I-1).
而 F(n; I,J)可以显式表达， 比如很土的一个：当I+J>=n时，
I+J-n-epsilon 其中epsilon =1 if n偶 且 I>= n/2 且 J>= n/2.
=0 otherwise.
看到epsilon,然后我就知难而退了。。。
| m*********a
发帖数: 2000 | 3 should be n+3 choose 3?
something like that.
【在 D******r 的大作中提到】
: Given I>=0, J>=0, K>=0, and n
: Find the number of distinct triplet (i,j,k) such that
: 0<=i<=I
: 0<=j<=J
: 0<=k<=K
: i+j+k = n
: Is it possible to derive a function F(n) which is the number of these
: distince triplets in terms of I,J,K, and n?
| b*****d
发帖数: 7166 | 4 w=min(I+J,K,n)
F(n)=sum_{a=0}^w min(I,J,a)
没检查啊 | D******r
发帖数: 25 | 5 当n<＝min(I,J,K) 的时候就是 n+2 choose 2，
当这个条件不满足的时候，变的很messy，好像很难搞出一个漂亮的东西出来。。。
【在 l*****e 的大作中提到】
: 这问题看上去很经典，应该有现成答案，不过我解不出来。
: 不妨设I,J,K<=n. 否则可由n代替。
: 考虑i,j,k中出现0的情况，有递推
: F(n;I,J,K)= F(n-3; I-1,J-1,K-1)
: + F(n-2; I-1,J-1)+F(n-2; J-1,K-1) + F(n-2; K-1,I-1).
: 而 F(n; I,J)可以显式表达， 比如很土的一个：当I+J>=n时，
: I+J-n-epsilon 其中epsilon =1 if n偶 且 I>= n/2 且 J>= n/2.
: =0 otherwise.
: 看到epsilon,然后我就知难而退了。。。
:
| y*****0
发帖数: 1189 | 6 (n+2 choose 2) - ( n+2-I -J -K choose 2)
use 2 extral elements to break n to 3 group
if I+J+K >m, disccuss if I+J>m
...
it is not tricky but has several conditions
【在 D******r 的大作中提到】
: Given I>=0, J>=0, K>=0, and n
: Find the number of distinct triplet (i,j,k) such that
: 0<=i<=I
: 0<=j<=J
: 0<=k<=K
: i+j+k = n
: Is it possible to derive a function F(n) which is the number of these
: distince triplets in terms of I,J,K, and n?
| W******r
发帖数: 789 | 7 我觉得很难得出一个用I,J,K和n表达的简洁的公式。最多只能得到if I,J,K is such
such then F(n) is such such这样的公式。 | f*******i
发帖数: 1049 | |
|
