I need to estimate the number of possible permutations of a problem.

A way to do this, I suspect, is to randomly generate a decent amount of problems, and then find out how many were repeated. If there are a few repeated problems, then I know the number of permutations is high, and if there are a lot, then it's closer to the number of generated problems.

An example problem:

Enter the degree of the polynomial:

$-6y^2 + 2x^3 + 3x^2 - 4y^5$

Now imagine the exponents are randomly chosen numbers in a range: $n_1, n_2, n_3, n_4$. Every time I click a button, the problem is randomly generated.

$-6y^{n_1} + 2x^{n_2} + 3x^{n_3} - 4y^{n_4}$

What I want to do is estimate the number of possible permutations of this problem. How do I do that?

I need a general solution that I can apply to a bunch of different problems, some may have more variables.

Another example:

Ann has 10 apples and 5 friends. What's the highest number of apples she can give to each friend if she wants all of them to have the same number of apples.

The name Ann can be randomly chosen from a set of names (Ann, Ron, Rose, Joe, etc). The number of apples is random between 10 and 20. The fruit is also random (apples, oranges, bananas, etc), and the number of friends y also random between 3 and 7).

Whenever I press a button I get a randomly generated problem. Pressing the button many times ends up getting repeated problems. I suspect I can estimate the number of possible problems by generating a lot of random problems and seeing what's the rate of repetition. Is this true? If it is, do you know how?

  • $\begingroup$ what parts are permutable ? $\endgroup$ – Roddy MacPhee Apr 11 at 16:25
  • $\begingroup$ It depends on the problem, in the case I gave an example, the exponents are permutable. The first term is sometimes $-6y^3$, sometimes $-6y^7$, sometimes $-6y^4$ (the rest of the terms also vary). But it really depends on the problem, other problems have different possible permutations. $\endgroup$ – ArianJM Apr 11 at 16:40
  • $\begingroup$ Then perhaps there's no general formula, that will calculate faster than listing them all in some cases. Also, permutations can have fixed points or not, repetions, or not, restrictions or not, be cyclical or not, etc. $\endgroup$ – Roddy MacPhee Apr 11 at 17:06
  • $\begingroup$ @RoddyMacPhee I suspect there is. If I generate many random problems, and look at the rate of repetition of problems, I should be able to estimate the number of possible problems. There has to be a formula for that, I just can't think where to look for it, or what's it's name, or how to search for it. $\endgroup$ – ArianJM Apr 11 at 21:00
  • $\begingroup$ Suspecting, and knowing are completely different. it's bound from $n^y$ from above. That's the number of y-tuples in the lattice of size n in y dimensions. $\endgroup$ – Roddy MacPhee Apr 11 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.