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)

1
vote
2answers
29 views

Confusing probability problems based on product rule and combinations

I am going thru probability exercise. Faced first problem: Book Q1. Ten tickets are numbered 1,2,3,...,10. Six tickets are selected at random one at a time with replacement. What is the ...
1
vote
3answers
15 views

Algebraic and combinatorial proof of an identity

For any two integers $2 \le k \le n-2$, there is the identity $$\dbinom{n}{2} = \dbinom{k}{2} + k(n-k) + \dbinom{n-k}{2}.$$ a) Give an algebraic proof of this identity, writing the binomial ...
0
votes
1answer
36 views

The ant is moving through the coordinate system, Started at $(0,0)$ to $(4,4)$. What is the probability that the ant will find food at $(3,2)$?

The path to the $(3,2)$ is $3+2 \choose 3$ or $3+2 \choose 2$. Total path is $4+4 \choose 4$ And the probability is : $ \frac{3+2 \choose 3}{4+4 \choose 4}$ = $ \frac{5 \choose 3}{8 \choose 4}$ = ...
2
votes
1answer
26 views

Birhdays: find the probabilities for the various configurations of the birthdays of 22 people

Let S,D,T,Q stand for simple,double,triple and quadruple, respectively: So, for example: the probabilities of 22 simple birthdays(22 person have birthdays in different days) are $ P(22S) = ...
4
votes
1answer
26 views

Integer Tetrahedra

The points $\{(0, 0, 0), (12, 27, 44), (48, 0, 20), (48, 0, -64)\}$ have the property that All vertices are on the integer grid, All edge lengths are integers and different $\{51, 52, 53, ...
2
votes
2answers
39 views

Alternative interpretation of ball and urns problem

Suppose an urn has r red balls and b black balls. They are withdrawn one at a time at random until a total of k, k $\leq$ r, red balls have been withdrawn. Find the probability that a total of n balls ...
0
votes
1answer
21 views

Say we have a double-decker Lazy Susan with two levels that can be turned independently. If we have n + k dishes in total, how many ways

Say we have a double-decker Lazy Susan with two levels that can be turned independently. If we have n + k dishes in total, how many ways is that solution is correct ???
1
vote
1answer
30 views

Numbers between $200$ and $1200$ that can be formed with the digits $0,1,2,3 $

How many numbers between $200$ and $1200$ can be formed with the digits $0,1,2,3 $ (repetition of digits not allowed ) ? $a.)\ 6\\ b.)\ 8\\ c.)\ 16\\ \color{green}{d.)\ 14}$ I divided it in ...
4
votes
2answers
50 views

Proof that $2^n-(n+1) $ equations are necessary to establish the independence of n events.

