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.

Filter by
Sorted by
Tagged with
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
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 ...

1
2 3 4 5
965