Counting-Examples

Some counting problems 1 Ordered non-negative partitions of an integer : the number S N,n of non-negative solutions of x 1 + x 2 + . . . + x n = N (1) is S N,n = ( N + n − 1 n − 1 ) . (2) One way to see it: put N + n − 1 boxes in a row, then put the plus sign in n − 1 of them; this establishes a bijection between the box configurations and solutions of the equation (1). For example, with N = 9, n = 4, the following configuration corresponds to the ordered partition 9 = 2 + 0 + 6 + 1. The total number of these box configurations is given by (2). Variation: ordered partitions with lower bound , that is, non-negative integer solutions of (1) satisfying x k ≥ ℓ i for some positive integers ℓ k . This is reduced to the original problem with the same n , but with N − ∑ n i =1 ℓ i instead of N . The reason: corresponding box configuration will have only N + n − ∑ n k =1 ℓ k places to put the pluses. Equivalently, replacing x k with x k − ℓ k reduces the problem to an unrestricted one. For example, S + N,n = ( N − 1 n − 1 ) is the number of positive solutions of (1) and corresponds to taking ℓ i = 1 for all i . The general counting technique, establishing a bijection between the objects we want to count and the linear configurations of two types of objects, is known under names stars and bars , sticks and stones , balls and bars , and dots and dividers (and maybe more). Multinomial formula: ( x 1 + · · · + x n ) N = ∑ k 1 + ... + k n = N N ! k 1 ! k 2 ! · · · k n ! x k 1 1 x k 2 2 · · · x k n n Example: ( a + b + c ) 3 = a 3 + b 3 + c 3 [3 = 3 + 0 + 0] + 3( ab 2 + ba 2 + ac 2 + ca 2 + bc 2 + cb 2 ) [3 = 2 + 1 + 0] + 6 abc [3 = 1 + 1 + 1] Further reading: Young tableau, Young diagram, etc. Runs in Bernoulli trials: In a finite sequence of tosses of a coin, a run of heads is a consecutive appearance of heads. For example, each of the following three sequences ( a ) HH TTT H T HH TTT ( b ) T HH TTT H T HH TT ( c ) TTT HH TTT H T HH (3) has three runs of heads and the total length 12. By convention, the number of runs of tails in each case is four : the first sequence started with H , and the convention is to say that the first run of tails has length 0; similarly, the third sequence ends with heads, and the convention is to say with the fourth run of tails has length 0 When the coin is fair and the tosses are independent, all 2 N sequences of length N are equally likely. Then, given that the sequence contains n heads and m = N − n tails, the probability to have r runs of heads is R n,m ; r = ( n − 1 r − 1 )( m +1 r ) ( n + m n ) . 1 Sergey Lototsky, USC. Updated August 28, 2022 1