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)

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

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
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search