Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
9 views

In a shooting a man scored 5,4,3,2,0 points for each slot ,then in how many ways can the person score 30 in seven shots?

In a shooting a man scored 5,4,3,2,0 points for each slot ,then in how many ways can the person score 30 in seven shots ? Firstly ,can someone please explain why this is a combinations question and ...
2
votes
2answers
24 views

Getting a wrong answer on evaluating permutations separatly

Good Day! I was doing some combinatorics problems when I got stuck. The problem was: Suppose that a teacher selects 4 students from 5 boys and 4 girls. If at least one boy and one girl must be ...
0
votes
1answer
7 views

Can we decompose any connected Regular graph (or subclass of it) into Hamiltonian cycles and Perfect matchings?

I need to decompose any connected Regular graph into Hamiltonian cycles and Perfect matchings. Is there any theorem that guarantees this or is there any counter example to this ? If there is such ...
1
vote
2answers
55 views

Sorting $n$ identical balls to $3$ urns under some conditions

Task: We have an even number of $n=2k$ identical balls, but only $3$ urns A,B and C. In urn A should be at least 2 balls and in urn C not more than $\frac{n}{2} = k$. As many possibilities are there ...
0
votes
1answer
7 views

Permutations and Combinations of 3 books and 3 shelves.

We have $3$ books and $3$ shelves. We are to put $2$ books on $1$ shelf and $1$ book on the other two. Answer given in the book is $6$ but I feel that—— We can select $2$ books from $3$ in $C_{(3,2)}=...
1
vote
1answer
18 views

Different ways of computing probability

There are twelve unique watches and five men. Each of the five men are asked to choose a watch for themselves. What is the probability that at-least two of them choose the same watch. I could think ...
0
votes
0answers
5 views

“Align” ring squares to a uniform color

A ring of N squares, and N is a double of 3. At first, K squares are painted white, and the other squares are painted black. The SWITCH operator, which can be activated again and again, is placed on ...
0
votes
1answer
12 views

How can I choose the highest resulting combination out of arbitrary sized chunks, worth an arbitrary amount each

I am given a set of companies that each want to buy my product in different sized chunks. I have a maximum of 28 Million units to sell and each company pays a different amount of money for their order....
0
votes
1answer
21 views

Sequence of letters ABCD, pigeon hole?

Show that in every sequence $(a_1 , a_2 , \ldots, a_{100})$ of the letters $A,B,C,D,$ there are two indices $1 \leq i < j < 98$ such that $(a_i,a_{i+1},a_{i+2}) = (a_j,a_{j+1},a_{j+2})$. I don’...
0
votes
0answers
28 views

If more than half of the integers from $\{1, 2, \ldots, 2n\}$ are selected, then they must include two integers such that one divides the other [duplicate]

Pigeonhole Principle problem: If more than half of the integers from $\{1, 2, \ldots, 2n\}$ are selected, then there must exist two integers among the selected integers that have the property that ...
2
votes
1answer
31 views

Counting number of combinatorial sequences.

Let $n$ be a positive natural number. A sequence of $n$ positive positive integers (not necessarily distinct) is called a ”four-group” sequence if it satisfies the following requirements: for any ...
1
vote
0answers
35 views

Assigning people to jobs

We have $n$ people and $n$ jobs. Assume that each person is able to do $k$ jobs $0<k<n$ and each job can be done by $k$ people. Proof that each job can be done at the same time My try Ok, I ...
0
votes
0answers
19 views

Prove that $ C^m_{n+k+1}= $ $\sum_{i=0}^{m}$ $C^{i}_{k+i} $ $\times$ $C^{m-i}_{n-i} $ [duplicate]

Prove that $ C^m_{n+k+1}= $ $\sum_{i=0}^{m}$ $C^{i}_{k+i} $ $\times$ $C^{m-i}_{n-i} $. I tried using double counting and Newton binom. Any idea? I don't now many identities......
0
votes
1answer
29 views

How does distinguishability of boxes change the number of ways to distribute n objects into separate boxes

I was going through problems related to distributing n distinguishable objects all into boxes, a in the first, b in the second, c in the third where a+b+c = n. The solutions I've seen usually comes to ...
1
vote
1answer
26 views

Size of Set Equal to 1? $|U \cap \{s,t\}| = 1$

I am not sure what to call this but in the preliminaries for chapter 2 on sets in Alexander Schrijver's Combinatorial Optimization book he states the following: A set $U$ is said to separate $s$ and $...
0
votes
1answer
26 views

How to prove this fact about the discrete closure? [on hold]

The content is given two relationships: R₁ and R₂ prove that s(R₁ ∩ R₂)=s(R₁) ∩ s(R₂) My teacher has taught us the UNION versions in class, and I figure it's easy. Also I have already finished the ...
1
vote
1answer
43 views

Is there a way to classify all power-invariant graphs?

