perplexus.info :: Numbers : Queue weight possibilities 2.

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}

Submitted by Jer

Rating: 3.0000 (1 votes)

Solution: (Hide)

For a problem with v votes and a score of s, F(v,s) can be found in several ways related to trinomial expansion.
by symmetry F(v,s)=F(v,-s)
F(0,0)=1
F(1,0)=1
F(1,1)=1
F(2,0)=3
F(2,1)=2
F(2,2)=1
F(3,0)=7
F(3,1)=6
F(3,2)=3
F(3,3)=1
F(4,0)=19
...
F(10,5)=1452
One way to find these is to look at (10...010...01)^n
Another way is to us the triangle where each term is the sum of the three numbers above:
1 1 1 1 1 2 3 2 1 1 3 6 7 6 3 1 1 4 10 16 19 16 10 4 1
To generate a single term, the following sum can be used
Sum(i from 0 to [(v-s)/2]) v!/((v-s-2i)!(s+i)!(i)!)
in ti83 calculator notation:
sum(seq(V!/(V-S-2I)!/(S+I)!/(I)!,I,0,int((V-S)/2))
Where V and S have been stored previously.
See also http://en.wikipedia.org/wiki/Trinomial_expansion

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
re(2): solution -- recurrences	Charlie	2007-05-23 16:00:10
re: solution -- recurrences	Charlie	2007-05-23 15:46:24
solution	Charlie	2007-05-23 15:40:13

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (12)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info