37 votes

Collecting alternative proofs for the oddity of Catalan

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 ...
37 votes

Collecting alternative proofs for the oddity of Catalan

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 ...
24 votes
Accepted

The verbs in combinatorics: Enumerating, counting, listing and all that

I'm not sure if this is exactly what you're looking for, but the main topic of Herb Wilf's article What is an Answer? is how to answer the question "How many ______ are there?" His basic ...
  • 69.6k
24 votes
Accepted

Can this probability be obtained by a combinatorial/symmetry argument?

If I understand correctly, $c_i := b_i/a_i$ should also be symmetric and non-atomic. Then the result holds if there exists $t$ so that for all $i$ $t \geq c_i$ if $a_i > 0$; $c_i \geq t$ if $a_i &...
  • 1,769
22 votes
Accepted

an identity for a sum over partitions

Multiply the whole equality by $(-1)^n$. First of all, notice that $k\choose m_1,\dots,m_k$ is the number of ways to permute the numbers $\lambda_1,\dots,\lambda_k$, so the left-hand side equals $$ ...
22 votes
Accepted

A rather curious identity on sums over triple binomial terms

Just playing around with it: The RHS multiplied by $n$ is the same as $$2 \sum_{k=0}^{n-1} \binom{n+1}{k} \binom{n}{k} \binom{n+1}{k+2}.$$ Subtracting this from $n$ times the LHS gives $$\sum_{k=0}^{n-...
20 votes
Accepted

A "quantum" identity: in search of a proof -Part II

Both sides are equal to $\binom{x+y+1}{n}_q$. This enumerates lattice paths in an $n\times (x+y-n+1)$ rectangle, according to the area statistic. We will assume that these paths start at $(0,0)$ and ...
19 votes
Accepted

An interesting identity: in search of a proof -Part I

This is known as Jensen's identity and dates back to 1902. See here an overview of this identity and related ones, and a proof: https://arxiv.org/abs/1005.2745, a paper by Victor Guo.
18 votes
Accepted

How many finitely-generated-by-elements-of-finite-order-groups are there?

Grigorchuk showed that there are uncountably many growth degrees of 2-generated infinite p-groups for any prime p. Hence there are uncountably many isomorphisms classes and even quasi-isometry classes ...
18 votes
Accepted

Two interpretations of a sequence: an opportunity for combinatorics

Here is a bijective proof that equates both $a(n)$ and $b(n+1)$ to the quantity $$p(n)+2p(n-1)+\cdots+np(1)+(n+1)p(0) \tag1$$ where $p(n)$ is the number of partitions of $n$. For $a(n)$: each ...
18 votes
Accepted

Equality of two $q$-series. Proof?

I take it from looking at the previous problem that you are familiar with the Dyson rank on partitions with distinct parts. Let's denote by $Q(r,n)$ the number of partitions of $n$ into distinct parts ...
17 votes
Accepted

The Möbius number of the nonabelian finite simple groups

The answer to your question is ``yes". Something more general was proved by Hawkes, Isaacs and \"Ozaydin in a 1989 paper in the Rocky Mountain Journal of Mathematics. CORRECTION: As Sebastien ...
16 votes
Accepted

How does the number of trees on $n$ vertices *up to isomorphism* grow as $n \to \infty$?

For Q1 the answer is known to be $\sim C_1C_2^n n^{-5/2} $ for $C_1\approx 0.5349496061...$ and $C_2\approx 2.9955765856...$. This can be found in Flajolet and Sedgewick's "Analytic Combinatorics&...
16 votes
Accepted

Non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?

Here is at least a heuristic argument for why we should expect fewer vertical dominoes than horizontal dominoes. As we increase the length of the strip (to the right, say), let us think about how the ...
  • 69.6k
16 votes
Accepted

Looking for a "clever" argument for a $q$-series identity

Here's a proof that indicates a systematic method for proving such identities. Let $\eta(z) = q^{1/24} \prod_{n=1}^{\infty} (1-q^{n})$, with $q = e^{2 \pi i z}$. The identity you state in the equation ...
  • 19.1k
16 votes
Accepted

Convergency radius of the generating series for A93637

This is pretty simple, really. Note that we can obtain our power series in the following way. Define on (formal) power series with positive coefficients the transform $$ T\sum_{k=0}^\infty b_kx^k=\...
  • 55.4k
15 votes

A conjecture harmonic numbers

We can use the characterization by Christie. Let $\pi \in S_n$. Add a fixed point $0$ to $\pi$, and let $c$ be the cycle $(0, 1, \ldots, n)$. Then the smallest number of block interchanges to sort $\...
15 votes
Accepted

Extracting constant terms: is there a direct way?

For power series $u(x_1,\ldots,x_n),v(x_1,\ldots,x_n)$ call $u,v$ similar and write $u\sim v$ if all monomials $\prod x_i^{c_i}$ with $c_i\in \{0,1\}$ have equal coefficients in $u,v$. In other words, ...
  • 91.9k
14 votes
Accepted

Imprimitive solutions to $x^2+y^3=z^7$

You can find the solutions for any given $z$ by looking for the integral points on the elliptic curve $$x^2 = (-y)^3 + z^7$$ (which would usually be written $y^2 = x^3 + z^7$). The curve is isomorphic ...
14 votes

an identity for a sum over partitions

Here is a purely combinatorial proof of a more general identity $$ \sum_{\lambda\vdash n}(-1)^{n-k}\frac{k!}{m_1!\cdots m_n!}\prod_{i=1}^k\binom{A}{\lambda_i}=\binom{A+n-1}n. $$ As Ilya suggests, we ...
  • 91.9k
14 votes
Accepted

Is there a natural relationship between OEIS A127670 and Cayley's tree formula?

Yes there is a connection. While $n^{n-2}$ counts the number of vertex labeled trees on $n$ vertices, the expression $2^n(n+1)^{n-2}$ counts the number of edge labeled trees on $n$ edges. There is a ...
13 votes

An interesting identity: in search of a proof -Part I

Oh no, I was too slow... sorry for the double reference. This is Jensen's identity. It first appeared (in a slightly modified form) in: Jensen, Sur une identité d'Abel et sur d'autres formules ...
12 votes

Distinct numbers in multiplication table

There's a beautiful lecture by Carl Pomerance in which he discusses Erdos's Multiplication Table Problem and then goes on to talk about dense product-free sets of integers. The talk was at the JMM in ...
12 votes

A recurrence relation on Catalan numbers

Let $$C(x) = \sum_{n=1}^\infty C_{n-1} x^n = \frac{1-\sqrt{1-4x}}{2}.$$ Then the identity in question follows easily from $C(x(1-x)) = x$.
  • 14.5k
12 votes

Number of collinear ways to fill a grid

By the method I used to solve Counting "connected" edge orderings (shellings) of the complete graph, I can show the following: $$ g(m,n) = (mn-1)!\,m!\,n!\sum \frac{b_1 b_2\cdots b_{m+n-...
12 votes

Real rootedness of a polynomial with binomial coefficients

Let's consider $n\geqslant 5$ case only ($n=1,2,3,4$ are straightforward). Then $Q_n$ has non-negative coefficients and we care on the number of negative roots of $Q_n$. We have $2P_n(-x)=(1+i\sqrt{x})...
  • 91.9k
11 votes

A "quantum" identity: in search of a proof -Part II

If we substitute $y:=v+n$ in the identity, the LHS becomes a convolution of two similar sequences, $$\sum_{k=0}^nq^{(v+1)k}\binom{x+k}{k}_q \binom{v+(n-k)}{n-k}_q =\sum_{k=0}^n q^{n-k}\binom{x+v+n-k}{...
  • 52.5k
11 votes
Accepted

The number of Dyck paths of length $2n$ and height exactly $k$

EDIT: Ira points out that the below method, for general $k$, appears in Howard D. Grossman, Fun with lattice points, Scripta Math. 15 (1949), 79–81, but this paper does not seem to be available online....
11 votes
Accepted

Enumerating all permutations that are "square roots" of derangements

Check out "Example 2. Permutations with no small cycles" on pg. 176 of H. Wilf's "generatingfunctionology": https://www.math.upenn.edu/~wilf/DownldGF.html. It explains, using generating functions, how ...
  • 20.2k
11 votes
Accepted

Total sum of characters of the symmetric group $\frak{S}_n$

The sum $\sum_\mu \chi^\lambda_\mu$ over partitions $\mu$ of $n$ is the multiplicity of the irreducible $\chi^\lambda$ in the character afforded by $\mathfrak S_n$ acting on itself by conjugation. If $...
  • 250

Only top scored, non community-wiki answers of a minimum length are eligible