Suppose $G = (V, E)$ is a finite undirected simple graph. Let’s, define the $n$-th power of a graph (where $n \in \mathbb{N}$) as graph $G^n = (V, E_n)$, where $$E_n = \begin{cases} E & \quad n = ...
1
vote
1answer
21 views

Given constraints, in how many ways can actors be chosen for roles?

Given $13$ actors and $6$ unique roles, in how many ways can the actors be assigned a role if a certain actor (Alan) will not join if another actor (Betty) joins? My method was to compute total ...
0
votes
0answers
30 views

Combinatorics Ramsey Theory Proof

There are 9 passengers on a bus, some know each other. Among every 3 passengers there are two who know each other. Prove that there are at least 5 passengers, each of which knows at least 4 people on ...
0
votes
0answers
22 views

Prove $O(\frac{1}{T})$ convergence rate

Suppose we have the following first-order non-homogeneous recurrence relation $$z_{t+1} \leq \frac{1}{(1+b_1c_t)^2}\big(\left(1+b_2c_t^2 \right)z_t + b_3c_t^2\big) $$ where $t$ is an integer which ...
0
votes
0answers
35 views

Check my math - Number of one-to-one functions $f$ from $\{1, \ldots, n\}$ to $\{1, \ldots, 2n-1\}$ such that $f(x) \neq 2x - 1$ for all $x$

What is the number of one-to-one functions $f$ from the set $\{1, 2, \ldots, n\}$ to the set $\{1, 2, \ldots, 2n − 1\}$ so that $f(x) \neq 2x − 1$ for all $x$? I'm not sure if I did the question ...
2
votes
1answer
28 views

Number of hands (card deck)

I have a deck of 12 cards - one Jack, Queen and King of each suit. There are 5 cards in one hand. How many hands are there in which a Jack, Queen and King all show up and all 4 suits show up? My ...
2
votes
2answers
42 views

Die roll and coin flip - Bayes' theorem

I am thinking to the question posed here: Die roll and coin flip. "Suppose I roll a 4-sided die, then flip a fair coin a number of times corresponding to the die roll. Given that i got three heads on ...
3
votes
1answer
29 views

Labeling nodes in a bipartite graph to satisfy edge constraints

I'm trying to find an algorithm for the following problem. Let $G$ be a bipartite graph. The edges in $G$ have labels $R$; each label $R(u, v)$ is an integer range $[a, b]$ with $a$ and $b$ being ...
0
votes
0answers
22 views

Betti numbers of the Stanley-Reisner ring of a simplicial complex which is the cycle on $n$-vertices

Let $\Delta$ be a simplicial complex which is the cycle on $n$-vertices $V=\{x_1,...,x_n\}$ (say) i.e. the facets of $\Delta$ are $\{x_i, x_{i+1}\}$ for $1\le i\le n$ with $x_{n+1}=x_1$. Let $S=k[x_1,....
5
votes
3answers
95 views

Combinatorics problem on counting.

How many positive integers n are there such that all of the following take place: 1) n has 1000 digits. 2) all of the digits are odd. 3) the absolute value of the difference of any two consecutive (...
0
votes
1answer
46 views

Problem that involves Stirling numbers

With both of the parents working, Thomas, Stuart, and Craig must handle 8 weekly chores among themselves. (a) In how many ways can they divide up the work so that everyone is responsible for ...
2
votes
1answer
21 views

Combinations with Restrictions

Automobile license plates for a state consist of four letters followed by a dash and two single digits. How many different license plate combinations are possible if exactly one letter is repeated ...
0
votes
2answers
17 views

Calculating r-combinations by hand (canceling out numbers in the denominator)

My textbook does an interesting cancellation process to simplify the r-combinations. How does this process work? How do you cancel out $4!$ with $19*18*17*16$? BTW how do you do this 31! with <...
1
vote
1answer
17 views

Showing existance of tournament without transitive subtournament

Show that there exists a tournament on $n$ vertices that does not contain a transitive tournament on $2\log_2n+2$ vertices. My attempt: The number of tournaments of $n$ vertices is $2^{\binom{n}{2}}$...
2
votes
0answers
42 views

An order-6 configuration

Here's an example of an order $96_6$ configuration found by L.W. Berman. Every point has six lines, every line has six points. The unique 6,6 cage graph is bipartite and is a Levi graph for the ...
1
vote
1answer
35 views

Proving $|E| \leq \frac{1}{2}(\sqrt{t-1}\;n^{3/2} + n$) in a graph with no copies of $K_{2,t}$

Show that if an $n$-vertex graph $G=(V,E)$ has no copy of $K_{2,t}$ then: $$|E| \leq \frac{1}{2}(\sqrt{t-1}\;n^{3/2} + n)$$ I know how to prove it for $n=2: \;$ Dentoe $|E|=m,$ $d(v)$ the degree of $...
1
vote
2answers
36 views

Sum $\sum_{i = 1}^N \sum_{j = i + 1}^N \mathbb{I} (j - i \leqslant K)$

Let $N,K$ be non-negative integers. What's the value of the following sum? $$S(N,K) = \sum_{i = 1}^N \sum_{j = i + 1}^N \mathbb{I} (j - i \leqslant K)$$ where $\mathbb{I}(\mathcal P)=1$ if $\mathcal ...
0
votes
0answers
26 views

There is a group of 4 married couples. What is the number of the groups of 4 people in which there is at least 1 married couple? [on hold]

There is a group of 4 married couples. What is the number of the groups that consist of 4 people in which there is at least 1 married couple?
0
votes
1answer
24 views

In how many different ways can 7 people sit around 2 round tables , one of which has 3 and the other has 4 seats?

In how many different ways can 7 people sit around 2 round tables , one of which has 3 and the other has 4 seats? The answer to the question is 460
2
votes
0answers
27 views

Proving that intersection in an array contains different coloured points

The following is a combinatorics problem that I need help with. I have no idea how to go about it. Any help is deeply appreciated. All points in a 100x100 array are coloured in one of four colours ...
0
votes
0answers
30 views
+50

How to calculate quantity of Hamilton cycles

If I have $n^2$ vertices and each vertex is adjacent to $2n-2$ vertices, how may I calculate the quantity of possible Hamilton cycles? Would I need to modify the computation if I stipulated that I'm ...
0
votes
0answers
40 views

Showing that $\lim_{n \to \infty}\frac{c_n}{4^n} = 0$

Here $c_n$ represents the Catalan numbers. This question is from an old exam paper with no solutions available. I have an approach to the problem but it feels very long-winded considering only a few ...
0
votes
0answers
40 views

Is there an infinite class of Bose Steiner triple systems that are resolvable?

Does there exist an infinite subclass of Steiner triple systems yielded by the Bose construction that are resolvable? Recall that a Steiner triple system of order $v$ is resolvable if its block set ...
-4
votes
1answer
47 views

I am stuck in this question please help. [on hold]

The number of ways in which an examiner can assign 30 marks to 8 questions, giving not less than 2 marks to any question is A) $ 21 \choose 7$ B) $ 21 \choose 8$ C) $ 21 \choose 9$ ...
3
votes
0answers
35 views

