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)

0
votes
2answers
21 views

How many $3$ integer subsets have no consecutive integers, where integers are less than $20$?

I have to determine how many integers between $1$ and $20$ are possible if no two consecutive integers are in a set. I've thought it has something to do with a combination of an element $(a,a+2,a+4)$ ...
1
vote
2answers
34 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 ...
2
votes
3answers
26 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
40 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
27 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
53 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
261 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
26 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
34 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
39 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? ...