All Questions
Tagged with combinatorics or co.combinatorics
11,023 questions
19
votes
2
answers
7k
views
Generalization of the shakehands/condom puzzle?
The classic handshake puzzle goes something like this:
"Given that everyone has a different skin disease, how can you safely shake hands with 3 people when you have only 2 gloves?"
Its common ...
- 235
40
votes
9
answers
255k
views
The factorials of -1, -2, -3, … [closed]
Well, $n!$ is for integer $n < 0$ not defined — as yet.
So the question is:
How could a sensible generalization of the factorial for negative integers look like?
Clearly a good generalization ...
- 1,054
2
votes
1
answer
1k
views
computing lengths in the A_2 affine weyl group
The A_2 affine Weyl group is the symmetry group of the triangulation of the plane by equilateral triangles. As Sean points out, it may be generated by reflections $r_1, r_2, r_3$ about the edges of a ...
- 22.8k
1
vote
0
answers
142
views
Term to describe how much harder an optimization problem can become after constraining a small part of the domain?
This is a follow up to this question.
I'm interested in discrete optimization problems formulated as 0-1 integer programs; essentially, anything of the form
$$\Phi = \max_{\mathbf{x} \in \left\{0,1\...
- 341
12
votes
3
answers
1k
views
distance regular metric spaces
A metric space (V,d) will be called distance regular if for every distances a>0, b, c a nonnegative integer p(a,b,c) is defined, so that whenever d(B,C)=a, there are precisely p(a,b,c) points A ...
32
votes
7
answers
71k
views
Notation for the all-ones vector [closed]
What's the most common way of writing the all-ones vector, that is, the vector, when projected onto each standard basis vector of a given vector space, having length one? The zero vector is frequently ...
- 439
5
votes
1
answer
415
views
Does an inverse polynomial map on the taylor coefficients of a rational function preserve rationality?
Supppose there are integers $a_1,a_2,\dots$ and a polynomial $p$ so that the integers $p(a_1),p(a_2)...$ satisfy some linear recurrence, i.e. $\sum p(a_i)x^i$ is a rational function of $x$. Must ...
- 85.6k
7
votes
1
answer
758
views
Explicit computation of induced modules of semidirect products with the symmetric group
I've gotten stuck in a project I have been working on, essentially on the following combinatorial question about the symmetric group.
One can obtain a 1-dimensional representation $M^n_c$ of the ...
- 25.6k
26
votes
2
answers
997
views
Is $\varphi(n)/n$ the maximal portion of $n$-cycles in a degree $n$ group?
Let $G$ be a degree $n$ group, i.e., a subgroup of the symmetric group $S_n$. Let $p(G)$ be the number of $n$-cycles in $G$ divided by the size of $G$.
Examples:
If $G$ is a cyclic transitive ...
- 3,362
12
votes
2
answers
1k
views
Highbrow interpretations of Stirling number reciprocity
The number ${n \choose k}$ of $k$-element subsets of an $n$-element set and the number $\left( {n \choose k} \right)$ of $k$-element multisets of an $n$-element set satisfy the reciprocity formula
$\...
- 118k
2
votes
3
answers
1k
views
Is there an English translation of Kuratowski's theorem on forbidden minors of planar graphs?
Is there an English translation of Kuratowski's proof about planar graphs?
- 343
22
votes
4
answers
2k
views
What exactly is the relationship between codes over finite fields and Euclidean sphere-packings?
So I know that error-correcting codes are sphere packings in the Hamming metric, and that intuition and technical tools from the Euclidean case can often be applied to the finite-field case and vice ...
- 12.6k
39
votes
9
answers
3k
views
The shortest path in first passage percolation
Update (January 17): The problem has now been solved by Daniel Ahlberg and Christopher Hoffman. (Thanks to Matt Kahle for informing us.)
Consider a square planar grid. (The vertices are pair of ...
- 24.7k
12
votes
5
answers
13k
views
Number of permutations with a specified number of fixed points
Let $F(k,n)$ be the number of permutations of an n-element set that fix exactly $k$ elements.
We know:
$F(n,n) = 1$
$F(n-1,n) = 0$
$F(n-2,n) = \binom {n} {2}$
...
$F(0,n) = n! \cdot \sum_{k=0}^n \...
- 9,720
7
votes
12
answers
18k
views
Uniquely generate all permutations of three digits that sum to a particular value?
I'm looking for a way of generating all permutations of three digits (actually xyz) that sum to the same value.
For example:
...
- 221
31
votes
2
answers
3k
views
Is there a "finitary" solution to the Basel problem?
Gabor Toth's Glimpses of Algebra and Geometry contains the following beautiful proof (perhaps I should say "interpretation") of the formula $\displaystyle \frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} ...
- 118k
8
votes
2
answers
1k
views
Poincaré quasi-isomorphism
Suppose we have a simplicial combinatorial manifold (just a triangulated manifold) and its Poincaré dual cell complex.
Corresponding homology simplicial and homology cell complexes are quasi-...
- 1,482
22
votes
4
answers
3k
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?
- 9,720
45
votes
16
answers
8k
views
What does the generating function $x/(1 - e^{-x})$ count?
Let $x$ be a formal (or small, since the function is analytic) variable, and consider the power series
$$ A(x) = \frac{x}{1 - e^{-x}} = \sum_{m=0}^\infty \left( -\sum_{n=1}^\infty \frac{(-x)^n}{(n+1)!}...
- 54.6k
19
votes
6
answers
37k
views
Pascal triangle and prime numbers
Back in the days when I was in high school, I developed a big interest about number theory specifically prime numbers and prefect numbers, I used to stay awake all night long with a bunch of sketch ...
- 299
25
votes
1
answer
1k
views
Disjoint stable sets in tournaments
Let $(V,A)$ be a tournament. A subset of vertices $V'\subseteq V$ is stable if
there exists no $v\in V\setminus V'$ such that $V'\cup${$v$} contains an inclusion-maximal transitive subtournament with ...
- 331
11
votes
2
answers
2k
views
Maximum degree in maximal triangle free graphs
It's easy to see that in bipartite maximal triangle free graphs (n vertices), the maximum degree is at least $\lceil n/2 \rceil$. What about mtf graphs in general? Must there always be some vertex ...
- 183
15
votes
5
answers
4k
views
Discrete harmonic function on a planar graph
Given a graph $G$ we will call a function $f:V(G)\to \mathbb{R}$ discrete harmonic if for all $v\in V(G)$ , the value of $f(v)$ is equal to the average of the values of $f$ at all the neighbors of $v$....
- 85.6k
42
votes
6
answers
7k
views
Number of valid topologies on a finite set of n elements
I've heard that the problem of counting topologies is hard, but I couldn't really find anything about it on the rest of the internet. Has this problem been solved? If not, is there some feature that ...
7
votes
2
answers
627
views
Probability vertices are adjacent in a polygon
With regard to my original question:
A subset of k vertices is chosen from the vertices of a regular N-gon. What is the probability that two vertices are adjacent?
I suppose that the responses ...
- 73
21
votes
1
answer
767
views
The density hex
Gale famously showed that the determinacy of n-player, n-dimensional Hex is equivalent to the Brouwer fixed point theorem in n dimensions.
We can (and Gale does) view this as saying that if you d-...
- 12.6k
4
votes
0
answers
497
views
A Local CLT with large variance
For n an even integer, $0 \leq i \leq$ ${n} \choose{j}$, $1 \leq j \leq n$ let $X_{i,j}$ be a
random variable taking values $\frac{n}{2}-j,0,j - \frac{n}{2}$ with equal probability. Let $S_{n}$ be ...
- 263
7
votes
4
answers
4k
views
Number of spanning trees in a grid
Given a $\sqrt{n}\times\sqrt{n}$ piece of the integer $\mathbb{Z}^2$ grid, define a graph by joining any two of these points at unit distance apart. How many spanning trees does this graph have (...
- 3,511
4
votes
1
answer
1k
views
alternating sums of terms of the Vandermonde identity
Using Vandermonde's identity we know:
$\sum_{i=0}^k \binom{k}{i}\binom{n-k}{n/2-i} = \binom{n}{n/2}$.
I'm interested in how close the alternating sum is to 0 when k << n. I.e.,
$\sum_{i=0}^k (...
- 43
14
votes
4
answers
6k
views
Battleship Permutations
Using the game of Battleship as an example, is there a general solution for determining the number of arrangements of a given set of 1xN rectangles on a X by Y grid?
Example: In Battleship, each ...
- 143
20
votes
5
answers
1k
views
Is there a natural family of languages whose generating functions are holonomic (i.e. D-finite)?
Let $L$ be a language on a finite alphabet and let $L_n$ be the number of words of length $n$. Let $f_L(x) = \sum_{n \ge 0} L_n x^n$. The following are well-known:
If $L$ is regular, then $f_L$ is ...
- 118k
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 ...
- 6,523
16
votes
5
answers
2k
views
Elliptic Curves over F_1?
Is there an notion of elliptic curve over the field with one element? As I learned from a previous question, there are several different versions of what the field with one element and what schemes ...
- 27.5k
8
votes
1
answer
820
views
Inequality of the number of integer partitions
I am familiar with the partition function p(k,n) where p is the number of partitions of n using only natural numbers at least as large as k.
Is there a way of determining if p(k1, n1) > p(k2, n2) that ...
- 81
12
votes
1
answer
827
views
Graphs of Tangent Spheres
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 circle packing whose graph is G. What ...
- 6,523
19
votes
4
answers
2k
views
Irreducible polynomials with constrained coefficients
Over at the Cafe, after reading about TWF 285, I asked more-or-less
About how many polynomials with coefficients in $\{\pm 1\}$ and of degree $d$ are irreducible?
and that's what I want to ask ...
- 1,987
4
votes
2
answers
320
views
Is there a poset with 0 with countable automorphism group?
Is there a poset P with a unique least element, such that every element is covered by finitely many other elements of P (and P is locally finite -- actually, per David Speyer's example, let's say that ...
- 12.6k
16
votes
6
answers
2k
views
Sum of $n$ vectors in $(\mathbb Z/n)^k$
Let $n,k$ be positive integers. What is the smallest value of $N$ such that for any $N$ vectors (may be repeated) in $(\mathbb Z/(n))^k$, one can pick $n$ vectors whose sum is $0$?
My guess is $N=2^...
- 30.5k
8
votes
1
answer
419
views
Universal property for collection of epimorphisms
Question Is there a nice universal property which captures the notion of "collection of all epimorphisms out of a given object". Of course I will have to consider two epimorphisms $X \rightarrow Y$ ...
- 12.1k
23
votes
9
answers
4k
views
What methods exist to prove that a finitely presented group is finite?
Suppose I have a finitely presented group (or a family of finitely presented groups with some integer parameters), and I'd like to know if the group is finite. What methods exist to find this out? I ...
- 1,861
2
votes
1
answer
380
views
Parity, Balls and Boxes
Start with a distribution $\mu$ on [n], and drop m balls into these n+1 slots independently and according to the distribution &mu. That is, we have iid random variables x 1 through x m ...
- 263
36
votes
21
answers
6k
views
Generalizations of Planar Graphs
This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...
- 24.7k
16
votes
7
answers
965
views
Extremal question on matrices
The following question was posed to me a while ago. No one I know has a given a satisfactory (or even a complete) proof:
Suppose that $M$ is an $n$ x $n$ matrix of non-negative integers. Additionally, ...
- 1,588
2
votes
2
answers
2k
views
Inversion of Laurent series
For a power series $f(z) = \sum_{i=0}^{\infty} a_i z^i$ with $a_1$ nonzero, Lagrange's inversion formula gives an explicit way to compute the Taylor coefficients of the inverse function.
Is there any ...
- 21k
16
votes
3
answers
3k
views
A riddle about zeros, ones and minus-ones
I was asked this years ago, but I don't remember by whom, and have never managed to solve it.
Consider the $2^n \times n$ matrix of all vectors in {-1,1}$^n$.
Someone comes and maliciously replaces ...
- 435
12
votes
4
answers
1k
views
Asymptotics of q-Catalan numbers
q-Catalan numbers are defined recurrently as C0=1, $C_{N+1}=\sum_{k=0}^N q^k C_k C_{N-k}$.
What can be said about the asymptotics of Cn when 0<q<1?
P.S. In ...
- 1,765
16
votes
7
answers
2k
views
Learning About Schubert Varieties
I am a combinatorist by training and I am interested in learning about the connections between combinatorics and Schubert varieties. The theory of Schubert varieties seems to be a difficult area to ...
- 163
47
votes
4
answers
10k
views
Why are planar graphs so exceptional?
As compared to classes of graphs embeddable in other surfaces.
Some ways in which they're exceptional:
Mac Lane's and Whitney's criteria are algebraic characterizations of planar graphs. (Well, ...
- 12.6k
5
votes
2
answers
408
views
How are graph automorphisms are affected by transformations?
I have a heavily symmetric regular graph whose automorphisms I know. I remove one subgraph and insert another one in a consistent manner; for example, this could be a Delta-Y transformation (...
- 275
11
votes
3
answers
2k
views
Matrices whose nullspace is nicely shaped
I'm looking for natural conditions on $a_{ij}$ to guarantee that the null space of the $n\times m$ matrix $A=(a_{ij})$ has a nice basis.
The null space of { {1,-2,1,0,0}, {0,1,-2,1,0}, {0,0,1,-2,1} } ...
- 9,756