Thursday, October 20, 2016

Permutation facts

By Vasudev Ram

Today, I was using the permutations function in Python's itertools module to generate permutations for a few different values of integers, as part of some work I was doing. Looking at the lengths (1, 2, 6, 24, ...) of a few sets of permutations, I noticed a pattern that seemed familiar, so I wrote this program to verify my guess about what it meant:
```#--------------------------------------------------------------
# perm_fact.py
# Author: Vasudev Ram
# Web site: https://vasudevram.github.io
#--------------------------------------------------------------

import sys
from itertools import permutations

def num_perms_upto(n):
num_perms = []
for i in range(1, n + 1):
num_perms.append(len(list(permutations(range(i)))))
return num_perms

def factorial(n):
if n < 0:
print "Argument n should be >= 0"
sys.exit(0)
if n == 0:
return 1
return n * factorial(n - 1)

def factorials_upto(n):
factorials = []
for i in range(1, n + 1):
factorials.append(factorial(i))
return factorials

print "Number of permutations of 1 .. n, where n in 1 .. 10:"
print num_perms_upto(10)
print "Factorial of n, where n in 1 .. 10:"
print factorials_upto(10)
```
which, when run, gave this output:
```\$ python perm_fact.py
Number of permutations of 1 .. n, where n in 1 .. 10:
[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
Factorial of n, where n in 1 .. 10:
[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
```
This confirmed (empirically, of course) that the number of permutations of n items (taken n at a time), is just n factorial.

Then I looked up factorial in Wikipedia, and found some interesting facts (pun intended). Here are some excerpts from that page:

[
The factorial operation is encountered in many areas of mathematics, notably in combinatorics, algebra, and mathematical analysis.
...
Its most basic occurrence is the fact that there are n! ways to arrange n distinct objects into a sequence (i.e., permutations of the set of objects). This fact was known at least as early as the 12th century, to Indian scholars. Fabian Stedman, in 1677, described factorials as applied to change ringing.
...
Although the factorial function has its roots in combinatorics, formulas involving factorials occur in many areas of mathematics.
...
Factorials occur in algebra for various reasons, such as via the already mentioned coefficients of the binomial formula.
...
Factorials also turn up in calculus; for example they occur in the denominators of the terms of Taylor's formula.
...
Factorials are also used extensively in probability theory.
...
As n grows, the factorial n! increases faster than all polynomials and exponential functions (but slower than double exponential functions) in n.
...
(Hence) ln n! ~ n ln n ... This result plays a key role in the analysis of the computational complexity of sorting algorithms
...
Factorials have many applications in number theory.
...
The reciprocals of factorials produce a convergent series whose sum is Euler's number e:
...
In mathematics, the gamma function (represented by the capital Greek letter G) is an extension of the factorial function, with its argument shifted down by 1, to real and complex numbers.
...
The gamma function is applicable in the fields of probability and statistics, as well as combinatorics.
...
There are several other integer sequences similar to the factorial that are used in mathematics:
...
Double factorial
...
...
Superfactorial
...
Hyperfactorial
...
Bhargava factorial
]

I did a double take (or should that be factorial take? :) when I saw that one, because I didn't expect a factorial type to be named after a person (but why not, really); the person is Fields Medal-winning mathematician Manjul Bhargava.

All the above factorial-related terms are mentioned in the Wikipedia factorial article, and there are also links to some of them there.

And did you know that triangular numbers are the additive analogues of factorials?

The image at the top of the post is a visual representation of Nicomachus's theorem, which involves what are called squared triangular numbers. His theorem says that:

The sum of the first n cubes is the square of the nth triangular number. That is,

1 cubed + 2 cubed + 3 cubed + ... + n cubed = (1 + 2 + 3 + ... + n) squared,

where the nth triangular number is the sum of the natural numbers from 1 to n.

Speaking of mathematics, you may also like this earlier post by me:

Bhaskaracharya and the man who found zero. In fact, the Wikipedia article on permutations says that the relationship between permutations and factorials (described above) was known to mathematicians in India by around 1150 A.D.

- Enjoy.

- Vasudev Ram - Online Python training and consulting

Get updates on my software products / ebooks / courses.

1 comment:

Vasudev Ram said...

BTW, while reviewing the above program, I noticed that it has 37 lines of code (including comments and blank lines). On a whim, I googled the number 37 (knowing that certain numbers have special properties - this again is part of number theory) and this is what I found:

https://en.wikipedia.org/wiki/37_(number)

Excerpts:

Thirty-seven is the 12th prime number, a permutable prime with 73 (which is the 21st prime number). 37 is the fifth lucky prime,[1] the first irregular prime,[2] the third unique prime[3] ...

[snip an image of an equation, which cannot be pasted here - but see the article linked above ]

37 is the smallest prime that is not also a supersingular prime.

It is a centered hexagonal number[5] and a star number.[6]

Every positive integer is the sum of at most 37 fifth powers (see Waring's problem).

37 appears in the Padovan sequence, preceded by the terms 16, 21, and 28 (it is the sum of the first two of these).[7]

Since the greatest prime factor of 372 + 1 = 1370 is 137, which is substantially more than 37 twice, 37 is a StÃ¸rmer number.[8]

Also, I had found a while ago, that 37 multiplied by some numbers, gives numbers with repeating digits, like 111, 222, etc. - at intervals. Try this:

for i in range(1, 37):
....print 37, "x", i, "=", 37 * i

(Replace the 4 dots above by 4 spaces).

:)