All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Queue weight possibilities 2. (Posted on 2007-05-23)
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}

 See The Solution Submitted by Jer Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 1 of 3

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         3A0                                         11                               1         1         12                     1         2         3         2         13           1         3         6         7         6         3         14           4        10        16        19        16        10         45          15        30        45        51        45        30        156          50        90       126       141       126        90        507         161       266       357       393       357       266       1618         504       784      1016      1107      1016       784       5049        1554      2304      2907      3139      2907      2304      155410       4740      6765      8350      8953      8350      6765      474011      14355     19855     24068     25653     24068     19855     1435512      43252     58278     69576     73789     69576     58278     4325213     129844    171106    201643    212941    201643    171106    12984414     388752    502593    585690    616227    585690    502593    38875215    1161615   1477035   1704510   1787607   1704510   1477035   116161516    3465840   4343160   4969152   5196627   4969152   4343160   346584017   10329336  12778152  14508939  15134931  14508939  12778152  1032933618   30759120  37616427  42422022  44152809  42422022  37616427  3075912019   91538523 110797569 124191258 128996853 124191258 110797569  9153852320  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   return100   for A=0 to 20103       locate 1,A+1104       print A105       if A<3 then Lim=A:else Lim=3110       for B=-Lim to Lim120          locate 35+10*B,A+1130          gosub 15140          print using(10,0),T;150       next160   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 A0           11           1         12           3         2         13           7         6         3         14          19        16        10         4         15          51        45        30        15         5         16         141       126        90        50        21         6         17         393       357       266       161        77        28         78        1107      1016       784       504       266       112        369        3139      2907      2304      1554       882       414       15610       8953      8350      6765      4740      2850      1452       61511      25653     24068     19855     14355      9042      4917      227712      73789     69576     58278     43252     28314     16236      807413     212941    201643    171106    129844     87802     52624     2774214     616227    585690    502593    388752    270270    168168     9309315    1787607   1704510   1477035   1161615    827190    531531    30673516    5196627   4969152   4343160   3465840   2520336   1665456    99621617   15134931  14508939  12778152  10329336   7651632   5182008   319831218   44152809  42422022  37616427  30759120  23162976  16031952  1017174619  128996853 124191258 110797569  91538523  69954048  49366674  3209909420  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   return100   for A=0 to 20103       locate 1,A+1104       print A105       if A<6 then Lim=A:else Lim=6110       for B=0 to Lim120          locate 10*B+5,A+1130          gosub 15140          print using(10,0),T;150       next160   next`

Edited on May 23, 2007, 3:41 pm
 Posted by Charlie on 2007-05-23 15:40:13

 Search: Search body:
Forums (0)