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
8
votes
0answers
124 views

Being even or odd in the product expansion $\prod(1+x^k+x^{k+1})$

Consider the generating function of "partitions with distinct parts" $$\sum_nQ(n)x^n=\prod_k(1+x^k).$$ It's known that $$\left[\prod_k(1+x^k)\right] \mod 2=\prod_m(1-x^m)=\sum_{j\in\mathbb{Z}...
1
vote
1answer
127 views

What is the inverse Laplace transform of $\frac{(1/s)_{n}}{s} $?

Introduction So far, I have found (p. 5) the following generating functions of the unsigned Stirling numbers of the first kind: \begin{equation} \tag{1} \label{1} \sum_{l=1}^{n} |S_{1}(n,l)|z^{l} = (z)...
2
votes
0answers
69 views

Number of sets of distinct pairs which doesn't share difference

Inspired by This question by Vidyarthi I tried to find the value of $T(2m)$ where, $T(2m)$ is the number of sets of distinct pairings (so, the sets have $m$ elements) of the numbers $1,2,3....,2m$ ...
2
votes
0answers
76 views

Partitioning a set of consecutive nonnegative integers into distinct pairs

Let us have a set of $k$ consecutive natural numbers $2,3,\ldots, k+1$, $k$ even. In addition, we are given a set of $m=\frac{k}{2}$ 'differences' from one among the $k$ numbers $1,2,\ldots, k$. My ...
0
votes
1answer
38 views

Knapsack problem with value range constraint

The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$, and a bag with capacity $B$, we want to insert items ...
1
vote
0answers
117 views

Is this graph theory paper in German translated into English?

I recently read such a paper and want to understand the proof idea of ​​this article. However since it is in German and I have not studied German before, I'd like to ask whether this paper has an ...
-4
votes
0answers
31 views

How to sit n couples around a table with distinct seats [closed]

How many ways are there to sit $n$ couples ($2n$ people) in a round table, with numbered chairs, so that no couples sit together?
0
votes
0answers
51 views

Optimal numbering of a bipartite graph [closed]

We have a complete bipartite graph $K_{m,n}$. That is, the set of vertices is divided at one vertex $m$, in another $n$. Any two vertices from different parts are connected by an edge. There are no ...
4
votes
0answers
90 views

Positivity conjecture for Somos sequences

