Combinatorics - Counting Problems | Computer Science Cafe

Bijection Approach

Bijection is one of the approach used in combinatorics Bijection is transforming some new problem to known problem set. Bijection with another problem set reduces new problem to similar known problem.

Bijection with [Bit]strings

Problem Move from cordinate (0,0) to (3,4) with only a move in either x or y at a time

Bijection with the string with 3X and 4Y where X is move in X direction and Y is move in Y direction
like XXXYYYY
possible arrangements with 3X and 4Y

C(7 3)

Problem 5 objects to be placed in 3 boxes
Bijection to string with 2X where X divides the string like 2X in string will divide string in 3parts or 3boxes

********X***********X******
box1 box2 box3

and 5Y where Y represents object to be placed
like XXXXXYY
Total arrangements C(7 2)

Problem 15 books are on shelf in how many ways to choose 5 books so that no two chosen book is adjacent

Bijection with bit string with 5 1's and 6 0's where 0 is for selected book and 1 for not selected book

lets take some instances for selecting books
101010101000
1000010010001001
00101001010001

now question states that there must be atleast one not selected book (0) between each selected book (1)

so the required base patten is
101010101
or more appropiately
10⁺10⁺10⁺10⁺
that is there should be at least one 0 between two 1's

Now remaining books are 15 - 9 = 6

there can be others books before between and after this pattern like

101010101 000000 after this pattern
000000101010101 before this pattern
1000010010001001 between this pattern

if we consider 10 to be one element now we have elements as

(10) (10) (10) (10) (1) 0 0 0 0 0 0

so its arrangement of this elements which is (11 6)

Problem Number of subsets of set with n elements
Bijection n length bit string where 0 is for element not selected and 1 for element selected
so for set {x1,x2,x3....xn}
if we consider subset {x2,x5} we will have bit string 0100100..0 where 2nd and fifth are 1 rest zero
so if we count number bit strings with zero and 1 we would have the possible subsets
Number of subsets is 2^n as each position can be either zero or one

Placing n indistinguishable objects in k distinguishable boxes in general
Like we saw number of ways to put 3 objects in to 2 boxes

box1 box2

aaa

                  aaa

aa                a

a                 aa

This problem was mapped into problem of positioning 1 in the four bitstring where the left of 1 specify the number of objects in box1 and right of 1 specify number of object in box2
or we need one divider for making two boxes
**********|***********
box1                   box2
like 0001 divides object, all in box1 none in box2

that is if we have to place indistinguishable objects in k boxes then we would need k-1 dividers
so general formula for placing n indistinguishable objects in k distinguishable boxes is
(n+(k-1))C(k-1)

Each box contains at least one object
If the constraint is such that each box should contain atleast 1 object or box can not be empty

we first place one object in each box which can be done in 1 way since objects are indistinguishable and then distribute remaining n-k objects in k boxes which is (n-k)c(k-1)

or if we look at bitstring when there are three boxes 5 objects and atleast one objet should be there in each

we can assume following to be single object and find the possible combinations

(01) (010) 0 0

or its pattern

(0)+1(0)+1(0)+

Problem A doughnut shop offers Plain, Glazed, Hoclate and Jelly doughnuts How many different orders of dozen doughnuts are possible. Also find when we need to select atleast one from each variety

Of the dozen doughnuts the various possibilities are

we select 2P 3G 4H 3J or 7P 3G 0H 2J and so

we need to place 12 indistinguishable doughnuts in to 4 distinguishable boxes which is (12+(4-1))C(4-1) = 15C3

or if we map the problem to bit string it is like

(0)*1(0)*1(0)*1(0)*

zero's specify doughnut in that group consider simple instance like

000001000010010

At least one from all :
when we need to select atleast one from each variety its like selecting 4 doughnuts from each variety first which can be done in single way and then selecting 8 doughnuts

which is (8+4-1)C(4-1)

Problem. Consider number from 1 to 20 we need to select three numbers from this group then what is probabability of getting pair of consecutive numbers in the three selected numbers.

Sample space S is = (20 3) that is ways to select three numbers
the selected numbers could be like
1 2 5, 2 5 6,
so a consecutive pairs can be selected in 19 ways 12,23,34,45,... 1920
and then select any number this can be done in 18 ways (except two selected numbers)
giving E = 19*18 but
there are possibility when we select the consecutive number like 4 5 and we select other number as say 6 these selection will repeat when we select consecutive number 5 6 and select other number as 4
so this repeated selections will be when we select three consecutive numbers
so number of consecutive numbers is = 18
actual E= 19*18 -18
probability = E/S

