HW2 Q5

Please confirm:

A sequence of positive integers is full if for any k greater than 1 which appears in the sequence, the number k-1 appears at least once before the last occurence of k.

(otherwise the answer is 0, no?)

Advertisements

18 comments

  1. emac32

    I think we must assume that if a sequence is full, then it has no 1s.

  2. but if there’s a 2 there must be a 1; if there’s a 3 there must be a 2 and a 1, etc.

  3. I think I agree that as it’s written, k must be greater than 1. Because then k-1 can be 1, but zero will never appear. Another possibility is the sequence should be of nonnegative integers, and k can then be greater than or equal to 1? I tried to look up other references, but can’t find any other def of a full sequence..

  4. ninalyssa

    It seems like this may have already been agreed upon, but I just wanted to confirm that I also interpreted this to mean that $ latex k > 1 $.

  5. note to federico: i’ve had to “approve” the above comments to this post; can that be changed? it’s a little frustrating that folks aren’t responding in a very timely manner to simple questions (it seems), but maybe part of the problem is there is a delay due to moderation of the threads.

  6. rafael11112013

    Is the sequence (1,1,1,1) full, when n=4?

  7. i claim yes. I found 21 full sequences for n=4, how about you?

    • dgklein

      I think there are 23:

      (1, 1, 1, 1)
      (1, 1, 1, 2)
      (1, 1, 2, 1)
      (1, 1, 2, 2)
      (1, 1, 2, 3)
      (1, 2, 1, 1)
      (1, 2, 1, 2)
      (1, 2, 1, 3)
      (1, 2, 2, 1)
      (1, 2, 2, 2)
      (1, 2, 2, 3)
      (1, 2, 3, 1)
      (1, 2, 3, 2)
      (1, 2, 3, 3)
      (1, 2, 3, 4)
      (1, 3, 2, 3)
      (2, 1, 1, 2)
      (2, 1, 2, 1)
      (2, 1, 2, 2)
      (2, 1, 2, 3)
      (2, 1, 3, 2)
      (2, 2, 1, 2)
      (3, 1, 2, 3)

  8. Kyla is right, the condition of the statement only applies for k>1. And 1111 is a full sequence.

    (The approval of comments is strange, but I don’t think it is slowing down the discussion significantly. To avoid spam, (only) the first time that a person participates, I am asked to approve their first comment. I do that as soon as I see the comment. You were also asked to approve these because you are the author of the post.)

  9. *spoiler alert*, maybe

    we noticed that the full sequences of length n, f(n) can be broken up in a natural way:
    f(1)=1
    f(2)=1+1
    f(3)=1+4+1
    f(4)=1+11+11+1.
    these numbers also appear in lecture (5?), hinting at a bijection.

  10. dgklein

    @jdbastidas: I don’t seem to be able to reply to your reply to my comment directly, but you’re right, I missed one. (Actually, I misread the problem, so I thought that all the numbers less than k had to appear before the last k; thanks for helping me to discover this!)

  11. As @kyqu mentioned (I’m sorry but I can’t figure out your name from your nickname lol) there seemed to be a correspondence between the full sequences of length n with maximum k and the A(n,k) coefficients. Did anyone find a way to solve the problem using this approach? Or maybe someone tried cases greater than n=4 and found out that it didn’t work out that way?

    • dgklein

      I wrote a program to check this, and it continues to hold for n \le 8 (which was the largest n I checked). Interestingly, I think I found a bijection between permutations and full sequences, but it doesn’t necessarily send permutations with k - 1 descents (or ascents) to full sequences with largest element k.

  12. Hey it’s Kyla! I have been struggling to find a bijection this way myself! Still open to Bright Ideas..

  13. dgklein

    The bijection is a little hard to describe in the abstract, but it’s basically an algorithm for constructing a full sequence f from a permutation w. The idea is as follows: Start with f empty. The first step is to find the 1 in w, and put a 1 in the same position in f. For 1 < j \le n, the rule is: If the j in w is to the left of the j – 1, insert a k into f in the same position as the j in w (where k is the largest number added to f in the first j – 1 steps); if the j in w is to the right of the j – 1, insert a k + 1 into f in the same position as the j in w.

    So, for example, if w = 2764135, we construct f as follows:

    (1) since the 1 in w is in the fifth position, we put a 1 in f in the fifth position;
    (2) since the 2 in w is in the first position and is to the left of the 1, we put a 1 in f in the first position;
    (3) since the 3 in w is in the sixth position and is to the right of the 2, we put a 2 in f in the sixth position;
    (4) since the 4 in w is in the fourth position and is to the left of the 3, we put a 2 in f in the fourth position;
    (5) since the 5 in w is in the seventh position and is to the left of the 4, we put a 3 in f in the seventh position;
    (6) since the 6 in w is in the third position and is to the left of the 5, we put a 3 in f in the third position;
    (7) since the 7 in w is in the second position and is to the left of the 6, we put a 3 in f in the second position.

    So f = 1332123. (Maybe I'll leave it as an exercise to prove that this does always give a full sequence and is a bijection.) However, w has both 3 ascents and 3 descents, while the largest number in f is 3.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: