Time Complexity of Simplex Algorithm

            Based upon the maximum number of Bases.

            When m=n/2, it is at max for a given n.

            And, in this case, C(2*m,m) = (2*m)!/m!m!

                        =(2*m)(2*m-1)(2*m-2)…(m+1)/m!

                        >2^m . And this is in theory.

 

            But, in practice, it is often (n+m)/2

 

Occupancy Problem:

            Counting different ways of distributing Balls into Cells.

            Examples:

1.      Accident analysis.

Balls = accident types

Cells = days of the week

2.      Cosmic-ray experiments.

Balls = Particles reaching a Geiger counter.

Cells = counters   

3.       Book Publishing

Balls = misprints

Cells = pages

           

            Differences:

 

1.      Whether balls are distinguishable or not

2.      Whether cells are distinguishable or not

3.      Whether cells can be left empty or not.

 

Examples:

 

1.      2 distinguishable balls to 3 distinguishable cells.

(Cells can be empty)

	1	2	3	4	5	6	7	8	9
C1	ab			a	a		b	b
C2		ab		b		a	a		b
C3			ab		b	b		a	a

 

2.      2 indistinguishable balls to 3 distinguishable cells.

(Cells can be empty)

	1	2	3	4	5	6
cell1:	aa			a	a
cell2:		aa		a		a
cell3:			aa		a	a

 

Notes.

1.      In example-1 above, if cells are not distinguishable but balls are, then distributions

1,2, and 3 are considered the same: two balls in one cell and none in the other cells.

Similarly, distributions 4-9 are considered the same: two cells with one ball each and

one cell with no balls. So, there are only two distinct distributions:

1:  Only one cell with both distinguishable balls

2:  Each distinguishable ball in a different cell, that  is,

     two cells with one ball each and it does not matter

     which cell it is and which ball it is.

 

2.      In example-2 above, if cells are not distinguishable either, then the first three distributions are

considered the same and the last three distributions are as well,

so there are only two distinct distributions in this case.

1:  Only one cell with both indistinguishable balls.

2:  Two indistinguishable cells with one

      indistinguishable cell each. 

 

3.      It is also common to distinguish between occupancy problems where the cells are allowed

to be empty and those where they are not.

For instance, if we have two distinguishable balls and two distinguishable cells,

then there are four distinct distributions as follows (cells can be empty):

 

	1	2	3	4
cell1:	ab		a	b
cell2:		ab	b	a

 

However, in this case, if cells are not allowed to be empty, then there are only two distributions,

the last two in the above table.

 

Classification of Occupancy Problems (for n balls and k cells)

           

                        1.         YYY (yes-yes-yes)     kⁿ .

                        2.         YYN (yes-yes-no)      k!S(n,k)

                        3.         NYY                           c(n+k-1,n)

                        4.         NYN                           c(n-1, k-1)

                        5.         YNY                           S(n,1) + S(n,2) +…+ S(n,k)

                        6.         YNN                           S(n,k)

                        7.         NNY                           Number of partitions of n into k

                                                                        or fewer parts

                        8.         NNN                           Number of partitions of n into

exactly k parts

 

                        Notes:

1.                  Number of partitions of a positive integer n:

If n=5, we have the following seven partitions:

1.                  {1,1,1,1,1}

2.                  {1,1,1,2}

3.                  {1,1,3}

4.                  {1,2,2}

5.                  {2,3}

6.                  {4,1}

7.                  {5}

Namely, we are interested in collections of positive integers that sum to n (5 in this case).

Note that {2,3} are the same as {3,2}

 

2.                  S(n,k): Stirling number of the second kind expressed as:

        k

=   ( S    (-1)^j c(k,j) (k-j)ⁿ ) / k!     

        j=0       

 

                                    For example,

                                    S(3,2) =   (+2³  -  2* 1³ + 0) / 2!  = (8-2+0)/2 = 3 which is the

                                    number of distinct distributions of a YNN case where

                                    we have three distinguishable balls and two indistinguishable

                                    cells and cells cannot be left empty.    

 

	1	2	3
cell1:	ab	ac	bc
cell2:	c	b	a

   

Proof of YYY Case:

Each distinguishable ball of n can be in one of k distinguishable cells, so there are  k*k*…*k (n of  those)

distinct distributions, namely, kⁿ.

This is just like the number of different numbers when numbers have each exactly n digits out of k digits.

For instance, there are 8⁵   5-digit numbers out of 8 octals such as

00000, 00001, 00002, 00003, 00004, 00005, 00006, 00007,

