
RFMontraz

NP Italian Stallion

Total Posts: 2019 
Joined: Mar 2004 


Hi guys
long time no "speak"!
I have a question to calculate some combinations, my math is rusty, I looked around the web but didn't find what I was looking for.
Say you have 8 elements:
4 from group A (1,2,3,4) 4 from group B (5,6,7,8)
How many combinations of pairs do I get considering that no element can be repeated in the same pair (so no 1,1), order does not matter (so 1,2 is identical to 2,1) and members of group A can appear 4 times overall, while members of group B only twice?






Just for future Googling reference, this is called a partial sum of binomial coefficients.
I'm assuming:
> members of group A can appear 4 times overall, while members of group B only twice
Means: The combo can include 0,1,2,3 or 4 distinct A elements, and 0, 1 or 2 distinct B elements. Please note the 0s, meaning that the empty set is a valid combination. (If that's not the case adjust the below math accordingly.)
Every valid A combinatorial can be paired with every valid B combinatorial. So the answer is just [Apartialsum] * [Bpartialsum].
A is a special case, since it's actually just the full sum. A's total sum is just 2^A = 2^4 = 16.
B is a true partial sum, and you there's no shortcut to just adding up the individual binomial coefficients. 4Choose0 = 1 4Choose1 = 4 4Choose2 = 6 B's partial sum = 1+4+6 = 11.
Therefore the size of the total combinatorial set is 11*16 = 176. (If zero selections aren't valid, then the answer is 15*10 = 150)
https://en.wikipedia.org/wiki/Binomial_coefficient 
Good questions outrank easy answers.
Paul Samuelson 


RFMontraz

NP Italian Stallion

Total Posts: 2019 
Joined: Mar 2004 


Hi EL
I do not think I explained the part of the repetition properly (most likely I'm not using the correct terminology, so apologies). When I said elements of group A can appear only 4 times, I meant that after a set like:
1,2 1,3 1,4 1,5
If we add 1,6 we would be in violation as 1 already appears 4 times, so it cannot be used anymore. We can add 2,3 / 2,4 and 2,5 but now we cannot use either the 2 (it appears already four times) or the 5 (it appears already twice) anymore.
I wonder if there is a generic formula for this (the actual number of elements and groups is bigger than this, and it is not pairs but baskets of 3, hence my problem)





RFMontraz

NP Italian Stallion

Total Posts: 2019 
Joined: Mar 2004 


in my example the solution is 12 (calculated manually) 




Understood. Your terminology was fine, misunderstanding was mine. I guess I'm being tripped up on this:
> no element can be repeated in the same pair (so no 1,1), order does not matter (so 1,2 is identical to 2,1)
Just to clarify: each time we pick, we pick a pair of elements  one from group A and one from group B. (Otherwise does that mean we can pick a pair with two elements from group A?)
I'm assuming this means it's possible for elements to appear in both group A and group B. (Otherwise why do repeated elements need to be explicitly excluded?) I.e. something like:
Group A = (1,2,3,4) Group B = (2,4,6,8)
If that's the case, what side do we "count" towards when we pick an element from the intersection? In the above example if we pick (2,4) does the use of the 2 count toward's group A's budget or group B's budget? Or both? If 2's in the first position of the pair does it always count toward A's budget? (And if that's the case, then order does matter.) Or do we have leeway when selecting intersected elements to apply it to the most advantageous budget?
Sorry, for being so pedantic... Just trying to make the problem as precise as possible. This basically sounds like a variant on the knapsack problem.

Good questions outrank easy answers.
Paul Samuelson 



deeds


Total Posts: 407 
Joined: Dec 2008 


Hi RF  if it's not closely held secret, can I ask what you are using these calculations for?
thanks d 



rftx713


Total Posts: 100 
Joined: May 2016 

 

ronin


Total Posts: 384 
Joined: May 2006 


The meaningful part seems to be that each member of group B can appear twice.
There are four mebers of group B, so you can only have up to eight pairs. The restriction on group A doesn't come into it.
How did you get to twelve?

"There is a SIX am?"  Arthur 


RFMontraz

NP Italian Stallion

Total Posts: 2019 
Joined: Mar 2004 


Hi guys
Hardly a secret in fact happy to share details with whoever is interested.
The background here is building a portfolio made of structured products which some call low strikes, some call geared put, some call Phoenix Plus Security and I guess some might call bullshit but that’s another matter.
To make a long story short, we are talking about selling an OTM put on the worst performer of a basket of equity indices. Normally the plain vanilla flavour is SPX/SX5E/NKY but I’m looking at building a whole portfolio of it so I want more diversification to avoid to have one index that brings all the temple down (yes I am aware that when the shit hits the fan correlation goes to 1 and SPX and IBEX become the same thing, but when the dust settles things change again. These products have a life of 5 years, at least 40% OTM barrier, so the outlook is long term).
My idea would be to execute a tranche (indicatively) every month. Basket components are chosen via an optimization at that time of the month (which of course would keep into account vols and correlations). But not all indices are created equal. So while I would be comfortable to have 4 tranches with the SPX (group A) I wouldn’t be with the FTSEMIB (group B) and much less with SX7E (group C).
Hence my question: if I have X elements in group A (which can each appear in max 4 tranches), Y elements in group B (max 2), Z elements in group C (max 1), how many possible baskets of 3 (i.e. how many possible tranches) do I have to play with? It is crucial to figure out the % to allocate for a trache and the frequency of the execution (above I wrote monthly, but that is just indicative)
"Just to clarify: each time we pick, we pick a pair of elements  one from group A and one from group B. (Otherwise does that mean we can pick a pair with two elements from group A?)"
No. You can pick the elements from the same group, the constraint is that each element of group A shows max 4 times overall and so forth. This should address also Ronin question.






Thanks for the clarification. I think I have the answer that you're looking for. There's good news and bad news...
Let P be the set of all the elements from any group. For now, we'll just treat everything as part of one huge set.
Let Q be the set of all 2combinations from X. 2combination means any pair of elements, with no repeats and ordering doesn't matter. (Also you can trivially extend this to Ncombindations if you want triplets, etc.). Q will be about P^2/2 in size.
Let S be some enumeration of all the elements in Q. Doesn't matter how we enumerate the 2combos, just we have to put them in some ordering. Let's just say alphabetical ordering.
Now we basically have a Linear Programming problem. We want to solve for some 1/0 vector X of length S. X corresponds to whether we include the specific element from S in the final set or not. I.e. if the fifth entry in X is 1, then we include the fifth 2combination from the enumeration, S. If it's 0, we exclude it.
The objective function is to maximize sum(X). We want as many entries to be 1 as possible, because that means we've included the maximum possible number of 2combinations and hence have selected the larger subset.
Finally we introduce some constraint functions which correspond to the pergroup limitations. Let's say we want to restrict any member from group A from appearing more than M times. We define a new constraint vector, C. C also is a 1/0 vector of length S. Each entry in C is 1 if the equivalent 2combo from the S enumeration contains an element from group A. 0 if it doesn't. E.g. if group A = {1,2,3,4} and the fifth element of S is (1,3), then the fourth entry in C would be 1. If the seventh entry of S was (5,6), then the seventh entry of C be 0.
Using this we add a constraint to the LP problem. X * C <= M. (Where M is the number of times we want to restrict elements from that group from appearing. * just means the vector dot product.) Nonsolutions that contain a group's element too many times will be rejected by this constraint. You can add similar constraints for however many groups you have.
And that's it, just solve the LP and you have your solution. More specifically this is just a multidimensional knapsack problem.
The bad news is there's no a closedform solution. In fact even worse, this problem is NPcomplete, so it's not even computationally cheap. Particularly if your set sizes are large. The good news is that multidimensional knapsack problems have been around a long time. We know how to solve them, and there's plenty of free software that will do it for you. The second good news is that, even if the problem is NP complete, I strongly suspect that your set sizes aren't that large relative to what a modern Xeon can crank out in a few minutes.
The final good news is that even if this isn't the case, there are a lot of good approximation algorithms that run in polynomial time, and probably will give you a "goodenough" solution even if it isn't optimal. 
Good questions outrank easy answers.
Paul Samuelson 


RFMontraz

NP Italian Stallion

Total Posts: 2019 
Joined: Mar 2004 


Thanks a lot EL. Will need some time to digest it though.
Have a good w/e! 




deeds


Total Posts: 407 
Joined: Dec 2008 


2 bps:
Doesn't seem that NP complete is going to bite in these circumstances.
Seems an enumeration algorithm with clever ordering would feed the bulldog in this age multicore whizbang on your wrist. (lots of impossibilities in combinatorics come into scope)
D 







