# Combinatronics problem **URL:** \ **Category:** Factual Questions\ **Created:** [September 5, 2003, 4:07pm UTC](https://boards.straightdope.com/t/combinatronics-problem/199740 "2003-09-05T16:07:59Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![Opus1](https://avatars.discourse-cdn.com/v4/letter/o/858c86/32.png) [@Opus1](https://boards.straightdope.com/u/Opus1)\ **Post date:** [September 5, 2003, 4:07pm UTC](https://boards.straightdope.com/t/combinatronics-problem/199740/1 "2003-09-05T16:07:59Z")
At least I think that’s what this is called. It’s math, anyway. I know how to do nCr to find the number of distinct ways to choose r elements from a group of n. But what if two or more set members are the same? How do you calculate that? The particular problem I’m doing now is 11 c 7 from a group of A,A,B,C,D,E,F,G,H,I,J. But I’m really interested in the general formula. Thanks in advance. ---
**Author:** ![Orbifold](https://avatars.discourse-cdn.com/v4/letter/o/779978/32.png) [@Orbifold](https://boards.straightdope.com/u/Orbifold)\ **Post date:** [September 5, 2003, 5:25pm UTC](https://boards.straightdope.com/t/combinatronics-problem/199740/2 "2003-09-05T17:25:43Z")
For your specific problem you break it down into cases: i.e. there are 9 c 7 ways to do it without picking any A’s, 9 c 6 ways to do with choosing exactly one A, and 9 c 5 ways to do it choosing two A’s, so your answer is (9 c 7) + (9 c 6) + (9 c 5). I’m not certain if there’s a more general formula. ---
**Author:** ![Orbifold](https://avatars.discourse-cdn.com/v4/letter/o/779978/32.png) [@Orbifold](https://boards.straightdope.com/u/Orbifold)\ **Post date:** [September 5, 2003, 5:37pm UTC](https://boards.straightdope.com/t/combinatronics-problem/199740/3 "2003-09-05T17:37:04Z")
Oh, and the word is “combinatorics”. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 5, 2003, 7:50pm UTC](https://boards.straightdope.com/t/combinatronics-problem/199740/4 "2003-09-05T19:50:48Z")
There is a general formula. The phrase to type into google is “distinguishable combinations”. ---
**Author:** ![Orbifold](https://avatars.discourse-cdn.com/v4/letter/o/779978/32.png) [@Orbifold](https://boards.straightdope.com/u/Orbifold)\ **Post date:** [September 5, 2003, 8:49pm UTC](https://boards.straightdope.com/t/combinatronics-problem/199740/5 "2003-09-05T20:49:33Z")
Um, **ultrafilter** , I just put that phrase into Google and got bupkiss. Lots of stuff about how to calculate, say, the number of permutations of n elements when some of the elements are indistinguishable (i.e., references to multinomial coefficients) but that doesn’t answer the OP. I can’t think of any nice general formula that isn’t just a straightforward case-by-case analysis based on the make-up of the original set. I’d be happy to be proven wrong, but I don’t see the answer in any of the stuff I got from the Google search you suggested. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 5, 2003, 8:56pm UTC](https://boards.straightdope.com/t/combinatronics-problem/199740/6 "2003-09-05T20:56:44Z")
Maybe that’s not exactly it. I’ve got a book at home that should answer this, so I’ll check that out. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 6, 2003, 3:36am UTC](https://boards.straightdope.com/t/combinatronics-problem/199740/7 "2003-09-06T03:36:58Z")
Yeah, turns out the book didn’t have what I want. This is a tricky problem, and I’ve tried to figure it out before but got stymied. It’s equivalent to determining how many factors a number has given its prime factorization. Perhaps **Wendell Wagner** can shed some light on the situation. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [September 6, 2003, 4:33am UTC](https://boards.straightdope.com/t/combinatronics-problem/199740/8 "2003-09-06T04:33:23Z")
**ultrafilter** : > [@](#): > > It’s equivalent to determining how many factors a number has given its prime factorization. That problem is trivial, actually. Did you mean to say, “It’s equivalent to determining how many divisors _with a set number of prime factors (not necessarily distinct)_ a number has given its prime factorization.” In other words, for example, 12 = (2^2)_3, has 3_2 = 6 factors (1, 2, 3, 4, 6, and 12), but we can also talk about the factors of 12 with, say, Exactly zero prime factors: 1 Exactly one prime factor: 2 and 3 Exactly two prime factors: 4 and 6 Exactly 3 prime factors: 12 I think that’s what you meant to say. So the OP would be equivalent to having a number with a prime factorization such as: (2^2) \* 3 \* 5 \* 7 \* 11 \* 13 \* 17 \* 19 \* 23 \* 29 and asking how many divisors _with exactly seven prime factors_ that number has. The best and most general way I can think of for this type of problem is to use generating functions. For the example in the OP, do it like this: For each distinct object, we need a polynomial of the form: 1 + x + x^2 + … + x^n, where n is the number of times the object is repeated in the original group. For example, for the OP’s problem, the polynomial for A would be: 1 + x + x^2 and the polynomials for B through J would each be 1 + x. Multiply all your polynomials together to get your generating function: (1 + x + x^2) \* (1 + x)^9 Since we want to know how many ways to select seven objects, our answer is the coefficient of x^7 in our generating function (which is 246 if I didn’t screw that up). Do you see how that works? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 6, 2003, 4:37am UTC](https://boards.straightdope.com/t/combinatronics-problem/199740/9 "2003-09-06T04:37:17Z")
Yeah, that is what I meant to say. I’m not all that familiar with generating functions, so I’ll have to take your word for this problem.