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)

2
votes
0answers
21 views

Number of $2 \times 2$ images in RGB

I am a bit rusty on math and was wondering if someone could check my back of the envelope calculation. Each RGB component has values between 0 and 255 inclusive. There are three components so you ...
1
vote
1answer
36 views

Let $A=\{1,..,n\}$. How many pairs $(B,C) \in P(A) \times P(A)$ there are such that $B\space \cap \space C^{c} = \varnothing$? [closed]

How do I solve this set theory problem? Let $A=\{1,..,n\}$. How many pairs $(B,C) \in P(A) \times P(A)$ there are such that $B\cap C^{c} = \varnothing$?
1
vote
0answers
59 views

Counting no of ways under overlapping cases.

I have infinte supply of red and black balls and i am asked what will be the count of number of different arrangements having occurrences of RR, RB, BB and BR equal to inputs A,B,C, and D, ...
-1
votes
1answer
63 views

find number of strings

Find the number of strings consisting of only a and b which have P occurrence of aa Q ...
1
vote
2answers
46 views

How many arrangements are there of the word POISONS so that no two vowels are together?

I actually have 3 questions to ask. You just have to say if my solution is right or not. First question: How many arrangements are there of the word POISONS so that no two vowels are together? I ...
1
vote
3answers
54 views

how many $7$ digit numbers can be formed using $1,2,3,4,5,6,7,8,9,0$

How many seven digit numbers can be made if $(a)$ they must be odd and repetition is not allowed $(b)$ they must be even and repetition is not allowed $0532129$ is not a seven digit number So the ...
1
vote
1answer
83 views

Number of binary numbers given constraints on consecutive elements

I've been trying to solve this question for quite a while, given to us by our discrete maths professor. I've been having a hard time in general with it, so I thought I tried looking it up online but ...
2
votes
1answer
19 views

How many 5-card hands are there with 3 hearts and a three-of-a-kind?

How many possible 5-card hands from a deck of 52 cards are there that consists of 3 hearts and a three-of-a-kind? I did: C(13,3) = number of ways to choose three hearts C(3,1) = number of ways to ...
1
vote
0answers
55 views

Name of this formula or more explantation of the proof?

I have found this formula which is a combinatorial identity for counting binary words. I'd like more information on it, or the name of the proof. I am also not totally clear on the step between the ...
0
votes
1answer
19 views

probability of the product of drawn numbers is positive

We have just started learning probability in class, and have done one lesson on basic combinatorics, I'm going through some practice questions and have stumbled upon a few. The first is: A box ...
0
votes
2answers
54 views

Closed form for a binomial identity another solution

Is this true? $$\sum_{j=0}^n{j \cdot \displaystyle\binom{j}{r}} =\displaystyle\frac{(n+1)(r+1)-1}{r+2}\displaystyle\binom{n+1}{r+1}$$
-2
votes
3answers
55 views

Of 100 people seated at a round table, more than half are women. Prove that there exist two women who are seated diametrically opposite each other. [closed]

Of 100 people seated at a round table, more than half are women. Prove that there exist two women who are seated diametrically opposite each other.
4
votes
2answers
175 views

There are 40 men and 40 women. In how many ways can you pick a board of 31 people that has a majority of women? [duplicate]

There are 40 men and 40 women. In how many ways can you pick a board of 31 people that has a majority of women? I was thinking - let's start with the women. There are $\binom{40}{16}$ ways to pick 16 ...
2
votes
1answer
28 views

Switching balls among 3 piles

There are 3 piles of balls. Each hour, I take a ball from one pile and move it to another. The amount of points I earn from this move is the amount of balls in the pile I took the ball from minus the ...
0
votes
3answers
49 views

Given a number '$N$' find how many how many numbers are there between $1$ to $N$ that doesn't contain the digit $3$?

You are given a number $N\le 10^{18}$. You need to find out how many numbers there exist in between $1$ to $N$, which doesn't contain the digit $'X'$ in it . Say $N = 5, X=4$ The answer is $4$. ...
0
votes
2answers
39 views

What kind of binomial formula works here?

I need to write the following sum in a simple way (without sigma): $$\sum\limits_{k=2}^{50}\binom{50}{k}\cdot k \cdot (k-1)$$ I tried Newton's binomial theorem and even Vandermonde's identity but I ...
0
votes
3answers
29 views

How many ways can 20 coins be selected from four containers filled with pennies, nickels, dimes, and quarters?

How many ways can 20 coins be selected from four containers filled with pennies, nickels, dimes, and quarters? (Each container is filled with only one type of coin) So, 20 slots and four choices per ...
2
votes
2answers
35 views

In how many ways can 10 (identical) dimes be distributed among five children?

