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.
10,563
questions
7
votes
1
answer
911
views
Best possible sieves for the jacobsthal problem, linear programming, and the prime 2
Background/Motivation
Gerhard Paseman asked a question about bounds on the Jacobsthal function a while ago, which made me curious about whether the known bounds are best possible. Briefly, the ...
- 8,543
6
votes
4
answers
1k
views
What are the odds two permutations in S_n do NOT generate the whole group?
What are the odds two uniformly chosen elements of S_n span the whole group (or just the alternating group)? Mathematica experements suggest those odds approach 1 - this might have been proven a long ...
- 22.6k
6
votes
5
answers
1k
views
Combinatorial equation
Can any one help me in proving the following equality:
$$n^n= \sum_{i=1}^n {n \choose i}\cdot i^{i-1}\cdot (n-i)^{n-i}$$
I tried some different ideas but none of them worked!
- 271
6
votes
5
answers
2k
views
Convert integer to permutation number
I have no idea how to achieve this, any help would be greatly appreciated and very useful to me.
I have a loop in some computer code, that loops through every single combination of 7 on bits in a 64 ...
- 71
6
votes
2
answers
9k
views
Count of full, binary trees with fixed number of leaves
How many ways is there to build an arithmetic expression with fixed number of terms and fixed order? Let’s assume we have only one distinct operation that is neither commutative nor associative. The ...
- 71
6
votes
3
answers
850
views
Series involving power of the index
How to prove the following identity
$$ \sum_{n=1}^{\infty} \frac{n^{n-1} e^{-n}}{n!} = 1$$
analytically (which can be confirmed with $Mathematica$)? The standard trick for geometrical series does not ...
- 77
6
votes
2
answers
1k
views
Products and sum of cubes in Fibonacci
Consider the familiar sequence of Fibonacci numbers: $F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$.
Although it is rather easy to furnish an algebraic verification of the below identity, I wish to see a ...
- 41.8k
6
votes
4
answers
1k
views
fourier analytic proofs
While searching through Mathoverflow, I found out a fourier analytic proof of the Isoperimetric Inequality.Also, by google search I found a fourier analytic proof of Quadratic Reciprocity theorem.I ...
6
votes
3
answers
640
views
Real orthogonal and sign [closed]
I came across the following conjecture, reading a recent paper in the Monthly, an orthogonal matrix of order $n\neq 0 \pmod 4$ has a nonnegative (up to a scalar) row vector.
It should be straight in ...
- 640
6
votes
3
answers
1k
views
Does -I belong to Weyl group?
Let $\Phi$ be an irreducible root system, with positive roots $\Phi^+$ relative to the base $\Delta$.
If $W$ is the Weyl group, how can I determine if $-I$ belongs to $W$? Equivalently how can I see ...
- 63
6
votes
4
answers
426
views
The dimension of the Grassmannian cohomology ring $H^*(\mathrm{Gr}_{n,d})$ and the fundamental $\frak{sl}_n$-representation $V_{\pi_d}$
The vector space dimension of the cohomology group of the $2$-plane Grassmannian $\mathrm{Gr}_{2,n}$ is given by the number of tuples $(\lambda_1,\lambda_2)$ satisfying
$$
n - 2 \geq \lambda_1 \geq \...
6
votes
6
answers
1k
views
Least number of vertices in a graph with which one can uniquely recover some partition of N
Given a partition of an integer $N$, its $P$-graph is the graph whose vertices are its parts, two of which are joined by an edge if and only if they have a common divisor greater than one (i.e. they ...
- 3,677
6
votes
3
answers
1k
views
Looking for cubic, bipartite graphs with girth at least six and no cycles of length 8.
Aside from the Desargues graph, are there nice (at least vertex-transitive), small (say, less than 60 vertices), cubic, bipartite graphs with girth at least 6 and no 8-cycles? (or, even better, no ...
6
votes
4
answers
1k
views
Number of integer combinations $x_1 < \cdots < x_n$?
I asked this question earlier on math.stackexchange.com but didn't get an answer:
Let $0 < a_1 < \cdots < a_n$ be integers. Is there a closed formula (or some other result) for the number $N(...
- 16.1k
6
votes
4
answers
1k
views
Approximating $e$ with 2s and 3s
How can I generate a series of 2s and 3s such that the average of the generated values (so far) is as close to $e$ as possible?
For example:
...
- 161
6
votes
2
answers
4k
views
Derangements with repetition
Hi all,
given (a1,...,an) formed by distinct letters, it's a well known problem to count the number of permutations with no fixed element.
I've been trying to solve a generalization of this problem, ...
- 1,638
6
votes
6
answers
3k
views
Let $G$ be a graph such that for all $u, v ∈ V (G)$, $u \ne v$, $|N (u) ∩ N (v )|$ is odd. Then show that the number of vertices in $G$ is odd
After working for sometime I figured out the following course of action. (from a few sample cases on 4 and 5 vertices)
i) I wanted to prove that the graph had no odd degree vertex.
ii) There exists ...
- 61
6
votes
3
answers
1k
views
Graphs from the point of view of Riemann surfaces
I was listening to the lecture "Graphs from the point of view of
Riemann surfaces" by Prof. Alexander Mednykh. I am looking for references for the basics of this topic. Any kind of ...
6
votes
3
answers
732
views
A question about symmetric matrix
Let $A= (a_{ij})_{ij}, 1 \leq i, j \leq n$ be a symmetric $n \times n$ matrix. Suppose
(1) $a_{ij} \geq 0$ are real numbers;
(2) The sum of each row $\sum_{j=1}^{n} a_{ij} = 1$ for $1 \leq i \leq n$...
- 3,362
6
votes
2
answers
224
views
Realizing a monoid as $\mathrm{End}(G)$ for some graph $G$
This question relates to Realizing groups as automorphism groups of graphs.
Given a monoid $M$, is there a graph $G$ such that the endomorphism monoid $\textrm{End}(G)$ is isomorphic to $M$?
- 45.5k
6
votes
2
answers
507
views
Can I finitely color Z^2 such that (x,a) and (a,y) are different for every x,y,a?
I ran into this obstacle in a harmonic analysis problem; I know epsilon about coloring problems.
Is it possible to finitely color Z^2 so that the points (x,a) and (a,y) are differently colored for ...
6
votes
2
answers
725
views
Prove positivity of a binomial sum
Some problems appear easy on the face of it, but perhaps they are not. Here is an instance of a certain calculation which is slightly reformulated from its original encounter in a current work. I have ...
- 41.8k
6
votes
3
answers
1k
views
Is there an entropy proof for bounding a weighted sum of binomial coefficients?
Given a probability $p \in (0,1)$ and parameter $\alpha \in (0,1)$, is there an entropy-based proof which yields a good upper bound for the sum
$$\sum_{\ell = 0}^{\alpha n} \binom{n}{\ell}p^\ell(1-p)^{...
- 455
6
votes
4
answers
601
views
Request for an exact formula related to a partition in number theory
The Frobenius equation is the Diophantine equation $$
a_1 x_1+\dots+a_n x_n=b,$$
where the $a_j$ are positive integers, $b$ is an integer, and a solution $$(x_1, \dots, x_n)$$
must consist of non-...
- 10.3k
6
votes
3
answers
1k
views
Does a planar triangulation always contain a Hamiltonian path?
What about a Hamiltonian path in a triangulation of an n-gon? If not, how long is the longest path?
- 337
6
votes
5
answers
1k
views
Table of planar connected graphs
For the other day I need to use the table of planar connected graph with few vertex. In the wolfram's mathworld , they listed only the graph with $4$ vertex.
Does anyone knows webpages or pdf on the ...
- 161
6
votes
5
answers
534
views
Bounds for $a(n)=a(n-1)+a(\lfloor n/2 \rfloor)$
This is related to problem in graph theory.
OEIS defines A033485 as
$a(1)=1$ and $a(n)=a(n-1)+a(\lfloor n/2 \rfloor)$.
Q1 what are upper bounds and asymptotics for $a(n)$, can we get $\exp(o(n))$?
...
- 24.2k
6
votes
2
answers
855
views
Create a graph with a specified number of spanning trees
I read that one of the current challenging problems in mathematics is constructing a minimal graph with a specified number of spanning trees (say, $k$).
However, is there a quick way to create some ...
- 171
6
votes
4
answers
2k
views
edges minus vertices
Is there a more interesting name for this graph invariant: edges minus vertices? It seems to have been called 'complexity' in
Remco van der Hofstad, Joel Spencer, Counting Connected Graphs ...
6
votes
2
answers
1k
views
Permutations with restriction
We have $n$ types of objects, the number of objects of type $i$ being $a_i$, $1\leq i\leq n$.
What is the number of permutations of the
$\sum_{i=1}^n a_i$ objects, if no two objects of the same type ...
- 143
6
votes
1
answer
718
views
Bridge game with only one suit: strategy
This game looks like bridge, but 1- there are only two players Alice and Bob, 2- there is only one suit, whose cards are numbered $1, 2,\ldots,2n$. One deals each player $n$ cards. Therefore Alice ...
- 51.6k
6
votes
3
answers
2k
views
Unidentified Combinatorial Problem
Given a (finite, simple, undirected) graph $\mathcal{G} = (V, E)$, an edge binning associates each $e_{ij} \in E$ with one or the other of its vertices $v_i, v_j \in V$. Let $c_i$ be the number of ...
- 175
6
votes
4
answers
446
views
Counting card distributions when cards are duplicated
If we have a deck of $48$ different cards and $4$ players each get $12$ cards, it is well known how to calculate the number of possible distributions: $\frac{48!}{12!12!12!12!}$
In a german card came (...
6
votes
3
answers
432
views
is this a familiar gen. fn. for partitions?
The $2$-adic valuation of $n\in\mathbb{N}$, denoted $\nu(n)$, is the largest power $t$ such that $2^t$ divides $n$. The number of integer partitions of $n$, denoted by $p(n)$, has generating function
...
- 41.8k
6
votes
2
answers
2k
views
Example of Möbius inversion on integer partition poset
We know that integer partitions form a poset (actually we can define more than one partial orders on it), and so we can have some kind of Möbius function on it and consequently Möbius Inversion ...
- 211
6
votes
3
answers
430
views
Prime numbers and strings of symbols
Suppose you have N symbols (e.g. "1","2",...,"N" or "a","b",...,"$") and a string of these symbols (say, the first trillion digits of pi). Then does there exist a prime number whose N-ary ...
- 205
6
votes
2
answers
606
views
Threshold function for a graph not being planar
A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property.
It is well-known that every ...
- 505
6
votes
2
answers
531
views
2-adic valuation of a certain binomial sum
Consider the sequence (of rational numbers) given by
$$a_n=\sum_{k=1}^n\binom{n}k\frac{k}{n+k}.$$
Let $s(n)$ be the sum of binary digits of $n$, i.e. the total number of $1$'s.
QUESTION. Is it true ...
- 41.8k
6
votes
4
answers
2k
views
Sum over integer compositions
Sorry if the question is trivial - are there closed form expressions or good approximations for the sum of a symmetric function taken over all integer compositions (into given number of parts) of a ...
- 721
6
votes
5
answers
3k
views
How many "different" colorings (excluding exchanges) exist for a given map (graph)?
In particular I'm interested in regular maps, excluding all maps that can be colored with 2 or 3 colors.
For what I need to analyze, maps have to be regarded as differently colored, if the same ...
- 351
6
votes
2
answers
994
views
Inverse Length 3 Arithmetic Progression Problem for sets with positive upper density
It is a famous theorem of Roth, which Szemerédi famously generalized, that if a set of natural numbers has positive upper density then it contains arithmetic progressions of length $k$. The famous ...
- 25.5k
6
votes
2
answers
709
views
Recreation with Catalan
Consider the well-known sequence $C_k=\frac1{k+1}\binom{2k}k$ of Catalan numbers. I came across the below identity while working with certain generating functions. I thought it might be of interest to ...
- 41.8k
6
votes
2
answers
782
views
Conjecture about partitions of the powerset without the empty set
I would like to have some ideas about possibilities of proving or disproving the following conjecture:
For any partition $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_m} \}$ of the powerset without ...
- 690
6
votes
5
answers
894
views
Combinatorial proof of Catalan's identity
Consider the problem of tiling a board of length $n$ with squares of size $1×1$ and dominoes of size $1×2$, Let's denote $f_n$ to be the number of ways to tile this so-called ($n$)-board.Then $f_n=F_{...
user153001
6
votes
3
answers
529
views
Waring problem for binomial coefficients (generalization of Gauss' Eureka Theorem)
Is there a number k such that every natural number can be written as $\sum_{i=1}^k \binom{a_i}{3}$ for some natural numbers $a_i$'s?
- 337
6
votes
2
answers
7k
views
How many perfect matchings in a regular bipartite graph?
We have a $d$-regular bipartite graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$.
What is an upper bound on the number of perfect matchings of $G$?
- 61
6
votes
4
answers
539
views
(Non)uniqueness of the common-factor graph
Let $S=\{x_1,\ldots,x_k\}$ be a set of $k$ distinct natural numbers,
a subset of $\{1,\ldots,n\} = \mathbb{N}_{\le n}$.
Define the common-factor graph $G(S)$ as the (undirected) graph with
a node for ...
- 149k
6
votes
1
answer
495
views
How many triangulations of a regular octahedron are there, without introducing new vertices?
It is easy to find three triangulations, each consisting of four tetrahedra. Are there more?
- 61
6
votes
1
answer
300
views
Are the Fourier coefficients of $\eta(q^m)^m / \eta(q)$ non-negative?
In this paper, the following result is proved.
For any prime $p$, all the Fourier coefficients of
$$\eta(q^p)^p / \eta(q) = q^{\frac{p^2-1}{12}} \prod_{n=1}^\infty (1 - q^{pn})^p (1 - q^{n})^{-1}$$
...
- 427
6
votes
2
answers
365
views
Provoking involutions further
Let $\mathfrak{S}_n$ denote the permutation group, and $I_0(n)=\sum_{j\geq0}\binom{n}{2j}\frac{(2j)!}{2^jj!}$ stand for involutions see A000085 for more interpretations. There is also these numbers $...
- 41.8k