Questions tagged [co.combinatorics]

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

Filter by
Sorted by
Tagged with
17 votes
1 answer
1k views

Smith Normal Form of powers of a matrix

What invariants of a matrix determine the Smith Normal Form (SNF) of all the powers of a matrix? The question makes sense over any PID $R$. If we let $M = M_n(R)$ and $G=Gl_n(R)$, then SNF is a ...
Robert Bruner's user avatar
17 votes
8 answers
3k views

Cyclotomic polynomials in combinatorics

I am searching for a combinatorial significance of cyclotomic polynomials. The only examples I got are a paper by Neville Robbins http://www.emis.de/journals/INTEGERS/papers/a6/a6.pdf and two recent ...
17 votes
1 answer
719 views

Reference request: a conjecture of Rota on positive functions of a random variable

Rota and Shen's On the Combinatorics of Cumulants ends with a conjecture which I'll restate as follows: Let $p \in \mathbb{R}[x_1, x_2, ...]$ be a polynomial such that, for any sequence $X_1, X_2, ...
Qiaochu Yuan's user avatar
17 votes
11 answers
2k views

Chromatic number of graphs of tangent closed balls

The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a disk packing whose graph is $G$. What ...
Kristal Cantwell's user avatar
17 votes
2 answers
2k views

Number of isomorphism types of finite groups

Are there some good asymptotic estimations for the number $F(n)$ of non-isomorphic finite groups of size smaller than $n$?
Al Tal's user avatar
  • 1,271
16 votes
4 answers
9k views

Exact formulas for the partition function?

I am curious, what kind of exact formulas exist for the partition function $p(n)$? I seem to remember an exact formula along the lines $p(n) = \sum_k f(n, k)$, where $f(n, k)$ was some extremely ...
Frank Thorne's user avatar
  • 7,199
16 votes
3 answers
701 views

Can we realize a graph as the skeleton of a polytope that has the same symmetries?

Given a graph $G$, a realization of $G$ as a polytope is a convex polytope $P\subseteq \Bbb R^n$ with $G$ as its 1-skeleton. A realization $P\subseteq \Bbb R^n$ is said to realize the symmetries of $...
M. Winter's user avatar
  • 12.5k
16 votes
0 answers
452 views

A Product Related to Unrestricted Partitions

