My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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!
Apostolos is offline  
 
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!
Apostolos is offline  
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!
Apostolos is offline  
April 21st, 2015, 05:43 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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!!
Apostolos is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.