April 19th, 2015, 11:08 PM  #1 
Newbie Joined: Apr 2015 From: Amsterdam Posts: 5 Thanks: 0  Counting of combinations
Hello guys! I have some problem : I am in a situation where I have to choose 4tuples of a specific form. Let s be the set we choose from. s={R1,R2,..,}, so that s = N, N>1 Step1 : Choose pairs in s, "N choose 2" (with repetition, unordered) pairs : (Ri, Rj). Let the total numbers of those pairs M= "N choose 2" Step2 : Choose pairs of pairs in s (without repetition, unordered) by pairing the choices of previous step. Exclude all (4tupples) pairs of pairs which have at least a common element between the two pairs. We encounter 4tuples ([Rp,Rq],[Rx,Ry]) so that any of Rp,Rq is different from Rx,Ry. Notice that from step 1 we have collected pairs [ Ri,Rj ] and at step 2 pairs over this set. What is the number of excluded elements at step2 in this case and what in general? (When instead of pairs we choose ltuples (l>2) at step 1) answer: N:=n Step1 : Total choices1 = The n th triangular number Tn Step2 : Total choices2 = The Tn1 th triangular number .(Doubly triangular numbers) Number of excluded = nTn1. How does this generalises? When we consider (instead of pairs), ltuples at step1. Please let me know if something is not very clear. Any suggestions or help would be appreciated. Thanks! 
April 20th, 2015, 05:29 AM  #2 
Newbie Joined: Apr 2015 From: Amsterdam Posts: 5 Thanks: 0 
Example : s= {1,2,3} Step1: (1,2), (1,1), (2,2),(2,3), (3,3) (1,3), Cardinality N=6 Step2 :[(1,2),(3,3)], [(1,1),(2,2)],[(1,1),(2,3)],[(1,1),(3,3)],[(2,2),(3,3)],[(2,2),(1,3)] Cardinality M=6 Number of excluded pairs of pairs : 9 =15 6 where 15 is the total number of pairs encountered by taking pairs without repetitionsunordered from step1's output. I hope this makes it easier to help. What if I chose triplets or ltuples at first Step (Step1)? How many do I "delete" given the cardinality of s ? Cheers! 
April 21st, 2015, 02:23 AM  #3 
Newbie Joined: Apr 2015 From: Amsterdam Posts: 5 Thanks: 0 
In general, I am interested in combinations of the form ((p1p2...pn) , (p1'p2'...pm')) where p1,p2,..,pn are all different from p1'p2'...pm' and also share no common divisor.I was able to understand and make the counting for m=n=2 ((px1,px2),(py1,py2)) but I got confused when I had to consider higher order classes. I considered as natural to think of two types of classification of such combinatoric choices. First with respect to the number of members of the lk tuples ( Above we find the "22" class when m=n=2, For n=m=3 we naturally have three classes : "22","23","33" and so generalizes ) Within each class we can obtain distinct subclasses by taking under consideration the number of different pi's and pj's forming each of the "lk" classes. In this sense the "22" class will be subdivided into 3 subclasses at max. Say the classes *11*, *12*,*22*. In that shape we may consider "up to MM" combinatorial choices of this type. I am interested in 1) Counting of all possible members of classes and subclasses I was able to observe certain pattern behaviors. I would like to work in a more serious manner with it. I am not yet able to relate the above distribution to something that I already know. I need help. Is there anyone who can relate this problem to something that already exists? Just let me know your thoughts or experiences about it.Thanks! 
April 21st, 2015, 05:43 AM  #4 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
Let's first handle pairs with different elements. There are (N choose 2) = N(N1)/2 of these. To choose a second without overlap you have (N2 choose 2) other choices, for a total of (N^4  6N^3 + 11N^2  6N)/8 pairs of pairs. For pairs with the same element there are N choices for the first and N1 choices for the second, for a total of (N^2  N)/2 pairs of pairs. For mixed groups there are (N choose 2) choices for the pair of different elements and N2 choices for the pair of the same, for a total of (N^3  3N^2 + 2N)/4 pairs of pairs. The grand total is (N^4  4N^3 + 9N^2  6N)/8. 
April 21st, 2015, 11:20 PM  #5 
Newbie Joined: Apr 2015 From: Amsterdam Posts: 5 Thanks: 0 
Please help me understand your calculations and the process of thinking . : I am trying to understand how does usually a person classifies those combinations. What is the stepwise process to receive the required "pairs of pairs". The number of "pairs of pairs" members that occur with common elements shall be dependent on the size of each of the parity components which I called them a "kl" tuple pairs. Points where I need some further explanation: " ...pairs with different elements.."Please give an example. As I understand you count the unordered 2tuples with repetition. "...a second without overlap.."An example. "...pairs with the same element there are N choices for the first and N1 choices for the second.." Where does the "same" element occurs for you? "..mixed groups.." Do you mean mixed sized pair. Pair of (kl)tuples ? "..grand total.." Is the total without the "excluded" pairs of "kl" tuples? Notice : I label as "kl" tuple pair the combinatoric choices of k p's with l other p's (without common elements). A possible choice in this sense could be the pair ((a,b,c), (d,e)) while an example of excluded pair is ((a,b,c), (a,e)) Could you please break the calc process to tell me how to work with those problems in general. I see it as a 2 step process of choices with an third extra step to exclude (remove) the non wanted choices. Do you remove those choices at the first steps or you do it at the end of the 2step process as I do? Thanks!! 

Tags 
combinations, counting 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Counting  USAMO Reaper  Probability and Statistics  2  February 9th, 2015 01:21 PM 
Counting  jbergin  Probability and Statistics  1  December 23rd, 2014 07:58 AM 
Complex Combinations Within Combinations Problem?  bugrocket  Advanced Statistics  2  January 23rd, 2011 04:02 PM 
Combinations within combinations possibilities?  aimpro2000  Advanced Statistics  2  September 20th, 2010 02:12 PM 
counting  mia6  Algebra  4  October 4th, 2008 06:30 AM 