a. If there are no restrictions? b. Each child gets at least one dime? c. The oldest child gets at least two dimes? For part (a), the textbook gives the answer $14 \choose 10$. Where did the 14 ...
6
votes
3answers
302 views

Give a combinatorial proof for a multiset identity

I'm asked to give a combinatorial proof of the following, $\binom{\binom n2}{2}$ = 3$\binom{n}{4}$ + n$\binom{n-1}{2}$. I know $\binom{n}{k}$ = $\frac{n!}{k!(n-k)!}$ and $(\binom{n}{k}) = ...
2
votes
1answer
19 views

Given that there is at least one error in the bit, what is the probability that it will be retransmitted?

A communication channel can increase the probability of successful transmission by using error-correcting codes. One of the simplest of these is called a "parity scheme". In such a scheme, the message ...
3
votes
1answer
33 views

Probability of having at least one error in block of three bits?

A communication channel can increase the probability of successful transmission by using error-correcting codes. One of the simplest of these is called a "parity scheme". In such a scheme, the message ...
1
vote
2answers
49 views

Baseball related problem (balls and boxes)

Thanks in advance for any help! So I am trying to figure out if the number of hits an inning of baseball is random, or if hits tend to come in bunches. To do this, I'm just using a fairly small ...
1
vote
1answer
36 views

Determine the number of graphs on the vertex set $\{1, 2, 3 , 4, 5\}$, every vertex is incident to at least one edge.

I have the problem of determining how many graphs from the set $\{1, 2, 3, 4, 5\}$ there are, given the property that every vertex is incident to at least one edge. The at least one part of the ...
2
votes
3answers
56 views

$20$ people sit at a round table, how many ways can we choose $3$ with no $2$ being neighbors?

My thought process to this problem was as follows: $1st$ move you have $20$ choices, when you pick you eliminate $3$ people, the first person and their two neighbors. The $2nd$ move you have $20-3$ ...
0
votes
0answers
15 views

Combination($N$ choose $R$) variation for multiple numbersets

Looking to work out an equation that determines all possible combinations that must include the the number(s) in set $2$ returned as a single set. Set $1 = [1, 2, 3, 4]$ Set $2 = [5]$ Combination ...
2
votes
4answers
129 views

(Probability) How many integer solutions are there to the inequality $x_1 + x_2 + x_3 \le 17$

How many integer solutions are there to the inequality $$ x_1 + x_2 + x_3 \leqslant 17 $$ if we require that $$ x_1 \geqslant 1,\; x_2\geqslant2,\; x_3\geqslant 3 $$ My first approach to this ...
-3
votes
0answers
16 views

permutation :no. of ways of counting votes

$2$ candidate $A$ and $B$ contested for presidentship in elections. Each of them got $5$ votes.Find the number of ways of counting so that at no stage of counting $A$ lags behind $B$.
0
votes
0answers
13 views

How does cycle index change along an equivariant map?

Question. Suppose $G$ acts on $X$ (via $\Psi$) and on $Y$ (via $\Phi$), and let $f : X\to Y$ be an equivariant map ($f\circ\Psi = \Phi$). Is there a formula relating the cycle indices $Z_\Psi$ and ...
1
vote
2answers
60 views

Ways to create a quadrilateral by joining vertices of regular polygon with no common side to polygon

How many ways are there to create a quadrilateral by joining vertices of a $n$- sided regular polygon with no common side to that polygon? It's quite easy to solve for triangles for the same ...
1
vote
1answer
34 views

Recurrence relation with blocks

