Counting Alternating SubsetsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/