Permutations & Combinations: When Objects are Not All Distinct

[qbslug]

How many permutations (when objects are not all distinct) of size k can be created from a set of size N composed of n1, n2,n3,...,nr parts?
When k = N this is easy and is equal to N!/(n1!n2!...nr!)

The following question would be then how many combinations (when objects are not all distinct) of size k can be created from a set of size N composed of n1, n2,n3,...,nr parts?
When all objects are distinct we know that this would be N!/((N-k)!k!)

Looking through the combinatorics section of my statistics book they don't mention these seemingly important situations.

 

[awkward]

How many permutations (when objects are not all distinct) of size k can be created from a set of size N composed of n1, n2,n3,...,nr parts?
When k = N this is easy and is equal to N!/(n1!n2!...nr!)

The following question would be then how many combinations (when objects are not all distinct) of size k can be created from a set of size N composed of n1, n2,n3,...,nr parts?
When all objects are distinct we know that this would be N!/((N-k)!k!)

Looking through the combinatorics section of my statistics book they don't mention these seemingly important situations.

Problems like the two you pose are generally solved using generating functions: exponential generating functions in the case of permutations (your first question) and ordinary generating functions in the case of combinations (your second question). When the problem is sufficiently complicated or general, you may be able to find the generating function which "solves" the problem even though you are not able to get a formula for the "number of ways". There is still value in the generating function in such a case, because you may be able to discover facts about the problem that are not obvious, such as recurrences or asymptotic behavior of the solution.

See http://en.wikipedia.org/wiki/Generating_function

The wikipedia article also has links to additional information.

 

[qbslug]

So there is no general solution for this problem?? How can this be?!

 

[awkward]

There is a general solution in so far as it is easy to write down the generating functions, but unfortunately extracting the "number of ways" formula from the generating functions (in the general case) is so complicated that it's not really worth the trouble. For specific problems you can often use the generating function method to get a relatively simple answer.

Moral: don't expect an analytic solution to every combinatorics problem. Some of them are just too hard. It's a little like "The Hunting of the Snark": some problems are Snarks, some are Boojums. You don't really know which is which until you try to solve one.