Possible combinations

[Function]

Hello everyone

 

I'd like to know which formula can express the number of unique possibilities in which a number, consistent of [math]m[/math] cyphers and [math]n[/math] different numbers.

 

For example, a number with [math]n=3[/math] and [math]m=4[/math] can be written in 11 unique ways. [math]\left(=\frac{n!+m!}{2}-m\right)[/math]

Be [math]n=3[/math] and [math]m=3[/math], then there are 6 possibilities. [math]\left( = 3!\right)[/math]

Be [math]n=1[/math] and [math]m=3[/math], then there's only 1 possibility.

 

Thanks!

 

Function

Edited January 12, 2014 by Function

[imatfaal]

If by cypher you mean digits then I am not sure about your maths

 

3 digits 1 number = 3 combos

111

 

3 digits 3 numbers = 27 combos

111

222

333

112

113

122 ...

 

3 digits 3 repeats if no repeats allowed = 6 combos

123

132

213

231

312

321

 

but if repeats are not allowed how can you have m=4 ( 4 digits) with n=3 (3 different numbers); or are repeats allowed iff no of digits >different numbers. But if that is the case fr m=4 / n=3 you could have at least all the above 6 numbers with a one, a two or a three suffixed to them - that's min 18 without much work

 

So really not sure what you mean. Why not give a few examples to make it clear

[Function]

If by cypher you mean digits then I am not sure about your maths

 

3 digits 1 number = 3 combos

111

 

3 digits 3 numbers = 27 combos

111

222

333

112

113

122 ...

 

3 digits 3 repeats if no repeats allowed = 6 combos

123

132

213

231

312

321

 

but if repeats are not allowed how can you have m=4 ( 4 digits) with n=3 (3 different numbers); or are repeats allowed iff no of digits >different numbers. But if that is the case fr m=4 / n=3 you could have at least all the above 6 numbers with a one, a two or a three suffixed to them - that's min 18 without much work

 

So really not sure what you mean. Why not give a few examples to make it clear

 

 

Well, I do mean by "n" the number of different digits; and "m" the total amount of digits; n can thus never be larger than m, making 'your' maths invalid (27 combinations).

 

I'm afraid I also have to bust your first statement: a number consistent of 3 digits and only 1 'value', can only be formed in 1 unique way: e.g. 111.

 

Let me reform my original questions:

 

Give me a formula which gives the total amount of unique possibilities in which a number, consistent of m amount of digits, of which n are different, can be formed.

 

I give the example with m = 4 and n = 3:

 

1123

1132

1231

1213

1321

1312 (there are 6 unique possibilities)

 

2113

2131

2311 (there are only 3 unique possibilities)

 

3112

3121

3211 (there are only 3 unique possibilities)

 

