HW2 Q5

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?)

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)

• jdbastidas251

you’re missing $(2,3,1,2)$.

• jdbastidas251

so, there are 24 full sequences of length 4.

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.)

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$.

• how is it defined?

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.