Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Counting Alternating Subsets

Date: 03/29/2003 at 13:52:30
From: Lindsay
Subject: Finding the number of alternating subsets.....

A subset of A_n={1,2...,n} is said to be alternating if, when the 
elements of S are listed in increasing order, the smallest is odd, 
the next is even, the next is odd, and so on. The last element of S 
may be odd or even as long as the pattern is followed. By convention, 
null is alternating. 

Find the number of alternating subsets of A_n.  The answer must be in 
terms of a known sequence, or a simple formula, and you must prove 
that it is correct.


Date: 03/30/2003 at 09:58:54
From: Doctor Jacques
Subject: Re: Finding the # of alternating subsets.....

Hi Lindsay,

We will count separately the subsets ending in an odd and an even 
number.

Let:

  * x(n) be the number of alternating subsets from A_n ending in an
    even number (we will call these even subsets)
  * y(n) be the number of such subsets ending in an odd number (we 
    will call these odd subsets)
  * z(n) be the total number of subsets.

We have:

    z(n) = x(n) + y(n) + 1

where the 1 comes from the empty subset (which is counted neither in 
x(n) nor y(n)).

Assume that n is even.

An even subset can arise it two ways:

  * either it ends in n, and this means that it follows an odd subset
    of A_(n-1), of which there are y(n-1)
  * or it does not, and this means that it is an even subset of
    A_(n-1), of which there are x(n-1)

Note that, since alternating subsets must start with an odd number, 
we cannot have n alone.

The total number of even subsets is therefore:

    x(n) = x(n-1) + y(n-1)

An odd subset cannot end in n, so the odd subsets are just the odd 
subsets of A_(n-1):

    y(n) = x(n)

Consider now the subsets of A_(n-1); n-1 is odd.

An even subset cannot end in n-1, so the even subsets are just the 
even subsets of A_(n-2)

An odd subset can now arise in three ways:

  * it is {n-1} alone
  * it is an even subset of A_(n-2) followed by n-1
  * it is an odd subset of A_(n-2)

We have thus:

    x(n-1) = x(n-2)
    y(n-1) = x(n-2) + y(n-2) + 1

Notice that we have:

    x(n) = z(n-1) - 1
    y(n) = y(n-1) = z(n-2)

If you put everything together, you should indeed recognize z(n) as a 
well-known sequence. (You will still have to check the initial 
values.)

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 


Date: 04/01/2003 at 12:38:28
From: Lindsay
Subject: Re: Finding the number of alternating subsets

I am still confused about which well known sequence z(n) is and what 
the final correct solution is.  

Thanks!


Date: 04/03/2003 at 06:39:33
From: Doctor Jacques
Subject: Re: Finding the number of alternating subsets

Hi Lindsay,

We have shown that:

  x(n) = z(n-1) - 1
  y(n) = y(n-1) = z(n-2)

We are interested in z(n); as shown before,

  z(n) = x(n) + y(n) + 1

If we substitute the values of x(n) and y(n) above, we obtain:

  z(n) = z(n-1) + z(n-2)

This is for n even. If n is odd, we repeat the argument above, but we 
interchange the two cases (n and n-1):

  x(n) = x(n-1)
  y(n) = x(n-1) + y(n-1) + 1 = z(n-1)

  x(n-1) = x(n-2) + y(n-2) = z(n-2) - 1
  y(n-1) = y(n-2)

and we also obtain the same formula:

  z(n) = z(n-1) + z(n-2)

This is indeed a very well-known series, the Fibonacci series. If you 
are unfamiliar with it, you can search our archive for that name, or 
start with the Dr. Math FAQ and follow the links at the bottom of the 
page:

   Golden Ratio, Fibonacci Sequence
   http://mathforum.org/dr.math/faq/faq.golden.ratio.html 

Note that in this case, the first two terms are z(0) = 1 and z(1) = 
2, so you would start at the second term of the Fibonacci sequence.

Does this make sense ? Please write back if you require further 
assistance.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/