Combinatorics Definition and 421 Threads

Homework Statement {n \choose 0} + {n+1 \choose 1} + {n+2 \choose 2}+...+{n+r \choose r} = {n+r+1 \choose r} We have to prove by counting both sides in a different way. For example, consider {n \choose 0}^2 + {n \choose 1}^2+...+{n \choose n}^2 = {2n \choose n} The RHS can be described as a...

given the numbers 1 2 3 4 5 6 7, how many even 3 digit numbers can be made from these 7 digits a) if each number can only be used once b) if each number can be rused for b) what i did was: for the first digit i have 7 options, for the second still 7, since i can reuse, and for the 3rd...

Homework Statement A poker hand contains five cards dealt from a deck of 52. How many distinct poker hands can be dealt containing: a) two pairs (for example 2 kings, 2 aces, and a 3) b) a flush (five cards in a given suit) c) a straight flush (any five in sequence in a given suit, but not...

Homework Statement Give two proofs (algebraic and combinatorial) of the following formula: ((nchoose2) choose 2)=3(n choose 3) +3(n choose 4) Homework Equations The Attempt at a Solution Alright, I have part of the algebraic one but I get stuck, also I don't know how to...

Homework Statement Let a, b, and c be positive integers. How many paths are there from (0, 0, 0) to (a, b, c) if we are only allowed to increase one of the coordinates by one at each step? Homework Equations The Attempt at a Solution This problem is easy for the path between...

Homework Statement The sum of 5 positive real numbers is 100. Prove that there are two numbers among them whose difference is at most 10. Homework Equations Nothing really... The Attempt at a Solution The biggest problem I'm running into is that I can think of specific examples...

If a hand of 5 cards are dealt from a 52 card pack (order doesn't matter), what is the probability that the hand will contain the ace of spades GIVEN that there is at least one ace? Thanks.

Which one do you find more interesting and why? My school offers separate classes in these two subjects and I'm wondering about which one I should take. I have very little experience with combinatorics (not much more than my high school algebra II course), so I have no idea.

Homework Statement We say that a relation R on a set X is symmetric if (x, y) \in R implies (y, x) \in R for all x, y \in X. If X = \{a, b, c, d, e, f \}, how many symmetric relations are there on X? How many of these are reflexive? Homework Equations The Attempt at a...

What's a good graduate level introductory combinatorics text. I've been looking at Cameron and Van Lint-Wilson, they seem like sound texts. Do you guys have any recommendations?

Homework Statement Suppose that a teacher wishes to distribute 25 identical pencils to Ahmed, Bar- bara, Carlos, and Dieter such that Ahmed and Dieter receive at least one pencil each, Carlos receives no more than five pencils, and Barbara receives at least four pencils. In how many ways can...

Homework Statement Suppose that a teacher wishes to distribute 25 identical pencils to Ahmed, Bar- bara, Carlos, and Dieter such that Ahmed and Dieter receive at least one pencil each, Carlos receives no more than five pencils, and Barbara receives at least four pencils. In how many ways can...

This question is out of the book, graduate problems in physics. problem 4 mathematical physics. In dealing 52 cards among two teams (containing two partners), what is the probability a particular team will obtain one complete suit between them? To determine the answer we need to find the...

A group of 3 couples has decided to start a dinner club. The first couple’s dinner table is rectangular with room for two people on either of the longer sides and room for one on either of the shorter sides. The second couple’s table is triangular, with room for two people on each side. The...

Homework Statement In how many ways can we create the sum k = x_1 + x_2 + ... + x_n where each x_i is either 1 or 2 with repetitions allowed. n <= k <= 2n For example n = 4 k = 5 1+1+1+2 1+1+2+1 1+2+1+1 2+1+1+1 are four ways. Homework Equations Is this solving...

ere me now. I'm trying to figure out how many words of length r having exactly k distinct letters can be made with an alphabet of size n. Call this number a_k,r. It satisfies the recursion a_{k,r} = ka_{k,r-1} + (n-k+1)a_{k-1,r-1} a_{1,r} = n for r >= 1 a_{k,r} = 0 for r < k My...

This isn't a hwk question, it's just something I've been trying to show my dad. I'm probably wrong. Okay my question is, suppose you pick ONE letter out of the alphabet. The odds of me picking your letter are 1/26, if I only have one guess. However, if I have two guesses, aren't the odds a...

I'm having problems wrapping my head around this...so I want to post some questions out of this Introductory Combinatorics book and what I believe to be the solutions: 1.) There are 6 rooks placed on a 6 by 6 chessboard. How many ways if there are 2 red and 4 blue? I got 6!*\binom{6}{4}...

Homework Statement Find a one-to-one correspondence between the binary strings (i.e. sequences of 0's and 1's) of length k that have an odd number of 1's, and those that have an even number of 1's. Homework Equations The Attempt at a Solution I'm not exactly sure of what it's...

Is it always possible to prove combinatorial identities in a brute force way, as opposed to the preferred way of seeing that the RHS and LHS are two different ways of counting the same thing? For example, the identity \left (^{n-1}_{k-1}\right) + \left (^{n-1}_{k}\right) = \left...

Hi! Does anybody know how to solve the following problem: \sum_{p=0}^{M}\binom{2M+2}{p}(M+1-p)=? Well, actually i know that the solution is: (2M+1)\binom{2M}{m}=\frac{2^{2M+1}\Gamma(\frac{3}{2}+M)}{\sqrt{\pi}\Gamma(M+1)} but i cannot prove it (mathematica calculates the first...

Homework Statement There is a word given: "RAKSH" and n slips are provided. A person is free to write anyone of the letters (R,A,K,S,H) in each of the slips. Repetition is allowed, i.e. for eg. one such case would be that all the 'n' slips are filled with the letter "R'. Then we begin our...

A complete tripartite K r,s,t is a generalization of a complete bipartite graph. There are three subsets of vertices, r in teh first subset, s in the second subset, and t in the third subset. Every vertex in one particular subset is adjacent to every vertex in the other two subsets; that is, a...

Homework Statement 1. In the manufacture of commercial license plates, a valid identifier consists of four digits followed by two eltters. Among all possible plate identifiers how many contain only the letters W, X, Y, or Z with a four digit number divisible by 5? 2. All the vertices of...

Homework Statement How many subsets S \subseteq {1,2,...,21} are there if S is required to contain 5 odd integers and 6 even integers? 2. The attempt at a solution I am having trouble breaking this one down. If the subsets contain 5 odd and 6 even, do they only contain 5 odd and 6 even...

How many ways can you place 10 identical balls into 3 identical boxes? Note: Up to two boxes may be empty. I approached this problem as: Let B represent ball Let 0 represent nothing (empty) |box wall| 0 0 B B B B B B B B B B |box wall| So, there must be two other box walls that...

I have n comparable sets of data, several thousand numbered values in each set. A certain number can be calculated by choosing m of these sets, let's call it S_m. Now, the value of S_m depends on which sets I choose, so it can be thought of as a function of m variables which can only take...

Say you have 5 regular die, how many permutations are possible if permutations such as 1,1,1,1,2 and 1,2,1,1,1 are not unique but considered the same (ordering doesn't matter)? I haven't done any combinatorics work in almost 6 years, so I am completely rusty on counting problems. No this...

In theory I'm done this question, but would like to get it checked. 22) How many permutations of the letters ABCDEFGH contain c) the strings BA and FGH? Answer: 5 objects: BA, C, D, E, FGH. Total: 5! = 120 This is following the example in the book. However, the example only has...

I have taken an undergraduate course in combinatorics (and graph theory). I am looking for a graduate-level text at that does everything completely rigorouslym and is suitable for self-study. Any suggestions?

Homework Statement An IT-company with 12 hired workers, has been given four jobs. The company wants to use four workers on the first job, three on the second, three on the third and two on the last job. How many ways can the company put these 12 people on the four different jobs? The...

Problem Statement: Assume that there are n items (numbered from 1 to n) in an urn. We select b items from the urn and record their numbers. We return the selected b items into the urn and perform another selection. We do in total m such selections. At the end of the m selections we...

given 17 coins. a coin can either be red, blue or yellow. show there exists a three coins all of which are the same color.

Followup: Suppose we have 2^9 ways of choosing topics on a pizza. Then, if we want different topics on 3 pizzas, we can do that in 2^9C3 = (2^9*(2^9)-1*(2^9)-2)/3! and if we want the same toppings on all the 3 pizzas, we already know that we can do that in 2^9 ways. But what about the...

My friend says that : If there are 9 different toppings then the number of ways to choose toppings for one pizza is 2^9, the number of the possible subsets of the set of 9 toppings. How can this be? Could someone explain with an example? Sorry if this seems very trivial...

Arby's has this deal out now: 5 for $5.95. You can pick from 8 choices to fill 5 spots. The menu says "over 790 possible combinations" , so one can assume that the number of choices is between 790 and 800. What is the equation to figure out how many choices you have and what is the exact number...

Homework Statement The following is a question from a set-text that I have chosen to explore. What digit is imediately to the right of the decimal point in (sqrt(3) + sqrt(2))^2002 Homework Equations The Attempt at a Solution I have not gone very far with this, and may need...

let a\in R and Q>=3 where Q\in Z, i need to prove that in the set {a,2a,...,(Q-1)a} there exists a number which its distance from the nearest whole number is smaller than 1/Q. i got this as an assignment in topic of the pigeon hole, now i don't see how to use it here, what i did so far (havent...

What would be a good text on elementary combinatorics and combinatorial probability (I don't know if I'm using the right term here)? I'm looking for a classic and elegant text, nothing too modern or fancy.

Here is the question from the book: -------- John was recently diagnosed with a lethal disease and is said to have n hours left to live. John would like to spend his remaining time with his three girlfriends and wife, Jane, Jill, Joan and Amy, respectively. Assuming that John must spend...

Hello everyone. I'm revewing these 2 problems and im' not seeing how they are getting the answer for the "...exactly 4 penny's" Here's the 2 problems: (a) A large pile of coins consist of quarters, dimes, nickels, and pennies (at least 20 of each). How many different collections of 20...

Hello, Recently, I've come across a textbook question based on permutation. I've even got the answer to that, but i want to verify my steps, because each time i solved the question, i realized how tricky it was, and i had to modify my approach. Heres my final approach, please spot any...

I'm unsure about the following questions. Theyre from my introductory combinatorics class. 1) Let a_n denote the number of ways to distribute n objects to three people: A, B, C. A must have at least 2 of the objects, and B must have an amount divisible by 5. Find the generating function of...

There are a few questions that have been giving me trouble with this binomial theorem stuff. (1). Using the binomial theorem and the relation (1+x)^{m_1} (1+x)^{m_2} = (1+x)^{m_1 + m_2} prove that: \sum_{k=0}^n \binom{m_1}{k} \binom{m_2}{n-k} = \binom{m_1 + m_2}{n} (2). Prove by induction...

You're playing standard bridge with three other people. If you know that you and your partner have 10 hearts altogether, then what is the probability that the remaining 3 hearts are all in the same hand ? Is it comb(3,3)*comb(23,10)/comb(26,13) ? Since there is only 1 way of selecting 3...

I rarely care enough about one problem to ask for help, but there are a million problems that are similar to this one and I don't really understand any of them. The problem I'm looking at reads: In a room there are 10 people, none of whom are older than 60 (ages are considered as whole...

First, is this the right area to post topics on combinatorics? It seemed better than "General Math" to me, but I'm not quite sure this is right either. OK, my question is a general one. I've been trying to calculate some things recently, and it strikes me that what I'm doing is essentially...

I have two Pigeon Hole Principle questions that I am having trouble with. First Question: In a room there are 10 people, none of whom are older than 60, but each of whom is at least 1 year old. Prove that one can always find two groups of people (with no common person) the sum of whose ages...

I have to choose between two classes because of a schedule conflict: CS 575, combinatorics and graph theory This course is taught by the chief undergraduate advisor and earlier I mentioned to him that I'd be taking the course. So politically it may be a good idea. The course says it...

Hello, so this is what I am stuck on: In how many different ways can you seat 11 men and 8 women in a row so that no two women are to sit next to each other. I know it's going to be combination and not permutation and that total number of seating them is 11!*8! but that is as far as I could...