We have a path of size $N$ and $1\times1$ blocks of $4$ colors: yellow, red, blue and white. We need to fill the path with blocks but we cannot have $2$ blocks of the same color in a row (we can have ...
2
votes
3answers
53 views

Combinatorial Proof, Binomial Coefficients [duplicate]

I have the following question: Give a combinatorial proof that if $0\le a,k\le n$ are integer than $$\sum_{b=0}^k\binom{a}{b}\binom{n-a}{k-b}=\binom{n}{k}.$$ I'm new to the notion of a ...
3
votes
1answer
62 views

Formula of a sum

Lets define formula: $f(n)=\sum_{i=0}^n i^2 \binom{n}{i}$ What would be genral formula of that? I first went to discover $f(n)=\sum_{i=0}^n \binom{n}{i}=2^n$ (cardinality of power set), and ...
1
vote
2answers
61 views

This sigma to binom?

Can you please show me how to get from the left side to the right side? $$\sum\limits_{k=0}^{20}\binom{50}{k}\binom{50}{20-k} = \binom{100}{20}$$
0
votes
1answer
41 views

Codewords of C(6,K,4)

Suppose we have code with length of binary words 6. Like 000000 000001 But with distance 4 like 000000 001111 (meaning ...
2
votes
3answers
43 views

In how many ways can $12$ different balls go into $3$ different boxes so that in every box there are $4$ balls? [closed]

I need help with this question: In how many ways can $12$ different balls go into $3$ different boxes so that in every box there are $4$ balls? The answer should be $34650$. Thank you.
1
vote
0answers
19 views

Projection of hyper-cubes via multiple variable elimination

I am not a mathematician but I do use some tools from geometry in robotics. So, I apologize if what I am writing here is not mathematically consistent but I really do need your help. I have a linear ...
1
vote
0answers
32 views

Variant of the Coupon Collector's Problem with Two Probabilities

The Coupon Collector's Problem is well-known in probability theory. Say there are $n$ types of coupons, where there is a probability of 1/n of getting each coupon with each draw. One expects to draw ...
2
votes
1answer
67 views

How many ways to multiply n matrices?

Say I have 4 matrices A,B,C,D I can multiply them like this ((AB)C)D = (A(BC))D = (AB)(CD) = A((BC)D) = A(B(CD)) So, how many ways can n matrices be multiplied? ...
0
votes
2answers
51 views

Combination - Distribution of gifts

Seven different type of gifts are to be distributed among 10 children.Every kind of gift must be at least given to one child. Then, how many combinations do we have? Note:You have A, A, A.... ...
3
votes
1answer
55 views

How many ordered pairs (A,B) are there so that they satisfy the condition $A\subseteq B$ , A and B are subsets of a set S with n elements? [duplicate]

How many ordered pairs $(A,B)$ are there so that they satisfy the condition $A\subseteq B$ , where $A\subseteq S$ and $B\subseteq S$, and $S$ has $n$ elements? How to approach this question ? ...
6
votes
2answers
93 views

Number of solutions $(x_1)(x_2)(x_3)(x_4) = 2016$

Having some trouble wrapping my head around this one: find the number of solutions to the equation $(x_1)(x_2)(x_3)(x_4) = 2016$, where $(x_i)$s are integers that are not necessarily positive. ...
0
votes
4answers
41 views

Number of ways to roll five 6-sided dice with sum 7

I would like to determine the number of possible outcomes that are possible to roll five fair $6$-sided dice where the sum of the faces adds up to $7$. I am interested in the case where order does ...
0
votes
3answers
33 views

How many binary words of length $9$ are there that contain 4 $0$s and 5 $1$s?

I'm studying for a Discrete Mathematics II exam, and I came across this example in the textbook of the course. The writer proceeds to solve as $\dfrac{9!}{4!5!}=126$ and provides no explanation. ...
0
votes
4answers
60 views

How many numbers are there of 2n digits that the sum of the digits in the first half equals the sum of the digits in the second half

The question is how many number of a given number of digits 2n where the sum of the first half of the digits equals the sum of the digits in the second half. So this is for a programming problem and ...
6
votes
4answers
100 views

# of partitions of $n$ into at most $r$ positive integers $=$ # of partitions of $n + r$ into exactly $r$ positive integers?

How do I see that the number of partitions of the integer $n$ into at most $r$ positive integers is equal to the number of partitions of $n + r$ into exactly $r$ positive integers?
1
vote
0answers
52 views

Find the probability that no boy sits between two girls.

Example. Five boys and three girls are seated at random in a row. Find the probability that no boy sits between two girls. Solution.: $\quad n(s) = 8!$ $n$(E) = The number of arrangement of $5$ ...
1
vote
1answer
21 views

Count the ways to choose distinct subsets $A_0, A_1, . . . , A_n$ of ${1, 2, . . . , n}$ such that $A_0 ⊂ A_1 ⊂ . . . ⊂ A_n$

I was given this question. Count the ways to choose distinct subsets $A_0, A_1, . . . , A_n$ of ${1, 2, . . . , n}$ such that $A_0 ⊂ A_1 ⊂ . . . ⊂ A_n$ I followed a different example to solve this ...
0
votes
2answers
30 views

RSA Encryption Original Primes $p$ and $q$

I am well aware of the math behind the RSA encryption system, and why it works. The bank, for example, publishes a pair of numbers $(e,n)$ which are used for encryption by the customers. The bank then ...
9
votes
1answer
63 views

Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$

So i was given this question. Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$ Here is my solution: Given $2n$ objects, split them into $2$ groups of $n$, $A$ and $B$. ...
1
vote
4answers
57 views

Combinatorics Problem with symbols and spaces

Here is my problem that I have to solve: An agent will send a secret code made up of 12 different symbols across a secure wire. In addition to the 12 symbols, the agent will also send a total of 45 ...