For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

5
votes
1answer
171 views

Solitaire Solvability

Is there a fairly straightforward procedure for determining if a given game of Solitaire (say Klondike) is solvable? One of my students would like to write a Solitaire game and give an "always ...
0
votes
3answers
167 views

Expected number of sixes tossed before success

Given a fair dice, what is the expected number of sixes that get tossed before throwing 2 sixes in a row? Would I start by finding all possible sets that occur without two sixes in a row and multiply ...
1
vote
2answers
93 views

Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$

I'm stuck on this combinatorics question: Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$. I've ...
1
vote
6answers
409 views

prove $\sum_{i=0}^{n}\binom{2n+1}{i}=2^{2n}$

Can someone help me to prove $\sum_{i=0}^{n}\binom{2n+1}{i}=2^{2n}$. The right side means the total number of subsets of $[1,2,3,..,2n]$. Then What does the left side mean? Can someone please help ...
6
votes
3answers
273 views

Prove that $\sum_{k=0}^{m}\dfrac{\binom{m}{k}}{\binom{n}{k}}=\dfrac{n+1}{n+1-m}$

Prove that $\sum_{k=0}^{m}\dfrac{\binom{m}{k}}{\binom{n}{k}}=\dfrac{n+1}{n+1-m}$. We know, n > m. From the right side. we have $\dfrac{n+1}{n+1-m}=\dfrac{1}{1-\dfrac{m}{n+1}}$. since n > m. ...
1
vote
2answers
245 views

computing probability of pairing

Alice has $n$ pairs of socks with $n$ colors ranging in shades of grey enumerated from $1$ to $n$. She takes the socks out of the drier and pairs them randomly. We will assume in each pair,the right ...
0
votes
1answer
821 views

How many topological orderings exist for this graph?