Suppose $A_1,A_2,\cdots,A_n$ are $n$ events, we say that they are all independent if for all $\{i_1,\cdots, i_m\}\subset \{1,2,\cdots,n\}$(where $m\ge 2$), we have $$\mathrm{Pr}[A_{i_1}\cap ...
0
votes
0answers
9 views

Question regarding isomorphisms formed by deleting various edges in a plane triangulation…

Consider a plane triangulation $T$ with $m$ edges numbered $1, 2, … , m$. Form the near-triangulation $G_k$ by deleting the edge $e_k$ in $T$. Suppose the $m$ near-triangulations $G_k$ for $k = 1, 2, ...
5
votes
3answers
260 views

When are products of binomial coefficients equal?

It's known that $\binom{n}{r} = \binom{n}{s}$ if and only if $r = s$ or $r = n - s$. If $n \neq m$, is it true that $\binom{n}{s} \binom{m}{r} = \binom{n}{k} \binom{m}{\ell}$ if and only if ($s = k$ ...
0
votes
1answer
55 views

Permutations on word $MISSISSIPPI$.

In how many ways can the letters of the word $MISSISSIPPI$ be rearranged ? I am confused on whether it is $\dfrac{11!}{4!4!2!}$ or $\dfrac{11!}{4!4!2!}-1$ since it is given rearranged and not ...
2
votes
1answer
25 views

Optimizing number of 6-digit strings differing in at least two places

A certain province issues license plates consisting of six digits (from 0 to 9). The province requires that any two license plates differ in at least two places. (For instance, the numbers ...
0
votes
2answers
27 views

Find number of unordered pairs $(A,B)$

Find number of unordered pairs $(A,B)$ such that $\bullet \space A$ and $B$ are subsets of an $n$ element set $S$ $\bullet \space A \cup B=S$ $\bullet \space A≠B$
2
votes
1answer
33 views

Must the number of people at a party who do not know an odd number of other people be even

I have a homework question in my discrete mathematics class as the title shows, I feel the answer is no, but googling this question seem's to contradict my answer. Let me explain: So if they are ...
2
votes
1answer
21 views

How many ways to select distinct pairs from k disjoint sets

How many pairs can be generated from k disjoint sets. For example I have following 3 sets(k=3): A = {1,2,3} B = {4,5} C = {6,7} I want to form pairs such there's no element of pair coming from the ...
2
votes
1answer
31 views

Permutation of students in a class

In how many ways can 10 BS and 7 MS students be arranged in a line so that no two MS students may sit together? My approach: Total number of ways all 17 students can be arranged in a line is ...
0
votes
3answers
47 views

What is the sum of nine dates in a month? [on hold]

9 dates in a certain month are enclosed by a rectangle as following: 7 8 9 14 15 16 21 22 23 Let $n$ be the number at the top left hand corner of the rectangle. Express the sum of the ...
2
votes
1answer
38 views

Permutations and Combinations - conceptual

Suppose we have 10 objects. I want to create a group with those 10 objects. The group should contain a minimum of 2 objects (it can contain anywhere from 2-10 members). How would I find the total ...
0
votes
2answers
58 views

An online calculator that can calculate a sum of binomial coefficients

Is there any online calculator that can calculate $$\dfrac{\sum_{k=570}^{770} \binom{6,700}{k}\binom{3,300}{1,000-k}}{\binom{10,000}{1,000}} $$ for me? There are a few binomial coefficient ...
0
votes
2answers
55 views

Combinatorics: How many 6 digit numbers have AT LEAST one '9' among them?

The Question is pretty simple and straight forward when we try to find the count of numbers without 9 and Subtracting that with Total arrangement of numbers [9*10^5] - [8*9^5]. But how do you ...
0
votes
0answers
33 views

Highest efficiency suub collection of sets.

Hy can some one help me to figure out this. X is a set of type1 elements. Y is a set of type2 elements. Given a collection of sets (S) in which each set(Si) is a subset of XunionY. The efficiency ...
5
votes
4answers
116 views

How many ways to write $2010$?

Let $ N$ be the number of ways to write $ 2010$ in the form $ 2010 = a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0$, where the $ a_i$'s are integers, and $ 0 \le a_i \le 99$. An example of ...
2
votes
1answer
34 views

dots/ beads on a grid

I've got some difficulties with the following problem. We have an infinite grid. We put $4$ beads on the point $(0, 0)$. If we want to move a bead from $(x, y)$ we have to replace it with two ...
2
votes
2answers
36 views

How many zero-sum $n$-tuples are there?

The question is extremely short and concise. How many $n$-tuples $X \in \{\, -1,0,1 \,\}^n$ have the zero-sum property $\sum_{x \in X} x = 0$ ? At the moment I have nothing to share of my own since ...
5
votes
1answer
53 views

How to prove$\displaystyle \sum_{i=0}^{k}(-1)^i\binom{n}{k-i}\binom{n+i-1}{i}=0$

I saw a combinatorial identity when i study linear-algebra, But the author didn't explain how to get it. $\displaystyle \sum_{i=0}^{k}(-1)^i\binom{n}{k-i}\binom{n+i-1}{i}=0$ I tried $n=10$ or ...
2
votes
0answers
28 views

Properties of a specific antichain of a lattice formed by the cartesian product of finite ordered sets

Introduction Let $X$ be a poset of all $n$-tuples, $x = (x_1, x_2, ..., x_n)$, where $0 \leq x_i \leq m_i - 1$ for $i = 1, ..., n$ together with the relation $x \prec y$ defined so that for ...
2
votes
1answer
35 views

Find the number of functions

How many functions $f : \{0,1\}^n \mapsto \{0,1\}$ have the equal number of function values $0$ and $1$? I have the answer to the question: $ \sum_{k=0}^{2^{n-1}} 2^{n-1}\binom{2n}{2k}\binom{2k}{k}$, ...
0
votes
1answer
19 views

Solution of recurrence relation for roots having multiplicity $ \ge 1 $

If there is a recurrence relation of the form $ a_n = c_1 a_{n-1} + c_2 a_{n-2}+ ... + c_k a_{n-k} $, then if b is a non zero complex root of the recurrence relation with multiplicity t, $t \ge 1 $, ...
2
votes
1answer
40 views

In how many ways can the letters of the word $PATNA$ be arranged?

In how many ways can the letters of the word $PATNA$ be arranged ? $a)\ 60 \\ b)\ 120 \\ c)\ 119 \\ \color{green}{d)\ 59 }\\ $ I thought it would be $\dfrac{5!}{2}=60$ but in book answer is ...
1
vote
1answer
17 views

Cardinality of the set $D$

Let , $D$ be the set of tuples $(w_1,w_2,\cdots,w_{10})$ , where $w_i \in \{1,2,3\},1\le i\le10$ and $w_i+w_{i+1}$ is an even number for each $i$ with $1\le i\le 9$. Then find the cardinality of ...
2
votes
1answer
29 views

How to solve this kind of combinatorics problem?

I have a question about combinatorics. Here is the question: A waiting area outside the doctor's office contains a row of 7 chairs. In how many different ways can a man, a woman and a boy occupy 3 ...
-2
votes
0answers
36 views

Counting math problems [on hold]

1) Ann, Bobby, and Cece are randomly placed in a line with 26 people total. What is the probability that Ann is to the left of Bobby, and Bobby is to the left of Cece? Express your answer as a common ...
5
votes
1answer
58 views

