### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for MATH 294A with Professor Savitt at UA

### View Full Document

## 17

## 0

## Popular in Course

## Popular in Department

This 2 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 17 views.

## Reviews for Class Note for MATH 294A with Professor Savitt at UA

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Combinatorics and Sums Math 294A Problem Solving Seminar Combinatorics is the mathematics of counting objects in various ways One of the basic notions in combinatorics is the kth binomial coe cient of degree n or the number of ways to choose k objects out of n objects a quantity often called n choose 16 and is equal to n nl 7 gt gt ltkgt nik kl where n 7 k 7 0 Note that we have the identities ltZgtltnikgt and if nZkZL The following is often useful in nding sums involving binomial coef cients and is of course why we call a binomial coef cient in the rst place The Binomial Theorem Let I and y be variables and n 2 0 an integer Then n 7 n n nii 239 19 y Not all of the problems below will use binomial coef cients but they all deal with some type of enumeration Example 1 Show that for any integer n 2 l n2n 1 Example 2 Let n gt 1 How many ways can the set l2n be written as the union of k nonempty disjoint subsets each consisting of consecutive integers Example 3 Give a combinatorial proof that if mn 2 l and l S k S n then 16 n m 7 mn 239 k 7239 7 k 10 Example 4 Consider all 2 7 l nonempty subsets of 1 2 For each of these subsets we nd the product of the reciprocals of each of its elements Find the sum of all of these products Problem 1 a Prove that for n 2 0 n ZHVC 0 i0 Z b De ne M as a function on the positive integers by M1 l or if n gt 1 has prime factorization n pil 17quot by 716 ifei 1 for each 239 Mn 0 otherwise Using part a prove that for any positive integer n E Md 0 w Problem 2 Prove that the product of n consecutive integers is always divisble by n1 Problem 3 Prove that if n 2 1 then 41 n lt71gtn11 i1 i 7 n1 0 Problem 4 How many subsets of 1 2 n have no two successive numbers Problem 5 What is the probability of an odd number of sixes turning up in a random toss of n fair dice Hint Consider y i I i Problem 6 In the Lotto six numbers are chosen from 12 49 How many of these six elernent sub sets have at least a pair of consecutive numbers Problem 7 Let 0 lt a1 lt a lt lt an be real numbers and let ei i1 Prove that ELI eiai takes at eas IS 1110 va ues as e 6139 range over e pOSSI e com 1na 10118 O s1gns 1 t 1 d39t39 t 1 th th 2 39b1 b39 t39 f39 Problem 8 Prove that for each positive integer n 1 lt 1 11 Hint Use the Binomial Theorem Problem 9 How many ways can you select two disjoint subsets from a set consisting of n elements We se lect the two subsets as an unordered pair so we do not distinguish which order the two subsets are selected Problem 10 Let 1 S 7 S n and consider all subsets of 7 elements of the set 12 n Each of these subsets has a smallest elernent Let Fn 7 denote the arithmetic mean of these smallest elernents Prove that Fn 7 Problem 11 Prove that n 21 2 ltZgt12lt255gt k0 Problem 12 Prove that

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.