Another way to think of the weight of a walk beginning at vertex j is that each stationary step is given weight 1 and each forward step in the walk is given weight ωj , and the weight of the walk is defined as the product of the weights of its steps. Consequently, the total weight of all n-walks that begin at j is (1 + ωj )n, since each (1 + ωj ) represents a choice in our walk to make a stationary or forward move. (Alternatively, (1 + ωj )n = k≥0 n k ωjk is the sum of the weights of all n-walks starting at j since n k ωjk is the total weight of all such walks with k forward steps.) Summing
over all possible starting points,