00010, 00011, 00012, 00013, 00014, 00015, 00016, 00017, ...

 

Proof of NYY Case:                                          

              The case of distributing n indistinguishable balls into k distinguishable

              cells when cells can be empty.

              Suppose that k distinguishable cells are labeled as

                        C1, C2, C3, …, Ck

              Then a distribution of n indistinguishable balls can be identified as a collection of n of these cells.

              For example, the collection,{C1, C1, C2, C5}, may represent the distribution of four indistinguishable

              balls where C1 has two such balls occupied, C2 has just one and C5 has just one and

              other cells all unoccupied.

              However, above collection is the same as each of the following:

                         {C1,C2,C5,C1}

                         {C1,C2,C1,C5}

                         {C5,C2,C1,C1}, and so forth. Namely the order does not

                          count.                                                                                               

              This is the same as the number of n-combinations out of k-set,

              {C1, C2, C3, …, Ck} with repetitions permitted,

              which is c(k+n-1,n).                         QED.                                                   

 

Proof of NYN Case.

 

Just like the case of NYY, we consider collections of cells like:

            {C1,C2,C3,C1,C1}

            {C1,C2,C3,C1,C2}

These two collections indicate that we have 5 balls and 3 cells (each occupied).

So, the number of distinct distributions is the same as the number

of (n-k)-combinations out of the k-set {C1,C2, …, Ck} with repititions.

 

It is  c^R (k, n-k) = c (k+n-k-1, n-k) = c (n-1, n-k) = c (n-1, k-1)

                                                                                    QED.

 

Examples of Occupancy Problems:

 

a.         Hospital Deliveries.

            Suppose that 80 babies are born in September in a hospital

            and we record the day each baby is born.

            Babies = balls, Days = cells.

            (1)        Babies in distinguished but days distinguishable.

                        C(109,80) if days can be empty.

                        C(79,29) if each day must have at least one baby

                        delivered.

            (2)        If we only care about the number of days in which exactly

                        one baby was born, exactly two were born, exactly three

                        were born, and so on, it is either an NNY case or an NNN case.

And for the former, we have the number of partitions

of the integer 80 into 30 or fewer parts.

                        For the latter, we have the number of partitions of the

                        integer 80 into exactly 30 parts.

 

b.         Sex Distribution.

            Suppose that we record the sex of the first 1000 people to get

a degree in CS at a new school.

            People = balls,

            Sex = cells. (distinguishable)

 

            (1)        if we distinguish individuals (very unlikely) then we have

                        a YYY case and hence the count is 2¹⁰⁰⁰ .

            (2)        if we are only interested in the number of each sex, we have

                        either an NYY case or an NYN case.

                        In the former case,  c(1001,1000) = 1001 distributions.

                        In the latter case, c(999,1) = 999 distributions.

 

c.         Elevator Traffic

            Suppose an elevator has 8 passengers and 5 floors to stop.

            Passengers = balls, (distinguishable)

            Floors = cells. (either)

 

            In this case, if we are only interested in different people getting

            off the elevator together on any floor, we have a YYY or a YNY

            case.

            In the former case, we have 5⁸   distinct distributions, and

            in the latter case, we have S(8,1)+S(8,2)+S(8,3)+ …+ S(8,6)

            distributions.

 

 

Applications of (Ordinary) Generating Functions to Counting.

 

1.         Sampling Problems.

            Suppose that we have three types of objects, a’s, b’s and c’s.

            And suppose that types are distinguishable but objects of the

            same type are not.

            If we are to pick either 0, 1, or 2 a’s, 0 or 1 b, 0 or 1 c, how many

            ways are there to pick k objects, 0 <= k <= 4.

 

            Now consider:

  [(ax)⁰ + (ax)¹ +  (ax)² ] [(bx)⁰ + (bx)¹] [(cx)⁰ + (cx)¹]

              (1 + ax + a² x² ) (1 + bx) ( 1 + cx)

              1 + (a+b+c)x + (ab+ac+bc+aa)x²  + (abc+aab+aac) x³ + aabcx⁴ 

              1 + 3x + 4x²  + 3 x³ + x⁴ 

              which is the generating function for b_k  representing  the number

              of different ways to pick exactly k objects in this case.

 

            Generalizing  this idea, we have the following theorem:                     

           

            Suppose that we have p types of objects, with n_k  indistinguishable

            objects of type k, k=1,2, …, p.

            The number of distinct ways of picking k objects if we can pick

