wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> How Many Sequences?
        
(Message started by: inexorable on Nov 7^th, 2005, 12:05pm)

Title: How Many Sequences?
Post by inexorable on Nov 7^th, 2005, 12:05pm

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?

Title: Re: How Many Sequences?
Post by Icarus on Nov 12^th, 2005, 11:23am

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 {a_i} 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=1^n-k+1 C(n,j)R(n-j,k-1)

The value desired is R_n = [sum]_k=1ⁿ R(n,k).

Title: Re: How Many Sequences?
Post by Eigenray on Nov 12^th, 2005, 2:50pm

Looks a lot like [hide](n+1)^n-1[/hide].

Title: Re: How Many Sequences?
Post by Eigenray on Nov 12^th, 2005, 10:26pm

Let [n+1]={1,2,...,n+1}, and define a function F:[n+1]ⁿ -> [n+1] as follows.

For a sequence a=(a₁,...,a_n) in [n+1]ⁿ, construct an injection f_a:[n]->[n+1] by taking f_a(i) to be a_i 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 f_a.

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 f_a(i) in {F(a)+1,...,n+1}, we must have a_i > F(a). Conversely, if F(a)=n+1, then for any k<=n, there can be at most n-k values of i with a_i>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+1) = (n+1)^n-1.