In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. The study of permutations of finite sets is a topic in the field of combinatorics.
We find the number of $k$-permutations of $A$, first by determining the set of permutations and then by calculating $\frac{|A|!}{(|A|-k)!}$. We first consider the special case of $k=|A|$, which is equivalent to finding the number of ways of ordering the elements of $A$. First we import the itertools library.
import itertools
A = {1, 2, 3}
# Find all permutations of A and |A!|
permute_all = set(itertools.permutations(A))
print("Permutations of %s: " %A)
for i in permute_all:
print(i)
print;print ("Number of permutations: ", len(permute_all))
Permutations of {1, 2, 3}: (3, 1, 2) (1, 3, 2) (3, 2, 1) (2, 3, 1) (1, 2, 3) (2, 1, 3) Number of permutations: 6
# Find |A|! directly
from math import factorial
print(factorial(len(A)))
6
A = {1, 2, 3, 4}
k = 3
# Print all the k-permutations of A
n = len(A)
permute_k = list(itertools.permutations(A, k))
print("%i-permutations of %s: " %(k,A))
for i in permute_k:
print(i)
print;
print ("Size = {}!/({}-{})! = {}".format(n,n,k, len(permute_k)))
3-permutations of {1, 2, 3, 4}: (1, 2, 3) (1, 2, 4) (1, 3, 2) (1, 3, 4) (1, 4, 2) (1, 4, 3) (2, 1, 3) (2, 1, 4) (2, 3, 1) (2, 3, 4) (2, 4, 1) (2, 4, 3) (3, 1, 2) (3, 1, 4) (3, 2, 1) (3, 2, 4) (3, 4, 1) (3, 4, 2) (4, 1, 2) (4, 1, 3) (4, 2, 1) (4, 2, 3) (4, 3, 1) (4, 3, 2) Size = 4!/(4-3)! = 24
# Print |A|!/(|A|-k)! directly
print(int(factorial(len(A))/factorial(len(A)-k)))
24
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics, from evolutionary biology to computer science, etc.
Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry, as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving an ad hoc solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics is graph theory, which by itself has numerous natural connections to other areas. Combinatorics is used frequently in computer science to obtain formulas and estimates in the analysis of algorithms.
We find the number of $k$-combinations of $A$, first by determining the set of combinations and then by simply calculating ${|A|}\choose{k}$.
from scipy.special import binom # to calculate the binomial coefficients |A| choose k
A = {1, 2, 3, 4}
k = 2
# Print all the k-combinations of A
choose_k = list(itertools.combinations(A,k))
print("%i-combinations of %s: " %(k,A))
for i in choose_k:
print(i)
print;print("Number of combinations = %i!/(%i!(%i-%i)!) = %i" %(n,k,n,k,len(choose_k) ))
2-combinations of {1, 2, 3, 4}: (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) Number of combinations = 4!/(2!(4-2)!) = 6
# Print |A|!/(k!(|A|-k)!) directly
print(int(factorial(len(A))/(factorial(k)*factorial(len(A)-k))))
6
A = {'m','a','t','h'}
k = 3
# Print all the k-permutations of S
n = len(A)
permute_k = list(itertools.permutations(A, k))
print("%i-permutations of %s:" %(k,A))
for i in range(0, len(permute_k)):
print(''.join(permute_k[i]),end=',')
print;print ("Size = %i!/(%i-%i)! = " %(n,n,k), len(permute_k))
print("\n")
n = len(A)
k=4
permute_k = list(itertools.permutations(A, 4))
print("%i-permutations of %s:" %(k,A))
for i in range(0, len(permute_k)):
print(''.join(permute_k[i]),end=',')
print;print ("Size = %i!/(%i-%i)! = " %(n,n,k), len(permute_k))
3-permutations of {'a', 'h', 'm', 't'}: ahm,aht,amh,amt,ath,atm,ham,hat,hma,hmt,hta,htm,mah,mat,mha,mht,mta,mth,tah,tam,tha,thm,tma,tmh,Size = 4!/(4-3)! = 24 4-permutations of {'a', 'h', 'm', 't'}: ahmt,ahtm,amht,amth,athm,atmh,hamt,hatm,hmat,hmta,htam,htma,maht,math,mhat,mhta,mtah,mtha,tahm,tamh,tham,thma,tmah,tmha,Size = 4!/(4-4)! = 24
# Print |A|!/(|A|-k)! directly
print(int(factorial(len(A))/factorial(len(A)-k)))
24
A = {'a', 'b', 'c', 'd'}
k = 2
# Print all the k-combinations of A
choose_k = list(itertools.combinations(A,k))
print("%i-combinations of %s:\n" %(k,A))
for i in range(0, len(choose_k)):
print(''.join(choose_k[i]) )
print;print ("Size = %i!/(%i!(%i-%i)!) = " %(n,k,n,k), len(choose_k))
2-combinations of {'a', 'd', 'b', 'c'}: ad ab ac db dc bc Size = 4!/(2!(4-2)!) = 6
# Print |A|!/(k!(|A|-k)!) directly
print(int(factorial(len(A))/(factorial(k)*factorial(len(A)-k))))
6