Author |
Topic: Self-counting sequences (Read 1423 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Self-counting sequences
« on: Apr 8th, 2005, 6:43pm » |
 Quote  Modify
|
Determine all sequences
x0, x1, ..., xn-1,
such that xk is the number of times k appears in the sequence.
(I asked this a while ago in another thread, but nobody answered.)
A bit harder: How many such infinite sequences are there?
|
|
 IP Logged |
|
|
|
markr
Junior Member
Gender:
Posts: 90
|
|
Re: Self-counting sequences
« Reply #1 on: Apr 8th, 2005, 10:12pm » |
Quote Modify
|
If I understand correctly, I get these finite sequences (probably not all):
1 2 1 0
2 0 2 0
2 1 2 0 0
3 2 1 1 0 0 0
4 2 1 0 1 0 0 0
5 2 1 0 0 1 0 0 0
...
N 2 1 (N-3)*0 1 0 0 0
...
|
|
IP Logged |
|
|
|
markr
Junior Member
Gender:
Posts: 90
|
|
Re: Self-counting sequences
« Reply #2 on: Apr 8th, 2005, 10:44pm » |
Quote Modify
|
How about this for infinite sequences:
Let xn-1 be the last term in any of the above sequences.
The next n2 terms are n n's, n (n+1)'s, n (n+2)'s, ...
After this the sequence dictates itself if you follow a string of n's with a string of (n+1)'s.
It's hard to describe, but here's an example:
1 2 1 0 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 ...
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Self-counting sequences
« Reply #3 on: Apr 9th, 2005, 8:31am » |
Quote Modify
|
That is in fact all of the finite sequences (proof?). And each finite sequence can be extended to at least one infinite sequence as you show. But what is the exact cardinality of the set of such infinite sequences?
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Self-counting sequences
« Reply #4 on: Apr 9th, 2005, 2:30pm » |
Quote Modify
|
| hidden: |
Well, the n terms sum to n; also, a0 along with the a0 zero terms are a0 + 1 terms that sum to a0. So the remaining k terms sum to k+1, and all are >= 1; the only way this is possible is if one term is 2 and the rest are 1. So there is at most one term greater than 2, and there is at most one nonzero term beyond a2.
If a0 > 2, then aa_0 = 1, so we must have a1 = 2, and a2=1; the remaining terms must be all zero, and we get n = a0 + 4.The cases a0 = 1 or 2 are straightforward.
For infinite sequences, we can do the following: at step zero, pick any postive integer for a0, then pick a0 arbitrary terms and set them to 0; at step i, we set ai if it has not already been set. ai cannot be a value k such that ak has been set and setting ai=k causes more than ak terms to be k; nor can it be less than the number of terms already set to i. However, any of the infinitely many other possibilities are fine. Then we can set however many unset terms we need to be i, so that there are ai such terms. This won't cause a term to be too low, since for any unset term ak we have k > i, and only terms aj with j < i can have value k. Following this procedure will generate a sequence with the desired property, since for any i, we insure that term ai has the right value at step i, and don't add any more terms with value i thereafter. Since we make infinitely many choices, each choice having more than one possibility, the cardinality is that of the continuum.
|
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Self-counting sequences
« Reply #5 on: Apr 9th, 2005, 4:05pm » |
Quote Modify
|
Correct.
One can generalize the notion of self-counting:
For an ordinal A, a function X : A -> A+1 shall be called A-cromulent if for each c in A, { b : X(b) = c } has order type X(c).
Note that if A=n, a natural number, this is exactly the same as before. If A=omega, the sequences
A, 0, 0, 0, ...;
A, 0, 2, 2, 0, 3, 3, 0, 5, 5, 5, 0, 6, 6, 6, 0, ...;
A, A, 0, 1, 3, 0, 1, 4, 4, 4, 0, 1, 7, 7, 7, 7, 0, 1, 8, 8, 8, 8, 0, 1, ...;
are all examples of cromulent functions.
Determine the cardinality of the set of A-cromulent functions.
Alternatively, replace
"{ b : X(b) = c } has order type X(c)."
with
"{ b : X(b) = c } has cardinality X(c)."
or
"{ b : X(b) = c } has the same cardinality as X(c),"
and require A to be a cardinal if you like.
(To be fair, I just made this up and have no idea what the answer is. So I don't know how hard it is.)
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Self-counting sequences
« Reply #6 on: Apr 9th, 2005, 11:20pm » |
Quote Modify
|
A-cromulent? That sounds nasty! 
The previous procedure works for arbitrary cardinals alpha, provided that at each step, if we choose the value of abeta to be alpha, we still leave alpha terms unset. We get the number of sequences to be |alpha^alpha| = |2^alpha|, where ^ is cardinal exponentiation.
For noncardinals alpha, set all terms abeta with beta >= |alpha| to be 0, and set a0 sufficiently large. This will still give us |2^alpha| sequences. I haven't tried to create a procedure that will specify all sequences for noncardinal alpha.
The other versions work the same way.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print