Problem In how many ways can 2n students be paired up
Arrange students in row and first each two 12 34 ..
consider 4 students 1 2 3 4 now we first find the way to arrange them
4!
1234

1243
2143
2134
1324
1342
3124
3142
1423
1432
4132
4123
2341
2314
3214
3241
2431
2413
4231
4213
3412
3421
4321
4312

we are overcounting here by
(number of ways of arranging first ) (number of ways of arranging second pair)
(2!)(2!)
now we are left with
//pending

Problem How many different outcomes are possible when 3 similar dice are tossed
Solution
If we had three distinct dice that is if we consider dice as numbered A B and C
then number of different outcomes are 6^3 that is we differentiate between outcomes
3 4 3 and
3 3 4

Here for similar dice number of different outcomes means that if on two dice its n1 and on third its n2
we donot differentiate between two dice which has n1 output so cases like
1 1 2
2 1 1
1 2 1 are all same
we can think of possible outputs as box numbered 1 2 3 4 5 6
then output of dice toss would be like

**   |         *        |          |            |         |

that is we got number 1 on two dice and number 2 on one here for six containers we have five separator
***|||||
so number of arrangements of * and | that is C(8 3)

Number of partitions of set of n objects into k groups

Stirling number of second kind

S(n,0) = 0
S(n,1) =S(n,n) = 1

Triangular Property
S(n,k) = S(n-1,k-1)+k*S(n-1,k)
can be interpreted as partition of n objects into k groups would either contain subset {n} or it does not
If it contains the subset {n} then we have one group and remaining groups can be formed in S(n-1,k-1)
If it is not contained then we have n-1 objects which should be partitioned into k groups S(n-1,k)

that each number can be derived from number directly above it and before that.
for k between 0 to n
                0    1     2     3     4         ------->k size of partition
----------------------------
S(3,k) = 0    1     3      1
S(4,k) = 0    1     7      6     1

Sum {k=0 to n }(S(n,k))
that is partition of all size is done by bell number

Counting Functions

Consider set A of r elements and set B of n elements

Counting number of functions
each value from set A can be assinged any value from the set B

for each value there are n options so its n^r

Counting Injective functions
Injective function one-to-one function states that no two values from set A can be assigned same value from set B. So if we have

r>N we don't have sufficient values in the set B and from pigeonhole principle we can prove that atleast two values will have same mappings so its 0

for r

Counting Bijections

Bijection states that every value in y should have their image in x + injection property

so for
r != n its 0 and for
r = n its n!

Counting Surjective functions

sujection or onto states that image of function is equal to its Range that is all the y in image are mapped to some x in domain

If r elements in the domain and n elements in the image

we first partition r elements in the domain to map to all n elements in the image

1)partition the elements in set X, call it S(r,n), in to n partitions

if we partition above function where r=3 and n=2 we would have partitions like {12,3} {13,2} {23,1}

2) we pick value for each partition that is for (12) and for (3) we can pick value for them in n! ways

So we have number of onto functions = S(r,n)*n!
where S(r,n) is Stirling number

Another method for counting surjection

Let m be number of element in domain and n be number of element in co-domain
Using principle of inclusion and exclusion
let elements y1 y2 ..yn be not in range and conidtion p1 p2 ....pn represent this resp.
then for surjection there should be all element in codomain should be in range so

N(p1'p2'..pn') = N- N(p1p2p3)

that is condition when all elements not mapped = total number of function - condition when all the element are mapped

N= n^m

N(p1p2p3) = when 1 element is not mapped + when 2 elements are not mapped +.. when all m elements are not mapped

N(p1p2p3) = C(n,1)(n-1)^m +C(n,2) (n-2)^m.........(-1)^n-1 C(n,n-1) 1^m

so total surjections are
n^m -C(n,1)(n-1)^m +C(n,2) (n-2)^m.........(-1)^n-1 C(n,n-1) 1^m

Problems number of way to assign 5 different jobs to 4 different employee such that every employee gets at least one job

Solution
Its surjection from 5 to 4 elements n=4 and m=5

4^5 - c(4,1)3^5 + c(4,2) 2^5 - c(4,3)

References
Some useful links for combinatorics problems and solutions

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2005/assignments
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-sma-5512-fall-2002/assignments/ http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2005/assignments/
http://www.geometer.org/mathcircles/solnscount.pdf
www.cs.pitt.edu/~adamlee/courses/fall_08/cs441/.../lecture21.pdf
http://2000clicks.com/MathHelp/CountingObjectsInBoxes.aspx
http://www.math.cornell.edu/~web4410/ //solutions to 'A course in combinatorics '