Today’s world is shifting more and more towards coding and other AI stuff. Due to increasing use of various coding language and tools it has become extremely important for an individual to learn coding and other scientific tools that makes our life easy .
This project is an attempt towards using python language and see how it can help us in the study of combinatorics. We will primarily study basic topics of combinatorics and try to implement the python code to generalize or print the the result. For example printing all binary strings of length n !! For a human being listing all binary strings of length 10 will take a long time and we might make lots of mistakes while listing it but for computer using appropriate code and tool its a piece of cake.
We will deal with many such problems and make the study of combinatorics easy and more fun.
In combinatorics, binary strings are sequences made up of only two distinct types of symbols or elements, most commonly 0s and 1s. They are fundamental in counting problems and represent a variety of situations where there are only two possible outcomes for each position in a sequence.
Binary strings of length n is nothing but are binary strings of different length and it is a natural number. For example binary string of length one, length two,length three and so on. Now if I ask you to list all the binary strings of length 3 you will easily list it i.e \(\{000,001,010,100,011,110,101,111\}\). But listing higher length binary strings will become difficult and is likely to have some error while listing. That’s where the coding comes into picture and solves our problem. Thus we present our first code for the following problem statement :–
The below r chunk helps to run Python code in R-Markdown and the reticulate package acts like a bridge between r studio and python.
library(reticulate)
reticulate::use_python("/Users/akashkumarmishra/Desktop/venv/bin/python")def binary_str_len_n(n): # n denotes string of length n
list_1=["0","1"] # base case
if n==1:
return list_1
else:
for i in range(1,n):
list_2=[] # Defining an empty list
for j in range(len(list_1)):
list_2.append(list_1[j]+"0")
list_2.append(list_1[j]+"1")
list_1=list_2
return list_1
binary_str_len_n(4) # Function calling## ['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']In the above code we used the recurrence relation of total number of binary strings of length n . Thus for a given n we recursively find binary string of that length meaning for n = 5 we first find all binary strings of length 2 the using this we find binary strings of length 3 and so on we reach till the list of all binary strings of length 5. Hope you understood the math behind it 😁 By the way the recurrence relation is as follows: \[b_n=2b_{n-1}\] where \(b_n\) denotes the total number of binary strings of length n and \(n>2\) and \(b_1=2\).
In the previous section we saw that how to list all the binary strings of length n, where n is given by the user as an input . Now we are interested in answering the question, how many binary strings of length four with exactly two ones are there from the set of all binary strings of length four and can we list them all ?? The answer to this question is definitely yes but for small values of n . What if the n is large ? How can we list them all? Again python code comes to our rescue. But before going towards python code lets quickly look at a small example.
List all Binary Strings of Length 4 with exactly three ones: — {0111 , 1110 , 1011 , 1101}
To achieve this we will use the previously defined function of listing all binary strings of length n . After retrieving that list we will separate the required elements from that list to a new list and return that as an output . Lets do this 😊
def binary_str_len_n_with_k_ones(n,k): # function name,n=length of string and k is number of ones
list_1=binary_str_len_n(n)
list_2=[]
for i in list_1:
count=0
for j in i:
if j=="1":
count=count+1
if count==k:
list_2.append(i)
return list_2
binary_str_len_n_with_k_ones(5,2) ## ['00011', '00101', '00110', '01001', '01010', '01100', '10001', '10010', '10100', '11000']From the above code we can also check one of the fundamental result of combinatorics that is \(\binom{n}{k} = \binom{n}{n-k}\) How can we achieve this ?? If you look at the code it returns a list of the desired strings so we can find the length of this list and compare it with its complement meaning if you call above function for values n=5 and k=3 you will get a list of binary strings of length 5 with exactly 3 ones . We will now call the same function but with values n=5 and k=2 . What do you notice ??🤔 length of both the list is exactly same 😳 Thus the result is verified 😎
We now present the code for printing binary strings of length n with odd numbers of ones. This can be achieved by using the previous function we defined to get list of all binary strings length n. Then by some modification to this we can get a new list of the desired output.
def binary_str_len_n_odd_ones(n): # n = number of binary strings
list_1=binary_str_len_n(n)
list_2=[]
for i in list_1:
count=0
for j in i:
if j=="1":
count=count+1
if count%2!=0:
list_2.append(i)
return list_2
binary_str_len_n_odd_ones(4) ## ['0001', '0010', '0100', '0111', '1000', '1011', '1101', '1110']The idea is very simple . We already had a list of binary strings for a given n , so we just had to check how many ones each element has i.e first we need to access each element, for that i loop is used . When the first iteration begins, 0 indexed string was stored inside i now our job was to find out how many ones does i has ? For that we have defined an inner for loop that access each element of i (since it is a string). If element turns out to be one we increase the count by 1 (initially the count was zero) so by the end of the inner loop we have a count value . If i has odd number of ones then count will be an odd number using this observation we wrote the if condition but in the outside for section (Why?)
This checks whether count is odd or not. If found to be odd then we add that element in the empty list defined before i loop. This process continues and by the end of this process we get a list of binary strings of length n with odd number of ones. Hope you understood the code 😊
Immediately follows from 5.2 . The code is almost same but with a small modification. Can you find it ??
def binary_str_len_n_even_ones(n): # n = number of binary strings
list_1=binary_str_len_n(n)
list_2=[]
for i in list_1:
count=0
for j in i:
if j=="1":
count=count+1
if count%2==0:
list_2.append(i)
return list_2
binary_str_len_n_even_ones(4) ## ['0000', '0011', '0101', '0110', '1001', '1010', '1100', '1111']We want to establish an one-to-one correspondence between set of binary strings of length n and total subsets of an n element set. For example consider the set of binary strings of length 3 and call that set as \(S_1\) and consider a set of subsets of the set \(\{1,2,3\}\) and call it \(S_2\) . We will define a one-to-one correspondence between these two sets by defining a bijective map as follows
\(f:S_1 \to S_2\) as
\(f(x) = \text{index of ones present in the binary
string}\)
For example let \(S_1=\{000,001,010,100,011,110,101,111 \}\) and \(S_2=\{ \{\phi \},\{1 \},\{2 \},\{3 \},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\}\) By above function definition \(f(000)=\phi ,f(001)=\{1\},f(011)=\{1,2\}\) and like that. Thus there is a one-to-one correspondence between these two sets. That’s it for the theory part , now we proceed towards our actual goal. We have already seen that \(S_1 \approx S_2\) this suggest that their cardinalities are also same i.e |\(S_1\)|=|\(S_2\)| thus we have another way of looking at this binary strings as subsets of a natural number . Another fun fact is that total number of binary strings of length n will be equal to total subsets of an n element set and that would be \(2^{n}\). To verify this we take the help of python to see whether they are same or not ??
def find_subsets_bit_manipulation(nums):
n = len(nums)
result = []
# Iterate from 0 to 2^n - 1
for i in range(0,2**n): # 1 << n is equivalent to 2^n
current_subset = []
for j in range(n):
# Check if the j-th bit is set in i
if (i >> j) & 1:
current_subset.append(nums[j])
result.append(current_subset)
return result
# Example usage
S_2= [1, 2, 3]
all_subsets = find_subsets_bit_manipulation(S_2)
print(f"Subsets using bit manipulation: {all_subsets}")## Subsets using bit manipulation: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]The method of bit manipulation is nothing but using binary strings . What is the above code doing ? Roughly speaking if \(|S_2|\)=3 then it considers the set of all binary strings of length three and based on the index of ones it is making set of the values of \(S_2\). One can also check that the size of the above list for |\(S_2\)|=n and size of the set of binary strings of length n using previously defined function in section 5 is exactly same . Thus we verified the relation using Python 😁
We wish to establish a connection between binary strings and
fibonacci sequence . How can this be done? This can by achieve by
listing all binary strings of length n with no consecutive zeros. For
example when
n = 1, the required set would be \(S_1=\{0,1\}\) The size of this set is 2
n = 2, the required set would be \(S_2=\{01,10,11\}\) The size of this set is
3
n = 3, the required set would be \(S_3=\{111,110,011,010,101\}\)
what is
the size of this set? Is it related to n = 1 and n = 2 case ? The answer
is Yes!!. Infact for n = 3 we observe that \(|S_3|=|S_2|+|S_1|\).
Thus for an n element set the following recurrence relation holds \(S_n=S_{n-1}+S_{n-2}\). This is nothing but the recurrence relation of fibonacci sequence 😏. Now we wish to list all the fibonacci numbers upto given number n . For a general case we need to use Python and write a code for the same. Thus we introduce the following section
The following Python code does the job for us 😎
def fibo_seq(n): # n denotes the nth term of the fibonaci sequence
if n==1:
return [1]
elif n==2:
return [1,2]
else:
l=[1,2]
for i in range(1,n):
l.append(l[i-1]+l[i])
return l
fibo_seq(15)## [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]Catalan numbers are a sequence of natural numbers that appear frequently in combinatorial problems. In terms of binary strings, the n-th Catalan number,\(C_n\) counts the number of binary strings of length 2n that have an equal number of zeros and ones, with the additional constraint that at any point while reading from left to right the number of ones is greater than or equal to number of zeros.
For example when
n = 2 : the set is \(\{ 1100,1010\}\)
n = 3 : the set is
\(\{ 111000,110100,101100,1010101\}\)
and so on.
For large values of n listing set of Catlan numbers
becomes more and more difficult as the string length is becoming 2n.
Thus we need to figure out the pattern and write the code for the
same.
The following code does the job for us 😏
def Catalan_Binary_String(n): # Defining a function
result=[] # list that will contain the final result
def backtracking(num_one,num_zero,curr):
# Base case:
if len(curr)==2*n:
result.append(curr)
return
# It will always start with 1 (inclusion case)
if num_one<n:
backtracking(num_one+1,num_zero,curr+"1")
# Adding zero
if num_zero<num_one:
backtracking(num_one,num_zero+1,curr+"0")
# Backtarcking
backtracking(0,0,"")
return result
Catalan_Binary_String(3) ## ['111000', '110100', '110010', '101100', '101010']