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.
49,697
questions
4
votes
0answers
24 views
For which $n$ we can divide set $M= \{1,2,3,…,3n\}$ in to $n$ subsets each with $3$ elements such that in each subset $\{x,y,z\}$ we have $x+y=3z$?
For which $n$ we can divide set $M= \{1,2,3,...,3n\}$ in to $n$ subsets each with $3$ elements such that in each subset $\{x,y,z\}$ we have $x+y=3z$?
Since $x_i+y_i=3z_i$ for each subset $A_i=\{x_i,...
0
votes
1answer
41 views
Number of ways in which exactly $1$ person is alive
The following question was given by my teacher in an assignment.
There is a group of $6$ persons. The $6$ persons shoot each other, no one shoots himself. Everyone shoots exactly once and no shot is ...
0
votes
4answers
32 views
probability of 4 couples sitting opposite to each other at a round table with 8 seats
After all are seated, I though I can look at four of them. There is a $1/8$ probability of the first person sitting in front of its mate, then $1/7$ for the second, $1/6$ for the third and $1/5$ for ...
0
votes
2answers
21 views
Question about possibilities of a team
consider an experiment that consists of determining the type of job - either blue-collar or white collar- and the political affiliation -republicans, democratic or independent - of the 15 members of ...
1
vote
1answer
27 views
Iberoamerican Olympiad 2005: Determine the number of ways of coloring these $2n$ points
Let $n$ be a fixed positive integer. The points $A_1$, $A_2$, $\ldots$, $A_{2n}$ are on a straight line. Color each point blue or red according to the following procedure: draw $n$ pairwise disjoint ...
0
votes
3answers
40 views
How can we count the number of combinations without casework in this problem?
This is an interesting problem that I remembered today:
If a billboard can be painted either red, orange, or yellow, and it is never painted red for 3 days in a row, then how many paint-sequences ...
-2
votes
2answers
59 views
Combinations: How many possible codes does she have
A spy is trying to open a security door by entering the correct code into a key pad. The
key pad has 10 buttons (for the digits $0,\dots ,9)$. How many possible codes does she have
to try at most if......
2
votes
2answers
55 views
A probably simple combinatorics question
I've faced the following problem, it comes from physics actually, but the precise details are of no importance. Consider a set $\{x_{n}\}_{n=1, ..., N}$. We construct the following function
$$F(\{x_{n}...
0
votes
3answers
69 views
Why is this problem solved using 'stars and bars' theorem?
We have a set of $n^2$ integer and each number of them is in interval $[1, n]$.
Every number from $1$ to $n$ is frequent $n$ times.
For example, $n = 3$ and set is $\{1, 1, 1, 2, 2, 2, 3, 3, 3\}$.
We ...
0
votes
0answers
25 views
Partitioning a rectangle or tiling it with rectangles
Can we count or even recursively construct all ways to tile or partition a rectangle with rectangles? Many other questions ask either of two things none of which I am after:
Partitioning a rectangle ...
3
votes
0answers
26 views
Derangements of the letters of the word PURPLE [duplicate]
In a Youtube video on the channel @blackpenredpen, the number of derangements of the word "PURPLE" is calculated as $$\frac{!6 \,- \,!5\, -\, !5\, - \,!4}{2!}$$ I don't understand two ...
1
vote
0answers
17 views
Minimal number of intersections of families of lines
I'm considering two families, $F_1$ and $F_2$, of lines in the plane with $\vert F_1 \vert= N_1$ and $\vert F_2 \vert =N_2$. The families are such that if we pick $g \in F_1$ and $l \in F_2$ we get ...
1
vote
0answers
20 views
Given a necklace with length $N$, how many ways to color it using 2 colors, such that any rotation should be counted only once? [duplicate]
My problem is this:
Given a necklace with length $N$, how many ways to color it using $2$ colors, such that any rotation should be counted only once?
For example, following $2$ necklaces should only ...
0
votes
0answers
22 views
Is it unordered selection without replacment?
Following my question here,
I tried to review my statics course which I took over a decade ago. (sorry forgot most of it, I rarely use it)
In any case the new conditions are as follows:
47 apartments ...
0
votes
1answer
35 views
Minimum for combinatorial sortingproblem
I'm stuck with a combinatorial problem, maybe one of you can help me out, thanks in advance. So heres the problem:
Consider tuples $(i,j)\in \{1,...,N_1\}\times\{1,....,N_2\}=A$. Let $S_1,...,S_x$ be ...
0
votes
1answer
11 views
Inner product of a doubly stochastic matrix by a non-negative matrix
Let $W = (w_{ij})$ be a $n \times n$ non-negative matrix and define a function $f$ in the set of all doubly stochastic matrices $n \times n$ by setting for $A = (a_{ij})$,
$$f(A) = \sum_{i,j} a_{ij}w_{...
3
votes
0answers
33 views
Number of $n$ digit integers where digits appear an odd number of times
Another question asked about the convergence of the sum of reciprocals of integers where digits appear only an odd number of times. (Digits which do not appear are ignored, so for example $14404$ is ...
0
votes
0answers
21 views
Knitting pattern with five different colors.
I have 5 different colors: Red, green, blue, yellow, purple.
I am going to use 3 colors at once, then change one of the colors, then after a while change one more of the 3 colors. This pattern ...
1
vote
3answers
67 views
Amount of numbers $n \in \{1,\ldots,9999\}$ such that there aren't $2$ consecutive odd digits
I want to find out the amount of numbers $n \in \{1,\ldots,9999\}$ such that there aren't $2$ consecutive odd digits. I want to use the principle of inclusion and exclusion.
There are 9999 numbers in $...
2
votes
1answer
28 views
How many license plate numbers contain the digit 4 exactly once in the string of $3$ digits (after the region code)?
So I have been stuck on this question for a few days now and I am honestly just floored at how to get the correct answer. The question is as follows:
A license plate number consists of eight ...
1
vote
0answers
44 views
The congruent mod 5 relation partitions the integers into following five classes :
The congruent mod 5 relation partitions the integers into following five classes :
$S_{0} = \{...,-5,0,5,10,...\} \cdots (0)$
$S_{1} = \{...,-4,1,6,11,...\} \cdots (1)$
$S_{2} = \{...,-3,2,7,12,...\} \...
0
votes
0answers
14 views
How many distinct binary strings have Hamming distance at least $k$?
Given length $n$, what's the largest set of distinct binary strings that any two members would have Hamming distance at least $k$? Is there a solution or best strategy to create such a set? For ...
0
votes
0answers
19 views
Question about Permutations of Separate Groups
So, my question is about what formula you would use if you want to count the combinations and permutations of two separate groups amongst each other.
By exact problem is this.
I want to find the ...
1
vote
0answers
23 views
When the objects are not all distinct, the number of ways to select one or more objects from them is equal to : $(q_{1}+1)(q_{2}+1)\cdots (q_{t}+1) $
Theorem : When the objects are not all distinct, the number of ways to select one or more objects from them is equal to :
$$(q_{1}+1)(q_{2}+1)\cdots (q_{t}+1) -1$$
where, there are $q_{1}$ objects of ...
1
vote
1answer
21 views
Unsigned Stirling number of the first kind summation
I'm solving a question and I confronted with this summation:
$A_n = \sum _{k=1}^n\left(n-k\right)\begin{bmatrix}
n\\
k
\end{bmatrix}$
Where$ \begin{bmatrix}
n\\
k
\end{bmatrix}$ is unsigned Stirling ...
1
vote
1answer
41 views
Number of different shapes for a full binary tree with height n
I am trying to understand the solution to the following problem:
continuation:
As per the document, the correct answer for (4) is (a):
But I don't get why there's the $-s_{n-1}$ at case 3. $T_1$ ...
0
votes
1answer
51 views
3 different books can be distributed among 5 students in an English literature class.
https://imgur.com/a/n2snKwS
Question:
Find the number of ways in which 3 different books can be distributed among 5 students in an English literature class.
Though I can think of different ways to ...
0
votes
0answers
16 views
How would one enumerate relations that are transitive but not symmetric?
Of late, I have been trying to enumerate various types of relations on a set. Counting transitive relations seems very hard. However, it is known that the number of relations on an n-element set that ...
0
votes
1answer
52 views
How to find total number of unique subsets in an array containing duplicates?
We are given an integer array containing duplicates. The array is [2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 7, 7] .
After converting the array into a map of <integer, frequencies>, the ...
-2
votes
0answers
37 views
I was giving elitmus test. I encountered this question
How many numbers are possible between 9 to 1000 , such that first digit is greater than second digit?
Eg: 12, because 2 is greater than 1.
I tried hard but couldn't come up with any solution.
2
votes
2answers
31 views
When repetitions in the selection of the objects are allowed, the no. of ways of selecting 'r' objects from 'n' distinct objects is $C(n+r-1,r)$
How to show that : When repetitions in the selection of the objects are allowed, the no. of ways of selecting $r$ objects from $n$ distinct objects is $C(n+r-1,r)$.
EDIT It's also known as "Stars ...
1
vote
1answer
29 views
If no 3 diagonals of a convex decagon meet at the same point, inside the decagon. Into how many line segments are diagonals divided by their…
Question : If no 3 diagonals of a convex decagon meet at the same point, inside the decagon. Into how many line segments are diagonals divided by their intersections?
Answer : The no. of ways of ...
1
vote
0answers
12 views
Finding a lower bound on number of edges in cut-set of a directed graph
Let $G=(V,E)$ be a directed graph s.t. $V=\mathbb{Z}_n=\{0,1,\cdots,n-1\}$ where $n$ is odd. Now the directed edges out of $x\in V$ are described. These edges are $x\to 2(x-1)\mod n$, $x\to 2x\mod n$, ...
4
votes
2answers
88 views
Show that $(k!)!$ is divisible by $(k!)^{(k-1)!}$
Question : Show that $(k!)!$ is divisible by $(k!)^{(k-1)!}$.
Answer : Suppose we've $k!$ objects, where k objects of 1st kind, k objects of 2nd kind,...k objects of $(k-1)!$ kind (why?). And from the ...
1
vote
1answer
60 views
How to prove $P(A\cup B\cup C\cup D)$?
I know that $P(A\cup B\cup C\cup D)=$ $$P(A)+P(B)+P(C)+P(D)-P(A\cap B)-P(A\cap C)-P(A\cap D)-P(B\cap C)-P(B\cap D)-P(C\cap D)+P(A\cap B\cap C)+P(A\cap B\cap D)+P(A\cap C\cap D)+P(B\cap C\cap D)-P(A\...
0
votes
2answers
34 views
Looking for a simple combinatorics approach to solve a bin-sorting question
I thought stars and bars but it will not work for distinct objects:
How many ways to split $4$ identical red balls, $5$ identical green balls and $7$ identical white balls among two bins?
I was only ...
0
votes
0answers
23 views
Question on combinatorics telling the difference between distribution and division
$\bf{Problem}$ A double-decker bus carry $(u+l)$ passengers, $u$ in the upper deck and $l$ in the lower deck. Find the number of ways in which the $u + l$ passengers can be distributed in the two ...
1
vote
0answers
20 views
To prove that, a graph $G$ is bi-colored iff, when in it doesn't have a cycle of odd lengths. [duplicate]
To prove that, a graph $G$ is bi-colored iff, when in it doesn't have a cycle of odd lengths.
How to prove this theorem, I need some hints/resource recommendation.
0
votes
1answer
57 views
How many shortest paths are there in a brick wall
This is one of the Austrian math competition questions which I am quite sure about.
From the top-left corner of this brick wall to the bottom-right corner, how many shortest paths are there? (One can ...
0
votes
0answers
35 views
In the set of integer greater than 1 find the numbers of the roots in equation $a+b+c+d=16$ [closed]
I don’t know how to this problem, please help me
1
vote
0answers
23 views
Combinatorics question about cube with vertices marked as + or - 1 and faces marked with the product of 4 vertices [duplicate]
This question is from a practice workbook for a college entrance exam.
Let each corner of a cube is represented by +1 or -1 arbitrarily and on each of the six faces of the cube we write the product of ...
0
votes
1answer
41 views
Understanding the Bachet's game competition problem
In lectures we were just solving the following problem :
So we have n stones and a set S that has given positive natural numbers. Two players take stones from the n stone pile and the one who takes ...
0
votes
0answers
31 views
Number of possible 8-character strings
How many 8 character passwords can be made using the 26 letters of the alphabet and the 10 digits (0-9) that don't contain repeated numbers and that contain at least 3 digits?
1
vote
2answers
35 views
An elevator starts moving from the ground floor with $8$ passengers, so that all passengers get off the elevator until the sixth floor
An elevator starts moving from the ground floor with $8$ passengers, so that all passengers get off the elevator until the sixth floor.
Assuming passengers are the same, then
In how many ways is it ...
-1
votes
1answer
26 views
Circle dividing a set of points [closed]
Suppose there be $2n+3$ points in a plane so that no 4 lie on a circle. Then there exists a circle through 3 points such that $n$ points lie inside the circle and the rest $n$ points lie outside that ...
1
vote
1answer
23 views
k distinct books in n identical shelves
How many ways to distribute 6 numbered books into 4 identical shelves?
I solved for 3 books into 2 shelves by taking two cases
a) Selecting all 3 books and keeping it on one self. ( 3C3- 1 way )
b) ...
0
votes
1answer
34 views
Given 2 ≥ colors, a forest with c trees and n amount of vertices: In how different many ways can you paint them? [closed]
So i have this task that gives me a headache.
I have 2 ≥ colors and a forest with c trees and n amount of vertices. The question is, if i colorize them, how many options do exists to do that?
I would ...
2
votes
0answers
62 views
A proof using mathematical induction
By observing the base cases for $t=2,3$, I conjectured the following general inequality which I don't know is true or false:
$$\frac{(n_{1}+n_{2}+ \cdot \cdot \cdot n_{t})(n_{1}+n_{2}+ \cdot \cdot \...
1
vote
1answer
32 views
A question on permutation and combination with the application of elementry coordinate geometry
In how many shortest ways can we reach from the point (0, 0, 0) to point (3, 7, 11) in space where the movement is possible only along the x-axis, y-axis, and z-axis or parallel to them and change of ...
3
votes
1answer
31 views
Subgroup of $S_n$ with maximal proportion of derangements
Consider a subgroup $G$ of $S_n$. I'm interested about the proportion of derangements (permutations with no fixing point) in $G$. For example, the cyclic group $C_n$ has $n-1$ derangements and thus ...