Of course, this reasonning wouldn't be so... nice in probability maths: a first 1 isn't equal to a second 1 (e.g. with 2 coins of 1 euro: head-tails [math]\neq[/math] tails-head (first coin-second coin); but let's assume that in casu, a 1 stays a 1 and will forever be the same 1.

 

Maybe it's smart to tell you that "n" amount of different digits means, that every digit must be in the number: let n = 4, m = 7; with the digits = 3, 9, 7 and 2; then every digit (3, 9, 7 and 2) must be present in the number, something I'm afraid you didn't really get (what you did in your second reasonning)

Edited January 12, 2014 by Function

[imatfaal]

OK - thanks I think I get it now. Will have a think about the questions

HMM your example m=4 n=3 . The section with repeated 1s makes sense. But what is wrong with - for example the number 2213 or 3312? Both those numbers have three different digits in four spaces. Why can only the digit one be repeated?

[Function]

Ah yes, oversaw that. Let's make a new calculation..

 

1123

1132

1231

1213

1321

1312

1223

1232

1332

1323

 

Multiply by 3, I think, to give all possibilities? = 30 possibilities

 

More series must be made, however... there are 2 things I can come up with for now:

30 = (3!)(4+1) <=> u = (n!)*(m+1)

30 = 3! + 4! <=> u = n! + m!

 

With u = the number of possibilities in which a number, formed by m digits, of which n are different, can be formed.

Last one seems better; it seems to me that the first formula (u = (n!)*(m+1)) is just coincidential.

Edited January 12, 2014 by Function

[imatfaal]

At least on the same page now.

[Function]

Yes.. Nice page we're on

 

To find this formula I'm looking for, let n = 3 and m = 5:

 

11 123

11 132

11 213

11 231

11 321

11 312

12 311

12 131

12 113

13 211

13 121

13 112

21 113

21 131

21 311

23 111

31 112

31 121

31 221

32 111

 

==> 20 possiblities x 3 series (with each respectively 3x1, 3x2 and 3x3) = 60 possibilities

 

EDIT: there are way more possibilities; let there for example, be 2 times 1 and 2 times 2... There would be, as a consequence, 6 (= 3!) series: (3x1,1x2,1x3), (1x1,3x2,1x3), (1x1,1x2,3x3) (2x1,2x2,1x3), (2x1,1x2,2x3), (1x1,2x2,3x3).

 

Let me write down the second series.

Here is the second serie of possibilities:

 

11 223

11 232

11 323

13 221

13 212

13 122

31 221

31 212

31 122

12 312

12 321

12 231

12 213

12 123

12 132

21 312

21 321

21 231

21 213

21 123

21 132

 

There are, if I made no mistakes, 21 possibilities when both 2 and 1 may appear 2 times; multiply by 3 to get total possiblities of the (2,2,1)-series = 63 possibilities

 

Adding the 3x20 (from the (3,1,1)-series) gives: 63 + 60 = 123 = 5! + 3

 

My presumption: a number, consistent of "m" amount of numbers, of which "n" are different, can be written in (m! + n) possibilities.

 

--> PROBLEM: 123, 132, 213, 231, 321, 312 states that if m = 3 and n = 3, then u = 6, not 3! + 3 = 9.

 

So, we need to find another formula.

I redid my maths, and found this:

 

• n = 3, m = 3 => u = 6
• n = 3, m = 4 => u = 36
• n = 3, m = 5 => u = 123

Edited January 12, 2014 by Function

[imatfaal]

OK - I always start simple. I enumerated various m for n=2

 

n m variants

2 2 2

2 3 6

2 4 14

2 5 30

2 6 78

Edited January 12, 2014 by imatfaal
CHANGED DATA (twice!)

[Function]

OK - I always start simple. I enumerated various m for n=2

 

n m variants

2 2 2

2 3 4

2 4 13

2 5 30

2 6 78

 

I got u = 14 for n = 2, m = 4:

 

1112

1121

1211

2111

1122

1212

1221

2112

2121

2211

1222

2122

2212

2221

 

And u = 6 for n = 2, m = 3:

 

112

121

211

221

212

122

Edited January 12, 2014 by Function

[imatfaal]

Sorry - added up wrong. Had amended my table

[Function]

Yet, the problem persists... Is there a formula which expresses the number of possibilities in function of n and m?

[imatfaal]

Nothing springs to mind yet. There will be a formula - I looked at something similar a long long time ago. Finally I realised it was analogous to another problem which lead to a solution.

[Function]

Allow me to write down everything what comes up in my mind when trying to make a link between n, m and u:

 

EDIT: oh god... I wrote down everything and now.. poof.. it's gone.

Edited January 12, 2014 by Function

[John]

OK - I always start simple. I enumerated various m for n=2

 

n m variants

2 2 2

2 3 6

2 4 14

2 5 30

2 6 78

I think the last entry is incorrect, unless I'm completely misunderstanding the problem. With two digits, there are only 2^m possible numbers period, and 2^6 = 64 < 78. Given the pattern and some reasoning, I think the entry here should be 62, i.e. 2^6 - 2, which is the total possible variants minus the ones consisting of only one digit.

 

This may help with finding a general formula, but I'm at work and can't really look into it right now.

[imatfaal]

I am not doing well with my sums. That's over half wrong!

[Function]

Don't sweat it. It's a very delicate subject and an error is very easily made. Some results may be overlooked, some may be taken in account twice.

 

I've attached a file I made, in order to find the formula. In the document, I assume that 1 and 1 aren't the same one Get it? It's like marbles: there are 5 red marbles in a sack and 7 black. The chance that I pick a random red marble, is 5/12, whereas the chance that I pick the third red marble is 1/12. So even in this case, it's best to imply every possibility and substract the equal results.

 

Why is it better? Well, to more easily find the formula. (It's easier to say what the number of possibilities are when e.g. 1112, 1112, 1112 and 1112 are considered different and substract the rest later)

Possib.pdf

Edited January 12, 2014 by Function

[John]

If we allow multiple counting, I think the formula is [math]{{m}\choose{n}}{n!} \times n^{m-n}[/math].

My reasoning is as follows: In order to ensure that we have at least one of each digit, we must reserve [math]n[/math] spaces to each hold a different digit. Given an [math]m[/math]-digit number, there are [math]m \choose n[/math] ways to select these spaces, and for each of these, the number of possible orderings of our [math]n[/math] digits is [math]n![/math], thus the [math]n! {{m}\choose{n}}[/math].

For each of these, the remaining [math]m-n[/math] spaces can be occupied by any of our [math]n[/math] digits, giving us [math]n^{m-n}[/math] possibilities.

This would provide a solution to the original problem, except that certain possibilities are counted multiple times. For example, given [math]m = 4[/math] and [math]n = 3[/math], the possible spacings 123_ and 12_3 will both include 1233.

So for the case of [math]m = 4[/math] and [math]n = 3[/math], we'd have [math]{{4}\choose{3}}(3!)(3^{1}) = 4(6)(3) = 72[/math]. In this example, the actual solution is 36, so the formula doubles the desired result. But for example, if [math]m = 6[/math] and [math]n = 2[/math], then the formula yields 480 while we know the answer is 62. Finding a modification to subtract the excess for general [math]m[/math] and [math]n[/math] is proving trickier for me than it seems it should be. I'm probably missing something simple.

Note that I'm not absolutely confident in this, but I think my reasoning is sound.

 

 

Edit (because the forum software won't let me put this into a new post):

 

I may be on to something, but it's a tad complicated. If we let [math]f(m,n)[/math] be the function we're looking for, then I think

 

[math]f(m,n) = \begin{cases}1 & n = 1 \\ n^{m} - \sum_{i=1}^{n-1} \left({{n}\choose{i}} f(m,i)\right) & n>1\end{cases}[/math]

 

For instance, consider m = 4. Now, as mentioned previously, m cannot be less than n. Using the definition I just gave then, we have

 

[math]\begin{array}{rcl}f(4,1) & = & 1\end{array}[/math]

[math]\begin{array}{rcl}f(4,2) & = & 2^{4} - \sum_{i=1}^{1} \left({{2}\choose{i}} f(4,i)\right) \\ & = & 2^{4} - {{2}\choose{1}}f(4,1) \\ & = & 2^{4} - 2(1) \\ & = & 14\end{array}[/math]

 

[math]\begin{array}{rcl}f(4,3) & = & 3^{4} - \sum_{i=1}^{2} \left({{3}\choose{i}} f(4,i)\right) \\ & = & 3^{4} - \left[{{3}\choose{1}}f(4,1) + {{3}\choose{2}}f(4,2)\right] \\ & = & 3^{4} - 3(1) - 3(14) \\ & = & 36\end{array}[/math]

 

[math]\begin{array}{rcl}f(4,4) & = & 4^{4} - \sum_{i=1}^{3} \left({{4}\choose{i}} f(4,i)\right) \\ & = & 4^{4} - \left[{{4}\choose{1}}f(4,1) + {{4}\choose{2}}f(4,2) + {{4}\choose{3}}f(4,3)\right] \\ & = & 4^{4} - 4(1) - 6(14) - 4(36) \\ & = & 24\end{array}[/math]

 

each of which matches my manual counts.

 

If you want, test this for other m's and n's. I've tried a few and it seems to work out, but I've by no means proved that this formula is correct.

Edited January 13, 2014 by John

[Function]

Indeed somewhat complicated. I shall digest it for now and look into it wednesday afternoon.

[John]

It may help if I explain my reasoning.

 

If we have n digits, and we want numbers of length m, then the number of possible numbers is n^m. However, this will include all the numbers that don't contain at least one of each digit, so we'll need to subtract those, leaving us with only the numbers that do contain at least one of each digit.

 

Of course, if n = 1, then it's pretty obvious that there is only one possible number.

 

But now consider the case where n = 2. Then we have 2^m possible numbers, but we must subtract the numbers that don't contain both digits, i.e. the numbers that contain only one digit. Since we have two digits, we can split this, essentially, into two cases of n = 1, and we've already shown that for n = 1, the number of possibilities is 1. Therefore, we have 2^m - 2(1) numbers that contain at least one of each digit.

Moving on to n = 3, we see that we have 3^m total possible numbers, but again we must subtract the numbers that don't contain all three digits. In this case, what needs to be subtracted are the numbers containing only one of the digits and the numbers containing only two of the digits. The first is fairly easy, as using the previous reasoning, we can see that this amounts to three cases of n = 1, so we first subtract 3(1), giving us 3^m - 3. To determine what else we must subtract, we must realize there are [math]{3\choose2} = 3[/math] ways to choose 2 of the three digits, so we also have three cases of n = 2 to subtract. From our discussion of n = 2, we see that this amounts to 3(2^m - 2), so in the end we have 3^m - 3(1) - 3(2^m - 2) total numbers that contain at least one of each digit.

For n = 4, we follow the same reasoning. Now we have our 4^m total possibilities, minus the 4 cases of n = 1, minus [math]{4\choose2} = 6[/math] cases of n = 2. We must finally subtract the cases of n = 3, which amount to [math]{4\choose3} = 4[/math]. This leaves us with the final formula 4^m - 4(1) - 6(2^m - 2(1)) - 4(3^m - 3(1) - 3(2^m - 2(1))).

Clearly, as n gets larger, the final formula becomes pretty unwieldy, which is why I defined it recursively in my previous post. What you may also notice is we're ending up with binomial coefficients. So for n = 2, we subtract 2 times some stuff. For n = 3, we subtract 3 times some stuff and 3 times some other stuff. For n = 4, we subtract 4 times some stuff, then 6 times some other stuff, then 4 times still other stuff. And so on.

Edited January 13, 2014 by John

[imatfaal]

that's gonna take some reading - but looks good

[John]

I don't know if anyone is still worried about this problem, but I was thinking about it today, and I've found what I believe is an accurate formula that may be easier to work with than the one I gave before. Here it is:

[math]f(m,n) = {n \choose n}n^{m} - \left[{n \choose {n-1}}(n-1)^{m}-\left[{n \choose {n-2}}(n-2)^{m}-\ldots-\left[{n \choose 2}2^{m}-{n \choose 1}1^{m}\right]\right]\right][/math]

 

This can be written as the following sum:

 

[math]f(m,n) = \sum_{i=0}^{n-1}\left[(-1)^{i}{n \choose {n-i}}(n-i)^{m}\right][/math]

 

The expanded formula can be simplified a bit if we realize that [math]{n \choose n}n^{m} = n^{m}[/math] and [math]{n \choose 1}1^{m} = n[/math], but I didn't make those simplifications, in hopes that the pattern is clearer than it would have been otherwise.

 

Example: Consider again the case of m = 4, n = 1 to 4. Then we have

 

[math]\begin{array}{rcl}f(4,1) & = & \sum_{i=0}^{0}\left[(-1)^{i}{1 \choose {1-i}}(1-i)^4\right] \\ & = & (1){1 \choose 1}(1)^{4} \\ & = & 1\end{array}[/math]

 

[math]\begin{array}{rcl}f(4,2) & = & \sum_{i=0}^{1}\left[(-1)^{i}{2 \choose {2-i}}(2-i)^4\right] \\ & = & (1){2 \choose 2}(2)^{4} + (-1){2 \choose 1}(1)^{4} \\ & = & 16 - 2 \\ & = & 14\end{array}[/math]

 

[math]\begin{array}{rcl}f(4,3) & = & \sum_{i=0}^{2}\left[(-1)^{i}{3 \choose {3-i}}(3-i)^4\right] \\ & = & (1){3 \choose 3}(3)^{4} + (-1){3 \choose 2}(2)^{4} + (1){3 \choose 1}(1)^{4} \\ & = & 81 - 48 + 3 \\ & = & 36\end{array}[/math]

 

[math]\begin{array}{rcl}f(4,4) & = & \sum_{i=0}^{3}\left[(-1)^{i}{4 \choose {4-i}}(4-i)^4\right] \\ & = & (1){4 \choose 4}(4)^{4} + (-1){4 \choose 3}(3)^{4} + (1){4 \choose 2}(2)^{4} + (-1){4 \choose 1}(1)^{4} \\ & = & 256 - 324 + 96 - 4 \\ & = & 24\end{array}[/math]

 

as we did using the other formula.

 

Reasoning: I was thinking again about the general method of taking all possible m-length numbers given n distinct digits and subtracting the ones that don't meet our criteria. It occurred to me that one method might be to simply subtract off the numbers that only contain (n-1) of the available digits. We'd have to subtract this for each possible combination of (n-1) digits, i.e. we'd need n^m - C(n, n-1)(n-1)^m.

 

But of course, this subtracts off too much, since some numbers will be counted multiple times (for instance, given m = 5 and n = 4, the digit combinations 123 and 124 will both include numbers like 12212). What must be done, then, is to exclude numbers containing only (n-2), (n-3), ..., 1 of the available digits, saving them to be subtracted later. This is similar to the reasoning used in the formula I gave a few posts back. Thus we have n^m - [C(n, n-1)(n-1)^m - [C(n, n-2)(n-2)^m - ... - [C(n, 2)(2)^m - C(n,1)]]].

I don't know if this explanation is extremely clear, but hopefully it conveys the idea to some extent.

Edited January 20, 2014 by John

[Function]

It's clear. A formula is what I wanted and a formula is what you gave me.

Thanks to everyone for their contributions to resolving this problem.

[Function]

I don't know if anyone is still worried about this problem, but I was thinking about it today, and I've found what I believe is an accurate formula that may be easier to work with than the one I gave before. Here it is:

 

[math]f(m,n) = {n \choose n}n^{m} - \left[{n \choose {n-1}}(n-1)^{m}-\left[{n \choose {n-2}}(n-2)^{m}-\ldots-\left[{n \choose 2}2^{m}-{n \choose 1}1^{m}\right]\right]\right][/math]

 

This can be written as the following sum:

 

[math]f(m,n) = \sum_{i=0}^{n-1}\left[(-1)^{i}{n \choose {n-i}}(n-i)^{m}\right][/math]

 

The expanded formula can be simplified a bit if we realize that [math]{n \choose n}n^{m} = n^{m}[/math] and [math]{n \choose 1}1^{m} = n[/math], but I didn't make those simplifications, in hopes that the pattern is clearer than it would have been otherwise.

 

Example: Consider again the case of m = 4, n = 1 to 4. Then we have

 

[math]\begin{array}{rcl}f(4,1) & = & \sum_{i=0}^{0}\left[(-1)^{i}{1 \choose {1-i}}(1-i)^4\right] \\ & = & (1){1 \choose 1}(1)^{4} \\ & = & 1\end{array}[/math]

 

[math]\begin{array}{rcl}f(4,2) & = & \sum_{i=0}^{1}\left[(-1)^{i}{2 \choose {2-i}}(2-i)^4\right] \\ & = & (1){2 \choose 2}(2)^{4} + (-1){2 \choose 1}(1)^{4} \\ & = & 16 - 2 \\ & = & 14\end{array}[/math]

 

[math]\begin{array}{rcl}f(4,3) & = & \sum_{i=0}^{2}\left[(-1)^{i}{3 \choose {3-i}}(3-i)^4\right] \\ & = & (1){3 \choose 3}(3)^{4} + (-1){3 \choose 2}(2)^{4} + (1){3 \choose 1}(1)^{4} \\ & = & 81 - 48 + 3 \\ & = & 36\end{array}[/math]

 

[math]\begin{array}{rcl}f(4,4) & = & \sum_{i=0}^{3}\left[(-1)^{i}{4 \choose {4-i}}(4-i)^4\right] \\ & = & (1){4 \choose 4}(4)^{4} + (-1){4 \choose 3}(3)^{4} + (1){4 \choose 2}(2)^{4} + (-1){4 \choose 1}(1)^{4} \\ & = & 256 - 324 + 96 - 4 \\ & = & 24\end{array}[/math]

 

as we did using the other formula.

 

Reasoning: I was thinking again about the general method of taking all possible m-length numbers given n distinct digits and subtracting the ones that don't meet our criteria. It occurred to me that one method might be to simply subtract off the numbers that only contain (n-1) of the available digits. We'd have to subtract this for each possible combination of (n-1) digits, i.e. we'd need n^m - C(n, n-1)(n-1)^m.

 

But of course, this subtracts off too much, since some numbers will be counted multiple times (for instance, given m = 5 and n = 4, the digit combinations 123 and 124 will both include numbers like 12212). What must be done, then, is to exclude numbers containing only (n-2), (n-3), ..., 1 of the available digits, saving them to be subtracted later. This is similar to the reasoning used in the formula I gave a few posts back. Thus we have n^m - [C(n, n-1)(n-1)^m - [C(n, n-2)(n-2)^m - ... - [C(n, 2)(2)^m - C(n,1)]]].

 

I don't know if this explanation is extremely clear, but hopefully it conveys the idea to some extent.

 

I have an issue with your formula - better said: my calculator (TI-84 Plus) has a problem with it:

 

I set at Y1 = [math]\sum_{i=0}^{n-1}{\left((-1)^I\cdot \left((N-I) \: nCr \: N\right)\cdot (N-I)^M\right)}[/math]

 

Let n = 1 and m = 4, Y1 = 1

Let n = 2 and m = 4, Y1 = 16, not 14.

...

 

EDIT: my bad, changed the things at nCr

Edited February 6, 2014 by Function