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
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
33 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
52 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
56 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
34 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
103 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
54 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
31 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
65 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 ...
4
votes
2answers
61 views

How many different strings can be made from letters in CHICAGOLAND, subject to constraints? [closed]

How many different strings can be made from the letters in CHICAGOLAND, using all letters, and such that no two vowels are adjacent to each other?
3
votes
1answer
56 views

Good set with $n$ elements must have element $\ge {2\over n}\binom{n}{n\over2}$?

Let $n$ be even. A set $\{a_1, \dots, a_n\}$ consisting of positive integer s is good if for every two different disjoint subsets $S$, $T \subseteq [n]$ of the same cardinality we have$$\sum_{i \in S} ...
3
votes
1answer
52 views

Putnam: Show that $a(n)=b(n+2)$

Let $a(n)$ be the number of representations of positive integer $n$ as a sum of 1's and 2's taking order into account. $$ \text{Example $n=4$: } (1+1+1+1), (1+2+1),(1+1+2),(2+1+1),(2+2)\implies ...
2
votes
1answer
37 views

“To be or not to be” permutations

The question is, how many ways to rearrange letters of "to be or not to be that is the question" so, that we would get: 1 8-letter word 1 4-letter word 2 3-letter words 6 2-letter words Words can ...
-1
votes
2answers
56 views

In how many possible ways can we write $3240$ as a product of $3$ positive integers $a$, $b$ and $c$?

In how many possible ways can we write $3240$ as a product of $3$ positive integers $a$, $b$ and $c$? This is the question where I've been stuck. The answer is $450$, but I don't know why. I've ...
1
vote
0answers
39 views

relations and equivalence classes

$S$ is the set of all equivalence relations on set $A = \{1,2,3,4,5,6,7,8,9\}$ in which one of the equivalence classes is $\{1,3,5,7,9\}$. What is the size of $S$? I don't even know how to start... ...
0
votes
1answer
21 views

Number of Permutation with Pro = k equals the Eulerian Number A(n,k+1)

The problem phrases as follows: Let $\sigma = (\sigma_1, . . . , \sigma_n)$ be a permutation. We say that element $i$ is progressive if $\sigma_i > i$. We write $pro(\sigma)$ for the number of ...
0
votes
2answers
48 views

Minimum number of moves to even out a row of brick piles

Consider a row of $15$ piles of bricks. There is a total of 75 bricks, all identical. The number of bricks per pile varies across the piles. For instance, the distribution of bricks per pile might be ...
0
votes
2answers
18 views

Maximum profit by optimizing assignment

So a company has n available projects and k employees on the bench. Each project has a "number of hours" associated with it. Each employee has an hourly rate that the parent company gets paid gets ...
0
votes
2answers
64 views

How many integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 12$ with restrictions on $x_1,x_2,x_3,x_4$

So I was given this question. How many integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 12$ with $x_i > 0$ for each $i \in \{1, 2, 3, 4\}$? How many solutions with $x_1 > ...
2
votes
2answers
30 views

How many combinations of three numbers using 1, 2, 3, and 4 exist?

If you count (4 4 3) as one combination, you cannot count (4 3 4) as another. My approach is $\dfrac{4^3}{3!}$, but obviously this does not work. I don't know why it doesn't work, and I don't know ...
0
votes
1answer
26 views

Calculating the number of arrangements of writing a word with $2$ letters beside each other

So i was given a question asking how many arrangements of letters in MATHEMATICS are there where the letters TH appear together (in this order)? From a different example they checked the repetitions ...
1
vote
1answer
58 views

Uses of Ramsey Theory in Astronomy?

In the last paragraph of a Scientific American article of July 1990 that can be found here http://www.math.ucsd.edu/~ronspubs/90_06_ramsey_theory.pdf Graham and Spencer write "Today we can easily ...
2
votes
3answers
40 views

Number of strings over a set $A$

How can I calculate the number of strings of length $10$ over the set $A=\{a,b,c,d,e\}$ that begin with either $a$ or $c$ and have at least one $b$ ? Is it accomplished through some sort of ...
0
votes
1answer
54 views

Number of ways to distribute the awards?

Q: There are 25 participant in a contest in which first, second, and third place prizes are awarded as well as 3 honorable mentions. How many ways are there to hand out the top three prizes? After ...
1
vote
1answer
21 views

Probability that a sample represents between X% and Y% of the population

Really no idea how to go about this. I thought about using a uniform normal distribution law but the answers I got made no sense. In a country that has a population between 1500000 and 3000000 ...
1
vote
2answers
28 views

Selection with condition

