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

Partition a set into g groups, k different ways, such that no pair of elements is ever in the same group together more than M times

Over at Wolves and Sheep on puzzling.stackexchange.com, noedne's answer involves repeatedly partitioning a group of 99 sheep into a series of "test groups" such that All but one sheep are tested ...
0
votes
0answers
9 views

number of sum free subsets

Given an abelian group $G$ of order $n$, how I do show that the number of sum free subsets of G is at most $2^{(n/2 + o(n))}$. Sum free subsets meaning $A\subseteq G$ s.t. $\forall x,y,z \in A, x + y \...
0
votes
0answers
20 views

How to combine shuffles to prove associativity of Eilenber-Zilber map

I've got a problem related to $(p,q)$-shuffles that comes from the Eilenberg-Zilber map $\nabla$ when I tried to show that this map is associative in the sense that $\nabla(\nabla\otimes 1)=\nabla(1\...
0
votes
0answers
11 views

Quantity of Hamiltonian cycles

If I have four vertices, each of which are adjacent to two others, how are the Hamiltonian circuits for those vertices typically counted? If I envision the unit circle of the real plane’s axis ...
0
votes
0answers
11 views

Permutation and combination when certain objects are alike.

What will be the number of permutations and combinations when m objects are to be taken from a group of n objects, having 'a' and 'b' number similar objects? Example: Find number of ways of ...
1
vote
0answers
56 views

What type of polynomials?

I am faced with the following sequence of polynomials: $1$ $1-x$ $1-x+x^2$ $1-2x+2x^2-x^3$ $1-2x+2x^2-2x^3+x^4$ $1-3x+6x^2-6x^3+3x^4-x^5$ $1-3x+5x^2-5x^3+5x^4-3x^5+x^6$ $1-4x+10x^2-16x^3+16x^4-10x^5+...
-4
votes
0answers
30 views

Combinatoric Algebra USAMO 1996 Problem 2

For any nonempty set S of real numbers, let (σ)(S) denote the sum of the elements of S. Given a set A of n positive numbers, consider the collection of all distinct sums (σ)(S) as S ranges over the ...
0
votes
0answers
16 views

Induction question about parenting with a condition

We have $n$ students which are in $k$ classes. We know that between each two classes, there exist two persons A and B who know each other. Prove that we can put students in $n-k+1$ groups such that ...
0
votes
1answer
31 views

How many way can you encode a five letter word

I have a solution for this problem, but the way iv carried it out seem a bit long and am wondering if and only if my ans is correct if there is a shorter method or maybe and alternate way of looking ...
1
vote
1answer
27 views

Probability of a certain 5 card hand from a standard deck

A poker hand consists of 5 cards randomly dealt from a standard deck of cards without replacement. What is the probability that you're dealt a hand that contains exactly one pair of red Queens with ...
2
votes
0answers
17 views

Reversal distance of strings (with duplicates)

Note: If the following is true, then it would be best if you could just point me in the right direction, rather than giving a complete proof right away. Let $\Sigma$ be a finite alphabet and $s,t\in\...
2
votes
0answers
20 views

Enumerating integer partitions

There is a natural way to order all $k=1..p(N)$ partitions of a given integer $N$ ($p(N)$ being a total number of partitions) in a "decreasing" order. Say, for $4$: $$ \{4\},\,\{3,1\},\,\{2,2\},\,\{2,...
0
votes
1answer
32 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
3answers
36 views

Getting a wrong answer on evaluating permutations separately

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
20 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 ...
0
votes
2answers
65 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
9 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)}=...
0
votes
1answer
34 views

For what n,m the following conditon hold

Suppose their are n people and each person is friend with exactly m other people . What should be the relation between n and m for the following condition to hold and how to prove that . For example ...
1
vote
1answer
30 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 ...
0
votes
0answers
8 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
15 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
22 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
35 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 ...
2
votes
0answers
38 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
21 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
32 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
44 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
22 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
46 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
25 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
38 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 ...