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
22 views

How many $4$-digit numbers can be made from $x$ of $1$, $y$ of $2$, and $z$ of $3$

How many different $4$-digit numbers can be made from $x$ of $1$, $y$ of $2$, and $z$ of $3$, given that $x+y+z \geq 4$?
0
votes
1answer
38 views

Nice combinatorics puzzle

Priscilla and Suzie are high-school students with an exceptional talent for mathematics. Their mathematics teacher has noticed their talent and now he does his best to encourage the two girls by ...
0
votes
2answers
20 views

Probability a string has $2$ digits, $4$ consonants, and $1$ vowel, given a length of $7$ w/o repetition

My thinking behind this problem would be to pick $2$ digits out of 10 total $\binom{10}{2}$, $4$ consonants out of $21$, vowels not included $\binom{21}{4}$, and the $5$ vowels, multiplied by $7!$. ...
1
vote
1answer
24 views

Number of ways of choosing at least $k$ objects out of $n$

Suppose you have three distinct items $a$, $b$, $c$. You want to find how many unique sets you can get by choosing at least one item. For example, $\{a\}$ would form a unique set, and $\{a, b\}$ would ...
0
votes
2answers
60 views

Multinomial Coefficients Definition in expansion of $(1+x+x^2+\cdots+x^l)^n$

The literature defines multinomial coefficients (or extended bnomial coefficients) as $$ \binom{n}{r_1,r_2,\cdots,r_l} = \frac{n!}{r_1!r_2!\cdots r_l!}$$ where $$ r_1+r_2+\cdots+r_l = n$$ Which is ...
1
vote
1answer
33 views

Urn problem and combinatorics

You have 5 red and 4 black ball. How many ways there are to distribute all under 3 different bottles? If i had 9 red ball then it would be $\binom{n+k-1}{k}$ = $\binom{3+9-1}{9}$, but i have no ...
0
votes
1answer
14 views

Calculating combinations without duplicate values

I have 128 chairs, and 256 people. How many different combinations of the 256 people can be sitting in the 128 chairs? Order doesn't matter, and obviously the same person can't be sitting in more ...
1
vote
3answers
40 views

Why is Binomial Probability used here?

A test consists of 10 multiple choice questions with five choices for each question. As an experiment, you GUESS on each and every answer without even reading the questions. What is the ...
1
vote
1answer
20 views

Ways to stack 65 different disks in 3 piles with constraints.

How many ways are there to stack 65 different disks in 3 piles if pile 1 but have at least 15 disks and pile 3 must be non-empty. Attempt: 1) Ways to arrange all the disks in a horizontal line: ...
4
votes
2answers
281 views

Count the number of integer solutions of a linear equation

What kind of approach can be used to solve this specific problem? An easy one if possible. I thought about the Inclusion-Exclusion Principle; I think using generating functions will be more ...
2
votes
2answers
44 views

How many solutions exists for this equation? [duplicate]

$$x_1 + x_2 + x_3 + x_4 = 28$$ I tried to solve it with generating functions. Is it correct to get to the form of $${(1 + x + {x^2} + {x^3} + ....)^4}$$ and this equals to: $${(1 - x)^{ - 4}}$$ ...
0
votes
0answers
22 views

Confused between cyclic sum and symmetric sums.

