User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 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 4-tuples 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 (4-tupples) pairs of pairs which have at least a common element between the two pairs. We encounter 4-tuples ([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 l-tuples (l>2) at step 1) answer: N:=n Step1 : Total choices1 = The n th triangular number Tn Step2 : Total choices2 = The Tn-1 th triangular number .(Doubly triangular numbers) Number of excluded = nTn-1. How does this generalises? When we consider (instead of pairs), l-tuples 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 repetitions-unordered from step1's output. I hope this makes it easier to help. What if I chose triplets or l-tuples 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 l-k tuples ( Above we find the "2-2" class when m=n=2, For n=m=3 we naturally have three classes : "2-2","2-3","3-3" and so generalizes ) Within each class we can obtain distinct sub-classes by taking under consideration the number of different pi's and pj's forming each of the "l-k" classes. In this sense the "2-2" class will be subdivided into 3 sub-classes at max. Say the classes *1-1*, *1-2*,*2-2*. In that shape we may consider "up to M-M" combinatorial choices of this type. I am interested in 1) Counting of all possible members of classes and sub-classes 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(N-1)/2 of these. To choose a second without overlap you have (N-2 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 N-1 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 N-2 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 "k-l" tuple pairs. Points where I need some further explanation: " ...pairs with different elements.."Please give an example. As I understand you count the unordered 2-tuples with repetition. "...a second without overlap.."An example. "...pairs with the same element there are N choices for the first and N-1 choices for the second.." Where does the "same" element occurs for you? "..mixed groups.." Do you mean mixed sized pair. Pair of (k-l)tuples ? "..grand total.." Is the total without the "excluded" pairs of "k-l" tuples? Notice : I label as "k-l" 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 2-step process as I do? Thanks!! Tags combinations, counting Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post USAMO Reaper Probability and Statistics 2 February 9th, 2015 01:21 PM jbergin Probability and Statistics 1 December 23rd, 2014 07:58 AM bugrocket Advanced Statistics 2 January 23rd, 2011 04:02 PM aimpro2000 Advanced Statistics 2 September 20th, 2010 02:12 PM mia6 Algebra 4 October 4th, 2008 06:30 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top

Copyright © 2019 My Math Forum. All rights reserved.       