Stack Exchange Network

Stack Exchange network consists of 174 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 [co.combinatorics]

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

105
votes
57answers
20k views

Important formulas in Combinatorics

Motivation: The poster for the conference celebrating Noga Alon's 60th birthday, fifteen formulas describing some of Alon's work are presented. (See this post, for the poster, and cash prizes offered ...
72
votes
11answers
50k views

Sum of 'the first k' binomial coefficients for fixed n

I am interested in the function $$f(N,k)=\sum_{i=0}^{k} {N \choose i}$$ for fixed $N$ and $0 \leq k \leq N $. Obviously it equals 1 for $k = 0$ and $2^{N}$ for $k = N$, but are there any other ...
36
votes
6answers
5k views

Generating finite simple groups with $2$ elements

Here is a very natural question: Q: Is it always possible to generate a finite simple group with only $2$ elements? In all the examples that I can think of the answer is yes. If the answer is ...
16
votes
7answers
8k views

Lower bound for sum of binomial coefficients?

Hi! I'm new here. It would be awesome if someone knows a good answer. Is there a good lower bound for the tail of sums of binomial coefficients? I'm particularly interested in the simplest case $\...
45
votes
3answers
4k views

Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$

Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?
18
votes
3answers
4k views

Number of unique determinants for an NxN (0,1)-matrix

I'm interested in bounds for the number of unique determinants of NxN (0,1)-matrices. Obviously some of these matrices will be singular and therefore will trivially have zero determinant. While it ...
7
votes
1answer
643 views

Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
33
votes
4answers
3k views

Cliques, Paley graphs and quadratic residues

A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs. If p=1 mod 4 is a prime, we can define the ...
14
votes
1answer
416 views

Is there a lift of the q-Vandermonde identity to some geometric (motivic) identity for Grassmannians over $F_q$?

The q-Vandermonde identity reads: $$ \binom{m + n}{k}_{\!\!q} =\sum_{j} \binom{m}{k - j}_{\!\!q} \binom{n}{j}_{\!\!q} q^{j(m-k+j)} $$ The q-binomial coefficients: $$ \binom{ a }{ b}_{\!\!q} $$ ...
7
votes
1answer
1k views

Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants

Zeta functions abound in mathematics. Audrey Terras describes in Zeta Functions and Chaos three zeta functions--the zeta fct. of a projective non-singular algebraic variety; the Artin-Mazur zeta ...
8
votes
3answers
3k views

Estimating a partial sum of weighted binomial coefficients

There is a well-known estimate for the sum of all binomial coefficients $\binom{n}{k}$ satisfying $k \leq \alpha n$ for some $\alpha$ satisfying $0 < \alpha \leq 1/2$: $$ \sum_{k=0}^{\alpha n}\...
13
votes
2answers
751 views

Explicit invariant of tensors nonvanishing on the diagonal

The group $SL_n \times SL_n \times SL_n$ acts naturally on the vector space $\mathbb C^n \otimes \mathbb C^n \otimes \mathbb C^n$ and has a rather large ring of polynomial invariants. The element $$\...
7
votes
1answer
274 views

Bound for largest eigenvalue of symmetric matrices of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s

Given a $n\times n$ symmetric random matrix whose diagonal elements are all fixed as $1$. In addition, there are $k$ $1$s will be randomly scattered in upper triangular (of course, the corresponding ...
68
votes
6answers
3k views

Does every polyomino tile R^n for some n?

This is a question posed by Adam Chalcraft. I am posting it here because I think it deserves wider circulation, and because maybe someone already knows the answer. A polyomino is usually defined to ...
23
votes
1answer
796 views

Two conjectures about zero inner products and dissociated sets

The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...
17
votes
4answers
2k views

Can you determine whether a graph is the 1-skeleton of a polytope?

How do I test whether a given undirected graph is the 1-skeleton of a polytope? How can I tell the dimension of a given 1-skeleton?
26
votes
3answers
2k views

Does the hypergraph structure of the set of subgroups of a finite group characterize isomorphism type?

Question Suppose there is a bijection between the underlying sets of two finite groups $G, H$, such that every subgroup of $G$ corresponds to a subgroup of $H$, and that every subgroup of $H$ ...
29
votes
4answers
2k views

Is it possible to define higher cardinal arithmetics

In number theory there are several operators like ‎addition, ‎multiplication and ‎exponentiation defined from ‎$‎‎‎\omega‎‎\times‎‎\omega‎$ ‎to ‎‎$‎‎‎\omega‎$. Each ‎of ‎them ‎is defined as an ‎...
12
votes
2answers
727 views

The Simultaneous Conjugacy Problem in the symmetric group $S_N$

We are interested in the following notions in the case $G=S_N$, the symmetric group on $\{1,\dots,N\}$. Fix a group $G$ and a number $d$. For $(g_1,\dots,g_d)\in G^d$ and $x\in G$, define $$(g_1,\...
10
votes
2answers
2k views

Riemann zeta function at positive integers and an Appell sequence of polynomials related to fractional calculus

I was exploring some raising and lowering operators related to an infinitesimal generator for fractional integro-derivatives and found an Appell sequence of polynomials, i.e., an infinite sequence of ...
20
votes
1answer
372 views

$q$-(and other)-analogs for counting index-$n$ subgroups in terms of Homs to $S_n$?

The following formula of astonishing beauty and power (imho): $$ \sum_{n \ge 0} \frac{| \mathrm{Hom}(G,S_n) | }{n! } z^n = \exp\left( \sum_{n \ge 1} \frac{|\text{Index}~n~\text{subgroups of}~ G|}nz^...
13
votes
2answers
707 views

Number of commuting pairs (triples, n-tuples) in GL_n(F_q) (and other groups)?

Question 1 What is the number of pairs of commuting elements in GL_n(F_q) ? I am aware of many results concerning commuting elements in Mat_n(F_q), but I am interested in GL i.e. non-degenerate ...
9
votes
4answers
5k views

Mean minimum distance for N random points on a unit square (plane)

A previously posted question "mean minimum distance for N random points on a one-dimensional line" produced an elegant answer: for a line of length L, the expected minimum distance (between random ...
3
votes
1answer
720 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 $...
21
votes
3answers
629 views

Kasteleyn's formula for domino tilings generalized?

It seems a marvel when a bunch of irrational numbers "conspire" to become rational, even better an integer. An elementary example is $\prod_{j=1}^n4\cos^2\left(\pi j/(2n+1)\right)=1$. Kasteleyn's ...
8
votes
1answer
229 views

Loday's characterization and enumeration of faces of associahedra (Stasheff polytopes)

From "The multiple facets of the associahedra" by Loday: Let us consider the formal power series $$f(x) = x+a_1 x^2 +a_2 x^3 + \cdots+ a_n x^{n+1} + \cdots$$ and let $$ g(x) = x+b_1 ...
4
votes
1answer
907 views

The property of Kendall-Mann numbers

The sequence A000140 is studied http://oeis.org/A000140 (Kendall-Mann numbers: the maximum number of permutations on n letters having the same number of inversions ) and I am looking for a proof ...
93
votes
5answers
7k views

integral of a “sin-omial” coefficients=binomial

I find the following averaged-integral amusing and intriguing, to say the least. Is there any proof? For any pair of integers $n\geq k\geq0$, we have $$\frac1{\pi}\int_0^{\pi}\frac{\sin^n(x)}{\...
61
votes
6answers
6k views

How to recognise that the polynomial method might work

A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson. Theorem. Let $(a_1,b_1),\dots,(...
41
votes
4answers
4k views

Integer-valued factorial ratios

This historical question recalls Pafnuty Chebyshev's estimates for the prime distribution function. In his derivation Chebyshev used the factorial ratio sequence $$ u_n=\frac{(30n)!n!}{(15n)!(10n)!(6n)...
46
votes
2answers
7k views

Walsh Fourier Transform of the Möbius function

This question is related to this previous question where I asked about ordinary Fourier coefficients. Special case: is Möbius nearly Orthogonal to Morse ! Harold Calvin Marston Morse (24 March ...
28
votes
2answers
6k views

Mean minimum distance for N random points on a one-dimensional line

Let's say that I have a one-dimensional line of finite length 'L' that I populate with a set of 'N' random points. I was wondering if there was a simple/straightforward method (not involving long ...
19
votes
6answers
8k views

A balls-and-colours problem

A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour of the ...
35
votes
5answers
4k views

Groups, quantum groups and (fill in the blank)

In the study of special functions there are three levels of objects, classical, basic and elliptic. These correspond to classical hypergeometric functions, basic (q-) hypergeometric functions, and ...
24
votes
5answers
6k views

Erdos Conjecture on arithmetic progressions

Introduction: Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length. Question: I ...
18
votes
10answers
4k views

Applications of infinite Ramsey's Theorem (on N)?

Finite Ramsey's theorem is a very important combinatorial tool that is often used in mathematics. The infinite version of Ramsey's theorem (Ramsey's theorem for colorings of tuples of natural numbers) ...
27
votes
5answers
2k views

Small simplicial complexes with torsion in their homology?

Fix a prime $p$. What is the smallest integer $n$ so that there is a simplicial complex on $n$ vertices with $p$-torsion in its homology? For example, when $p=2$, there is a complex with 6 vertices (...
36
votes
2answers
2k views

A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself

Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...
14
votes
2answers
1k 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$?
12
votes
4answers
6k views

How many $p$-regular graphs with $n$ vertices are there?

Suppose that there are $n$ vertices, we want to construct a regular graph with degree $p$, which, of course, is less than $n$. My question is how many possible such graphs can we get?
18
votes
3answers
1k views

The sum of integers being a bijection

What are the pairs $(P,Q)$ of subsets of $\mathbb N$ for which the map \begin{eqnarray*} P\times Q & \rightarrow & {\mathbb N} \\\\ (p,q) & \mapsto & p+q \end{eqnarray*} is a bijection ...
11
votes
1answer
434 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 ...
17
votes
1answer
602 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, ...
16
votes
2answers
971 views

Minimal graphs with a prescribed number of spanning trees

As its long ago since Erdős died and mathoverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem ...
11
votes
4answers
2k 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 ...
9
votes
1answer
351 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, ...
3
votes
1answer
320 views

Counting “connected” edge orderings (shellings) of the complete graph [duplicate]

This question is inspired by "Number of collinear ways to fill a grid" by Sebastien Palcoux and the comments of user44191 on this earlier question of Palcoux's. Let $G=(V,E)$ be a graph. An edge ...
15
votes
1answer
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 ...
3
votes
0answers
154 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,...
1
vote
0answers
225 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\}$....