any number of objects of each type (up to the given total of each

type) is given by the coefficient of x^k   in the ordinary generating  

            function:

            (1+x+x² +…+ x ⁿ¹ ) (1+x+x² +…+ x ⁿ² ) … (1+x+x² +…+ x ^np )

 

2.         Infinite Supply Problem.

           

            Suppose that we have p different kinds of objects, each in (for

            all practical purposes) infinite supply.

            How many ways are there to pick a sample of k objects?

 

            The answer is given by the coefficient of x^k in the ordinary

generating function:

            G(x) = (1+x+ x²  + …) (1+x+ x²  + …) … (1+x+ x²  + …)  

                     = (1+x+ x²  + …)^p .

 

            In order to more effectively find coefficients of above function,

we need the Binomial Theorem.

 

            (1+x)^u   = 1 + ux + u(u-1)xx/2! + u(u-1)(u-2)xxx/3! + …

       + u(u-1)(u-2)…(u-r+1)x^r /r! + …  possibly infinite

    if u is any real, positive or negative, rather than a positive

    integer.

           

Now applying this theorem to the above generating function,

            we have:

           

            G(x)    = (1+x+ x²  + …)^p

                        = (1/(1-x))^p    

                        = (1-x)^-p 

                              infinity

=     S     c(-p,r) (-x)^r .

      r=0                       

             

            For k>0, the coefficient of  x^k   is:

c(-p,k) (-1)^k

                    =  (-p)(-p-1)(-p-2)…(-p-k+1)(-1) ^k /k!

                    =  p(p+1)(p+2)…(p+k-1)/k!

                    =  c(p+k-1,k)

            Note above count is the same as that of the NYY case  in which the

            number of indis. balls corresponds to the number of indis. objects

            of the Sample.

 

            For example, if we have p=3 (3 dis. types of indis. objects in 

possibly infinite supply each), picking 4 objects will have c(6,4)

different ways.

C(6,4) = C(6,2) = 15.

            aaaa

            aaab

            aaac                                                 

                        aabb

                        aabc

                        aacc

                        abbb

                        abbc

                        abcc

                        accc

                        bbbb

                        bbbc

                        bbcc

                        bccc

                        cccc

 

 

Exponential Generating Functions.

 

Definition:

            If (a_k) is any sequence, the Exponential Generating Function is

            given by:

            H(x) =  a₀ x⁰/0!  +  a₁ x¹/1! + a₂ x²/2! + …+ a_k x^k/k! +  …       

                     =  S a_k x^k/k! , k=0,1,2,3,…, infinity.

 

Applications:

            This new generating function is useful when the sequence

            involves  permutations rather than combinations (as is the case

            with the ordinary generating functions)

 

Example:          a_k = p(n,k) = n(n-1)(n-2)…(n-k+1)

                                             = c(n,k)k!

            For this sequence, the ordinary G.F. is:

            G(x) = p(n,0)x⁰  + p(n,1)x¹ +  p(n,2)x² +  … + p(n,n)xⁿ                                                                   

                     = S n!x^k/(n-k)!  , for k=0,1,2, …, n

                        which is very hard to simplify any further.

 

            However, its exponential G.F. will be:

            H(x) =  p(n,0)x⁰/0! + p(n,1)x¹/1! + p(n,2)x²/2! + …+  p(n,n)xⁿ/n!                                                                                                                             

                     = c(n,0)*0!*x⁰/0! + c(n,1)*1!*x¹/1! + … +  c(n,n)*n!*xⁿ/n!

                     = c(n,0)x⁰ + c(n,1)x¹ + c(n,2)x² + … + c(n,n)x   

                     = (1+x)ⁿ 

 

Examples of exponential Generating functions.

1.                  Passcodes. 

A code can use three letters, a, b, or c. A sequence of five or fewer letters gives a passcode.

The passcode can use at most one b, at most one c , and up to three a’s.

How many different passcodes are there of length k, with k<=5?

H(x) = (1+ax/1!+a²x²/2!+a³x³/3!)(1+bx/1!)(1+cx/1!)

= 1 + (a/1!+b/1!+c/1!)x + 

    (ab/1!1!+ac/1!1!+aa/2!+bc/1!1!)xx +

    (abc/1!1!1!+aab/2!1!+aac/2!1!+aaa/3!)xxx +

    (aabc/2!1!1!+aaab/3!1!+aaac/3!1!)xxxx +

    (aaabc/3!1!1!)xxxxx                                           

