Math question I wanted help with.

[Traab]

Ok, this is a multi parter, and I would like it if someone could also show me how the answer is arrived at so in future problems I can do it myself.

Say I have a list of 25 numbers. How many different combinations of those numbers can I make using each digit AT MOST once? Meaning I can do a 1, or a 1,2, or I can do 1-25 and anywhere in between. But I cant do say, 1,1,2. And how do i figure out the math on this sort of thing. I used to know it but its been too many years and im not even sure how to search for it.

[Manga Shoggoth]

I may be grossly misteading the question here, but if you can't repeat digits then the absolute range you can produce is (depending on your position with leading zeroes) 0 - 9876543210.

Thus the total number of combinations should be


9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 (or 9 * 9!).
The reason it isn't 10! is because we can't have 0 as the leading digit.

EDIT: Explanation:


We have 9 possibilities for the leading digit (1 - 9, we can't use 0)
We have 9 possibilities for the second digit (0, plus the remaining 8 digits)
The number of successive digits then goes down by 1 each time until we reach 1.


This assumes that the set of numbers you have contains all the digits 0 - 9. If there are fewer than this the chain is shorter, so if we had say, 0, 1, 2, 4 then we get:


3 * 3 * 2 * 1

And of we had 1, 2, 4, 5 (ie, 4 digits available, no zero) we would have:


4 * 3 * 2 * 1

[Darth Credence]

Does the order in which the numbers are listed matter, i.e. is 1-2-3 different from 2-1-3?
Based on what you have written, I'll assume unordered. If that is the case, then IIRC the formula would be the addition of all "n choose k" for the set (sum all n choose k for k=1 to n). "N choose k" is the formula for how many possible combinations of k objects there are in a set of n total. The formula is n!/(k!(n-k)!).

Assuming I made my spreadsheet correctly, the answer to your question would be 33,554,431 different combos.

Edit: Manga Shoggoth got in while I was making a spreadsheet, and now I don't know if I read you correctly. Are you talking about each number basically being an object, which is what I assumed?

[kurokotetsu]

Combinatronics, that is the branch of mathematics you want. I think that the solution is (the other solutions asume you use all the numbers):

If there ara permutations (order matters) then for each term there is n!/(n-k)!, where n is the total and k is the amount that you choose (if you only choose one number there are 25 diferrent ways of choosing one of 25, if you choose two there are 25*24 wyas, etc.). The sum over all k={1,2,...,25} gives you your answer.

If the order doesn't matter (combinations) then the formula used is n!/(k!*(n-k)!) and you must add from all the k.

The number itself is just a matter of doing the numbers.

[Traab]

I may be grossly misteading the question here, but if you can't repeat digits then the absolute range you can produce is (depending on your position with leading zeroes) 0 - 9876543210.

Thus the total number of combinations should be


9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 (or 9 * 9!).
The reason it isn't 10! is because we can't have 0 as the leading digit.

EDIT: Explanation:


We have 9 possibilities for the leading digit (1 - 9, we can't use 0)
We have 9 possibilities for the second digit (0, plus the remaining 8 digits)
The number of successive digits then goes down by 1 each time until we reach 1.


This assumes that the set of numbers you have contains all the digits 0 - 9. If there are fewer than this the chain is shorter, so if we had say, 0, 1, 2, 4 then we get:


3 * 3 * 2 * 1

And of we had 1, 2, 4, 5 (ie, 4 digits available, no zero) we would have:


4 * 3 * 2 * 1

No, what I meant was you could only use each number 1-25 a single time in each combination at most. All of these count as combinations.
1
1,2,3
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 ,21,22,23,24,25.

However, 1,2,1 does not count as it uses the number 1 twice.

[kurokotetsu]

No, what I meant was you could only use each number 1-25 a single time in each combination at most. All of these count as combinations.
1
1,2,3
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 ,21,22,23,24,25.

However, 1,2,1 does not count as it uses the number 1 twice.

Like I said:

If the lists are permutations, order matters (1,2,3 different from 3,2,1) then you have
25 way of ordering 25 elements in one space, you have 25*24 ways of ordering 25 elements in two space... and n!/(n-k)! of ordering n elements (in this question 25) in k spaces. SO all you need to do is add all those. which is the sum since k=1 to k=n of n!(n-k)!.

If combinations (order doesn't matter) then just use the formula n!/(k!(n-k)!) instead of the one given above and do the same sum.

[Douglas]

Number of ways to select things from a set:
1) Is there a fixed number of items you're selecting? I.e., are you picking 4 items from the set, or "any number" of items from the set?

1A) Yes. Ok, now does order matter?

1Ai) Yes. Ok, what you need is the permutations (https://en.wikipedia.org/wiki/Permutation) formula.
1Aii) No. Ok, what you need is the combinations (https://en.wikipedia.org/wiki/Combination) formula.
1B) No. Ok, now does order matter?

1Bi) Yes. Ok, this will take quite a bit of computation. You know that permutations formula from 1Ai? Calculate that for every possible number of items you could select, and add them all up.
1Bii) No. Oh good, this will be easy. Each item can be either selected or not selected, and they're all completely independent of each other. That's 2 possibilities, multiplied for each item in the set. If there are N items in the set, the answer is 2N.

This case appears to be 1Bii, with N=25. Therefore, there are 225 possible selections, or 33554432.

[Traab]

Ah ok thanks for the help.