Re: Combinations
- To: mathgroup at smc.vnet.net
- Subject: [mg30828] Re: Combinations
- From: "Ian McInnes" <ian at whisper-wood.demon.co.uk>
- Date: Thu, 20 Sep 2001 03:51:20 -0400 (EDT)
- References: <9o96q8$cev$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
The number of permutations (possible orderings) of a list of n objects is n!
only if all items are different. There are fewer permutations if the list
contains repeated items.
For example:
Length[Permutations[{a, b, c, d}]] is 24
whereas:
Length[Permutations[{a, b, b, c}]] is 12
(the examples assume that the letters a, b, c... are undefined).
In fact the number of permutations is Factorial[n] divided by the product of
the factorials of the numbers involved in each repeated group.
For example, the number of permutations of: {a, a, b, b, b, c}is:
Factorial[6] / (Factorial[2] * Factorial[3] * Factorial[1]) = 60
The following one-liner computes the number of permutations of a list as
above:
In[1]:= permCount[x_]:=If[ListQ[x], Length[x]! /
Apply[Times, Map[Count[x,#]!&,
Union[x]]],1]
and can be efficiently applied to lists of arbitrary length:
In[2]:= permCount[{a,g,e,d,d,e,a,f,a,c,e,f,e,d,b,a,d,c,a,b,b,a,g,e}]
Out[2]:= 6233607431251200
Checking this result by the use of Length[Permutations[]] is not recommended
;-)
Ian McInnes.
"David Park" <djmp at earthlink.net> wrote in message
news:9o96q8$cev$1 at smc.vnet.net...
> Dana,
>
> The number of permutations of n objects is just n! (n factorial) which you
> can enter in just that way in Mathematica. For a set with 4 elements:
>
> 4!
> 24
>
> Which checks with
>
> Permutations[{1, 2, 3, 4}]
> Length[%]
> {{1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 3, 4, 2}, {1, 4, 2, 3}, {1,
> 4,
> 3, 2}, {2, 1, 3, 4}, {2, 1, 4, 3}, {2, 3, 1, 4}, {2, 3, 4, 1}, {2, 4,
1,
> 3}, {2, 4, 3, 1}, {3, 1, 2, 4}, {3, 1, 4, 2}, {3, 2, 1, 4}, {3, 2, 4,
> 1}, {3, 4, 1, 2}, {3, 4, 2, 1}, {4, 1, 2, 3}, {4, 1, 3, 2}, {4, 2, 1,
> 3}, {4, 2, 3, 1}, {4, 3, 1, 2}, {4, 3, 2, 1}}
> 24
>
> The number of k element subsets picked from n items is just Binomial[n,
k].
> For example:
>
> Binomial[4, 2]
> 6
>
> Needs["DiscreteMath`Combinatorica`"]
>
> KSubsets[{1, 2, 3, 4}, 2]
> Length[%]
> {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
> 6
>
> How precisely did I find this out? By looking up Permutations in my
> "Mathematics Handbook for Science and Engineering" and then looking up
> Binomial and Factorial in Help. Finding KSubsets is not that easy because
> the Combinatorica Help is not very good or convenient.
>
> There was a book "Implementing Discrete Mathematics: Combinatorics and
Graph
> Theory with Mathematica" by Steven Skiena the author of Combinatorica.
> Unfortunately, it has gone out of print. It would be a great thing if WRI
> could somehow arrange to bring it back into print, and also improve the
Help
> documentation for Combinatorica because it is a great package.
>
> New users of Mathematica are often disappointed that the precise command
or
> function they want is not there, or not there under the name they might
> expect. But you will quite often have to hit the math books to find how to
> calculate something and you will also quite often have to write your own
> small routines. If Mathematica tried to have direct routines for
everything
> it would end up with millions of commands and still fall short.
>
> David Park
> djmp at earthlink.net
> http://home.earthlink.net/~djmp/
>
> > From: Dana [mailto:ng_only at hotmail.com]
To: mathgroup at smc.vnet.net
> >
> > Hello. I have Mathematica 4.1
> >
> > In a Program like Excel, or a hand-held calculator, one can return the
> > number of combinations and permutations.
> >
> > However, I can not find an equivalent function in Mathematica.
> > For example, Permutations[ ] returns a long list of all the "Actual"
> > permutations.
> > I am looking for just the final number.
> > If there is one, could you include 'how' you found it. I have looked
> > everywhere.
> > I know DiscreteMath`Combinatorica` has some stuff in it, but the
> > Help system
> > appears not to explain many of them.
> >
> > I can write a custom function, but I am curious to find out if
> > this function
> > is built in to Mathematica.
> >
> > I hope the answer is not to take the Length[ ] of a rather long list.
> >
> > TIA. Dana
> >
> > (I posted this question a month ago, but it never showed up in the
> > newsgroup, or in the archives.
> > I hope I am not doing something wrong.)
> >
>
>