Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Choose function with non unique elements
Author Message
Raknarg

Posted: Mon Dec 08, 2014 9:23 pm   Post subject: Choose function with non unique elements

Is there a formula for calculating the number of ways to choose a certain amount of elements from a collection if some of the elements are not unique?

For example, you have the A, B, C, D, D, E, E, E. Is there a way to calculate the number of unique pairing or triplings you can make? Or any list with n unique values, and each value has n(i) number of copies in the list.

Posted: Mon Dec 08, 2014 11:22 pm   Post subject: Re: Choose function with non unique elements

Assuming the order in which the elements are chosen is unimportant.

 code: Suppose that you have distinct elements a_1,...,a_m with n_1,...,n_m occurrences in the list respectively. Suppose also that you want to pick k elements without replacement. Let S = { (i_1,...,i_m) | 0 <= i_j <= n_j for all 1 <= j <= m, i_1 + ... + i_m = k } Then the number of ways of choosing k elements without replacement is  product over all (i_1,...,i_m) in S of (n_1 choose i_1) * ... * (n_m choose i_m)

Or in prettier LaTeX form
[img]http://latex.numberempire.com/render?%5Csum_%7B%5Csubstack%7Bi_1%20%2B%20%5Ccdots%20%2B%20i_m%20%3D%201%20%5C%5C%0A0%20%5Cleq%20i_j%20%5Cleq%20n_j%5C%3B%20%5Cforall%5C%2C%201%20%5Cleq%20j%20%5Cleq%20m%7D%7D%20%5Cprod_%7Bj%3D1%7D%5Em%20%5Cbinom%7Bn_j%7D%7Bi_j%7D&sig=09b95f2cc98408095d05f922c5ba6e24[/img]

Not the prettiest but it works.
DemonWasp

Posted: Mon Dec 08, 2014 11:33 pm   Post subject: RE:Choose function with non unique elements

Yes, the formula you want is given on the Wikipedia page about combinations. Most of the article is pretty dense, so here's the simplest relevant section: http://en.wikipedia.org/wiki/Combination#Example_of_counting_multisubsets

Posted: Mon Dec 08, 2014 11:53 pm   Post subject: Re: Choose function with non unique elements

I'm no longer sure that I know exactly what you are looking for.
If you're choosing elements with replacement DemonWasp's link has the solution. If you're choosing them without replacement then you have to something messier like I posted.

Also, my image didn't work. Sorry for the really long link.
Raknarg

Posted: Mon Dec 08, 2014 11:57 pm   Post subject: RE:Choose function with non unique elements

OK I'll phrase my real problem: you have the prime factors of a number, and you want to know the number of combinations that you can make with these factors. So essentially you have a set of items but where some of the items are the same, and you need to know the combinations that could be made with all of these without repeats.

Posted: Tue Dec 09, 2014 10:46 am   Post subject: Re: Choose function with non unique elements

So basically you are counting divisors.
If you only care about divisors which factor into k primes (counted with multiplicity) then my previous answer is what you are looking for.

If you just want the number of divisors, regardless of the number of primes into which they factor then what you are looking for is the divisor function (in particular you care about the case for x=0).
Raknarg

Posted: Tue Dec 09, 2014 11:26 am   Post subject: RE:Choose function with non unique elements

As far as I can tell there's no actual algorithm, the divisor function is just notation to show that you're referring to the number of divisors or the sum of, but it doesn't actually tell you how it's calculated

Posted: Tue Dec 09, 2014 12:19 pm   Post subject: Re: Choose function with non unique elements

Halfway through the properties section it does give a formula. Here's the idea

 code: Let n be an integer. Let p_1^a_1 ... p_k^a_k be the unique decomposition of n into distinct prime powers. A divisor of n has the form p_1^b_1 ... p_k^b_k where 0 <= b_i <= a_i for i from 1 to k. So there are a_i + 1 possibilities for the power of p_i in the prime decomposition of a divisor of n. Thus the total number of divisors is the product (a_1 + 1)(a_2 + 1) ...  (a_k + 1)

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 8 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: