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.

7,572 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
55
votes
0answers
1k views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
53
votes
0answers
2k views

Mondrian Art Problem Upper Bound for defect

Divide a square of side $n$ into any number of non-congruent rectangles. If all the sides are integers, what is the smallest possible difference in area between the largest and smallest rectangles? ...
39
votes
0answers
1k views

How to find a total order with constrained comparisons

There are 25 horses with different speeds. My goal is to rank all of them, by using only runs with 5 horses, and taking partial rankings. How many runs do I need, at minumum, to complete my task? As ...
34
votes
0answers
512 views

Can Erdős-Turán $\frac{5}{8}$ theorem be generalised that way?

Suppose for an arbitrary group word $w$ ower the alphabet of $n$ symbols $\mathfrak{U_w}$ is a variety of all groups $G$, that satisfy an identity $\forall a_1, … , a_n \in G$ $w(a_1, … , a_n) = e$. ...
27
votes
0answers
1k views

Prove this determinant identity combinatorially

This is for those of you who understand the Lindstrom-Gessel-Viennot lemma. I am looking for a proof of the following identity using paths and such: Let $A$ be an $n\times n$ matrix, and for $i,j\in\{...
24
votes
0answers
750 views

Symmetric polynomials

I've got a seemingly simple question that I've become curious about as a result of supervising some undergraduate research. Let's suppose we have some sequence of polynomials $f_0, f_1, f_2, \cdots \...
22
votes
0answers
976 views

Blocking directed paths on a DAG with a linear number of vertex defects.

Let $G=(V,E)$ be a directed acyclic graph. Define the set of all directed paths in $G$ by $\Gamma$. Given a subset $W\subseteq V$, let $\Gamma_W\subseteq \Gamma$ be the set of all paths $\gamma\in\...
20
votes
1answer
658 views

The equation with binomial coefficient $\binom{n-m}{k+m}=\binom{n+m}{k-m}$

Find all positive integers $n,k$ such that $$\binom{n-m}{k+m}=\binom{n+m}{k-m}$$ 1) I solved problem if $m=1$. Its here: $k=1; n=3$ 2) $$\binom{n-m}{k+m}=\binom{n+m}{k-m}$$ $k=m, n=3m$ is root of ...
20
votes
0answers
325 views

How many ways can I arrange the numbers $1$ to $N$ with this divisibility condition?

For the numbers $1, \ldots, N$, how many ways can I arrange them such that either: The number at $i$ is evenly divisible by $i$, or $i$ is evenly divisible by the number at $i$. Example: for N = 2$, ...
19
votes
0answers
603 views

When can we quit a game of War?

Consider the game of War. (The rules are below.) It would be nice to be able to end the game early. Suppose, for example, one player has 50 of the 52 cards. It is very likely that he's going to win. ...
18
votes
2answers
9k views

Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$

So i was given this question. Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$ Here is my solution: Given $2n$ objects, split them into $2$ groups of $n$, $A$ and $B$. $2$-...
17
votes
0answers
317 views

A combinatorial identity involving generalized harmonic numbers

[This problem has now an answer here.] The $n$-th harmonic number is defined as $$ H_n=\sum_{k=1}^{n}\frac{1}{k}, $$ and the generalized harmonic numbers are defined by $$ H_{n}^{(r)}=\sum_{k=1}^{n}\...
16
votes
0answers
1k views

Minimal time gossip problem

The gossip problem (telephone problem) is an information dissemination problem where each of $n$ nodes of a communication network has a unique piece of information that must be transmitted to all the ...
15
votes
1answer
398 views

The number of non-singular $n\times n$ matrices over $\mathbb{F}_2$ with exactly $k$ non-zero entries

Suppose $M_{n}^{k}$ is the number of non-singular $n\times n$ matrices over $\mathbb{F}_2$, that have exactly $k$ non-zero entries. Is there some sort of formula to calculate $M_n^k$? If $k < n$ ...
15
votes
0answers
415 views

Random sum in coupon collection

I have a problem which involves the standard coupon collector's problem to find a probability density from the generating convolution. I start by defining the problem and a few basic statistics. Let ...
15
votes
0answers
629 views

Distributing groups of objects into boxes

How can I enumerate the number of ways of distributing distinct groups of identical objects (but various cardinality) into $k$ boxes such that at most one box is empty $(1)$ and no combination of ...
14
votes
0answers
341 views

Largest consecutive integer using basic operations and optimal digits?

If you are first time reading this, you may want to read the summary section last. Solution summary and questions Sequence values If the allowed operations are $(+,-,\times,\div)$ and parentheses $(...
14
votes
0answers
169 views

graph with many authomorphisms

Let $G(V,E)$ be an undirected graph, potentially with loops and multi-edges. Assume the following two properties hold: $\forall a \in V(G), \exists f \in aut(G), f(a) \ne a$ $\forall f\in aut(G), \...
14
votes
0answers
473 views

Who is the mathematician “Jacques” in this anecdote from Fadiman's “The Mathematical Magpie”?

Who is the mathematician "Jacques" in this anecdote, which I read on p. 260 of The Mathematical Magpie by Clifton Fadiman, who quotes it from the 1942 memoir The Last Time I Saw Paris by Elliot Paul? ...
14
votes
0answers
251 views

Reconstruction Conjecture and Partial 2-trees

Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old. Searching relevant literature,...
13
votes
0answers
376 views

Strategy for board game 2

In this question the following was asked: Alice and Bob are playing the following game: They have a $4 \times 4$ empty grid and take turns coloring one square each, starting with Alice, both using ...
13
votes
1answer
1k views

Domination problem with sets

Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets of $M$, satisfying: (1) $|S_i|\leq 3,i=1,2,...,k$ (2) Any element of $M$ is an element of at least $4$ sets among $S_1,....,...
13
votes
1answer
316 views

Upper bound for the widest matrix with no two subsets of columns with the same vector sum

Over at PPCG there is an ongoing contest going on to find the largest matrix without a certain property, called property $X$. The description is as follows (copied from the question). A circulant ...
13
votes
0answers
390 views

History of a combinatoric problem: exchanging numbers by throwing stones

Another user recently asked a question on the Puzzling stack: Two spies throwing stones into a river. Suitably generalised, it becomes: Two spies (Alice and Bob) need to exchange a message. Each ...
13
votes
0answers
427 views

Specializations of elementary symmetric polynomials

Let $\mathcal{S}_{x}=\{x_{1,},x_{2},\ldots x_{n}\}$ be a set of $n$ indeterminates. The $h^{th}$elementary symmetric polynomial is the sum of all monomials with $h$ factors \begin{eqnarray*} e_{h}(\...
13
votes
0answers
199 views

Generalization of Gray codes

A friend of mine asked me if it was possible - physical difficulties aside - to generate all 32 combinations of raised/lowered fingers by changing status of a fixed number of fingers at every step. ...
13
votes
1answer
2k views

Triangle dissection, no shared edges

It's possible to divide a triangle into smaller triangles such that no edge lengths are shared. Alternately, no two internal triangles share two vertices. The top three are the known simplest ...
12
votes
0answers
130 views

For what $n$ can $\{1, 2,\ldots, n\}$ be partitioned into equal-sized sets $A$, $B$ such that $\sum_{k\in A}k^p=\sum_{k\in B}k^p$ for $p=1, 2, 3$?

This is a recent problem in American Mathematical Monthly. The deadline for this question just passed: $\textbf{Problem:}$ For which positive integers $n$ can $\{1,2,3,...,n\}$ be partitioned into ...
12
votes
0answers
314 views

When does a set of sums uniquely determine a set of values?

This is a follow up to a question about determining the set of values from a set of sums. We consider the following setup: Consider a vector $A$ (which you will not see) of $n$ positive integers. ...
12
votes
0answers
407 views

How many distinct Unruly boards are there?

Unruly is a puzzle game played on a board of $2n × 2n$ squares. Each square must be colored either black or white, with the following constraints: Each column must have $n$ white squares and $n$ ...
12
votes
0answers
311 views

Different notions of q-numbers

It seems that most of the literature dealing with q-analogs defines q-numbers according to $$[n]_q\equiv \frac{q^n-1}{q-1}.$$ Even Mathematica uses this definition: with the built-in function QGamma ...
11
votes
0answers
210 views

All interval sequences mod integers

In music, an all-interval twelve-tone sequence is a sequence that contains a row of 12 distinct notes such that it contains one instance of each interval within the octave, 1 through 11. The more ...
11
votes
0answers
417 views

Every 4-regular simple graph contains a 3-regular subgraph

The following result was conjectured by Berge & Sauer, and proved by Tashkinov [T]. Theorem A. Every 4-regular simple graph contains a 3-regular subgraph. A simple graph is the one with no ...
11
votes
0answers
172 views

Given $a_1 \leq a_2 \leq \dots \leq a_n$, how many possible orders are there for $\{a_i + a_j\}$?

Suppose we have $n$ variables $a_1 \leq a_2 \leq \dots \leq a_n$. If the values of the variables are not known, in how many ways could $\{a_i + a_j\}_{\{i,j\} \in {[n] \choose 2}}$ be ordered using $&...
11
votes
0answers
471 views

Twin-prime sieve

My question concerns the following sieve (call it S), which was an exercise in applying some elementary aspects of Brun's sieve while reading Halberstam's text. Using the Chinese Remainder theorem ...
11
votes
0answers
183 views

Finding a separating family of subsets of $[n]$ of size $n+1$.

I have this friend who always tells me problems I can't solve. Here is the latest one. We are given a family $\mathcal F$ of at least $2^{n-1}+1 $ subsets $[n]$. We must prove that we can $\color{...
11
votes
1answer
354 views

Double factorial as a sum

I believe the following equality to hold for all integer $l\geq 1$ $$(2l+1)!2^l\sum_{k=0}^l\frac{(-1)^k(l-k)!}{k!(2l-2k+1)!4^k}=(-1)^l(2l-1)!!$$ (it's correct for at least $l=1,2,3,4$), but cannot ...
11
votes
0answers
354 views

The right way to motivate lattice theory in a combinatorics class

I am attending a course on combinatorics. I was asked to present Möbius functions on lattices for this course. I was trying to look for a simple non-trivial problem that illustrates the need for ...
11
votes
0answers
351 views

Combinatorial Proofs of Real Analysis Identity

In this question, a proof using real analysis is given of the following identity: $$ \sum_{n=1}^{\infty} \frac{(n-1)!}{n \prod_{i=1}^{n} (a+i)} = \sum_{k=1}^{\infty} \frac{1}{(a+k)^2}$$ Is there a ...
11
votes
0answers
745 views

How strong is the statement that Thompson F is amenable?

Justin Moore's proof turned out to have an error I just attended Justin Moore's talk on this today. Since I am neither a group theorist nor a combinatorist, and is not familiar with ultrafilters I ...
11
votes
0answers
211 views

How to prove that my sum coincides with a sequence on the Online Encyclopedia of Integer Sequences?

I have a topological space $X$ whose reduced $\bmod 2$ Betti numbers (that is to say, the dimension of the $\bmod 2$ reduced homology) I computed to be $$\small \dim \tilde{H}_t(X; {\mathbb{Z}}_2) = \...
10
votes
0answers
288 views

Maximum number of regions of a sphere partitioned by $\binom{n}{3}$ planes from $n$ points

We can place $n\in\mathbb{N}$ points on the surface of a sphere in a configuration so as to maximize the answer. A plane is defined by $3$ points. We create all $\binom{n}{3}$ planes from the $n$ ...
10
votes
0answers
318 views

Number of sets of vertices whose union of neighbours contains exactly $k$ vertices

Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows: For example, $g$ for $n=3$: If I ...
10
votes
0answers
348 views

Number of ways to express a binary number in a certain way

So I'm working on a problem where I get to a point where I have to count the number of solutions to an equation or at least find a decent upper bound to be used in an estimate I need later. The ...
10
votes
1answer
230 views

Counting the number of elements in a double coset

Let $G$ denote the groups of $n\times n$ invertible matrices and $H$ be the subgroup of invertible upper triangular matrices. For $n=2$, by row reduction, or equivalently LU decomposition, it is ...
10
votes
0answers
210 views

To what extent is it possible to generalise a natural bijection between trees and $7$-tuples of trees, suggested by divergent series?

In the paper "Seven Trees In One" by Andreas Blass, a "very explicit" bijection is found between trees and 7-tuples of such trees. The idea to construct such a bijection stems from looking at some ...
10
votes
2answers
1k views

What is the number of ways to divide a rectangle into $n$ smaller rectangles line by line?

The original problem was to consider how many ways to make a wiring diagram out of $n$ resistors. When I thought about this I realized that if you can only connect in series and shunt. - Then this is ...
10
votes
0answers
377 views

Extracting an (almost) independent large subset from a pairwise independent set of Bernoulli variables

Let $n>1$, and let $X_1,X_2, \ldots ,X_n$ be non-constant random variables with values in $\lbrace 0,1 \rbrace$. Let us say that a subset of variables $X_{i_1},X_{i_2}, \ldots,X_{i_d}$ is complete ...
10
votes
0answers
246 views

Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?

Remark: I recently rewrote this post, hoping to get answers! I am analyzing the following experiment: Pick an $x \in \{0,\ldots,2k\}$ uniformly at random Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
10
votes
1answer
1k views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...