four variables $a, b, c, d$ are given, what is the symmetric and cyclic sum? I thought: $$\sum_{cyc} ab = ab + ac + ad + bc + bd + cd$$ And $$\sum_{sym} ab = 2(ab + ac + ad + bc + bc + ...
3
votes
2answers
45 views

Number of ways to choose numbers from a list.

While studying, I came upon this question in my book: "How many ways are there to take 7 numbers from 1 to 12 such that none of the chosen numbers is twice the other?" The solution is shown as 47, but ...
1
vote
1answer
54 views

A bank has to give 5 positions for 15 candidates

A bank must give 5 different positions to 15 people: 7 men and 8 women. Question 1: In how many ways can the jobs be given if there must be at least 3 women selected? Question 2: In ...
4
votes
0answers
27 views

Show that $p \in \left[\frac{4^m}{\sqrt{2m}},\frac{4^m}{\sqrt{2m+1}}\right]$

If the number of ways in which $m$ identical apples can be put in $2m$ boxes, so that no box contains more than one apple, is $p$, prove that $$p \in ...
2
votes
0answers
54 views

Graph theory, $n$ people sitting around table.

$n$ people want to have dinner together around a table for $k$ nights so that no person has the same neighbor twice. How big can $k$ be in terms of $n$? Does everybody get to sit next to everybody ...
1
vote
2answers
39 views

How To Approach Dice Rolls

When asked about 2 dice roll, we do we count the result that both dice have the same number just one time and not two? If it is because we can distinguish between the two, so if the dice was colored ...
0
votes
2answers
36 views

Comparison of two sets of 4-tuples using combinatorics

My problem is to show that $\mathbf{A} = \mathbf{B}$. Specifically that $\forall a \in \mathbf{A} \implies a \in \mathbf{B}$ and $\forall b \in \mathbf{B} \implies b \in \mathbf{A}$, to be precise. ...
-4
votes
1answer
26 views

No of ways of selecting r objects from n distinct objects, allowing repeated selections [duplicate]

I'm self studying discrete math from a books which states the formula for No of ways of selecting r objects from n distinct objects, allowing repeated selections as $C(n+r-1, r)$. I couldn't ...
2
votes
0answers
24 views

Maximal determinant of a $\{1,−1\}$ matrix of size $n$ is $2n−1$ times the maximal determinant of a $ \{0,1\}$ matrix of size $n−1$.

Maximal determinant of a $\{1,−1\}$ matrix of size $n$ is $2n−1$ times the maximal determinant of a $ \{0,1\}$ matrix of size $n−1$. How to prove this result? (I found this statement while reading ...
2
votes
2answers
87 views

${2000\choose1}+{2000\choose4}+{2000\choose7}+\cdots +{2000\choose1996}+{2000\choose1999}=?$ [on hold]

${2000\choose1}+{2000\choose4}+{2000\choose7}+\cdots +{2000\choose1996}+{2000\choose1999}=?$
-2
votes
1answer
33 views

Calculate $\left(\begin{smallmatrix}n \\ r\end{smallmatrix}\right)/{k^n}$ for very large $n$

How to calculate large $ \frac{\left(\begin{matrix}n \\ r\end{matrix}\right)}{k^n}$, given very large $n$. Since n is large enough normal methods of calculating $ \left(\begin{matrix}n \\ ...
2
votes
4answers
81 views

A combinatorial proof for $\binom mk$+$\binom m{k-1}$=$\binom {m+1}k$

I do realize that there is a elementary proof of this result which follows from applying the formula $$\binom mk=\frac{m \cdot (m-1) \cdot \ldots \cdot (m-k+1)}{k!}.$$ I do wonder if there is an ...
1
vote
2answers
42 views

Another kind of derangement?

I reading about derangements, and the following question came to my mind. Suppose in an office, there work 5 teams, each consisting of 1 head and 3 staff (so there is a total of 15 staff). If the ...
-1
votes
1answer
32 views

How many different three-digit house numbers could be made? [on hold]

a shopkeeper sells house numbers. she has a large supply of the numerals 4, 7 and 8, but no other numerals. how many different three-digit house numbers could be made using only the numerals in her ...
0
votes
2answers
53 views

3 cards are drawn from a deck of 52. how many hands are possible if exactly 2 are black cards and exactly 1 is an ace? [on hold]

3 cards are drawn from a deck of 52. how many hands are possible if exactly 2 are black cards and exactly 1 is an ace? I'm not sure how this works. Never seen a question quite like this.
2
votes
3answers
326 views

Stumped - How would I solve this probability question?

This question was merely a fun online math problem to see how many people could solve it, but I haven't been able to since last week and it's beginning to drive me nuts. The question: A man has $7$ ...
4
votes
0answers
67 views

Algorithm to find shortest path to net values across nodes

I have an undirected graph $G = (V, E)$ with nodes $V$ and edges $E$. Each node $v$ has an associated number $n_v \in \mathbf{Z}$ Let us define for any two nodes $v, w \in V$ connected by an edge $e ...
4
votes
3answers
259 views

Proof for coloring combinations problem. (color vertices of pentagon)

While studying, I found a problem in my book that read: "Each vertex of convex pentagon ABCDE is to be colored with one of seven colors. Each end of every diagonal must have different colors. Find the ...
1
vote
1answer
41 views

Maths challenge problem: Why is the number of teams which require 4 substitutions 32?

I came across the following problem on a UKMT senior maths challenege: A hockey team consists of 1 goalkeeper, 4 defenders, 4 midfielders and 2 forwards. There are four substitutes: 1 goalkeeper, 1 ...
2
votes
1answer
22 views

Let $n$ be a positive integer and $S$ the set of points $(x,y)$ in the plane, where $x$ and $y$ are non-negative integers such that $x + y < n$.

Let $n$ be a positive integer and $S$ the set of points $(x,y)$ in the plane, where $x$ and $y$ are non-negative integers such that $x + y < n$. The points of $S$ are colored in red and blue so ...
8
votes
2answers
48 views

How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?

For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - ...
0
votes
1answer
14 views

Expectation of size of bootstrapped sample

Lets say we have a sample $\mathbf{X} = \{x_1, x_2, \dots, x_N\}$. We draw $N$ points from $\mathbf{X}$ with replacement (do a $\textit{bootstrap})$. What is the expectation of size of bootstrapped ...
3
votes
2answers
39 views

A grasshopper starts at the origin and is equally likely to hop north,s,e,w. What is the probability that it's coordinates will be 0,0 after 4 hops?

The grasshopper must hop in all $4$ directions (North, South, East, and West) to get back to the origin after $4$ hops. Therefore, I did: $\frac{(4 \cdot 3 \cdot 2 \cdot1)}{4^4} = .09375$. However, ...
6
votes
0answers
41 views

Given $100$ coplanar points, no $3$ collinear, then at most $70$ percent triangles formed using these points are acute-angled

(IMO-$1970$) Given $100$ coplanar points, no $3$ collinear, prove that at most $70$ percent of the triangles formed using these points are acute-angled. I know that one solution proceeds by ...
4
votes
2answers
31 views

Number of ways to select subsets

In how many ways can two distinct subsets of the set $\text{A}$ of $k$ $(k \geq 3)$ elements be selected so that they have exactly two common elements? I started by choosing two elements (that ...
0
votes
2answers
62 views

Powerset with constraints

I have two sets $NUMBERS$ and $LETTERS$ with: $ NUMBERS = \{1, 2, 3, 4, 5\} \\ LETTERS = \{ A, B, C, D, E\}$ No I want the power-set of my sets, i.e. the set of subsets of elements from both ...
2
votes
0answers
52 views

Number of games required such that two arbitrary players play together and against each at least once.

There are $2N$ players to form two teams of $N$ players that play against each other in a game. How many games are required such that two arbitrary players play together and against each other at ...
1
vote
3answers
58 views

How to solve this combinations with repetitions problem using generating functions?

Find the number of solutions to : $$x_1 + x_2 + x_3 + x_4 + x_5 = 10$$ where none of the variables can be the number $3$. I can solve this with Inclusion-Exclusion Principle, but I really love ...
0
votes
0answers
12 views

Optimization problems with combinations of a finite set as the feasible area?

For example: Provided that $S\subset \Re$ is a known finite set ($n\leq |S| < \infty$), number $k$ is known, and $1 \leq k<n$ minimize $f(x_{1},\ldots, x_{n}) = \sin (\sum_{1\leq i\leq ...
4
votes
1answer
122 views

Expected value when die is rolled $N$ times

Suppose we have a die with $K$ faces with numbers from 1 to $K$ written on it, and integers $L$ and $F$ ($0 < L \leq K$). We roll it $N$ times. Let $a_i$ be the number of times (out of the $N$ ...
0
votes
0answers
16 views

subsets with predefined sequences

I have a set $N=\{m,m+1,m+2,...,n\}$ And there are some generating functions of the format : $f(x,k) = (x^2 -1) \mod k$, where $k \le \sqrt m$ and $k$ is in the form $(6i+1)$ or $(6i-1)$, $\forall ...
0
votes
1answer
20 views

permutations vs combinations on slot machines with repeating elements on each reel

For a slot machine with 5 reels where there are repeated elements on each of the reel. Example: Reel 1 [ 1, 1, 2, 1, 3, 5, 6 ] Reel 2 [ 1, 2, 3, 4, 5, 5 ] Reel 3 [ 2, 2, 3, 2, 4 ] Reel 4 [ 1, 2, 3, ...
3
votes
1answer
68 views

Interesting Combinatorial Identities; e.g. $\sum_{k=0}^n {n\choose k}^2 = {2n\choose n}$ [duplicate]

I came across the following combinatorial identity: $$\sum_{k=0}^n {n\choose k}^2 = {2n\choose n}$$ Here's the kind of proof which caught my interest: $\sum_k {n \choose k}^2 = \sum_k {n \choose ...
-7
votes
0answers
37 views

Fundamental principle of counting? [on hold]

How many three-digit even numbers are there such that 9 comes as a succeeding digit in any number only when 7 is the preceding digit and 7 is the preceding digit only when 9 is the succeeding digit? ...
0
votes
1answer
49 views

Probability a blackjack dealer will bust if you know their score and know the exact deck?

If you know the exact cards left in a deck, and the score of the dealer, how can you calculate the exact probability that they will bust? The dealer behaves as follows: If the dealer's score is less ...
1
vote
1answer
38 views

How many surjective functions $f: X \to \{1,…,j\}$?

How many surjective functions $f: X \to \{1,...,j\}, |X|=j \cdot k.$ can be defined if they must satisfy: $$ |\{x\in X: f(x)=r\}|=|\{x\in X: f(x)=s\} \forall r,s\in \{1,...,j\} $$ My attempt: From ...
1
vote
1answer
40 views

Number of distinct necklaces using K colors

I have a task to find the number of distinct necklaces using K colors. Two necklaces are considered to be distinct if one of the necklaces cannot be obtained from the second necklace by rotating ...
1
vote
1answer
29 views

maximal matching in graph theory

if we have a graph $G = (V,E)$ and the four values $\beta_1(G)$, $\alpha_1(G)$, $\beta(G)$, $\alpha(G)$, where $\beta_1(G)$: Edge independenth number. The maximal number of independent edges in the ...
5
votes
2answers
118 views

Determine the number of subsets

How many distinct subsets of a set $\text{A}$ are there, containing at least $9$ elements, where the total number of elements in set $\text{A}$ is $18$ ? I've solved it by making cases of either ...