Graph: 1 --> 4 2 --> 5 3 --> 6 My thoughts: There are 3 choices for the first slot. Then there are 3 choices for the second slot (Two remaining ...
1
vote
0answers
121 views

Is there such an example?

Is there an example of a sequence of point sets $\left\{ S_{n}\right\} _{n=1}^{\infty}$in which $S_{n}$ is a set of $n$ points inside the unit triangle, such that the minimum altitude of the triangles ...
1
vote
2answers
102 views

Prove $\sum_{k=0}^{n}(-1)^k(k+1)\binom{n}{k}=0$

Prove that $\sum_{k=0}^{n}(-1)^k(k+1)\binom{n}{k}=0$. I know $\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0$ and even $\sum_{k=0}^{n}(-1)^k\dfrac{1}{k+1}\binom{n}{k}=0$ because I can multiply left side by n+1 ...
1
vote
1answer
410 views

use combinatorial reasoning to calculate $ \sum{\binom{100}{a}\binom{200}{b}\binom{300}{c}}$

Given $ a + b + c = 100 $. $a,\ b,\ c $ are non-negative integers. Calculate $$ \sum {\binom{100}{a} \binom{200}{b} \binom{300}{c} } $$ Can someone help me with this question? I have no idea how to ...
0
votes
1answer
54 views

Basic Counting Question

I'd just like to get the answer to this question checked by someone. You are buying cups from a vendor that sells cups in four different colors - blue, green, yellow, and red. You would like to buy ...
3
votes
2answers
85 views

Combinatorial proof for $a(n-a) \binom{n}{a} = n(n-1) \binom{n-2}{a-1}$

Prove $a(n-a) \binom{n}{a} = n(n-1) \binom{n-2}{a-1}$ by a combinatorial proof. This is what I tried: There is a set $X$ of $n$ elements. There is a subset $Y$ of $a$ elements. LHS, we ...
0
votes
1answer
95 views

Summing $dn$ floor functions = $d$ times Summing $n$ floor functions

Fix integer $d>1$, and assume real number $x\in[0,1]$. I claim the following statement: $\sum_{k=1}^{dn}\lfloor kx\rfloor=d\sum_{k=1}^n\lfloor kx\rfloor$ is true iff $x\in[0,\frac{1}{dn}]$. I can ...
0
votes
2answers
298 views

How many paths are there from A to B?

How many paths are there from A to B? 8 is wrong answer.
2
votes
2answers
183 views

Derangements: n men, n umbrellas and n coats

A number of men enter a disreputable establishment and each one leaves a coat and an umbrella at the door. When a message is received saying that the establishment is about to be raided by the police, ...
3
votes
0answers
201 views

Expectation of throws before having $k$ balls in each box

I remember that if there are $n$ boxes, and a ball is being thrown repeatedly into one of the boxes with uniform probability, then the expected number of throws before every box has a ball is ...
0
votes
1answer
321 views

Probability for fullhouse in POKER - 54 cards

I need to calculate the probability to get fullhuose in a poker game, using 54 cards - included 2 jokers. I know that I have 13 kinds of cards, but I need 2 out of 4, then I have 12 kinds and I need ...
1
vote
1answer
24 views

Probability of X

There can be only 2 possibilities either X or Y. If X occurs first then prob.of X occurring next is 0.4, and if Y occurs 1st prob. of Y occurs next is 0.3. So if X occurs at 5th instant what is the ...
1
vote
1answer
80 views

Ball selection combinatorics problem

Say I have 9 uniquely colored balls. I want to select them into 3 different groups. Each grouping must contain at least 1 ball, and all the balls must be selected. The first 2 groupings are ...
0
votes
1answer
231 views

How do I compute the summation where k is greater than or equal to $0$ of $\frac{1}{k+1}{99 \choose k}$ ${200 \choose 120-k}$

How do I compute $$ \sum_{k=0}^{\infty}\frac{1}{k+1}\binom{99}{k}\binom{200}{120-k}. $$ I have expanded it to this: $$ \frac{1}{k+1}\cdot\frac{99!}{k!(99-k)!}\cdot\frac{200!}{(120-k)!(80+k)!} $$ but ...
1
vote
2answers
983 views

Combinatorial probability of multiple dice rolls

I am trying to come up with a probability for a combinatorial problem that I'm working on and I'm stuck. I've managed to distil it down to a toy dice-roll problem: What is the probability of any two ...
3
votes
2answers
196 views

Find the expected number of '01's in a string

This is an interview question: For strings of length m + n, with m 0's and n 1's. Find the expected number of switches from 0 to 1 (a switch can be thought of as presence of '01' in the given ...
1
vote
0answers
59 views

What is up with the x! divisions when dealing with cards?

If you're calculating values for poker hand, you often use combinations. For example, if you're calculating the probability of 2 pairs in four cards, you would do $\frac { \frac { 13*{ _{ 4 }{ C }_{ 2 ...
1
vote
2answers
326 views

Letter-Sending probability problem

Here is another question from the book of V. Rohatgi and A. Saleh. I would like to ask help again. Here it goes: Consider a town with $N$ people. A person sends two letters to two separate people, ...
1
vote
2answers
398 views

Ticket-Change probability problem

Here is another question from the book of V. Rohatgi and A. Saleh. I would like to ask help again. Here it goes: Waiting in line for a Saturday morning movie show are $2n$ children. Tickets are ...
0
votes
1answer
92 views

Variant of the birthday problem

I would like to ask help regarding an example given in the book of V. Rohatgi and A. Saleh. I think this is a variant of the birthday problem. Here it goes: Consider a class of $r$ students. The ...
1
vote
1answer
62 views

Find The Number Equation Solutions

Find the number of non-negative integer solution of the equation: $$5x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=14$$
0
votes
1answer
87 views

Need help to prove pigeonhole problem

If we pick n+1 different positive integers with every integer is less than 2n. Prove that we can always find three numbers among these n+1 numbers that one is equal to the sum of the other two ...
1
vote
1answer
179 views

Number of ways of assigning jobs to a group (simple counting)

We have 4 different jobs to be done, and a group of 12 people from which to choose workers. How many different ways are there to choose 3 workers for the 4 jobs assuming that one worker does two jobs? ...
0
votes
2answers
133 views

Probability of balls being same color

There are X red balls and Y white balls. I randomly choose Z balls (without replacement, so I can choose the same ball twice). What is the probability that all Z balls have same color? i am getting ...
0
votes
2answers
108 views

Falling Factorial Identity

I would like to prove the following identity, preferably using a combinatorial argument $$\sum_{k=0}^n k^{\underline{m}} = \frac{(n+1)^{\underline{m+1}}}{m+1}$$ I'm assuming $m \ge 0$, although the ...
1
vote
1answer
84 views

Prove that this expression is an integer

Prove that $$ \frac{(p - 1)!}{(p - k)! \cdot k!} $$ is an integer if $0 < k < p$ and $p$ is prime.
0
votes
1answer
73 views

Find the number of possible triangles

An interview question. We are given three positive integers p, q, r such that: p + q + r = 27 and p<q<r. Find the number of triangles that are possible ...
2
votes
1answer
210 views

Conditional Probability: Sheldon Ross Example 2h

The following question comes from Example 2h, in Sheldon Ross's textbook A First Course in Probability on page 64. I got the same answer as the author through a different line of reasoning (given at ...
2
votes
1answer
84 views

Choosing from multiple bins

I have $n$ bins. All items in a bin are identical, and items from different bins are different. The $i^\textrm{th}$ bin contains $n_i$ items. How many distinct ways can I choose $k$ items from the ...
0
votes
1answer
142 views

Placing different color balls into distinguishable boxes

In how many ways can you place 4 red balls, 5 blue balls, and 6 yellow balls in 4 distinguishable boxes? (Balls with same color are indistinguishable)
4
votes
1answer
71 views

necklace of numbers with bounded distance

Starting from the numbers 1-2-3-4-5-6-7-8-9-10-11-12 arrange them in a circle so the difference |x-y| between neighbors is 1 or ...
4
votes
4answers
3k views

Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$

Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$ I have expanded it this far: $$\frac{k \cdot n!}{k!(n-k)!} = \frac{n \cdot (n-1)!}{(k-1)!(n-k)!} $$ but then I am ...
0
votes
1answer
383 views

How do I compute the summation of ${80\choose k}\cdot {k+1 \choose 31}$?

How do I compute the summation of ${80 \choose k}{ k+1 \choose 31}$? I have it expanded in this way $\frac{80!}{k!(80-k)!} \cdot \frac{(k+1)!}{31!(k-30)!}$ Is there a way I can write this as an ...
3
votes
2answers
400 views

Sum of derangements and binomial coefficients

I'm trying to find the closed form for the following formula $$\sum_{i=0}^n {n \choose i} D(i)$$ where $D(i)$ is the number of derangement for $i$ elements. A derangement is a permutation in which ...
0
votes
1answer
36 views

Abby, Bob, Chris, and Dan have 5 vehicles to choose from how many ways can this be done?

Abby, Bob, Chris, and Dan have 5 types vehicles to choose from a red car, red truck, green jeep, brown suv, and grey convertible. More than one person can have the same type of vehicle. If Abby and ...
4
votes
1answer
76 views

If 4 people have 5 different cars to choose from and two people cannot pick the same. How many different ways could people pick the cars?

If 4 people have 5 different cars to choose from and two of those people cannot pick the same(the remaining two people could have the same car). How many different ways could people pick the cars? At ...
3
votes
2answers
154 views

Maximum number of seating plans

15 people will be seat in a row of 15 chairs. Two seating plan are considered the same if two plans share same adjacent quadruples. What is the maximum number of seating plans can be made? For ...
4
votes
1answer
251 views

How prove this$\frac{1}{P_{0}P_{1}}+\frac{1}{P_{0}P_{2}}+\cdots+\frac{1}{P_{0}P_{n}}<\sqrt{15n}$

Let $P_{0},P_{1},P_{2},\cdots,P_{n}$ be $n+1$ points in the plane. Let $ d=1$ denote the minimal value of all the distances between any two points. Prove that ...
3
votes
2answers
75 views

A bishop on a grid

Suppose that we have an $n\times m$ chessboard and bishop on the square $(1,1)$. It starts to move diagonally with the following rules: If bishop is in any corner square except $(1,1)$, it stops ...
1
vote
1answer
219 views

If 4 people have five meal choices how many different ways can they order?

If 4 people have five meal choices, and multiple people can have the same meal. How many different ways can they order?
0
votes
1answer
32 views

inchange the order of the summation

If we inchange the order of the summation$$\sum_{r=0}^{n}\sum_{j=0}^{r}\sum_{k=0}^{r}$$, what we can get? the second order summation and the third order summation can inchange. but if we need the ...
1
vote
1answer
146 views

number of compositions of [n] that each contain a largest part

I am trying to generalize for any [n] the number of compositions that each contain a largest part. [1] has only one composition with a unique largest part, [2] has 1, [3] has 3 compositions with a ...
0
votes
2answers
111 views

Prove the following identity for Fibonacci numbers

Prove this: for any positive integer $a,b,c$, $F_{a+b+c+3}=F_{a+2}(F_{b+2}F_{c+1}+F_{b+1}F_c)+F_{a+1}(F_{b+1}F_{c+1}+F_bF_c)$ Is there any way other than induction to prove this?
1
vote
2answers
65 views

What is the Probability that the Lowest Card out of 4 Cards is X?

If I have four different value cards, what is the probability that the lowest card (ace, lowest -> king, highest) is some value X? Here is what I have so far: I know that the lowest value card ...