The problem statement is : 16 people are occupying seats round a table. If ever person refuses to work with any of his neighbours, in how many ways can a committee of 6 can be made with those ...
3
votes
0answers
36 views

Fill unit square in Euclid plane [closed]

Assume $A,B$ are two subset of $\mathbb{Z^2}$. In addition, $A$ is finite. Satisfies: i) For all $a_1,a_2 \in A$ and $b_1,b_2 \in B$ , $a_1+b_1=a_2+b_2$ implies $a_1=a_2$ and $b_1=b_2$ ii) ...
2
votes
0answers
30 views

Natural bijections between Dyck paths

A dyck path with $2n$ steps is a lattice path in $\mathbb{Z}^2$ starting at the origin $(0,0)$ and going to $(2n,0)$ using the steps $(1,1)$ and $(1,-1)$ without going below the x-axis. What are some ...
0
votes
1answer
34 views

Standard proof of permutations of $n$ people standing in line

I want to prove the statement: For $n$ people the number of permutations is $n!$. How to prove or justify this statement ? I think the easiest way is to use induction. If we have a line of $1$ ...
2
votes
0answers
48 views

A recursion formula related to *Catalan numbers*

When I was working on a problem related to Catalan Number, I deduced the following recursion formula: \begin{equation} a_{l,r}=a_{l-1,r}+a_{l-1,r-1}+a_{l-1,r-2}+\ldots+a_{l-1,l-1},\\ where \quad r \ge ...
3
votes
1answer
43 views

Is there an upper bound on the growth rate of analytic functions?

This problem comes from a solution tactic used in Is there a rational surjection $\Bbb N\to\Bbb Q$?, where I discovered that there is an analytic function $f(z)$ that takes the values $f(n)=a_n$ for ...
1
vote
1answer
54 views

Gaussian polynomial identities

I'd appreciate any hints for showing that these identities are true for Gaussian polynomials. I've tried to approach the problem using basic algebra but it gets messy very quickly and I've gotten ...
1
vote
0answers
25 views

number of ways to partition integer 'n' into exactly 'k' distinct parts where all parts have largest part 'y'

I am attempting to determine the generating function for the number of partitions of n into k-distinct parts all having a largest part y. My attempt is below. It appears to work for all cases I am ...
4
votes
3answers
72 views

Showing $\sum_{k = 2}^n \binom{k}{2} \binom{n}{k} = \binom{n}{2} 2^n$ without induction.

How do I prove the identity$$\sum_{k = 2}^n \binom{k}{2} \binom{n}{k} = \binom{n}{2} 2^{n-2}$$combinatorially, i.e. counting the cardinality of the same set in two different ways? I know how to do it ...
6
votes
2answers
64 views

At least $P(m, n - 1) = {{m!}\over{(m - n+1)!}}$ surjective functions from $[m]$ to $[n]$?

How do I see that there are at least$$P(m, n - 1) = {{m!}\over{(m - n+1)!}}$$surjective functions from $[m]$ to $[n]$?
4
votes
1answer
93 views

How many integers between $1$ and $2016$ are divisible by a nontrivial cube $p^3$, $p > 1$? [closed]

How many integers between $1$ and $2016$ are divisible by a nontrivial cube $p^3$, $p > 1$?
2
votes
1answer
54 views

Determining the number of non-negative integer solutions of the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 100$ with restrictions

a. $$x_{1} + x_{2} + x_{3} + x_{4} + x_{5} \leq 100; x_{1} \geq 4, x_{2} > 2$$ This is how I approached this problem: $$x _{1}^{'} = x_{1} - 4$$ and $$x _{2}^{'} = x_{2} - 3.$$ Then $$x _{1}^{'} + ...
3
votes
2answers
44 views

Finding combinatorial sum

How to compute $$\sum_{k=0}^{n} \left( k^2 \cdot \binom{n}{k} \cdot 3^{2k}\right)? $$ I have no idea other than guessing the answer and proving it by induction.
1
vote
3answers
69 views

Most efficient way to calculate possible combinations

So I just had discussion with a friend about a theoretical situation were he was to populate a server mother board with ram modules in his garage.. So lets assume there are 48 ram slots available to ...
2
votes
2answers
44 views

How many ways are there to distribute three different pens and nineteen identical pencils…?

How many ways are there to distribute three different pens and nineteen identical pencils to five people, if no person gets more than two pens, and such that everyone gets at least one pen or pencil? ...
3
votes
3answers
94 views

In how many ways can a $31$ member management be selected from $40$ men and $40$ women so that there is a majority of women?

Here's the question: In an organization there are $80$ people, $40$ men and $40$ women. In how many ways can we choose, from those $80$ people, a $31$ member management so that there is a ...