Combinatorics Definition and 398 Threads

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

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

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

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

Hey guys, I have a few questions: 1. There are 35 desks in a classroom. In how many ways can the teacher configure a seating plan for a class of 30 students? I'm not sure if order matters (35P30 or 35C30). 2. Sixteen people attend a meeting. Each person greets everyone with a single...

I've just managed to stump myself. Let's say you have M (identical) marbles and N boxes. How many ways can you put the marbles in the boxes if each box can have at most k (k <= M) marbles? for k=M we can take M .'s to be the marbles and N-1 |'s to be the boxes so a valid configuration...

Hey, so in 2003, it was announced that the human genome was more or less mapped. The difference between individual humans is about 0.2 percent of the 3 000 000 000 genes we have. So somehow, this percentage should account for all of the human variations that aren't dependent on environment...

Suppose you want to assign seats for a single row of 4 guys and 4 girls in such a way that each guy is sitting next to at least one girl and vice versa. How many ways are there to do this? This is not a hard problem at all, but I am lacking a good outlined approach to solving problems of this...

Can anyone help with this proof? Let k be an element of positive integers. prove that there exists a positive integer n such that k|n and the only digits in n are 0's and 3's This is in section on the pigeon hole principle and the only problem I have left. I'm not really sure where to...

Hi. We are doing permutations and combinations in class and we were given some formulas without proof to remember. I was able to derive most of them but was unable to derive 3 of them. But I would like to see how do I derive them for sake of fun (also if I forget them what will I do. :) ). 1...

Combinatorics...evil problem! Hi all, I am working on my combinatorics homework. I have completed all of the problems but one. Here it goes: ------------------------------------------ Let S_1 and S_2 be two sets where |S_1| = m and |S_2| = r, for m,r in Z+ (positive integers), and the...

We were given an extra credit problem in discrete structures 2 today. The problem is: n people go to a party and leave a hat. When they leave they take a random hat. What is the probability that no one ends up with the same hat? I can calculate the probability, but I was just wondering if I can...

There are 6 tennis players and each week for a month (4 weeks) a different pair of 5 play a tennis match. How many ways are there to form the sequence of 4 matches so that every player plays at least once? I believe this is an OR problem, but I don't know how to handle the 4 weeks information...

hey guys I am taking a class right now called Finite Mathematical Structures, and I am having a pretty tough time. although it's only about 1 - 2 weeks into the semester, i am having a hard time actually understanding graph theory problems. so far we are doing isomorphisms, edge coverings...

The question goes something like this... What is the probability of an E being one of the 4 randomly chosen letters from the word ENERGISE? This is how i did it (the book says its wrong): ENERGISE ==> 3 Es, 5 Non-Es (partitioning) hence: (3c1*5c3)/(8c4) the book has 55/56...

Birthday Problem (need help on combinatorics...) URGENT! Question: There are ''n'' ppl in a room. What's the probability of 2 or more ppl sharing the same birthday? My Answer: (Looking at 2 ways...) Let E be Event of 2 or more ppl sharing the same birthday... then: P(E) = 1 - P(E')...

Given a Natural number K, how many combinations \[ x = \left( {x_1 ,...,x_N } \right) \] of Natural numbers vectors are there, so that \[ \sum\limits_{i = 1}^N {x_i ^2 } = K \] ? I'm desparate and will believe anything...

Suppose you play a game of cards in which only four cards are dealt from a standard deck of 52 cards. How many ways are there to obtain three of a kind? (3 cards of the same rank and 1 card of a different rank, for example 3 tens and 1 queen.) Could someone help me with how to do this...

Here's a problem my friend gave me: The number of points of intersection of diagonals of a n-gon is 70. If no three diagonals are concurrent, find the number of sides of the n-gon. I believe the answer is 20. I tried to work out for small values of n to get a feel but that didn't do...

:zzz: :zzz: :zzz:

Hello all In my calculus book, this problem has been pestering me" Prove nC(k-1) + nCk = (n+1)Ck, where k > 0 which is read " n choose k-1" + "n choose k" = n+1C k. I tried using the formula for the binomial coefficient, but it becomes very messy. I also tried setting k = 1, but...

Hello all In my calculus book, this problem has been pestering me" Prove nC(k-1) + nCk = (n+1)Ck, where k > 0 which is read " n choose k-1" + "n choose k" = n+1C k. I tried using the formula for the binomial coefficient, but it becomes very messy. I also tried setting k = 1, but...

Hello... 1. In baseball, there are 24 different "base-out" configurations (ruuner out first - two outs, bases loaded - none out and so on). Suppose that a new game, sleazeball, is played where there are seven bases (excluding home plate) and each team gets five outs an inning. How many...

i need help with combinatorics...i need to finda ogf to compute the how many ways can 27 identical walls be distributed into 7 boxes, where the first box can contain at most 9 balls How do this??can you give me a method or explain to me how to do this step by step PLEASE! sAint

I need a little help with combinatorics. 2 Students have 6 dollar notes worth 500 dollars, and 4 notes worth 1000 dollars. Notes with the same value are not distinguished. A-How many ways to split the notes B-How many ways to split the notes, so that both get an equal amount of notes...