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

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

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