Proof of Vandermonde's Identity using a “different approach” using complex integration

Hi I'd like to know if the following proof of Vandermonde's Identity is correct (is really easy): Let $m,n,r$ be natural numbers such that $r\le \min \{m,n\}$. The Vandermonde's Identity gives us ...
0
votes
0answers
9 views

Number of possible non crossing paths on a grid of $m$ by $n$ size?

Given two points on 2 dimensional m by n grid, moving in units of 1 in either direction, how many non intersecting paths exist between the two points? in other words, with taxi cab metric, on a m by ...
0
votes
2answers
37 views

Number of divisors $d$ of $n^2$ so that $d\nmid n$ and $d>n$

I just wanted to share this nutshell with you guys, it is a little harder in this particular case of the problem: Find the number of divisors $d$ of $a^2=(2^{31}3^{17})^2$ so that $d$ does not ...
3
votes
1answer
26 views

Simplifying a Taylor polynomial that involves Stirling numbers of the second kind

I am currently trying to evaluate a complicated function $f$ at a point $x+a$ using a high order Taylor polynomial about the point $a$. The polynomial has the standard form: $$\sum_{n=1}^k ...
3
votes
0answers
25 views

Number of $m$-subsets $Y$ satisfying $|A\cap Y|\le t$

Let $X$ be a finite set with $n$ elements and $A$ be a subset of $X$ with $a$ elements. Let $m,t\le n$. I'm interested in counting the number of subsets $Y$ of $X$ with $|Y|=m$ satisfying $|A\cap ...
0
votes
0answers
11 views

Hadamard matice decomposition to sparce matrices

$H_2=\begin{pmatrix} 1 & 1\\1 & -1 \end{pmatrix}$ and $H_{2n}=H_2\otimes H_n$. I am looking for decomposition of $H_n$ to sparce matrices and its proof. Is there any good source to suggest ? ...
0
votes
4answers
27 views

No: of ways to distribute cards .

In how many ways can a person send invitation cards to $6$ of his friends if he has $4$ servants to distribute the cards ? $a.)\ 6^{4}\\ \color{green}{b.)\ 4^{6}}\\ c.)\ 24\\ d.)\ 120$ As the ...
3
votes
0answers
38 views

Number of players with most wins in tournament

$n\geq 2$ tennis players play each other once, and there are no draws. For which $1\leq k\leq n$ is it possible that exactly $k$ players have the (joint) highest number of wins? For example, $k=1$ is ...
0
votes
1answer
20 views

How many ways are there to make a row of three books in which exactly one language is missing (order matters)?

Given 10 different English books, 6 diff. French books, and 4 diff. German books... The way I went about this one I split into three cases. English missing, French missing, etc. Case #1: EGL misssin ...
0
votes
1answer
14 views

Degree of a self-complementary graph with $4k+1$ vertices [on hold]

How can we prove that every self-complementary graph on $4k+1$ vertices has a vertex of degree $2k$ ?
-4
votes
0answers
11 views

Condition about regular graphs

prove that in graph r regular there are route that in length of at least 2r-1 I don't know how to prove it some one can help me please I have a home work to suggest
0
votes
2answers
29 views

Grouping 15 rating grades in 10 buckets

I am trying to group 15 corporate rating grades into 10 buckets. The grouping cannot be done in a random way - for example the rating grades 1 and 14 cannot be in a single bucket (constraint). The ...
1
vote
2answers
41 views

Find $a_i, b_i$ such that they are all distinct

Very tough, I spent at least an hour, not solving this! From the set of integers $ \{1,2,3,\ldots,2009\}$, choose $ k$ pairs $ \{a_i,b_i\}$ with $ a_i<b_i$ so that no two pairs have a common ...
0
votes
0answers
18 views

Which correct sentence to explain the function $g(\nabla I)=\frac{1}{1+\beta |\nabla(G_{\sigma}*I)|^2}$

I have a edge indicator function that has formula as $$g(\nabla I)=\frac{1}{1+\beta |\nabla(G_{\sigma}*I)|^2}$$ where $\nabla$ is gradient operator, $*$ is convolution operator, $G_{\sigma}$ is a ...
2
votes
0answers
47 views

Combinatorics: Permutation Problem, how to know if a solution is correct or wrong

Question: Find the number of ways of arranging 8 Men and 2 Women in a row such that 2 Women are never together. For the above question, I thought of 2 ways to proceed 1> Arrange 8 men in 8! ...
3
votes
3answers
33 views

Combinatorics question on group of people making separate groups

If there are $9$ people, and $2$ groups get formed, one with $3$ people and one with $6$ people (at random), what is the probability that $2$ people, John and James, will end up in the same group? ...
1
vote
1answer
30 views

Probability that in bridge game the Players N,E,S,W have a,b,c,d spades respectively.

There are 52 cards in bridge and 13 cards of each suit. The formula for numerator is: $${13\choose a}{39 \choose 13-a}{13-a\choose b}{26+a\choose 13-b}{13-a-b\choose c}{13+a+b\choose 13-c}$$ But i ...