When a problem is being voted on in the Perplexus queue, the journeymen and scholars post comments and vote on the problem. A "thumbs up" (TU) scores +1 point, a "thumbs down" (TD) scores -1, and a comment with no vote scores 0.
Part one of this problem, which deals with combinations of TU and TD votes can be found here.
Suppose a problem in the queue has A responses and a score of B. Find a formula that gives the number of possible permutations of TU's, TD's and nonvoting comments the problem has received.
Note: For example a problem with 3 responses and a score of +1 has six possibilities:
{+1,0,0}
{0,+1,0}
{0,0,+1}
{+1,+1,-1}
{+1,-1,+1}
{-1,+1,+1}
I don't think I can avoid Sigma notation:
As mentioned in the solution to the first QW problem, the lowest number of the majority opinion that can be present is |B|; that's when there are zero opposing votes. The remainder of the votes (A - |B|) are neutral.
The maximum number of votes for the majority opinion is [(A + |B|)/2]; that's when there are [(A + |B|)/2] - |B| opposing votes. This may or may not leave one neutral vote.
In any instance, for the given A and B, the numbers of the other votes (opposing and neutral) depend completely on the number of positive votes.
Define i as the number majority-agreeing votes in a particular case, under the conditions of A responses and a score of B. We are here interested in the ways in which the various TU's, TD's and neutrals can be arranged within the list of A members. The TU's are indistinguishable among themselves, as are the TD's and the neutrals.
There are, by definition, i majority votes. Then there are i - |B| minority votes, and A - (2*i - |B|) neutral votes. As any value for i is possible between |B| and [(A + |B|)/2], the solution is the sum:
Sigma{i=|B| to [(A + |B|)/2]} A! / (i! * (i - |B|)! * (A - (2*i - |B|))!)
The A! in the numerator takes into consideration the ways of rearranging all A responses, but since i of them are indistinguishable majority votes, i - |B| are indistinguishable minority votes and A - (2*i - |B|) are indistinguishable neutral comments, the ways of rearranging those within category are divided out, resulting in the summation above for all possible values of i.
Tabulating that for different values of A and B:
B: -3 -2 -1 0 1 2 3
A
0 1
1 1 1 1
2 1 2 3 2 1
3 1 3 6 7 6 3 1
4 4 10 16 19 16 10 4
5 15 30 45 51 45 30 15
6 50 90 126 141 126 90 50
7 161 266 357 393 357 266 161
8 504 784 1016 1107 1016 784 504
9 1554 2304 2907 3139 2907 2304 1554
10 4740 6765 8350 8953 8350 6765 4740
11 14355 19855 24068 25653 24068 19855 14355
12 43252 58278 69576 73789 69576 58278 43252
13 129844 171106 201643 212941 201643 171106 129844
14 388752 502593 585690 616227 585690 502593 388752
15 1161615 1477035 1704510 1787607 1704510 1477035 1161615
16 3465840 4343160 4969152 5196627 4969152 4343160 3465840
17 10329336 12778152 14508939 15134931 14508939 12778152 10329336
18 30759120 37616427 42422022 44152809 42422022 37616427 30759120
19 91538523 110797569 124191258 128996853 124191258 110797569 91538523
20 272290140 326527350 363985680 377379369 363985680 326527350 272290140
from
4 cls
5 goto 100
15 T=0
20 for P=abs(B) to int((A+abs(B))/2)
30 T=T+!(A)//(!(P)*!(P-abs(B))*!(A-(2*P-abs(B))))
40 next
50 return
100 for A=0 to 20
103 locate 1,A+1
104 print A
105 if A<3 then Lim=A:else Lim=3
110 for B=-Lim to Lim
120 locate 35+10*B,A+1
130 gosub 15
140 print using(10,0),T;
150 next
160 next
The score can go above 3 or below -3, so here are some more columns, recognizing that score +n has the same numbers as score -n:
B: 0 1 2 3 4 5 6
A
0 1
1 1 1
2 3 2 1
3 7 6 3 1
4 19 16 10 4 1
5 51 45 30 15 5 1
6 141 126 90 50 21 6 1
7 393 357 266 161 77 28 7
8 1107 1016 784 504 266 112 36
9 3139 2907 2304 1554 882 414 156
10 8953 8350 6765 4740 2850 1452 615
11 25653 24068 19855 14355 9042 4917 2277
12 73789 69576 58278 43252 28314 16236 8074
13 212941 201643 171106 129844 87802 52624 27742
14 616227 585690 502593 388752 270270 168168 93093
15 1787607 1704510 1477035 1161615 827190 531531 306735
16 5196627 4969152 4343160 3465840 2520336 1665456 996216
17 15134931 14508939 12778152 10329336 7651632 5182008 3198312
18 44152809 42422022 37616427 30759120 23162976 16031952 10171746
19 128996853 124191258 110797569 91538523 69954048 49366674 32099094
20 377379369 363985680 326527350 272290140 210859245 151419816 100640340
from
4 cls
5 goto 100
15 T=0
20 for P=abs(B) to int((A+abs(B))/2)
30 T=T+!(A)//(!(P)*!(P-abs(B))*!(A-(2*P-abs(B))))
40 next
50 return
100 for A=0 to 20
103 locate 1,A+1
104 print A
105 if A<6 then Lim=A:else Lim=6
110 for B=0 to Lim
120 locate 10*B+5,A+1
130 gosub 15
140 print using(10,0),T;
150 next
160 next
Edited on May 23, 2007, 3:41 pm
|
|
Posted by Charlie
on 2007-05-23 15:40:13 |
solution
