Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
0
votes
0answers
17 views
Infinite sequence avoiding a countable set of words
As an application in group theory, I would need an infinite sequence over a finite alphabet, that avoids countably many words, each of length at least 10^8. I have found several results about avoiding ...
0
votes
0answers
65 views
Computing coefficients to power sums
Is it possible to find the (distinct) coefficients of monomials such as
$$(x_{1}^{3}+x_{2}^{3}+x_{3}^{3}+x_{4}^{3})^4\cdot(x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})\cdot(x_{1}+x_{2}+x_{3}+x_{4})^{2}$$
...
1
vote
0answers
37 views
Aperiodic graphs
The concepts of being non-periodic and aperiodic for tilings have obvious versions for connected graphs with a countable set of vertices and a finite number of edges meeting at each vertex. A graph ...
5
votes
0answers
77 views
Asymptotics of the multipartition function
Recall that the multipartition function $p_k(n)$ counts the number of $k$-tuples of partitions $\lambda^1,\ldots,\lambda^k$ of numbers $a_1,\ldots,a_k$ with $a_1+\cdots+a_k=n$. It has a generating ...
1
vote
0answers
27 views
Constructing pointwise-or independent binary matrices
Let $M$ be an $m \times n$ matrix such that every $M_{ij} \in \{0,1\}$.
We say that $M$ is `$\lor$-irreducible' if (i) no row is a pointwise-or of other rows, and (ii) no column is a pointwise-or of ...
1
vote
0answers
103 views
Experimentation with partial Euler products
Richard Mathar $[1]\& [2]$ shows that
\begin{align}
&\zeta_{2}(s)\equiv\prod_{\Omega(n)=2}^{}\left(\dfrac{1}{1 - n^{s}}\right)^{-1}=\exp \left(\sum _{k=1}^n \frac{P(k s)^2+P(2 k s)}{2 ...
0
votes
0answers
87 views
Combinatorial support set in CRT
Is there a function $g(s)$ such that if there is a set of numbers $\{r_i\}_{i=1}^m$ such that $r_i\bmod p_j\in\{0,1\}$ at every prime in $\{p_j\}_{j=1}^n$ such that $2^t\bmod p_j\neq1$ at every ...
8
votes
0answers
108 views
Maximizing the number of semistandard Young tableaux
Is anything known about the following question? Given a positive
integer $p$ and a real number $0<\alpha<1$, what partition $\lambda$
whose parts sum to $\alpha p^2$ (asymptotically) and whose ...
3
votes
1answer
252 views
Balancing real numbers in one dimension
Given numbers $0 \leq d_i \leq 1$ for $i=1,\ldots,m$, it is easy to see that you can always find signs $\varepsilon_i \in \{-1,1\}$ such that the partial sums $\sum_{i=1}^k \varepsilon_i d_i/2$, for ...
4
votes
0answers
89 views
Staircase Schur functions squared
Let $\Delta_n$ be the staircase-shaped partition $(n-1,n-2,\dots,1)$. Are there any non-obvious combinatorial objects that index $s_{\Delta_n}^2$? Here, $s_\lambda$ is the Schur function indexed by ...
2
votes
1answer
78 views
Relationship of clique, independence, and chromatic numbers
For any graph $G=(V,E)$ let $\bar{G}$ be the complement graph. Is $$\text{inf}\big\{\frac{\omega(G)+\omega(\bar{G})}{\chi(G)} : G \text{ is a finite graph}\big\}$$ known? If not, what lower bounds are ...
1
vote
0answers
40 views
Select n vectors from k vectors (in 3D) such that each component of the resultant vector >= each component of a given vector M
this was left unanswered for 1 week on MStackExchange, so I thought MOverflow would be more appropriate. Thanks :)
Let $R = (R_x, R_y, R_z)$ be the resultant vector of the n vectors and $M = (M_x, ...
5
votes
3answers
230 views
A balls and urns model for a hashing problem
Fix $N \in \mathbb{N}$. Suppose we throw $N$ numbered balls into $N$ numbered urns, so that for each $b \in \{1,\ldots,N\}$, ball $b$ lands in urn $j$ with equal probability $1/N$. Choose a number $c ...
4
votes
1answer
182 views
Decomposing $(\mathbb C^n)^{\otimes m}$ as a representation of $S_n\times S_m$
$V=\mathbb C^n$ is a $\mathbb CS_n$-module, where $S_n$ is the symmetric group of degree $n$, via the representation sending a permutation to the corresponding permutation matrix. The tensor power ...
0
votes
0answers
36 views
Property of summations [on hold]
Suppose to have the following identity:
$$
\sum_{i=i_0}^{i_1}\sum_{j=j_0}^{j_1} f(i,j) = \sum_{i=i_0}^{i_1}\sum_{j=j_0}^{j_1} f(i,j)g(i,j),
$$
for 'good' indexes $i,j$ and some functions $f,g$.
What ...
-1
votes
0answers
41 views
Combinatorics: Identical objects and distinct groups [on hold]
I'm confused between the following 2 formulae:
1) Number of ways to put n identical objects into r distinct boxes, such that the ordering is NOT important is:
(n+ r - 1) C r
2) Number of ways to ...
5
votes
0answers
99 views
How do you categorify the cycle index series?
Let $F$ be a combinatorial species. The exponential generating series of $F$ is defined to be
$$ \sum_{n \geq 0} \frac{ \lvert F_n \lvert x^n}{n!} $$
It was observed by Baez and Dolan in their paper ...
-2
votes
1answer
93 views
Combinatorical meaning of such expression [closed]
Any combinatorical meaning or interpretation of
$$1^{\alpha_1}2^{\alpha_2}3^{\alpha_3}...s^{\alpha_s}\alpha_1!\alpha_2!...\alpha_s!$$
for partition ...
6
votes
1answer
257 views
Flooding a cycle digraph via chip-firing: $n^{k-1} + n^{k-2} + \cdots + 1$ bound (a Norway 1998-99 problem generalized)
Let $k > 1$ and $n$ be positive integers. Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Let $D$ be a digraph which has exactly $k$ vertices $v_0$, $v_1$, ..., $v_{k-1}$ and exactly $k$ arcs $v_0 ...
1
vote
1answer
57 views
Hadwiger-Nelson problem in higher dimensions
Given a positive integer $n\in \mathbb{N}$ we define the Hadwiger-Nelson graph $\text{HN}_n$ by
$V(\text{HN}_n) = \mathbb{R}^n$;
$E(\text{HN}_n) = \{\{v_1, v_2\}: v_1, v_2 \in \mathbb{R}^n \text{ ...
5
votes
0answers
97 views
Intersections of the B-orbits and the orbits of some other Borel subgroups in the flag variety G/B
This is a follow-up of this previous question below:
Intersections of $B$ and $B^-$ orbits in the flag variety $G/B$
Let $G = SL_n(\mathbb{C})$, $B$ be the standard Borel subgroup, and consider some ...
2
votes
1answer
116 views
Existence of Steiner system designs given $n,k,t$
I am familiar with the recent Keevash paper here which proves that given some $t,n,k,\lambda$ then provided standard divisibility conditions hold, and $n$ is suitably large, there exists a ...
5
votes
2answers
254 views
Combinatorial designs textbook recommendation
Good evening, I am currently taking a class which has combinatorial designs as the first topic, we are using Peter Cameron's book Designs, Graphs, Codes and their Links which I am finding extremely ...
2
votes
0answers
76 views
Adding a row to a Young Tableau via Novelli-Pak-Stoyanovskii
Let $T_{\lambda}$ be the set of standard young tableaux (SYT) of shape $\lambda_1\geq \lambda_2\cdots\geq \lambda_n$. Now consider pushing a row $\mu$ with $\mu\geq \lambda_1$ onto $Y$ to give shape ...
7
votes
1answer
336 views
Quest for a human proof of a $q-$binomial identity
Let $$f(n,k) = \sum\limits_{j = - k}^k {{{( - 1)}^{k - j}}}
\binom{n-j}{k-j}\binom{n+j}{k+j}.$$
Then $f(n,k)=\binom{n}{k}$
because it satisfies $f(n,k)=f(n-1,k)+f(n-1,k-1)$ and the obvious ...
6
votes
1answer
193 views
A variant to the Hadwiger-Nelson problem
Consider the following graph $G=(V,E)$ where $V=\mathbb{R}^2$ and $E = \{\{x,y\}: x,y \in \mathbb{R}^2 \text{ and } |x-y|\in \mathbb{Q}\}$.
What is $\chi(G)$?
(This is a variant of the ...
2
votes
1answer
82 views
Minimal family of k-sets containing all t-sets
Let $n \ge k \ge t \in \mathbb{N}$, and consider a universe $U$ of size $n$. Let $\mathcal{F}$ be a family of $k$-subsets of $U$, such that every $t$-subset of $U$ is contained in at least one member ...
4
votes
1answer
194 views
The number of monotone full binary trees
Let $\rho$ be an equivalence relation on a semigroup $S$. A subsemigroup $S'$ of $S$ is called a $\rho$-cross-section of $S$, provided that $S'$ contains exactly one representative from each ...
8
votes
3answers
269 views
Distinguishing combinatorial maps by their linearizations
Every (not-necessarily invertible) map $f$ from $[n]:=\{1,2,,,,.n\}$ to itself determines a linear map $L_f$ from ${\bf R}^n$ to itself that sends the basis vector $e_k$ to $e_{f(k)}$ for $1 \leq k ...
2
votes
0answers
120 views
Ticket lottery — distributing $n$ tickets among $N$ people fairly
Suppose that I have $n$ tickets for an event that I want to distribute fairly among $N > n$ people. In this simple case, a lottery suffices. But suppose certain groups of people want to attend ...
9
votes
3answers
364 views
Is a distributive lattice planar iff it admits no B3 sublattice?
A finite lattice is planar if it admits a Hasse diagram which is a planar graph (we want the Hasse diagram to be represented in the plane so that the $y$-coordinate of each element respects the ...
3
votes
0answers
69 views
Efficiently computing (plethysm-like?)substitutions of symmetric functions
This is a rather technical question, it arose in connection of some calculations that I need to have better grasp of the question Formal group law over $\mathbb{F}_p$ and my own older one What is ...
2
votes
1answer
80 views
Stirling numbers of the second kind with maximum part size
The stirling number of the second kind $S(n,k)$ counts the number of partitions of the set $[n]$ into $k$ non-empty parts. I found a definition for the numbers called the $r$-associated stirling ...
5
votes
2answers
148 views
Number of Dyck paths with prescribed number of edges
I am trying to find a formula for the trace of certain matrix. To do that I was forced to determine the number of Dyck paths with prescribed number of edges.
By a Dyck path I mean a lattice path from ...
4
votes
1answer
92 views
Countable hypo-hamiltonian graph
If $G = (V,E)$ is a graph, then a $\omega$-path is an injective map $p:\omega\to V$ such that $\{p(k),p(k+1)\}\in E$ for all $k\in \omega$. In a similar fashion, we define a $\mathbb{Z}$-path.
Is ...
4
votes
1answer
196 views
Counting couples of square-free polynomials over finite fields
I have a curve defined by the following equations over the finite field $\mathbb{F}_q$ with $q=p^r$ with $p \geq 3$:
$$C_{h_1,h_2}:\begin{cases} y_1^2=h_1(t) & \\
y_2^2=h_2(t) ...
3
votes
2answers
192 views
Picking codewords that are close
I posted this question in http://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close a week back.
Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and ...
2
votes
0answers
68 views
Exact growth rate of Longest Increasing Subsequence expectation
Let $S_n$ be the symmetric group, $\pi\in S_n$ a uniformly random permutation and $L_n:=L_n(\pi)$ denoting the length of the longest increasing subsequence (LIS). We know that ...
3
votes
1answer
215 views
How many hamiltonian paths can be removed from a complete directed graph before it becomes disconnected?
The question started from a problem brought home by a friend's 5th grader: "How many ways you can arrange 5 people sitting around a round table so that the people sitting to the left of any person are ...
0
votes
1answer
50 views
Counting the orderings of outward-directed trees where the degree of each vertex is $2$
Let $T$ be a connected directed tree with the following properties:
The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it).
$T$ has a ...
3
votes
3answers
80 views
Block error-correcting codes over inhomogeneous alphabets
For $n := (n_1,\dots,n_N) \in \mathbb{N}_{>1}^N$, let $X_n := \prod_{j=1}^N [n_j]$, where as usual $[m] := \{1,\dots,m\}$.
Are there any known generic constructions for (Hamming) sphere ...
5
votes
1answer
153 views
English translation of Witt's paper on the Mathieu groups?
Does anyone know of an English (or French) translation of Witt's paper Die 5-fach transitiven Gruppen von Mathieu ? (It's the one in which the Witt design is introduced. Well, I guess.)
Here's an ...
2
votes
1answer
93 views
Network flows with shared capacities
Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:
$$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$
where $f(1, 2)$ denotes the flow through arc $(1, ...
1
vote
0answers
116 views
Counting number of ways to place bags and marbles inside bags so all bags contain an odd number of marbles
There was a famous trick question posed once in math.stackexchange here. The question can be loosely translated to "Is it possible to place nine marbles into four bags so that each bag has an odd ...
6
votes
1answer
189 views
A combinatorial identity generalizing identity (3.111) from Gould's book
I am trying to prove the following identity, which I am sure is correct:
$$
\sum_{m=0}^{K}(-1)^m{n \choose m}{(n-m)r-1 \choose n-1}=1,
$$
where $K:=\left[n\frac{r-1}{r}\right]$ for some integer $r$, ...
3
votes
1answer
255 views
Number of semi-standard tableau
What is the number of semi-standard tableau (weakly increasing on rows and strictly increasing on columns) for the partition $2n=n+n$ with entries $\{1,2, \cdots ,n\}$ such that each $i$ appears ...
0
votes
1answer
98 views
Number of squares in a grid under certain conditions
Consider an $(n+1)\times (n+1)$ grid of lattice points in the plane.
$A(n):$ # of squares with vertices on the grid.
It's relatively well-known that $A(n)=\frac{n(n+1)^2(n+2)}{12}$. Now, $A(n) = ...
3
votes
3answers
344 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?
1
vote
0answers
80 views
Occupancy problem with limited capacity and two types of balls [closed]
I am considering the following problem that I suspect to be standard.
One has a set of $N$ balls composed of a fraction $\alpha$ of red balls and $(1-\alpha)$ of black balls (we assume $\alpha N$ is ...
3
votes
0answers
206 views
Solving a doubly exponential generating function
I am analyzing the average time complexity of some algorithm on some probabilistic model, and I've come to a doubly exponential sequence for which I cannot find corresponding generating function. I ...
