Combinatorics Definition and 398 Threads

Homework Statement How many ways are there to pick 2 different cards from a standard 52-card deck such that the first card is a spade and the second card is not a queen. Homework Equations P(n,k) C(n,k) The Attempt at a Solution Since the player must have one spade, there are 13...

Homework Statement Given nine different English books, seven different French books, and five different German books: How many ways are there to mak a row of three books in which exactly one language is missing? Homework Equations P(n,k) C(n,k) The Attempt at a Solution I...

Homework Statement There are eight applicants for a job, and three different judges who each rank the three applicants. Applicants are chosen if an donly if they appear in the top three in all three rankings. a) How many ways can the three judges produce their three rankings? b) What is...

Homework Statement There are eight applicants for the job of dog catcher and three different judges who each rank the applicants.Applicants are chosen if and only if they appear in the top three in all three rankings a) How many ways can the three judges produce their three rankings? b) What...

So here is the problem: Now what seems logical to me is first choose 1 of the 10 non-performing and then choose 4 from the remaining 139 chips. What is wrong with my logic here? I don't get the answer the book gets (130,721,752), and instead get 148, 916, 260.

Homework Statement A dance class consists of 22 students, of which 10 are women and 12 are men. If 5 men and 5 women are to be chosen and then paired off, how many results are possible? Homework Equations The Attempt at a Solution We can say that for the first couple, there are a...

suppose that I want to walk from the corner of a block to the corner of another block (I depart from the corner of coordinates (0,0) and want to get to the corner with coordinates (X,Y), with X and Y being whole numbers. ); and I want to do so by walking N block sides (I can walk over the same...

Homework Statement There are 7 parties competing in the elections. One party has obtained 3 mandates, and the rest 6 have received one mandate each. a) How many different coalitions with at least 5 mandates can be formed? b) Assume that the parties are being called to join each other in a...

Homework Statement I have K birds to put into M cages. How many ways can I do this(no limit on the amount of birds in a cage - there can be empty cages)? Unfortunately I haven't had a combinatorics course (and my friends who have apparently have forgotten all of it...) so I'm a little...

Homework Statement How many permutations of the letters a, b, c, d, e, f, g have either two or three letters between a and b? b _ _ a is also very much possible.Homework Equations nPr= n!/(n - r)!, where n >= rThe Attempt at a Solution For this question there can be 4 cases which are as...

Homework Statement You have 3 types of postcards. There are 5 of each type. How many ways can you send the 15 postcards to 15 friends, if each friend receives 1. The Attempt at a Solution I thought it would merely be 15!/(3*5!)

In how many ways can 16 people be seated: A. In a row, if 4 of the 16 do not want to sit next to one another B. In a row, if 3 of the 16 must be seated next to one another C. In a circle, if 3 of the 16 must be seated next to one another D. In a circle, if 4 of the 16 do not want to...

Homework Statement Sum the series 1^2+2^2+\cdots|n^2 by observing that m^2=2* \dbinom{m}{2} + \dbinom{m}{1} and using the identity \dbinom{0}{k}+ \dbinom{1}{k} + \cdots+ \dbinom{m}{k}= \dbinom{m+1}{k+1}. Homework Equations The Attempt at a Solution I know that...

Homework Statement Prove that 1 - \dbinom{n}{1}\ + \dbinom{n}{2} \ - \dbinom{n}{3} \ + \cdots \ + (-1)^r \dbinom{n}{r} = (-1)^r \dbinom{n - 1}{r} by induction. Homework Equations The Attempt at a Solution Well, I know how to solve the normal binomial sums by using the...

In my combinatorics book, it's discussing inclusion-exclusion, and it says that n!-(n-1)! = (n-1)!*(n-1)! Can someone help me understand the rules of factorials? Thanks!

Probably the only area of math that really confuses me. :frown: I'm trying to calculate some probabilities for Liar's Dice. Essentially, the probabilities that a certain number of faces will appear when five dice are rolled, with one being a wildcard. If I try a specific combinatoric approach...

