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
0answers
15 views

Permutation formula is wrong for this question.

The number of permutations of n distinct objects taken r at a time is nPr. You have four letters, a, b, c, d. Consider the number of permutations that are possible by taking two letters at a time ...
-1
votes
2answers
10 views

Total number of possible binary operations .

If there are n elements in a set the number of binary operations that can be defined are 2n, am I right or wrong ?
0
votes
1answer
28 views

Number of paths in a MxN matrix

Given a MxN grid, how many paths can there be to reach the bottom right cell from the top left cell? The only constraints are one cannot visit a cell more than once, I tried checking the other ...
2
votes
1answer
28 views

Probability that a set of $n(n+1)/2$ elements will contain $1… n$ elements, respectively, of $n$ possibilities

We opened a 'fun size' bag of Skittles this afternoon, and it contained 5 yellow, 4 red, 3 blue, 2 green, and 1 purple Skittle. If the Skittles only come in these 5 colors, they are chosen randomly ...
1
vote
0answers
16 views

What are some properties of posets that are preserved or not preserved by a Dushnik-Miller embedding

The Dushnik-Miller dimension of a (discrete) poset, $P$, involves embedding $P$ into $\mathbb{N}^d$, for $d$ minimal. Inherent in the construction is that the embedding preserves the order of $P$. ...
7
votes
3answers
64 views

How many different arrangements are there problem

How many different arrangements are there of all the nine letters A, A, A, B, B, B, C, C, C in a row if no two of the same letters are adjacent? First I tried to find how many ways to arrange so at ...
0
votes
1answer
49 views

If $N$ is a $4$ digit number $x_1x_2x_3x_4$, then prove that $\frac{N}{x_1+x_2+x_3+x_4}\le1000$

So $N=1000x_4+100x_3+10x_2+x_4$ $0<x_4\le 9$ $0\le x_3\le 9$ $0\le x_2\le 9$ $0\le x_1\le 9$ $0<{x_1+x_2+x_3+x_4}\le 36$ What should be my approach?
3
votes
2answers
50 views

Bijection between $\Bigl\{1, 2, \dots, \frac{N(N+1)}{2}\Bigr\}$ and $\{ (i, j) \in \mathbb{N} : i \le j \le N\}$

Let $N$ be some positive integer and $A$ be the following set $\{ (i, j) \in \mathbb{N}^2 : 1 \le i \le j \le N\} = \{ (1, 1), (1, 2), \ldots, (1, N), (2, 2), (2, 3), \ldots, (2, N), \ldots, (N, N) ...
0
votes
3answers
37 views

Combinatorics - Coloring a 3x3 chess with a restriction.

Let's imagine a 3x3 chess with 9 elements and every element can be colored with red and blue paints.We have a restriction, that we must have at least 1 square 2x2 painted red.How many ways we have? ...
0
votes
1answer
26 views

N balls having M different colors in a box, how many times do I need to pick to get one particular color?

There are $N$ balls of $M$ different colors in a box i.e $c_1$ balls of color $1$ and so on. $c_1 + c_2 + \dots + c_M=N$, $c_1, c_2, \dots, c_M$ are known. We are looking for a ball of a particular ...
6
votes
2answers
69 views

How many routes are there from $A$ to $B$ that cross every node exactly once?

Imagine an $n \times n$ grid, we start on one corner of the grid in square $A$, and need to reach the opposite corner to square $B$. The rules are, you can only move to an adjacent square, you can't ...
0
votes
0answers
19 views

Relations between binomial polynomials (umbral calculus)

In the field of umbral calculus binomial polynomials are called such $p_n(x) : \text{deg} \> p_n = n$ that satisfy the binomial identity: $$p_{n}(x+y) = \sum_{k=0}^n \binom{n}{k} p_{k}(x) ...
4
votes
1answer
68 views

Binomial coefficients identity [duplicate]

Prove algebraically or otherwise: $$\sum \limits_{r=0}^n {2r \choose r} {2n-2r \choose n-r} = 4^n $$ where ${n \choose r}$ denotes the usual binomial coefficient. I think there is a combinatorial ...
-3
votes
0answers
27 views

combinatorics : there are 20 Boxes , you choose balls from 6 different colors , picking some, all or none and randomly place in the boxes. [on hold]

there are 20 Boxes , you choose balls from 6 different colors , picking some, all or none and randomly place in the boxes. Does there exist 2 different balls (different colors) such that these 2 are ...
1
vote
1answer
14 views

The number of quadrilaterals formed from collinear and non-collinear points.

There are $25$ points on a plane of which $7$ are collinear . How many quadrilaterals can be formed from these points ? I did this $^{25}C_{4}-^{7}C_{4}=12615$ quadrilaterals. But the book is ...
2
votes
5answers
69 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)$ ...
4
votes
3answers
72 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 ...
4
votes
3answers
59 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 ...
1
vote
1answer
51 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
29 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) = ...
6
votes
2answers
44 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, ...
3
votes
2answers
45 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 ???
2
votes
1answer
37 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 ...
5
votes
2answers
63 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
10 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, ...
7
votes
3answers
268 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
59 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 ...
3
votes
1answer
30 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
38 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
22 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
32 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
48 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
41 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
61 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
56 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
35 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
118 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
36 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
58 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
29 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
24 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
41 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
18 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
38 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 ...