Question on HW 3, Q1(b)

If I’m understanding the definition of a first run correctly, then the lengths of the first runs of the permutations of [3] are as follows:

123:  3

132:  2

213:  2

231:  2

312:  1

321:  1

Thus, the average length of a first run is 11/6, but 1/1! + 1/2! + 1/3! = 5/3 \ne 11/6. Am I doing something wrong?



  1. I think the permutation 213 has 1 as the length of its leftmost run. The 2 by itself, yes? This should give 10/6 for the average length, which does match up.

  2. suitored

    @dgklein But then how do you distinguish “leftmost” run from any other run? I think a leftmost run must begin at the beginning, right?

  3. suitored

    I did it for n = 4 and it seems they have to be consecutive…

  4. Sorry guys, I wrote HW3 on an airplane, and apparently I wasn’t writing very lucidly. I already fixed the mistake on the website.
    In problem 1(b), a run in a permutation w is a maximal sequence of increasing **consecutive** elements w_i < ... < w_{i+k}. So the runs of 213 are 2 and 13.

    On the other hand, I stated problem 1(d) slightly vaguely (what if there is no mth run? Etc.). I did that on purpose. It's good for you to get used to slightly open-ended question. 🙂

  5. So, for the example of 213, the leftmost run is 2?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: