How do you work out combinations where the number of objects chosen is undefined?

hatrickpatrick

Interesting problem I'm having. I'm trying to work out the maximum possible number of combinations, which would be a standard nCr, except that the problem is every method I've found and every calculator I've found requires one to define "How many will you choose", for example in a lottery scenario, choosing six numbers. The problem I'm having is that in my particular example, there are 14 boxes, numbers 1-36 to choose from in each box, BUT, one doesn't have to choose a number for every box. It's perfectly ok to pick a sequence which only has 7 numbers in it for instance, or even 1, even though there are 14 boxes available. So it's quite different to the standard problems which come up in questions such as these, unless I'm missing something glaringly obvious. I've tried a few methods already, but all of them come up with figures which are far, far lower than I know the answer to be.

How would one go about this?

If anyone's interested, I just discovered today that Twitter had a 14 character limit for @usernames, and was therefore curious as to the maximum number of users there can be, using every alphanumeric character (total of 36 characters) combination before there are literally no possible usernames left without changing the rules. But since it's possible to have a one character username or a 14 character one, it isn't a standard nCr question as I can't specify in advance how many numbers I'm going to choose. It could be anything from 1-14. Silly thing I know, but that's what happens when one is hungover and bored

Anyone got any idea as to how this could be calculated? Would I simply do standard combination calculations 14 times, assuming I choose 1 character the first time, 2 the second, etc until I've done it 14 times, and then add all the results together? Is there a less messy way of doing it?

locum-motion

What you're trying to do is find out what "zzzzzzzzzzzzzz" in base 36 equals when you convert it into base 10.

locum-motion

According to http://korn19.ch/coding/base_converter.php , it is 6.14094221446 x 10^21

or 6,140,942,214,460,000,000,000

Which is approximately enough for every person on earth to set up a trillion accounts each.

bnt

For the Twitter username question, it isn't like the lottery where each ball is only used once. aaaaaaaaaaaaaa is a valid username, for example. So it's a simple power formula: 36^14 = 6.1409 x 10^21 - the same answer locum-motion gave above.

Ciaran

bnt wrote: »

For the Twitter username question, it isn't like the lottery where each ball is only used once. aaaaaaaaaaaaaa is a valid username, for example. So it's a simple power formula: 36^14 = 6.1409 x 10^21 - the same answer locum-motion gave above.

That's the number of 14 character usernames. You have to add on all the 1, 2, 3, ..., 13 character usernames as well. That's 36 + 36^2 + 36^3 + ... + 36^14. That's a geometric series with an answer of 36(36^14 - 1)/(36 - 1) which equals 6.3164 x 10^21

locum-motion

Ciaran wrote: »

That's the number of 14 character usernames. You have to add on all the 1, 2, 3, ..., 13 character usernames as well. That's 36 + 36^2 + 36^3 + ... + 36^14. That's a geometric series with an answer of 36(36^14 - 1)/(36 - 1) which equals 6.3164 x 10^21

I don't think that can be right.

If (as you say) the answer I gave is only the number of 14 character usernames*, then surely if you add to that all the 13 character ones, all the 12 character ones and so on, surely the order of magnitude would be much higher than my answer.

According to you, the total number of possible usernames with 1,2,3,4,5,6,7,8,9,10,11,12 or 13 characters is

6.3164 x 10^12 minus 6.1409 x 10^21 equals 0.1755 x 10^21

which is only 2.85% of the possible number with 14.

I don't think that could possibly be right.

*: Before I edited this post, I said "But I think you're wrong". Actually, on second thoughts, you might be right on that.
A bank card's PIN has 10,000 possibilities, from 0000 through to 9999, because it MUST have 4 digits. But if it could have 1,2 or 3 digits, then the number of possibilities becomes 10 + 100 + 1,000 + 10,000 = 11,110. What threw me at first was that I was thinking that 1 was the same as 0001. It's not. I still think that my order of magnitude point should still stand, though. I'll do a bit of totting up to see.

locum-motion

List of possible 1 character usernames: 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,g,h,i,j,k,l,,m,n,o,p,q,r,s,t,u,v,w,x,y and z = 36
List of possible 2 character usernames: 00,11,12,13...1y,1z,21...a1,a2,a3...ay,az,b1...gf,gg,gh...zx,zy and zz = 36^2
List of possible 3 character usernames: 000,111,112...zzy,zzz = 36^3
etc
etc
etc

So, total is: 36 + 36^2 + 36^3 + ... + 36^14, as Ciaran said.

And a bit of work on excel tells me that Ciaran's maths were spot on, and I was wrong.

Ciaran

Each extra term is 36 times bigger than the one before so the last term dominates in the size of the overall answer.

ray giraffe

Actually twitter allows 15 characters, and each can be a letter, digit or underscore (37 possibilities)

So we end up with

37+37^2+...+37^15

=37 (37^15 - 1)/(37 - 1)

=342708664283810176729839

=3.427*10^23,

about 54 times more than the last estimate.


I don't think we'll be running out of usernames soon