Discrete Math - 2 - Permutations, ordered arrangements

I wrote on the product and sum rules here. Permutations are related to the product rule.

A permutation is a unique way to order a set of objects on a line.

A concrete example:

How many ways are there to arrange(order) the three characters (set), b, a, r (on a line)?

Six ways (permutations):

bar, bra, abr, arb, rab, rba.

Permutations are also called linear arrangements.

There are 6 permutations of size 3 for the set of 3 letters. We can think about this as 3 choices for the first position, then 2 choices for the second position, and 1 choice for the third position.

If you aren't familiar with factorial (!), go read.

The number of unique permutations of length n from a set of n unique members is n!.

If we have a set of n unique objects, how many unique linear arrangements of m of these objects can we make?

Another concrete example might help. Say we have 5 web developers on our team. We have a contest. The dev who does the best will be sent to a Python programming conference in Singapore, first class. The second best dev will also get sent but won't get a gift certificate for hot wings.

How many different ways could this turn out?

There are 5 ways to choose the 1 of the 5 who will be the best. Then there will be 4 ways to choose 1 from the remaining 4 to be second.

The formula turns out to be generalizable.

One way to read the left side of this equation may be, "The number of permutations of length m from the set with length n".

We can use this form for the first example (permutations of 3 from a set of 3) with and important aside:

So, therefore, the question of permutations of size 3 from a set of 3:

Here's a python function that makes use of recursion to calculate the factorial of a number:

def factorial(num):
    if num == 0:
        return 1
    else:
        return num * factorial(num-1)

So, we can define a permutations function that makes use of the factorial function.

def permutations(m, n):
    return factorial(n)/factorial(n-m)

Check it out in action in the python interactive interpreter shell!

>>> permutations(3,3)
6
>>> permutations(1,3) # b, a, r
3
>>> permutations(2,3) # ba, br, ab, ar, rb, ra
6
>>> permutations(2,5) # ways to choose first and second place out of 5
20

If you try numbers that are too large you will exceed the maximum recursion depth for your settings, see http://docs.python.org/library/sys.html. Another more efficient and terse way to define this function would be:

def factorial(x):
  return 1 if x==0 else reduce(operator.mul, xrange(1, x+1))

You can look up reduce. Learn more about importing the common operators as first-class passable functions here. For creating iterables with the python built-in, xrange, check here.

If you define factorial in this way, you can deal with bigger numbers. Still, to be more efficient in a large computation, it's more simple to just multiply the values,

Now, if we are going to label the different seats in Congress 1 through 535, and say there are 300000000 people in the United States (and disregard that you have to live in a certain place to run for a certain seat.. every person in the US is eligible for every seat in our game) then there would be P(535, 300000000) ways that Congress could be filled.

To do this computation efficiently, we can't use either of our convenience functions. Instead, we must use the simplified form.

A python function that will actually do this directly and skip the formality of our little formula (that was made for puny fleshlings) is:

def permutations(m,n):
    return reduce(operator.mul, xrange(n, n - m, -1))

Now, we can quickly return:

>>> perm(535,300000000)
181829559068429178671561838672942840250008823021704806316947274189481743424663502818044832307715580283550493281735063753713780627962684572829971245162752052846110436735404807875241809186454655345500724157471633365409856437556614220840129524166373808816708453500815917831639794242177623537604349623015530900527235777269275493468807628577329443762064601044531355511564620882824306679018210335407151105165044248861689154783687099749553444797926284774496958696579267477295041481324027806983410825572519212497652250096913290846395558384795185413442347739836633461151629038603054686284266315012220966917098577147511427857605503795218315787990480885175569479264740692017305203473959416845398232717027331600585057420542548290359030911631737657003786227488886707976335967648695957532960733299977333375148433570103424562759937739407500671395296168444546635136622423600451174264107325128790000626991715816166804110943672027420784370391081464328119996595662614604346393742015514295580571948223944545851364940763530709122821395285368613690763801774366117443788273464943885487137785546676271146010229811070005109511867861534308965458039338749957159659661086379056828966360643035857109978728896491644806446241331892880853982557229807885322486315525999192673030856975050589526806454411322659075123825345446351949707665559635935618416075227973852332190517816700779944842015190960084387854473792648831977320947163283763465141650554364186570243935686267695499230769608752496332638903233079525276946814290216281402572403211000692186136426509355574146891460557909972322184785682866292137801835687579052638303480805935306939336023135092099318966757006359341759151594645767042454193319575614555122166773281087850933732337070608787517979386042006013033675565909421856834661215477048516685205306791000637636549059473042737184301330785305335176746403392484597783953404303662541185011308545072694662217323717368099793582354022216820868305661716677856297678873777661772212177262151083992442282574677364851288160545706795334965737140262125365124757714923891260041932639141143055400468185296367187358002480008841377237618126612444573352508825265897789698439853853258228828510067523199900145850833090910512258222956054512948408439560358674152360735073044611972843282983591433404394148638810142614091050433804221911167220296686517065231422969279934689478947307167978651267828010970620161734182570061333267199022084075836639659414339601779635047726251688676853421490380607528641271087760227435625290172368531430690344722722169261055130504173079159022659069841392563940817380001271393214091970832599427121002271941242020834502483834557330516982902599341939378835564038372309950453371042318737239443063141645539990572309382705686954492326070452047221823233222043480266104082427881293486503437969268808867160094526798786061910274329775820570749866155487175874333054391729681177111888370741983315711493092701335953378068367158546950992595737108252378584986642287573246953225729535216887617188697209098680561707475931836235773867455706311953311167109130655633476855489638806900043611259578399172864279920909192729895487724910977699952318648244853523541297196893335588404555178776733406468406993136852473595473073303102180597970843846255068392726831767921746344881177048227785784306877355607991591431378515343960984557531524295957098481068793358741885884336439301851569629320056190389598637059125418576077135661242733777734847992791657305871212841075443771719716093192106947647212580890952040051024600176085484527713375589047203506518830430734223745001131119858099383097090006078374842669035049297554686882147729631870047755515148682567795914115816789846171655156804425711741328755957171159843062085679464797856802709349408508389536451544235843534498685437864802747116746093282792404150708033257172217028271092918523680207970183406257878349681467270574040875319953630497964468047173968371861824012374052666496073170384894432131071943282992926906885248781097897911165431119329982597208720750988236071498312611582983942618344771540637738510992416337986518942774634613693188354586928602232745564726789558622109154057978297470241077673758334784514898621200731428028290616841729345717124398495683124928233631340432382151471958673807525150418249412011918383919663110087668502097823351153993701393943254018095479276819927328098496126591035842476945893640912819022217205406913131201888456491924713621052522218393084781915239632509454051327344640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

That's a big number with 4536 digits. To get a real calculation, we would have to go district by district and do all kinds of things that have not yet been covered.