Questions tagged [combinatorics]
For questions about the study of finite or countable discrete structures, especially 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.
48,215
questions
1
vote
0answers
13 views
Number of combinations where a, b, c, and d appear?
I have 4 "containers", each with elements a, b, c, d, e. Each step, I randomly choose one element from each container and write them together. For example, I could have an outcome of "...
1
vote
1answer
32 views
Infinite series raised to a power being a power series
After thinking about how
$$\left(\sum_{k=0}^\infty \frac{1}{k!}\right)^{z} = \sum_{k=0}^\infty \frac{z^k}{k!}$$
I wondered about what kind of sequence $(a_n)_{n=0}^\infty$ satisfies
$$\left(\sum_{k=0}^...
1
vote
1answer
10 views
Probability of arrangement of letters following specific rules
I have letters ABCDEFG (7 letters). I want to find the probability that if I shuffle the letters and arrange them randomly that B is first and A is last (but I can pick any arbitrary two letters).
I ...
1
vote
2answers
26 views
Size of a set of integers
I am truing to prove that the size of the set:
$$R(n,r)=\{1\leq x\leq n: \lfloor \frac{(x-1)r}{n}\rfloor<\lfloor \frac{xr}{n}\rfloor\}$$
is exactly $r$, where $r<n$. This shouldn't be so ...
1
vote
1answer
35 views
What is the minimum number of broken queens required to cover an $n\times n$ board?
Consider an $n\times n$ board. Assume that the sides of the board are parallel to the north-south and the east-west directions. If a piece of "broken queen" is placed on this board, it &...
0
votes
0answers
13 views
decomposition of order preseving injective map $\phi:[n-k] \to [n]$
Let $d^j:[n-1]\to [n]$ be the order preserving injection that skip $\{j\}$ in the range,where $[n] = \{0,...,n\}$.
Prove the following two fact:
Let $\phi:[n-k] \to [n]$ is the injective order ...
2
votes
3answers
57 views
Identity on the sum $\sum_{i=1}^{n-2}{i-1 \choose k}{n-2-i \choose k-1}={n-2 \choose 2k}$
I need to evaluate the first summation for $k\geq1$ and $n\geq2$.
Some computer calculations allow the identification with the expression ${n-2 \choose 2k}$
above but, how can it be derived? Are there ...
2
votes
1answer
41 views
Ace Of Spades and Two of Clubs Right After An Ace
I came across this question
A Deck of 52 playing cards is shuffled and the cards are turned up and
kept on the table. What is the probability that ace of spades and 2 of
clubs come right after an ace?...
1
vote
1answer
46 views
Colouring of elements of set
Each of the numbers in the set $A = \{1, 2, ...., 2020\}$ is coloured either red or white. Prove that for $n \geq 18$, there exists a colouring of the numbers in A such that any of its $n$-term ...
-1
votes
1answer
28 views
How many positive four-digit numbers (from 1000-9999) do NOT have two or more 3’s next to each other? [closed]
I know the amount of numbers that contain at least one 3 is 3168, but I'm stuck on the next part
here is what I've tried so far...
How many have 2 threes
33 = 9911
33=8118
33=1189
how many have 3 3's?
...
4
votes
2answers
39 views
Formula for the number of edges of complete $m$-partite graph
The complete $m$-partite graph on $n$ vertex in which each part has either $[n/m]$ ($n/m$ rounded down to an integer) or $\{n/m\}$ ($n/m$ rounded up to an integer) vertices is denoted by $T_{m,n}$. ...
1
vote
1answer
26 views
Can these connections be considered as permutations or combinations?
I'm exploring the concept of involution numbers through graph theory.
So if I have $2$ vertices -
and if I connect both of them, can we say that there are $2$ "permutations"? One is when ...
0
votes
0answers
26 views
Why is this problem a question on the topic of permutations/combinations?
I am reviewing some random problems about combinations/permutations. I stumbled upon the following:
In a group of $20$ people, how long will it take each person to shake
hands with each of the other ...
3
votes
2answers
74 views
I have n pairs of socks, each pair of a different color. In how many ways can I pair them?
A) the socks are asymmetrical (I must pair a left one with a right one)
This looks trivial:
I place the left socks in a random order. the order is immaterial, because I only care which 2 colors I get ...
1
vote
1answer
48 views
Induction for binomial coefficients
I would like some help to prove the following equality :
$$\sum_{i=0}^n \binom{n}i^2=\binom{2n}n$$
I wanted to do a proof by induction :
$$\sum_{i=0}^{n+1} \binom{n+1}i^2=1+\sum_{i=1}^{n+1} \binom{n+1}...
1
vote
1answer
38 views
Transitivity of $nth$ tuple vectors of Lexicography ordering
I have read about
Definition Of Lexicographic Ordering,
Lexicographic Order,
Generalized lexicographic order,
Lexicographical order,
Lexicographic ordering,
Lexicographical order
and many other ...
3
votes
1answer
47 views
The value of the second-order Eulerian polynomials at x = -1/2.
Recently, the second-order Eulerian polynomials
$ \left\langle\!\left\langle x \right\rangle\!\right\rangle_n $
have been discussed on MSE [ a ,
b ].
$$ \left\langle\!\left\langle x \right\rangle\!\...
1
vote
1answer
24 views
Combinatorial interpretation of factorization identity
For $a,b,c\in\mathbb{N}$, it is the case that $a^{bc}-1=(a^b-1)(1+a^b+a^{2b}+\cdots+a^{b(c-1)})=(a^c-1)(1+a^c+a^{2c}+\cdots a^{c(b-1)})$. It is perhaps slightly more suggestive to write this as $a^{bc}...
1
vote
1answer
32 views
Counting numbers smaller than $N$ with exactly $k$ *distinct* prime factors
Using common notation, $\omega(n)$ is the number of distinct prime factors on $n$. Similiarly, $\Omega(n)$ is the number of prime factors of $n$, not necessarily distinct: $120=2^{3}\cdot 3 \cdot 5$ , ...
1
vote
2answers
36 views
Confusion in one of the combinatorics/probability problem, with my approach for its solution.
The only contents of a container are 10 disks that are each numbered
with a different positive integer from 1 through 10, inclusive. If 4
disks are to be selected one after the other, with each disk ...
1
vote
1answer
15 views
Expected number of vertices for a given random graph
So I have to find out the expected value of the number of vertices of degree 1.
Let's the given graph if G(n,p). Then the $$\mathbb{P}(deg(v)=1) = {n \choose 1} (p)^{1}(1-p)^{n-1}$$
And $$\mathbb{E}X =...
0
votes
0answers
22 views
Number of Routes and Valid Routes within a 2D grid w/ obstacles
9x9 Grid w/ Start, Goal, and U-Shaped Obstacle
Take this 9x9 grid with a start location (0, 0), goal location (9,9), and U-shaped obstacle at (2,3), (3,3), (4,3), (2,4), and (4,4), how would I tackle ...
0
votes
0answers
22 views
What is the size of the largest subset with a pairwise hamming distance of 3
Consider all binary strings of length $n$. Is there any known bounds on the size of the maximum subset such that the pairwise hamming distance between any two elements is at least 3.
7
votes
1answer
56 views
How many arrangements of red and blue balls are there so that, the number of red balls with: the ball immediately to the right is also red, is $9$.
The question is too long to fit in the title, but I tried.
$50$ balls: $23$ indistinguishable red balls; $27$ indistinguishable blue balls. The balls are arranged in a line. How many distinct ...
2
votes
2answers
55 views
$\pm 1$ valued vectors in an arbitrary subspace.
In a paper I have read on random Bernoulli matrices it was stated that for any subspace $V\subseteq \mathbb{R}^n$ of dimension at most $l$ one has:
$$|V\cap \{\pm 1\}^n|\leq 2^l$$
With no proof. A ...
1
vote
1answer
49 views
How many integers are there from 1 to 10000 that are divisible by exactly two of the numbers 4, 5, 6, and 7?
Could someone please help me solve this question:
How many integers are there from 1 to 10000 that are divisible by exactly two of the numbers 4, 5, 6, and 7?
Thanks!! Also, I think I would have to ...
0
votes
0answers
29 views
Pmf of a number of balls where bucket has a certain capacity.
There are $n$ buckets, each with a possibly different finite capacity $c_i \; (i=1, \dots, n)$. There are
$k$ balls, each to be distributed randomly to the buckets.
A bucket cannot be filled over its ...
2
votes
1answer
39 views
Subsets sharing at most $i$ elements
Assume I have a set $S$ of $N$ elements and I create subsets with $k$ elements from it. With no additional property the number of possible such subsets will be $N \choose k$.
Now I want my subsets to ...
0
votes
1answer
52 views
How to find number of solutions to $a+b+c=0$
As titled, I need to find number of solutions to the equation $a+b+c=0$, where $a,b,c$ are integers in the range $[-k,k]$.($k$ is a positive integer) and $a$ doesn't equal to $0$.
My attempt: let $$x=...
2
votes
3answers
71 views
7 balls are distributed randomly in 7 cells. If 2 cells are empty, show that the conditional probability of a triple occupancy equals 1/4
This problem comes from Feller's Introduction to probability. and it goes like:
"Seven balls are distributed randomly in seven cells. Given that two cells are empty, show that the (conditional) ...
1
vote
1answer
33 views
Number of symmetric square matrices with 0/1 such that all rows and all cols contain at least one 1
Symmetric meaning the main diagonal, i.e., matrix[i][j] = matrix[j][i].
Examples: identity matrix; matrix filled with 1s; matrix where the first row and first col are all 1s
I am stuck because I can't ...
0
votes
0answers
53 views
Positive Integers Solutions — Why Was I Wrong?
This is going to be a long question, so I apologize in advance. I'm currently doing self-study for discrete mathematics by going through Grimaldi, and I had a question regarding my problem-solving ...
5
votes
3answers
74 views
Combo problem, complementary counting
You have 5 blue nails in a column and 3 red nails in another column. You can attach a string between any red nail and blue nail. How many ways can we attach these strings such that every nail has at ...
-2
votes
1answer
45 views
How does he get $3^kn^k/k!$ from that binomial formula? [closed]
How does he get $3^kn^k/k!$ from that binomial formula?
1
vote
1answer
76 views
10 arbitrary points inside a rectangle with dimensions 5 and 2
Prove that if we put $10$ arbitrary points inside a rectangle with dimensions $5$ and $2$, there exist $2$ points $a,b$ such that $d(a,b)<\sqrt{2}$ where $d(a,b)$ is the distance of $a$ and $b$.
I ...
2
votes
2answers
99 views
Notation for newton-like expansion
Is there a compact way of referring to the expression $$a^n + a^{n - 1}b + a^{n - 2}b^2 + \cdots + b^n\:?$$ Maybe some notation I do not know about it.
Thanks!
0
votes
0answers
70 views
The Board Football Problem (Probability)
A and B are playing " board football", a two player in which the objective is to score as many goals as possible. As the game does not have any terminating statement, an infinite number of ...
-2
votes
0answers
20 views
a proof based on the Theorem of Hall is needed for the following question [closed]
suppose that $A_i$ with $i \in I$, is a finite Family of finite subsets of the of the Set M and $r \le |I| $.
prove that if $ \vert \cup_j A_j \vert \ge \vert J \vert - r$ $$$$($j \in J$) for all $J\...
0
votes
1answer
45 views
Probability problem about a card located in a wardrobe or in $1$ of $5$ drawers each of them have the same probability
A card is either in a wardrobe with a probability of $\frac{1}{5}$ or in one of five drawers with the same probability each drawer.
If we have opened four drawers, chosen at random, and the card is ...
0
votes
1answer
37 views
Combinatorics and logic equivalences
I've seen the following question and I wondered about whether or not the change I did is valid, the question is:
"For how many numbers $i$ when $1 \leq i \leq 120$, the following statement holds:
...
4
votes
4answers
208 views
There's 8 black balls and 7 white balls. 3 of the balls are drawn at random. Probability of drawing 2 of one color and 1 of the other color?
A bin has 8 black balls and 7 white balls. 3 of the balls are drawn at random. What is the probability of drawing 2 of one color and 1 of the other color?
Here's what I tried:
Case 1: 2 black balls ...
0
votes
0answers
18 views
Find The Number of ways in which letters of the word ENGINEER can be arranged so that no two alike letters are together [duplicate]
My attempt was based on principles of exclusion-inclusion but I'm unsure how to exclude in this case as the arrangements in which 'EEE' occur together are a complete subset of the arrangements in ...
2
votes
1answer
60 views
Finding the number of $2017$-digit numbers with leading digit $2$
Let $N$ be the number of $2017$-digit numbers such that the leading digit is $2$ and there are an odd number of $9$'s. Find the remainder when $N$ is divided by $1000.$
I first jumped to the thought ...
0
votes
1answer
37 views
In a finite affine space $(\mathbb{Z}/p)^3$, has at most $p^2 +p +1$ lines passing through a point.
It is a simple question not much backgrond information is required. However, I do need ton understand the proof of why.
Prove the finite affine space $(\mathbb{Z}/p)^3$, has only $p^2 +p +1$ lines ...
0
votes
0answers
31 views
Multinomial distribution sum
The problem is about a random walker with probabilities to go to the right $p_1$ and go to the left $p_2$ with an additional probability $p_3$ to stay still and a total number of steps $N=N_1+N_2+N_3$....
0
votes
0answers
21 views
Upper bound for distance between consecutive points by distribution
I was interested in the following problem.
Statement
The positive part of the $x$-axis somehow contains a finite number of points.
We do not know points coordinates, but we can find the number of ...
4
votes
1answer
37 views
A recurrence of the second-order Eulerian polynomials
Recently, some of the remarkable properties of second-order
Eulerian numbers $ \left\langle\!\!\left\langle n\atop k\right\rangle\!\!\right\rangle$ A340556
have been proved on MSE [ a ,
b , c ]
...
0
votes
1answer
28 views
Two-dimensional recurrence relation similar to that of Bessel numbers
I am trying to determine the solution for the two-dimensional recurrence relation
$$
C_{n+1,k}=C_{n,k}+nC_{n-1,k-1}
$$
I've noticed from this paper (1.3) that this is very close to that of the Bessel ...
1
vote
4answers
60 views
Evaluating $\sum_{r \in \mathbb{N}} (n-2r+1)^2 \binom{n}{2r-1}$
I am seeking to evaluate the sum $$S=\sum_{r \in \mathbb{N}} (n-2r+1)^2 \binom{n}{2r-1} \\ =(n-1)^2 \binom{n}{1}+(n-3)^2 \binom{n}{3}+(n-5)^2\binom{n}{5}+\cdots$$
I re-wrote the sum as $$S=(n+1)^2\...
0
votes
1answer
22 views
Probability of a choice overlapping N times in a row or more when choosing K items from a selection of size M
There are total of 13 players in a game, and 4 of them are assigned "evil" randomly. Some players have noted, that some players have been evil multiple times in a row (specifically, a player ...