=  1 + 1!(1/1!+1/1!+1/1!)x/1! + 

    2!(1/1!1!+1/1!1!+1/2!+1/1!1!)xx/2! +

    3!(1/1!1!1!+1/2!1!+1/2!1!+1/3!)xxx/3! +

    4!(1/2!1!1!+1/3!1!+1/3!1!)xxxx/4! +

             5!(1/3!1!1!)xxxxx/5!                                           

 

The coefficient of  x^k/k! in the above H(x) shows the number of different passcodes of length k.

For example, the number of different passcodes of length 3 is:

      3!(1+1/2+1/2+1/6)=6+3+3+1 = 13.

Note that 6 came from taking one a and one b and one c, and next 3 came from taking two a’s and one b,

and next three came from taking two a’s and one c, and finally the last one came from taking three a’s.

 

      Generalizing this idea, we have the following theorem:

 

Suppose that we have p types of objects with n_k             indistinguishable objects of type k, k=1,2, …, p.

The number of distinguishable permutations of length k with up to n_k objects of each type k is

the coefficient of x^k/k! in the exponential generating function given by:

 

(1+x+xx/2!+xxx/3!+…+ xⁿ¹/n₁!) * 

(1+x+xx/2!+xxx/3!+…+ xⁿ²/n₂!) *                   

(1+x+xx/2!+xxx/3!+…+ xⁿ³/n₃!) * … *

(1+x+xx/2!+xxx/3!+…+ x^np/n_p!)

   

2.                  YYN Case                    

Distribution of n distinguishable balls into k distinguishable cells with no empty cell.

Proof: 

            a.         A distribution can be represented by an ordered

sequence of cell numbers such that (1) first cell is

where the first ball is and the second cell is where

the second ball is , and the last cell is where the last

ball, n-th ball, is, and (2) every cell must appear at

least once to correspond to the “No empty cell”

requirement.

For instance, when k=3 (cells) and  n=5(balls),

we may have:

            {1,1,1,2,3}

            {1,1,1,3,2}

            {2,2,2,1,3}

            {3,3,3,1,2}

In the above examples, the first sequence is to indicate

that cell-1 has ball-1, ball-2, and ball-3, while cell-2 has

ball-4 and cell-3 has ball-5. The second sequence is to

indicate that cell-1 has the same three balls (just as the first sequence) but cell-2 and cell-3

have reversed their roles.

And, note that each of following sequences is illegal in this case:

            {1,1,1,2,2}       // cell-3 is missing

                                    {1,2,3,4,3}       // we do not have cell-4

                                    {3,3,3,3,2,1}    // We have only five balls and not six.

             

            b.         Let  T(n,k) = the count of YYN(n,k)

                        From above representations, we conclude that T(n,k) is

                        the number of all n-permutations out of the k-set

                        {1,2,3, …, k} with each number of this set appearing at

least once.

                        So, its exponential generating function is:

                        H(x) = (x+x²/2!+x³/3!+ …)^k   //note that we start from

//‘x’ instead of ‘1’          

         = (e^x – 1)^k .  

         = S c(k,j) (-1)^j e^(k-j)x , j=0,1,2, …, k, by the Binomial

                                             expansion.

c.         Now,  e^x = 1 + x/1!+ x²/2!+ x³/3!+ ... (as dⁿ(e^x)/dx(0)=1)

   = S xⁿ/n! , for n=0,1,2,3, …, infinity.

So,  e^(k-j)x = S(k-j)ⁿ    xⁿ/n! , for n=0,1,2,3, …, inf.             

            k                     inf.

                        H(x) = S c(k,j) (-1)^j   S  (k-j)ⁿ  (xⁿ/n!)

                                   j=0                  n=0

                              

                                   inf.         k

                                = S        S (-1) ^j c(k,j) (k-j)ⁿ (xⁿ/n!)                                

                                   n=0       j=0                     

                                              k                                                                                  

            d.         So, T(n,k) = S (-1) ^j c(k,j) (k-j)ⁿ   = k!(S(n,k))                       QED

                                             j=0     

            

Proof of YNN case.

1.                  Consider the sequences for the YYN case:

{1,1,2,2,3}       //Clearly k=3 and n=5

{1,1,3,3,2}

{2,2,1,1,3}

{2,2,3,3,1}

{3,3,1,1,2}

{3,3,2,2,1}

                        These six sequences all represent the same distribution when

                        cells are not distinguishable as they all indicate that ball-1

                        and ball-2 are in the same cell (and it does not matter which

                        cell it is) and ball-3 and ball-4 are in the same cell and ball-5

                        is in a cell by itself.