Start with the product for unrestricted partitions: $(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...$ Now replace some of the plus signs with minus signs and expand the product into a series. Is it ...
David S. Newman's user avatar
15 votes
4 answers
3k views

Ordinary Generating Function for Bell Numbers

In the OEIS entry for Bell numbers, there appears a generating function $$\sum_{k=0}^\infty B_k t^k = \sum_{r=0}^\infty \prod_{i=1}^r \frac{t}{1-it}$$ However, I could not locate any proof of ...
Amritanshu Prasad's user avatar
15 votes
3 answers
2k views

Integration of a function over 7-sphere

Suppose we have $x_1^2 + y_1^2 + x_2^2 + y_2^2 + x_3^2 + y_3^2 + x_4^2 + y_4^2 = 1$ and we define $z_j = x_j + iy_j$, where $j = 1,\,2,\,3,\,4$. The problem is finding or approximating the ...
Hrushikesh Pawar's user avatar
14 votes
4 answers
3k views

Number of closed walks on an $n$-cube

Is there a known formula for the number of closed walks of length (exactly) $r$ on the $n$-cube? If not, what are the best known upper and lower bounds? [Edit] Note: the walk can repeat vertices.
Lev Reyzin's user avatar
14 votes
5 answers
2k views

A general formula for the number of conjugacy classes of $\mathbb{S}_n \times \mathbb{S}_n$ acted on by $ \mathbb{S}_n$

$\def\S{\mathbb{S}}$ Dear all, So I have $\S_n$ acting on $\S_n \times \S_n$ via conjugacy. That is: for $g \in \S_n, (x,y) \in \S_n \times \S_n$: $g(x,y) = (gxg^{-1},gyg^{-1}).$ Is there a general ...
Ngoc Mai Tran's user avatar
13 votes
1 answer
1k views

Irreducibility of Schur polynomials

A natural question covering both this and this question would be Let $n>2$. Describe Young diagrams $\lambda$ with at most $n$ nonempty rows (or equivalently non-increasing sequences $\lambda=(\...
Vladimir Dotsenko's user avatar
13 votes
3 answers
851 views

A strengthening of Frankl's union-closed conjecture?

Frankl's union-closed conjecture states that if $F$ is a finite union-closed family of sets (i.e. a family that is closed under taking unions), then there must be an element that belongs to at least ...
MassiveJack's user avatar
12 votes
1 answer
842 views

The dance marathon problem

In his book, "The Strange Logic of Random Graphs", Joel Spencer describes the "Dance Marathon" problem: Imagine $n$ couples at a Dance Marathon. Each dance each couple remains ...
Bill Bradley's user avatar
  • 3,809
12 votes
3 answers
752 views

Can the equation $1+z+z^2=z^n$ for natural $n$ have multiple complex roots $z$?

The question is stated in the title of this post. It is easy to see that, if $z$ is a multiple root of $p_n(z):=1+z+z^2-z^n$, then $(n-2)z^2+(n-1)z+n=0$, so that we can successively express $z^2,\dots,...
Iosif Pinelis's user avatar
12 votes
0 answers
537 views

Possible orders of products of 2 involutions which interchange disjoint residue classes of the integers

Definition / Question Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$. Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition $...
Stefan Kohl's user avatar
  • 19.5k
12 votes
1 answer
483 views

Probability of a graph procedure

We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, ...
user43928's user avatar
  • 175
12 votes
2 answers
1k views

Combinatorics of the Stasheff polytopes

First a little background for those unaware. The Stasheff polytopes (or associahedra) are certain convex polytopes that arise in the theory of $A_\infty$-algebras. There is one polytope for each $n\...
Somnath Basu's user avatar
  • 3,403
11 votes
11 answers
1k views

Lattices on classical combinatorial families

I am asking for examples of lattices defined on classical combinatorial families, such as Permutations, Catalan objects, set partitions or integer partitions, graphs. I am mosty interested in lattices ...
Martin Rubey's user avatar
  • 5,533
11 votes
2 answers
995 views

Densest Graphs with Unique Perfect Matching

Given a graph $G$ with $n$ vertices, that has a perfect matching $M$, what is the maximal number of edges that $G$ can have without contradicting the uniqueness of $M$? Are examples of such extremal ...
Manfred Weis's user avatar
  • 12.6k
11 votes
1 answer
673 views

2-adic Logarithm and Resistance of n-dimensional Cube

Resistance across opposite vertices of n-dimensional cube with each edge at one ohm resistance is $$R_n=\sum_{k=0}^{n-1}\frac1{(n-k){n\choose k}}=\frac1n\sum_{k=0}^{n-1}\frac1{{n-1\choose k}}.$$ The ...
Alexey Ustinov's user avatar
11 votes
1 answer
569 views

Catalan determinants in search of a proof: Part II

This problem involves the Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$. I can prove the below equality by computing each of the two sides, directly. That means, there is an algebraic proof. ...
T. Amdeberhan's user avatar
10 votes
1 answer
1k views

How can we find n points on a plane so that as many pairs of points as possible have the same distance?

There are $n$ points on the plane, and we need to maximize the number of pairs of points which have the same Euclidean distance.
Cynasty's user avatar
  • 159
9 votes
1 answer
2k views

The line graphs of complete graphs and Cayley graphs

Let $n>3$ be an odd integer and let $K_n$ denote the complete graph on $n$ vertices. For which integers $n$ the line graph $L(K_n)$ is a Cayley graph? For even $n$, it follows from a result of ...
Alireza Abdollahi's user avatar
9 votes
2 answers
2k views

Sperner's lemma and Tucker's lemma

In their article "A Borsuk-Ulam Equivalent that Directly Implies Sperner's Lemma" (American Mathematical Monthly, April 2013), Nyman and Su write "[W]e are unaware of a direct proof that Tucker's ...
James Propp's user avatar
  • 19.4k
9 votes
0 answers
343 views

Factorisation of a polynomial from the Boolean algebra

Let $B_n$ denote the Boolean algebra of a set with $n \geq 2$ elements and $C_n$ the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in B_n$. Let $M_n:=C_n+C_n^T$ and $...
Mare's user avatar
  • 25.8k
8 votes
3 answers
703 views

Combinatorial interpretation of series reversion coefficients

In a recent paper studying some generalizations of Stirling numbers, my coauthors and I needed the following result: If $f(x)=\sum_{n \geq 1} a_n x^n/n!$ is a power series with $a_1 \neq 0$, and $g(x)...
David Galvin's user avatar
  • 1,112
7 votes
0 answers
242 views

How distributive are the fake Laver tables?

The Laver table $A_{n}$ is the unique algebra $(\{1,...,2^{n}\},*)$ such that $x*1=x+1$ for $1\leq x<2^{n}$, $2^{n}*1=1$, and $x*(y*z)=(x*y)*(x*z)$. Let's now replace the Laver table $A_{n}$ with ...
Joseph Van Name's user avatar
7 votes
2 answers
426 views

Limit associated with complementary sequences

Define $A=(a_n)$ and $B=(b_n)$ as follows: $a_0=1$, $a_1=2$, $b_0=3$, $b_1=4$, and $$a_n=a_0b_{n-1}+a_1b_{n-2}$$ for $n \geq 2$, where $A$ and $B$ are increasing and every positive integer occurs ...
Clark Kimberling's user avatar
6 votes
2 answers
1k views

How to understand the combinatorial Laplacian $\Delta$ which is defined on the graph?

I have a question about the combinatorial Laplacian $\Delta$ which is defined by $$\Delta(u,v)=c(u)1_{u=v}-c(u,v)$$ where $u, v$ are some vertices in the graph $G=(V, E)$, and $c(u,v)$ is a ...
Hermi's user avatar
  • 274
6 votes
3 answers
2k views

An Intriguing Tapestry: Number triangles, polytopes, Grassmannians, and scattering amplitudes

What are the roles that the classic number arrays-- Eulerian, Narayana--play in the application of totally non-negative Grassmannians, or amplituhedrons, to string / twistor scattering theory? (This ...
Tom Copeland's user avatar
  • 9,937
6 votes
1 answer
621 views

Positivity of the alternating sum of indices for boolean interval of finite groups

Let $G$ be a finite group and $H$ a subgroup such that the interval $[H,G]$ is a boolean lattice. Let $L_1, \dots , L_n$ be the maximal subgroups of $G$ containing $H$. Let the alternative sum ...
Sebastien Palcoux's user avatar
6 votes
1 answer
394 views

hooks and contents: Part I

For a cell $\square$ in the Young diagram of a partition $\lambda$, let $h_{\square}$ and $c_{\square}$ denote the hook length and content of $\square$, respectively. R Stanley proved the following ...
T. Amdeberhan's user avatar
5 votes
1 answer
559 views

differential operator power coefficients

Let $(F(x)\frac{d}{dx})^n=\sum_{i=1}^n H_{n,i}(F, F', F^{(2)}, \ldots , F^{(n)})\frac{d^i}{dx^i}$. I'm curious about the exact formula for $H_{n,i}(y_0, y_1, \ldots , y_n)$. What is known about it?
zroslav's user avatar
  • 1,412
4 votes
1 answer
288 views

Is the top interval of a finite distributive lattice, a boolean lattice?

Let $(L,\wedge,\vee)$ be a finite distributive lattice, and let $1$ its greatest element. An element $a \in L$ is called maximal if $a \le a' < 1$ implies $a = a'$. Let $b$ be the meet of all the ...
Sebastien Palcoux's user avatar
4 votes
3 answers
319 views

Minimal data required to determine a convex polytope

Let $P\subset \Bbb R^d$ be a convex polytope. Suppose that I know its combinatorial type (aka. the face-lattice), the length $\ell_i$ of each edge, and the distance $r_i$ of each vertex from the ...
M. Winter's user avatar
  • 12.5k
4 votes
2 answers
2k views

Estimate on sum of squares of multinomial coefficients

I am interested in approximating the sum of the squares of the multinomial coefficients, i.e. $a_\ell^p := \sum_{k_0+\ldots+k_p = \ell} (\frac{\ell!}{k_0! \ldots k_p!})^2$ or more general, $a_\...
Liss's user avatar
  • 145
4 votes
1 answer
394 views

Generating functions for Hankel determinants of Catalan numbers

The Hankel determinants of the Catalan numbers are well known and can be written as $d(k,n)= \det \left( C_{k + i + j} \right)_{i,j = 0}^{n - 1}=\prod_{i=1}^{k-1}\frac{\binom{2n+2j}{j}}{\binom{2j}{j}}$...
Johann Cigler's user avatar
3 votes
1 answer
434 views

An identity for polynomials over partitions

Given an integer partition $\lambda=(\lambda_1,\dots,\lambda_{\ell(\lambda)})$ of $n$ where $\ell(\lambda)$ is the length of $\lambda$, associate its conjugate partition $\lambda'$. Denote by $\lambda'...
T. Amdeberhan's user avatar
3 votes
1 answer
1k views

The number of pairings between multisets

Given two multisets $A$ and $B$ of the same finite cardinality $n$, how many ways are there of pairing the two sets together? If both sets consist of distinct elements, the answer is $n!$: there are $...
rlo's user avatar
  • 1,671
3 votes
0 answers
190 views

A conjectural lower bound for $|\{\sum_{k=1}^nka_k:\ a_1,\ldots,a_n\ \text{are distinct elements of }\ A\}|$

Motivated by Question 315568 of mine, I'm interested in the set $$S(n):=\bigg\{\sum_{k=1}^n k\pi(k):\ \pi\in S_n\bigg\}.$$ It is easy to see that $$S(1)=\{1\},\ S(2)=\{4,5\}\ \text{and}\ S(3)=\{10,...
Zhi-Wei Sun's user avatar
  • 14.4k
2 votes
2 answers
356 views

Number of bounded Dyck paths with negative length as Hankel determinants

This is a continuation of my post Number of bounded Dyck paths with "negative length". Let $C_{n}^{(2k+1)}$ be the number of Dyck paths of semilength $n$ bounded by $2k+1.$ They satisfy a ...
Johann Cigler's user avatar
1 vote
0 answers
194 views

Classical and free cumulants, symmetric functions, and inverses (references), related to associahedra, parking functions, noncrossing partitions

Looking for references for one or more of the following four sets of partition polynomials 1a) through 4a), particularly those which present geometric / topological combinatorial interpretations. ...
Tom Copeland's user avatar
  • 9,937
1 vote
0 answers
281 views

On the number of Eulerian orderings

This post is a sequel of Eulerian ordering of the integers modulo n. Let us recall the definition of an Eulerian ordering: Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$....
Sebastien Palcoux's user avatar
1 vote
1 answer
223 views

Will this greedy algorithm always work?

Let p(n) be the number of unrestricted partitions of n. p(0) is taken to be 1. Let set 1 and set 2 be two empty sets. Here's an algorithm. Put p(n) into set 1. On each successive step, k=1,2,3,..., ...
David S. Newman's user avatar
29 votes
3 answers
4k views

Roots of permutations

Consider the equation $x^2=x_0$ in the symmetric group $S_n$, where $x_0\in S_n$ is fixed. Is it true that for each integer $n\geq 0$, the maximal number of solutions (the number of square roots of $...
Fedor Petrov's user avatar
111 votes
7 answers
8k views

Is the set $ AA+A $ always at least as large as $ A+A $?

Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$? My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly ...
Oliver Roche-Newton's user avatar
101 votes
3 answers
6k views

Why do combinatorial abstractions of geometric objects behave so well?

This question is inspired by a talk of June Huh from the recent "Current Developments in Mathematics" conference. Here are two examples of the kind of combinatorial abstractions of geometric ...
Sam Hopkins's user avatar
  • 22.7k
70 votes
7 answers
13k views

Identifying poisoned wines

The standard version of this puzzle is as follows: you have $1000$ bottles of wine, one of which is poisoned. You also have a supply of rats (say). You want to determine which bottle is the poisoned ...
Qiaochu Yuan's user avatar

1 2
3
4 5
30