Let $\{s_n\}$ be the Somos-$4$ sequence, which is defined by $$s_{n+4}s_n=\alpha s_{n+3}s_{n+1}+\beta s_n^2.$$ It is known that $s_n$ is a Laurent polynomial: $s_n\in\mathbb{Z}[s_1^{\pm1}, \ldots, s_4^...
3
votes
1answer
168 views

Positioning ice-cream stands on a street

We want to position $n$ ice-cream stands on a street. Assume that the population on the street is modeled by a nonnegative integrable function $f$, and everyone goes to the nearest ice-cream stand. ...
25
votes
0answers
886 views

Can the fugitive escape?

A fugitive is surrounded by $N$ police officers, with the nearest one at distance $1$ away. The fugitive and the officers move alternatively. In a fugitive move, the fugitive can travel no more than ...
8
votes
2answers
201 views

Maximum of the weighted binomial sum $2^{-r}\sum_{i=0}^r\binom{m}{i}$

Let $m$ be a positive integer and let $f_m(r)=2^{-r}\sum_{i=0}^r\binom{m}{i}$. Clearly $f_m(0)=f_m(m)=1$ and $f_{2r+1}(r)=2^{2r}$. Conjecture: If $m>12$, then the maximum value of $f_m(r)$ for $r\...
7
votes
0answers
95 views

On the number of Reed–Muller codewords with no consecutive ones

$\DeclareMathOperator\RM{RM}\DeclareMathOperator\Eval{Eval}$Consider the polynomial ring $\mathbb{F}_2[x_1,x_2,\dotsc,x_m]$ and let $f\in \mathbb{F}_2[x_1,x_2,\dotsc,x_m]$. Let us now fix a Gray ...
0
votes
0answers
41 views

maximum radius for a $k$-set of vertices in a graph

this is a cross-post from mse here. Let $G$ be a connected graph and $S$ a subset of its vertices. Given a vertex $v$ of $G$ we define the $S$-eccentricity of $v$ as the largest distance between $v$ ...
1
vote
1answer
44 views

Expectation of the sum of the squares of the cardinal of an inverse function

I sample a random one-to-one function $\pi:\{0\,;\,1\}^n\to\{0\,;\,1\}^n$. I define $f$ as: $$\forall x\in\left[0\,;\,2^n-1\right]\cap\mathbb{N},f(x)=x\oplus\pi(x)$$ where $\oplus$ is the bitwise XOR. ...
1
vote
0answers
55 views

Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph

A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing's theorem states that every simple graph $G$ has a proper edge coloring using at ...
3
votes
1answer
103 views

A ratio of two probabilities

I am concerned about the monotonicity of the following ratio $ f(\eta)=\frac{\sum_{x=K}^{N}\left(\begin{array}{c} N\\ x \end{array}\right)\left(q_{G}\eta\right)^{x}\left(1-q_{G}\eta\right)^{N-x}}{\...
0
votes
0answers
216 views

Equality of the products involving (prime powers - 1)

Let $q_1,q_2,\dots,q_m$ be a collection of prime powers such that $q_i = p_i^{k_i}$. I have the following questions. When the products $\prod_{i=1}^m(q_i-1)^{r_i}$ and $\prod_{j=1}^m(q_j-1)^{s_j}$ (...
2
votes
1answer
118 views

Expectation of maximum of all period lengths of functions $f:\{1,\ldots,n\}\to\{1,\ldots,n\}$

This is based on an older question. For $n\in\mathbb{N}$, let $[n]:= \{1,\ldots,n\}$. Let $\text{Fun}(n)$ denote the set of all functions $f:[n]\to[n]$. To $f\in\text{Fun}(n)$ and ''starting value'' $...
1
vote
0answers
75 views

When are the 3-colorings of vertex subsets uncorrelated?

Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$. For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct ...
-1
votes
1answer
205 views

Given the index of two permutations, Is there a direct way to compute the index of their composition? [closed]

Suppose you are given two indexed permutations, (7 followed by 4, for instance) What is the best way to go about finding their composition, given the indices themselves? I'd imagine that the answer ...
9
votes
3answers
383 views

Pairs of vertices with high degree difference

Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us also fix an integer $k> n/2$. What are we able to say about the following quantity: $$\mathcal{I}_k(G) :=...
2
votes
1answer
231 views

Alternating sum of hook lengths: Part II

This is a follow up on my earlier MO post. Given $\lambda$ an integer partition of $n$, let $h_{ij}(\lambda)$ denote the hook length of cell $(i,j)$ in the Young diagram of $\lambda$. Let $$f_n=\sum_{\...
0
votes
0answers
46 views

Multiplication on a group of given cardinal and random permutations

Let $n$ be an integer, that we assume to be large (the order of magnitude for the motivation about the question is about 2^100). For the purpose of random automatic program certification, I need to be ...
6
votes
1answer
166 views

Constructing permutations avoiding a pattern

See here for some theory. It is fairly easy to explicitly generate all permutations of $n$ elements that have a pattern (just begin with the pattern and add the rest in all possible positions), but ...
5
votes
2answers
174 views

Expectation of period length of functions $f:\{1,\ldots,n\}\to \{1,\ldots,n\}$

For $n\in\mathbb{N}$, let $[n]:= \{1,\ldots,n\}$. Let $\text{Fun}(n)$ denote the set of all functions $f:[n]\to[n]$. To $f\in\text{Fun}(n)$ associate a sequence $\text{seq}(f))$ defined recursively by ...
7
votes
2answers
394 views

Chip-firing clocks

Let $G$ be some outdegree-regular directed graph with $n$ vertices and let $H$ be the Laplacian of $G$, so that the rows of $H$ correspond to chip-firing moves. I’m interested in linear functions $f$ ...
2
votes
1answer
152 views

Find a collection of values of polynomial

Given a polynomial $f(x)\in \mathbb C[x]$ where $\deg f(x)=n-1.$ Assume that we need to find a collection of values of this polynomial corresponding to the following set of $x$-values: $\{ e^{ik} \}$ ...
2
votes
0answers
48 views

Tail asymptotics of Durfee square identity

This post is related to the problem Asymptotics of a combinatorial series According to the Durfee square identity: $$\sum_{k \ge 0} \frac{q^{k^2}}{(q;q)_k^2} (q;q)_{\infty} = 1,$$ where $(q;q)_k$ is ...
-2
votes
0answers
190 views

$$\sum_{i=\lceil nx \rceil}^n\frac{\lceil nx \rceil (n-\lceil nx \rceil)! p^{i-\lceil nx \rceil} (1-p)^{n-i}}{i (i-\lceil nx \rceil)! (n-i)!}$$

I am planning to study a variant of the secretary problem and need the following auxiliary result. How to prove the following uniform convergence on [0,1]? Let $$ f_n(x):= \sum_{i=\lceil n x \rceil}^...
1
vote
0answers
33 views

Problem concerning cutting of 2n*2n square into 2 equal area connected figures using various cuts without self crossings

We have a square 2n*2n, where n belongs to N. The main problem is to find how many different equal area connected figures could be produced by cuttings without self-crossings. The orientability of the ...
11
votes
2answers
519 views

Alternating sum of hook lengths: Part I

Given $\lambda$ an integer partition of $n$, let $h_{ij}(\lambda)$ denote the hook length of cell $(i,j)$ in the Young diagram of $\lambda$. Is there a closed formula or a generating function for the ...
1
vote
0answers
36 views

Higher order Leibniz rule and ordered multiindex notation

Although I think this is probably known, I am making here a short exposition on the multiindex notations I am using to make this question self-contained. I note that there is at least two different ...
2
votes
1answer
109 views

Directed version of this lemma

On a paper by Shoham Letzter, available Here, there's a lemma that says as follows: Lemma 0: For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are ...
0
votes
1answer
60 views

Number of linear inequalities describing a polyhedron with prescribed number of vertices

If a polytope has $d$ vertices in $k$ dimensions how many linear inequalities is required to describe it?
7
votes
1answer
415 views

Packing equal-size disks in a unit disk

Inspired by the delicious buns and Siu Mai in bamboo steamers I saw tonight in a food show about Cantonese Dim Sum, here is a natural question. It probably has been well studied in the literature, but ...
0
votes
0answers
239 views

Is there a permutation $\tau\in S_n$ with $\tau(1)^{\tau(2)}+\cdots+\tau(n-1)^{\tau(n)}+\tau(n)^{\tau(1)}$ a square?

Let $n>1$ be an integer, and let $S_n$ be the symmetric group of all the permutatins of $\{1,\ldots,n\}$. I'm curious whether there is a permutation $\tau\in S_n$ such that $$\tau(1)^{\tau(2)}+\...
2
votes
1answer
56 views

Low-Hamming weight vectors in low-dimensional subspaces of $\mathbb{F}_p^n$

What is the maximum number vectors of Hamming weight at most $w$ in a $d$-dimensional subspace of $\mathbb{F}_p^n$, where $w,d,p$ are constant and $p$ is odd. (The Hamming weight is the number of ...
1
vote
0answers
122 views

Finding a tree with adjacency matrix near a given matrix

For defining a distance between trees, one can code them into $\mathbb{R}^n$ and use norms in $\mathbb{R}^n$ as distance. (For example we can use adjacency matrices as a tool for this coding) After ...
1
vote
1answer
82 views

Almost-parallel corners of the hypercube in high dimensions

Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are ...
3
votes
0answers
81 views

A connection between the Bell numbers and Bell polynomial

Let $B(n,x) = \sum_{k=0}^n {n\brace k}x^k$ be the Bell polynomials and $B_n = B(n,1)$ be the Bell numbers. I recently proved a nice relation between the two: $$ B(n,x)^{1/n}/x \ge B_{n/x}^{x/n}, $$ ...
3
votes
0answers
78 views

When is it possible to extend several linear orders defined “locally” into a single linear order defined “globally”?

This is a somewhat fuzzy question, so I will try my best to give a formulation which includes everything relevant while excluding everything else. I would like to find out if anyone else has studied ...
1
vote
1answer
54 views

“Circuit rank” but for vertices

A graph's circuit rank is the minimum number of edges that have to be removed for the graph to become a tree or forest. Is there a term that represents the minimum number of vertices that we must ...
2
votes
1answer
138 views

Expansion in hypergraphs

Is there a useful concept of expansion in hypergraphs, generalizing the concept for graphs (see: expander graphs)? Of course, expander graphs can be characterized in several qualitatively equivalent ...
2
votes
2answers
124 views

growth of the permanent of some band matrix

Consider such special band matrix of dimension $n$. It is a $0-1$ matrix, and only the first few diagonals are nonzero. Specifically, $$ H_{ij} = 1 $$ if and only if $|i-j| \leq 2$. How does the ...
7
votes
1answer
409 views

Hurwitz numbers and $t$-cores

For integers $k \geq 0$ and $d \geq 1$ let $H(k,d)$ be the Hurwitz number which, for the purposes of this posting, will be defined by: \begin{equation} H(k,d) \, := \ d! \, \sum_{\lambda \, \vdash d}...
2
votes
0answers
118 views

Square root of a function on a finite set

Let $S$ be a finite set and $f \colon S \to S$ be an arbitrary function. How can we find all functions $g \colon S \to S$ with $f = g \circ g$? If $f$ and $g$ are both required to be invertible, the ...
3
votes
0answers
97 views

Asymptotics of a combinatorial series

I am interested in the exact asymptotics of the following combinatorial series (which arises from the study of a Markov chain): $$F(q):=\sum_{k \ge 1} \frac{q^{k^2}}{(q;q)_k^2}\quad \mbox{as } q \to 1^...
2
votes
1answer
63 views

Min-sum and min-max node-disjoint path problems

Given an undirected weighted graph, we seek a pair of node-disjoint path between $2$ nodes $s$ and $t$: if the objective is to minimize the total path cost, the Suurballe algorithm can be applied; now ...
2
votes
2answers
235 views

sum of odious numbers to the power of k

In number theory, an odious number is a positive integer that has an odd number of $1$s in its binary expansion. The first odious numbers are: $1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, ...

1
2 3 4 5
168