2.                  That is, k! different sequences for YYN all represent the same distribution for the YNN case.  

3.                  So, the count is T(n,k)/k! which is 

                          k

                      S(n,k) = (1/k!)  S (-1) ^j c(k,j) (k-j)ⁿ      

                                      j=0

                 

Proof of NNN Case.

 

A distribution can be uniquely described by a sequence of

positive integers (at least one) such that

1.      all the numbers in the sequence add up to n (number of balls)

2.      the sequence has exactly k (number of cells) numbers.

This is exactly a partition of n into exactly k parts.            QED

 

For instance, there are five partitions of 8 into exactly 4 parts:

            {1,1,1,5}

            {1,1,2,4}

            {1,1,3,3}

            {1,2,2,3}

            {2,2,2,2}

           

Proof of NNY Case.

 

Each distribution in this case is a partition of the integer n into k or fewer parts

(rather than into exactly k parts as is the case with the NNN Case above).         QED.

 

For instance, there are 15 partitions of 8 into 4 or fewer parts:

 

            {1,1,1,5}

            {1,1,2,4}

            {1,1,3,3}

            {1,2,2,3}

            {2,2,2,2}

            {1,1,6}

            {1,2,5}

            {1,3,4}

            {2,2,4}

            {2,3,3}

            {1,7}

            {2,6}

            {3,5}

            {4,4}

            {8}

 

 

Generating function for the Partitions of n (into n or fewer parts)

            G(x) = 1/((1-x)(1-x²)(1-x³)(1-x⁴)(1-x⁵) …) in general.

 

When the last factor of the denominator above is (1-x^m), the resulting

generating function is good for all Partitions of up to m.

 

Relationship between “Partitions of k into m or fewer parts” and

“Partitions of k into exactly m parts:”

 

            5 partitions of 8 into                          5 partitions of 4 (which is 8-4)

            exactly 4 parts.                                   into 4 or fewer parts.

 

            {1,1,1,5}                                              {0,0,0,4} which is {4}

            {1,1,2,4}                                              {0,0,1,3} which is {1,3}

            {1,1,3,3}                                              {0,0,2,2} which is {2,2}

            {1,2,2,3}                                              {0,1,1,2} which is {1,1,2}

            {2,2,2,2}                                              {1,1,1,1}

 

 

Derangement Recurrence.

 

1.              D_{n+1  =}  n(D_n + D_n-1)

2.              D_{n+1  -} (n+1)D_n  =  nD_n-1 - D_n =  - (D_n - nD_n-1)

3.              (-1)^j  ( D_j  - jD_j-1) =  (-1)^k  ( D_k  - kD_k-1)

When k=2, we have   (-1)²  ( D₂  - 2 D₁) = (1-2*0) = 1

4.              (-1)^j  ( D_j  - j D_j-1) = 1 for all j’s.

5.              D_j  - j D_j-1 =  (-1)^j  for j>=1.        

6.              D_{n+1  -} (n+1) D_n =  (-1)ⁿ⁺¹  for n>=0.

7.              D_n+1 = (n+1) D_n  + (-1)ⁿ⁺¹   for n>=0.

8.              Use H(x) = S  D_n xⁿ /n!  for n=0,1,2,3, …, inf.

9.              S  D_n+1 xⁿ⁺¹ /(n+1)! = S (n+1)D_n xⁿ⁺¹/(n+1)! + S (-1)ⁿ⁺¹ xⁿ⁺¹/(n+1)!

                                          for n=0,1,2, …, inf. , from (7) above.    

10.          LHS = H(x) - 1   (as D₀  = 1  (D₁ = 0))

11.          First term of RHS = xH(x)

12.          Second term of RHS =  -x/1! + x²/2! -  x³/3!  +  x⁴/4! - … +

            =   e^{-x  -} 1  as   e^-x  = 1 – x/1! +  x²/2!  - x³/3! +            

13.          H(x)-1 = xH(x) + (e^-x – 1)   

14.          H(x)     =  e^-x / (1-x) = e^-x (1-x)^-1

=  (1 – x/1! +  x²/2!  - x³/3! + … -) (1+x+xx+xxx+xxxx+…+ )            

                      =  S xⁿ ( 1 – 1/1! +  1/2!  - 1/3! + 1/4! - … +  (-1)ⁿ /n! )

                                              for n=0,1,2,3, …, inf. 

15.          So, D_n  =  n!(1 – 1/1! +  1/2!  - 1/3! + 1/4! - … +  (-1)ⁿ /n! )