how can i find all possible combination of a decision tree?

hello all ,

for a project that i am doing

a team can score 1 goal or 2 goal per move , if someone told me that the end score between 2 teams was for example was 2:2

i need to find out all possible ways to reach that score

in this case its :

so in this case the answer is 60

but if someone told me that the end score was 3:2 or 8:8 how can i find out the number of possible ways to reach that score?

Thanks joe

[jgg]

I'm not sure what the answer is here, but it seems like this would be easiest if you augment the scores with a zero score, then add the rule if that last round 0 was scored, then this round zero cannot be scored, and have the teams alternate.

Then, you could just write a program to solve this recursively using a tree transit algorithm with halting criteria that stop if it reaches the desired score or encounters two sequential zero moves.

I'd bet there's a concise analytical answer, though.

Answer 1

[arich82]

There's a very good chance I've made several errors here, but this might get you started:

We seek the final score of a:b.

We'll first consider the rounds when Team A scores independently from the rounds when Team B scores. (I'm assuming that only one team can score per round, and one team MUST score; the scoring team can earn one or two points [never zero].)

If Team A earned only one point in each of its scoring rounds, it would need a rounds to achieve a points. In general, it needs at most a scoring rounds, and at least ceil(a/2) scoring rounds.

Let n1 be the number of scoring rounds where Team A scores one point, and n2 the number of two-point rounds; clearly a = 1*n1 + 2*n2, with 0 <= n1 <= a, 0 <= n2 <= floor(a/2), and the total nrounds = n1 + n2.

For a given pair of n1 and n2, the number of possible ways for Team A to achieve a points is (n1 + n2)!/(n1!*n2!) (I think; please correct me if I'm wrong...). [To compute this, I thought about how to assign the values 1:nrounds to two groups: one with n1 spots, and one with n2 spots.]

To compute the above, consider the function:

function out = nways(score)
% out(:, 1) = nrounds to achieve score
% out(:, 2) = number of possible ways to achieve score in nrounds
N2 = 0:floor(score/2);
out = NaN(numel(N2), 2);
for k = 1:numel(N2)  % for n1 = mod(a, 2):2:a
    n2 = N2(k);
    n1 = score - 2*n2;
    out(k, :) = [n1 + n2, factorial(n1 + n2)/(factorial(n1) * factorial(n2))];
end
end % function nways

I haven't had time to verify the rest, but see if this code dump works. I'll try to check back on Monday.

a = 2;
b = 2;
out_a = nways(a);
out_b = nways(b);

count = 0;
for ka = 1:size(out_a, 1)
    nrounds_a = out_a(ka, 1);
    nways_a = out_a(ka, 2);

      for kb = 1:size(out_b, 1)
          nrounds_b = out_b(kb, 1);
          nways_b = out_b(kb, 2);

          count = count + nways_a*nways_b*factorial(nrounds_a + nrounds_b)/(factorial(nrounds_a) * factorial(nrounds_b));
      end
  end