Author |
Topic: How Many Sequences? (Read 430 times) |
|
inexorable
Full Member
Posts: 211
|
 |
How Many Sequences?
« on: Nov 7th, 2005, 12:05pm » |
 Quote  Modify
|
Fix a positive integer n. How many sequences (a1, a2, ... , an) of positive integers are there with the property that at most i of the terms are greater than n-i, for all i = 0,1,...,n?
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
|
Re: How Many Sequences?
« Reply #1 on: Nov 12th, 2005, 11:23am » |
Quote Modify
|
This is what I have so far, which I am putting out to direct a little attention to this, rather than as any significant progress.
Let R(n,k) be the number of such sequences with maximal element <= k. Clearly R(n,1) = 1 for all n>0.
If {ai} is a sequence of n elements satisfying the condition for n, and we remove all instances of the highest element (which must be <=n), then the remaining sequence satisfies the same condition for the n-j, where j is the number of instances removed. For if i <= n-j, and m is the number of terms > n-j-i in the remaining sequence, then m+j is the number of terms > n-j-i in the original sequence, so m+j <= j+i, or m < i.
Now 1 <= j <= n-k+1, and there are C(n,j) locations for the elements k to be in. So, R(n, k) = [sum]j=1n-k+1 C(n,j)R(n-j,k-1)
The value desired is Rn = [sum]k=1n R(n,k).
|
| « Last Edit: Nov 12th, 2005, 11:56am by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: How Many Sequences?
« Reply #2 on: Nov 12th, 2005, 2:50pm » |
Quote Modify
|
Looks a lot like (n+1)n-1.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: How Many Sequences?
« Reply #3 on: Nov 12th, 2005, 10:26pm » |
Quote Modify
|
Let [n+1]={1,2,...,n+1}, and define a function F:[n+1]n -> [n+1] as follows.
For a sequence a=(a1,...,an) in [n+1]n, construct an injection fa:[n]->[n+1] by taking fa(i) to be ai if it's available, otherwise the first value (cyclically) after it which is not yet chosen. Let F(a) be the element of [n+1] not in the range of fa.
The construction is such that the set we are looking for is precisely F-1(n+1): If F(a) < n+1, then for each of the n-F(a)+1 values i with fa(i) in {F(a)+1,...,n+1}, we must have ai > F(a). Conversely, if F(a)=n+1, then for any k<=n, there can be at most n-k values of i with ai>k.
But since F(a+(k,...,k)) = F(a)+k for any a,k, where addition is mod n+1, it follows
|F-1(1)| = |F-1(2)| = ... = |F-1(n+1)| = |[n+1]n|/(n+1) = (n+1)n-1.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print