I was reading Stanley's first volume on Enumerative Combinatorics, and I am seemingly stuck on a basic question regarding compositions. It may be that my algebra skills are rusty, but I just cannot get the correct formula for the number of compositions of n into even numbers of even valued...

Dear all, I am attending a taught postgrad programme starting next October. I can not decide whether to take the Algebraic Number Theory or the (additive/arithmetic) Combinatorics modules. My choice will determine my PhD route, so it is a choice of career rather than just a choice of...

Find the number of ways of placing two knights in a chessboard that they can threaten each other. I tried to solve it like this but it was wrong because the answer was not among the four options. I wrote the number of squares that that the knight can threaten on every square that we place...

6 unique experienced persons 2 unique inexperienced persons How many 3-person combinations if at most one in the group can be inexperienced? 6*5*4/3! + 6*5*2/2! is the answer. My answer was 6*5*4/3! + 6*5*2/3! Why does the book divide by a 2-permutation and not a 3-permutation for...

Homework Statement Two n-digit integers (leading zeros allowed) are considered equivalent if one is a rearrangement of the other. (For example, 12033, 20331, and 01332 are considered equivalent five-digit integers.) If the digits 1, 3, and 7 can appear at most once, how many nonequivalent...

Homework Statement Determine the number of permutations of {1,2,3,4,5,6,7} in which exactly four integers are in there natural positions. The Attempt at a Solution Would this be solved by using the Inclusion/Exclusion Principle and finding \left|S\right| - \sum \left|A_{1}\right|...

Homework Statement Prove that n5^n = \frac{5}{4} \sum_{k=0}^{n}k\begin{pmatrix}n\\k\end{pmatrix}4^k (Hint: First Expand (1+x^2)^n) The Attempt at a Solution So if I expand that I get (1+x^2)^n = (1+x^2)(1+x^2)...(1+x^2) n times so it equals \sum_{k=0}^n (1+x^2) Not sure where to...

Homework Statement How many integers between 1 and 2009, inclusive are (a) not divisible by 3,2, and 10 (b) not divisible by 3,2, or 10? Homework Equations The number of objects of the set S that have none of the properties is given by the alternating expression: \mid S \mid -\sum...

Homework Statement 6 children are sitting arounbd a round table, with each chair numbered from 1 to six. In how many ways can we rearange them so that no child sits across from the child who was across him before. Homework Equations The Attempt at a Solution Because the chairs...

Homework Statement My professor has 50 questions. In the beginning of the semester he makes 10 work sheets each with 5 questions. At the end of the semester, he makes 10 new worksheets from the same quetions, this tiem sorted by difficulty. Prove that there exists a subset of 10 question in...

1. (a) How many repeating three-digit numbers can be formed using the numbers {1, 2, 3}? (b) How many non-repeating three-digit numbers can be formed using the numbers {1, 2, 3}? My solutions: a. 3 x 3 x 3=27 b. 3 x 2 x 1 =6 2. (a) Construct a tree diagram for 4 tosses of a fair coin...

Homework Statement Find the coefficient of x^{9} y^{10} in (3x^{3} - 4y^{2})^{8} Homework Equations The professor gave us a somewhat algebraic tactic or shortcut for solving these kinds of problems, mainly consisting of solving for each exponent. It can be somewhat tricky for me to explain...

Homework Statement You are given n identical As and n identical Bs. You are supposed to arrange them in a circle. How many unique arrangements are there? Homework Equations Use of combinatorics The Attempt at a Solution At first, I tried working out the answer if I arrange them in...

Homework Statement in a poker game we want to calculate the Probability to get differnet combinations. in a card deck there are 52 cards from 4 different series. each series has 13 cards. we assume that each card get 5 random cards. What is the number of combinations to get the cards? (The...

how do I evaluate \sum_{k=0}^d \binom{n+d-k}{n} ?

Hi, I'm trying to figure out a variation of the problem where you determine the number of paths on a discrete grid. For example, for the paths from (0,0) to (a,b), you can consider it to be a rearrangement of a word with a x's and b y's, so the number of paths is (a+b)! / a!b!. The...

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

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