Computer Science Canada Choose function with non unique elements |

Author: | Raknarg [ 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. |

Author: | Dreadnought [ 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.
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. |

Author: | DemonWasp [ 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 |

Author: | Dreadnought [ 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. |

Author: | Raknarg [ 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. So I'm assuming that Dreadnought's answer would be correct? |

Author: | Dreadnought [ 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). |

Author: | Raknarg [ 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 |

Author: | Dreadnought [ 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
EDIT: made notation more consistent. |

: |

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.