How Many Allocations Are There If...?

How many asset allocation combinations are there if one has five assets and allocations can be made in one percent increments?

Now, I'll be the first one to step up here and say that this question has no real practical application in my, or almost anyone's, day-to-day investment decisions except in an abstract, in-the-background kind of way.  The question came up recently, though, when I was trying to build a tool that generates a representation of an efficient frontier for 5 assets so that I could get some context for the return and variation of a strategy I run. 

One might think that the portfolio return or standard deviation might be the hard part, especially since the covariance formula for five terms looks like this:

But this is more tedious than it is hard.  The hard part was coming up with the allocations required to generate the frontier.  For two assets it's pretty easy.  You can generate a scatter plot of return and standard deviation with stock/bond combinations like this: 100/0, 90/10, 80/20, etc. or 99/1, 98/2, 97/3, etc.  That's pretty mundane. Now what about five assets?  I pondered this for a while.  Since I have lost a bit of my programming skills and I am at least 30 or more years away from any quant-ish class that would have helped me solve the problem I was a little bit adrift.  I first tried to see if there was a mechanical way to do it in a spreadsheet.  I quickly lost my mind trying to figure it out that way.  I also realized that in my version of Excel (65000 rows) I was toast; this was a combinatorial IED.  Even in the newer Excel (1M rows?) there was no hope.  

[ at this point, if you have a background in probability or combinatorics , you will likely know how to do this…but I didn't, so shhhh.]

The best I could do was to create a random[1] sampling technique[2] to get a workable subset. That worked pretty well and gave a satisfactory result for what little I was trying to achieve.  But I was still wondering how many combinations there were and how big or small my sample was.  Except that I did not have the math skills to figure it out and I did not have any colleagues or professors to help me or students or staff I could coerce.  Aha! I thought.  I have a daughter at Stanford on a quant track.  She'll know or know someone.  She handed it to a friend who didn't have a formula but rapped out a program in about 5 minutes to count (tech envy or nostalgia! I could have done this a few years or more ago...maybe).  It ran thru combinations with a counter and came up with 4,598,126.  

But a "program?" That seemed a little "blunt force" to me. It also did not give me a sense of having a conclusive final answer.  I couldn't see his code or know whether he missed something and I had no way of validating it other than saying "sounds ok."  So, like any good, perplexed student, I did what they do: ask the internet.  But not actually searches or google because I'm too lazy to read a bunch of random search results.  A more focused approach was to Ask Dr. Math at mathforum.org.  They warn you, of course, that you might never get a result or that they can't help if the question is too mundane or confused or whatever but I got an answer in about an hour from someone signed as Doctor Peterson at NTCM. Here is his solution which might have [emphasis on might have] been easy or obvious if I had had any serious and/or recent background in probability:

We can think of this as if we had 100 dollar bills to distribute among
5 buckets. The buckets are distinct, but one bill is indistinguishable
from any other.

We can use a classic trick called "stars and bars" to count the ways.

Imagine laying out the 100 bills in a row. Any distribution into the
buckets can be represented by placing sticks in the row to separate
them into five groups (which can be empty). For example, if we had
only 20 bills (so I can draw it out),

  * * * * * * * * * * * * * * * * * * * *

then one allocation might be

  * * * * * *|* * * *| |* * * * * * * *|* *
      A        B    C        D        E
      6        4    0         8        2

Any arrangement of the 100 stars and 4 bars will match up with a
possible allocation.

  * * * * * * | * * * * | | * * * * * * * * | * * = 6, 4, 0, 8, 2

How many ways can we do that? Think now of 104 positions into which
stars and bars can be placed (24 in my smaller example),

  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

We can choose the 4 places in which to put bars in C(104,4) ways, that is

  104!         104*103*102*101
  ------     =    ---------------               = 4,598,126
  100!4!         4*3*2*1

The formula, assuming we always have 1% increments, is  C(99+n,n-1)
where n is the number of asset classes (buckets).

So there you have it:  4.6 million[3] … all cleaned up and ready to go[4].

---------------------------------------------

[1] Or pseudo-random since Excel isn't up to the task, though it's good enough for now.

[2] This actually was the hard part for me but is another story than the "how many…" question I asked at the beginning.  Let's just say that it took me a little while to work out a robust way to do it.  Better than Lumosity.com, I guess.  

[3] That would make my sample size just over 1%.  As an historical side note, that 1% reminded me of some tech work I did at Northwest Airlines back in the late 80s.  At the time they, and every other airline, calculated their revenue for public reporting purposes by sampling 1% of the tickets redeemed at the gate.  That's pretty amazing if you think about it for a second. We had to build a bazillion-line-of-code multi-country-workflow system to solve the problem. It only took several hundreds of people over four or five years and a lot of money to do it. My problem suddenly looks trivial. 

[4] Now do the math for 6 asset classes...or more!