Complex Combinatorics issue - 2 fruits, 3 folks.

OK, so I've got a pretty complex problem i'm having trouble with. I need to divide w watermelons and l lemons among three people (Alex, Bart, Cody) with several requirements on the division (they can ...
0
votes
0answers
23 views

Chances of 3 players being in the same group 4 weeks in a row.

Forgive me because its been awhile since I did combinatorics and I am struggling remembering how to set this up. A scenario popped up in a game I was playing that is basically as follows: Each week ...
2
votes
1answer
49 views

Hard combinatorics question

The origin of the coordinates is a pixel. After 1 second, it splits into two particles, one shifts to the left and the other to the right. This process is repeated every second, and the two particles ...
0
votes
1answer
50 views

How many of 1,2,3,4,5…11000 are invertible modulo 880?

My work: I write 880 as $2^4$ x $5$ x $11$. I know that for a number to be invertible modulo 880, it must be coprime to 880. I have to count all such numbers from 1,2,3.....879 which I can then ...
3
votes
0answers
42 views

Minimum number of dominoes on an $n \times n$ chessboard to prevent placement of another domino.

OEIS sequence A280984 (based on this Math Stack Exchange question) describes the minimum number of dominoes on an $n \times n$ chessboard to prevent placement of another domino. The sequence ...
1
vote
0answers
29 views

combinations word problems math

There are two different problems I am stuck on. In how many ways can we divide ten candies of the same kind among four children? I haven't found a way to solve this one 2.In how many ways can we ...
0
votes
1answer
32 views

4 student's birthdays stars and bars problem

Alice, Bob, Charles, and Desiree are 4 students comparing the days of the week on which they were born. In total how many possibilities are there for the day of the week each is born?
0
votes
1answer
33 views

In how many ways can we select $5$ children from this group so that Mary and Jane are always in the selection?

In a group of $10$ children no two kids have the same name. We know that Mary and Jane are among these children. In how many ways can we select $5$ children from this group so that Mary and Jane are ...
2
votes
1answer
59 views

Distributing locks and keys so certain subsets of people can open all locks

A vault can be opened by n number of keys. Five people, A, B, C, D, E are given some of the keys. Each key can be duplicated arbitrary number of times. Find the smallest number n and the distribution ...
1
vote
2answers
41 views

Partitioning $[1,v-1]$ into sets of size three such that the sum of each set is $3v/2$

Suppose that $v \equiv 4\;(\bmod 12)$. In general, is it possible to partition the integer interval $[1,v-1]$ into integer partitions of $3v/2$ with three distinct parts (with each part in $[1,v-1]$)? ...