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

learn more… | top users | synonyms (1)

0
votes
0answers
18 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
23 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 ...
-1
votes
0answers
16 views

Hypergraphs that can be represented by simply closed curves respecting edge intersection

Good evening. Hypergraphs can be drawn by representing each vertex as a point in the plane and each hyperedge as a closed curve that contains the points corresponding to the vertices that belong to ...
5
votes
0answers
75 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
85 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
79 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 ...