## New answers tagged co.combinatorics

1

$\newcommand{\N}{\mathbb N}\newcommand{\Si}{\Sigma}$For integers $n$ and $k$, let $A_{n,k}$ denote the set of all $a=(a_1,\dots,a_k)\in\N^k$ such that $\sum_1^k a_j\le n$, and let $c_{n,k}$ denote the cardinality of the set $A_{n,k}$.
For $a\in A_{n,k}$, let $s_p:=s_p(a):=\sum_1^p a_j$.
We want to simplify the sum
\begin{equation*}
\Si:=\sum_{a\in A_{i+1,...

2

Yes. We can solve for $X$ quite easily since
$B_{0}=P_{0}^{X}A_{0}P_{0}^{-X}$ precisely when $X$ satisfies a system of linear congruence equations.
Suppose that the permutation corresponding to $P_{0}$ can be written as a product of $r$ disjoint cycles of lengths $n_{1},\dots,n_{r}$. Without loss of generality, we may therefore assume that $P_{0}$ is a block ...

5

The random variable $R$ here takes values in the power set ${\mathcal P}(X)$ of $X$, not in $X$: it's a random set in $X$, not a random point. For the purposes of this argument, the only important features of $R$ are that the events $(x \in R)$ for each $x \in X$ are independent events of probability $p$. But if you really wanted to formally model this ...

0

Counting the number of even and odd sized subsets of a set $A$ of size $n$:
$P(A)$ has a structure of vector space over $\mathbb F_2$ with the symmetric difference. Equivalently, one just takes the characteristic vectors in $\mathbb F_2^n$ with the usual addition.
The even sized subsets form a subspace $W$.
The odd sized is then the “affine” subspace $W+{...

2

The definition of $a_1$ given in OEIS is based on a bijection between integer partitions and natural numbers. A partition $\lambda_1\geq\lambda_2\geq\dots\geq\lambda_m>0$ with exactly $m$ parts corresponds to the number
$$2^{\lambda_1+m-2}+2^{\lambda_2+m-1}+\dots+2^{\lambda_m-1}.$$
The definition of $a_1$ can then be written as
\begin{equation}\label{a1d}(...

4

Late edit: having now read through the OP comments, I can see that my proof is essentially a carbon copy of @darij.grinberg's approach (although my derivation was independent). I'm okay to delete this answer once/if darij chooses to post theirs.
Pick a canonical ordering of unlabelled rooted trees, say, with lexicographical comparison of tuples $(n, T_1, \...

2

We can rewrite $$\sum_{i=0}^{|Q|} c_i x^ i = \prod_{q_i \in Q} (1+q_ix)$$ as $$c_i = \sum_{\substack{S \subseteq Q \\ |S| = i}} \prod_{q \in S} q$$
Then $$\sum_{a \in A} (1 - a) \langle C(A_{\neg a}), N(m) \rangle$$ can be split into two sums: $$\left(\sum_{a \in A} \langle C(A_{\neg a}), N(m) \rangle \right) - \left(\sum_{a \in A} a \langle C(A_{\neg a}), N(...

0

Let $(P,\le_P)$ and $(Q,\le_Q)$ be posets, although usually we will just refer to "$P$" and "$Q$". One can define a partial ordering $\le$ on the direct product $P\times Q$ as follows: $(p,q)\le(p',q')$ if $p\le_P p'$ and $q\le_Q q'$.
A function $f$ from $P$ to $Q$ is order-preserving if for all $p,p'\in P$, $p\le_P p'$ implies $f(p)\le_Q ...

7

This is a comment, not an answer, but it will be more convenient to post it as an answer. Consider the vertices of $G_n$ as subsets of $[n]=\{1,\dots,n\}$.
Observation 1. $\chi(G_n)\ge\left\lfloor\frac{3n}2\right\rfloor+1$.
This is because $G_n$ contains a clique of that size, namely,
$\varnothing,\{1\},\{2\},\{1,2\},\{1,2,3\},\{1,2,4\},\{1,2,3,4,\},\{1,2,3,...

4

It turns out that this is indeed true. The relevant proofs are given in Chapter 3 of this extended abstract.

1

The conditions you pose on $P_0$ imply that it is a reflexive polytope. (That is, a lattice polytope with the origin in its interior and such that its polar dual is also a lattice polytope).
There are finitely many reflexive polytopes in each dimension (modulo $GL(\mathbb Z,n)$), which implies that the answer to your question is negative.
For example, in ...

3

Hjalmar Rosengren gave a nice formula for $f_{m,n}(x)$ based on the theory of hypergeometric series. Here I provide a direct elementary proof of the same based on generating series.
Let us introduce the differential operator
$$D_r:=\frac{1}{r!}\frac{\partial^r}{\partial x^r}.$$
Then
$$\sum_{k=0}^\infty\binom{n+k}{k}x^k=D^n\left(\frac{1}{1-x}\right)=\frac{1}{(...

9

As pointed out by others, it is not clear what the contents of this lecture are.
However, after a quick internet search I did find some older (2018) lecture notes with the same title written by the same professor:
http://math.nsc.ru/conference/g2/g2r2/files/pdf/Lecture-8.pdf
At the start of these notes, five papers are mentioned. Based on the topic, the ...

4

Your nice observation is fairly easily explained: as you say $\chi_\lambda(n) = 0$ unless $\lambda$ is a hook partition of the form $(n-r,1^r)$ for some $r$. In this case, by the Murnaghan–Nakayama rule, we have $\chi_{(n-r,1^r)}(n) = (-1)^r$. Since there are $\binom{n-1}{r}$ standard Young tableaux of shape $(n-r,1^r)$, we have $\chi_{(n-r,1^r)}(1^n) = \...

3

With proofs abound, I would like to record yet another instance of application due to the Wilf-Zeilberger techniques. The aim is to prove the identity shown above (from GH from MO, Hjalmar Rosengren):
$$\sum_r\binom{m+n+k-r}{k-r}\binom{m}r\binom{n}r\binom{m+k}k^{-1}\binom{n+k}k^{-1}=1.$$
The mechanical process begins with letting (suppressing other variables)...

5

The book Graphs on Surfaces and Their Applications by Sergei K. Lando and Alexander K. Zvonkin
From Amazon page:
Graphs drawn on two-dimensional surfaces have always attracted researchers by their beauty and by the variety of difficult questions to which they give rise. The theory of such embedded graphs, which long seemed rather isolated, has witnessed the ...

6

This is Gauss' hypergeometric function
$F(n+1,m+1,1;x)$. You can then apply the huge theory of hypergeometric functions to derive further expressions. For instance, Euler's transformation formula gives the alternative expression
$$\frac 1{(1-x)^{m+n+1}}\,F(-m,-n,1;x)=\frac 1{(1-x)^{m+n+1}}\sum_{k=0}^{\min(m,n)}\binom mk\binom nk x^k$$
for the same series as ...

2

Let me elaborate on the use of Pólya enumeration for this problem.
Let $G\simeq S_m \times S_n$ act on $X=\{x_{i,j}\colon 1\leq i \leq m, 1\leq j \leq n\}$ via $(\sigma,\pi)\cdot x_{i,j} = x_{\sigma(i),\pi(j)}$, and via this action view $G\subseteq S_{mn}$. For $g\in G$ let $c_i(g)$ be the number of $i$-cycles of $g$ (in this embedding into $S_{mn}$), and ...

8

I believe one of the first paper was:
Bacher, Roland; de la Harpe, Pierre; Nagnibeda, Tatiana
The lattice of integral flows and the lattice of integral cuts on a finite graph,
Bull. Soc. Math. Fr. 125, No. 2, 167-198 (1997). Zbl 0891.05062
(Sorry, self-promotion).
It has been widely cited by subsequent papers on the subject
(use MathSciNet or Zentralblatt)
I ...

2

John Stembridge recently pointed me towards his very nice paper Quasi-Minuscule Quotients and Reduced Words for Reflections, which gives a lot of insight into the root poset.
Here is what I understand from his paper.
Let $t$ be a reflection and let $\beta$ be the corresponding root.
Then $\phi: w \mapsto - w \beta$ is a surjective poset map from the weak ...

31

Taking the fact that Catalan numbers $C_n$ measure the number of binary trees on $n$ nodes, we can find an involution on the set of these trees: choose the lexicographically first node in the tree that's unbalanced (i.e., where the number of nodes in the left subtree is different from the number in the right subtree). Then partner this tree with the one ...

3

As Joel mentions, this follows from the work of Tao and Ziegler.
Alternatively, this can be directly deduced from the density of the primes and the known bounds on the Furstenberg–Sárközy theorem. Indeed, the bounds of Pintz, Steiger, and Szemeredi from the 1980's are suffient. See:
J. Pintz, W. L. Steiger, and E. Szemeredi, On sets of natural numbers whose ...

34

Apparently not mentioned yet, though surely not new:
use the quadratic equation satisfied by the generating function.
Since we look for $n+1$ to be a power of $2$, we shift the index by $1$
and consider
$$
F = \sum_{n=0}^\infty C_n x^{n+1} = x + x^2 + 2 x^3 + 5 x^4 + 14 x^5 + 42 x^6 + 132 x^7 + 429 x^8 + \cdots.
$$
Then $F = x + F^2$. Instead of solving ...

answered Nov 20 at 22:02

Noam D. Elkies

69.7k1212 gold badges249249 silver badges333333 bronze badges

2

Okay, following the ideas from the comments, I do think there is a counterexample.
Let $G=K_4$, so $W$ is generated by involutions $v_1,\ldots,v_4$ subject to no other relations. Consider the Coxeter element $c=v_1v_2v_3v_4$. We can reverse the autonomous subset $\{v_1,v_2\}$ here to get $c'=v_2v_1v_3v_4$.
Now consider the homomorphism $\phi\colon W\to S_3$ ...

5

Here is one I've thought of a while ago for my combinatorics classes, but
never ended up using.
Let $C_{0},C_{1},C_{2},\ldots$ be the Catalan numbers. Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$.
Theorem 1. For each $n\in\mathbb{N}$, we have
\begin{align*}
C_{n+1}=\sum\limits_{k=0}^{\left\lfloor n/2\right\rfloor }2^{n-2k}\dbinom{n}{2k}
C_{k}.
\end{align*}...

9

A
proof by Koshy and Salmassi starting from Segner's recurrence formula for the Catalan numbers.
A proof by Ji and Wilf using the method of recursive palindromes.

answered Nov 20 at 17:27

Carlo Beenakker

136k1212 gold badges328328 silver badges469469 bronze badges

2

This is a difficult question in general; see for instance
https://people.mpi-sws.org/~joel/publications/positivity_and_minimality_holonomic21abs.html
https://people.mpi-sws.org/~joel/publications/holonomic-second-order21abs.html
for recent work on special cases. (As you noted, the paper by Bruno Salvy and myself that you mention is purely about upper ...

0

We will prove the identity (A8) that qifeng618 alluded to. The method is called the Wilf-Zeilberger methodology. To this end, define the two functions (suppressing $x$)
$$F(n,k):=\frac{\binom{2x+1}{2k+1}\binom{x-k}{n-k}(2n+1)}{(2x+1)\binom{x+n}{2n}4^n}
\qquad \text{and} \qquad
G(n,k):=-\frac{F(n,k)\,2k\,(2k+1)}{2(x+n+1)(n+1-k)}.$$
Next, verify (preferably ...

co.combinatorics enumerative-combinatorics generating-functions combinatorial-identities stirling-numbers

1

The formula (3.27) on pages 59--60 in the monograph [1] reads that
\begin{equation}\label{Sprugnoli-Gould-2006-(3.27)}\tag{A8}
\sum_{k=0}^n\binom{2x+1}{2k+1}\binom{x-k}{n-k} =\frac{2x+1}{2n+1}\binom{x+n}{2n}4^n.
\end{equation}
All the identities (Q1) to (Q7) in the question are variants or special cases of the identity \eqref{Sprugnoli-Gould-2006-(3.27)}.
...

co.combinatorics enumerative-combinatorics generating-functions combinatorial-identities stirling-numbers

1

We recite Theorem 2.1 and its proof in the paper [1] below as an answer.
Theorem 2.1. Let $n\ge0$ be an integer and $\Re(z)>0$. Then
\begin{equation}\label{sum-recip-binom-ext}\tag{1}
\sum_{q=0}^{n}\binom{n}{q}\frac{(-1)^q}{q+z}=B(z,n+1)
\end{equation}
and
\begin{equation}\label{sum-recip-binom-ext-inv}\tag{2}
\sum _{q=0}^n \binom{n}{q}[(-1)^qB(z,q+1)]=\...

2

Let, $n=2^{b_1}+2^{b_2}+...+2^{b_r}$. Using Kummer's rule we get $\binom{n}{j}$ is not divisible by $2$ (and so $\binom{n}{j} \mod 2 ≠0$) iff $j=\sum_{k_i} 2^{k_i}$ with $k_i \in \{b_i\}$ ; call this $j$, good. Because in those cases there will be no carrier while summing $n-j$ and $j$.
While for other $j$ there will be carriers. So, $\binom{n}{j} \mod 2 =0$
...

3

If $n\in \mathbb N$ has binary expansion $n=\sum_{k\in S}2^k$ for a finite subset $S\subset \mathbb N$, then
$$ \sum_{j=0}^n\Big[\big( {n \atop j}\big)\text{mod}\, 2 \Big]x^jy^{n-j}=\prod_{k\in S} (x^{2^k}+y^{2^k})$$
More generally, but not needed here (see below): for sums of $r$ indeterminates $x_i$, the binary coefficient homogeneous polynomial obtained ...

2

You might want to check out the concept of an orthogonal array Specifically a $t-(v,k,1)$ orthogonal array which has $k$ columns and $v^t$ rows filled with $v$ symbols in such a way that any $t$ columns contain each ordered $t$-tuple once. That article gives a $2- (4,5,1)$ example.
In your setup that is a $16$ element subset of $X^5$ with $X=\{1,2,3,4\}$ so ...

1

Not every distance set $l_k$ will give you a genuine $k$-simplex. But the theorem gives you a realization in $E$ of every set of distances $l_k$, including the ones coming from genuine $k$-simplices. There are a bunch of $T_{l_k}$'s, some of which are $k$-simplices, and they're all nonempty (when the conditions of the theorem are satisfied).
[Complete ...

9

Yes, this is true and follows from Wagner's theorem. Wagner's theorem asserts that every graph with no $K_5$ minor can be built from $0$-, $1$-, $2$-, and $3$-sums from planar graphs and a fixed $8$ vertex non-planar graph called the Wagner graph. Since the Wagner graph is not $4$-connected, this implies that every $4$-connected graph with no $K_5$ minor ...

3

This conjecture has now been proved by Valentin Bonzom, Guillaume Chapuy and Maciej Dołęga in their paper $b$-monotone Hurwitz numbers: Virasoro constraints, BKP hierarchy, and O(N)-BGW integral.

2

By expanding $(2^i-1)^{-1}=\sum_{p=1}^\infty 2^{-ip}$, and summing over $i$, we find
$$S_m=\sum_{i=1}^{m}\binom{m}{i}\frac{(-1)^{i+1}}{2^i-1}=\sum _{p=1}^{\infty } \left(1-\left(1-2^{-p}\right)^m\right).$$
This sum was considered in this post and in a publication On the expectation of the maximum of IID geometric random variables. The latter derives on page ...

answered Nov 16 at 15:50

Carlo Beenakker

136k1212 gold badges328328 silver badges469469 bronze badges

2

For each element of $x\in A+B+nS$ we construct at least $(\frac{|A||B|}{2|A+B|})^n$ distinct sequences $(t_0,\ldots,t_n)\in (A+B)^{n+1}$ such that $x=t_0+\ldots+t_n$ (the sentence after "observe that..." verifies that they are distinct). Since such sequences for different $x$'s are obviously distinct (they have not equal sums), all sequences are ...

2

So this is not exactly an answer, but too long for a comment.
This is a question in extremal set theory, which is mostly concerned with determining the maximum number of sets, often of equal size, that can be chosen while satisfying certain intersection properties.
For example, the famous Erdős-Ko-Rado theorem explains how to choose the maximum number of $k$-...

2

The answer is false.
Let $G$ be the 3-prism and $\varphi$ the coloring shown below.
$G$ cannot have a 2-distance vertex 4-coloring. As all pairs of vertices in $G$ have distance either 1 or 2, a 2-distance coloring of $G$ would require 6 colors.

20

Sure. Start with the Zeckendorf representation of $n$, $$ n = \sum_{ i} F_{j_i} $$ where $F_j$ are the Fibonacci numbers and $j_i \geq j_{i-1} + 2$.
Then the fibbinary number associated to $n$ is $\sum_i 2^{j_i}$ and $c(n)$ is obtained from this by removing a zero in front of each $1$, i.e. $$c(n) = \sum_i 2^{ j - (i-1)}$$
Now the $b(m)$ function is written ...

2

The answer is False. Let $G$ be the Möbius ladder on 12 vertices with every edge subdivided, or in SageMath code,
>G=Graph('K?AEF@oM?w@o') #Mobius ladder on 12 vertices
>G.subdivide_edges(G.edges(),1)
$G$ is a subcubic graph.
>max(G.degree())
3
If the line graph of $G$ admits a 2-distance vertex 4-coloring $\psi$ with colors in $\{1,2,3,4\}$, ...

3

The Durfee square formula for the generating function of the number of partitions doesn't seem to be in this list yet, I find it rather appealing:
$$
\frac{1}{(q)_\infty} = \sum_{n\geq 0} \frac{q^{n^2}}{(q)_n (q)_n} \ .
$$

6

I would suggest that much of what I said in my answer to another MO question applies here, in spades. To a first approximation, the canon is the empty set. Start with a problem, and learn what you need as you go along.
See also How to escape the inclination to be a universalist or: How to learn to stop worrying and do some research.

10

In fact the numbers $a_k$ in the various factors $1+a_k$ are multiples of $4$ and typically small ones.
$a_k=0$ unless every prime of the form $4m-1$ dividing $k$ occurs to an even power. If so, $$a_k=4(s_1+1)(s_2+1)\cdots (s_i+1)$$ where the $s_j$ are the exponents of the prime divisors of the form $4m+1$.
The number given $3^{114}\ 5^{19}\ 13^6\ 17^9$ ...

1

Miller and Harrison (2013, link) solved this problem, even for arbitrary row and column margins per row and column ( link full text).
I think there was even a package, but sadly can't find it right now. Hope this helps.

40

For any $k\in\mathbb N$ let $a_k$ be the number of points on the circle of radius $\sqrt{k}$ (this number may be zero). For any path as in question and for any $k$ between $1$ and $i^2+j^2-1$, there is going to be either none or exactly one of the points on the circle of radius $\sqrt{k}$ around $(i,j)$. As the sequence of points determines the path, this ...

8

I am not that strong on the representation-theory side, but know more about the combinatorics side. If you want to get an overview of the symmetric functions and the associated combinatorics (crystal bases, RSK etc), then one starting point (with references!) is www.symmetricfunctions.com.
I am the admin for this site, so all errors and issues are completely ...

ag.algebraic-geometry reference-request co.combinatorics rt.representation-theory geometric-representation-theory

answered Nov 12 at 20:38

Per Alexandersson

14.1k99 gold badges6161 silver badges114114 bronze badges

4

It's right in the beginning of De Bruijin's paper. More generally,
$\log p(rn) \sim \frac 1 {2 \log r} \log^2 \frac n {\log n}$
where $p(rn)$ is the number of partitions of $rn$ into powers of $r$.
The result is attributed to Kurt Mahler's paper "On a special functional equation", published in Journ. London Math. Soc. in 1940.

11

M. Haiman "Notes on Macdonald polynomials and the geometry of the Hilbert scheme of points on $\mathbb{P}^2$". By one of the greatest specialists of interactions between combinatorics and algebraic geometry.

ag.algebraic-geometry reference-request co.combinatorics rt.representation-theory geometric-representation-theory

Top 50 recent answers are included

#### Related Tags

co.combinatorics × 8994graph-theory × 1898

nt.number-theory × 970

reference-request × 811

pr.probability × 687

discrete-geometry × 471

rt.representation-theory × 430

linear-algebra × 414

gr.group-theory × 386

graph-colorings × 288

algorithms × 284

permutations × 264

enumerative-combinatorics × 263

ag.algebraic-geometry × 241

additive-combinatorics × 240

sequences-and-series × 221

partitions × 220

binomial-coefficients × 211

convex-polytopes × 210

matrices × 207

polynomials × 204

mg.metric-geometry × 203

computational-complexity × 202

finite-groups × 161

generating-functions × 158