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

- 73.8k

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

- 1,316

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
$$
...

- 19.9k

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

- 7,262

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

- 83k

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.

- 11k

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

- 34.9k

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

- 83k

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

- 83k

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

- 3,446

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&...

- 83k

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 $\...

- 5,192

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

- 10.7k

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

- 83k

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

- 1,374

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

- 43.3k

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

- 46.1k

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

- 527

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

#### Related Tags

enumerative-combinatorics × 423co.combinatorics × 324

reference-request × 69

graph-theory × 57

nt.number-theory × 42

permutations × 35

partitions × 30

generating-functions × 25

pr.probability × 19

rt.representation-theory × 19

gr.group-theory × 17

linear-algebra × 17

polynomials × 17

algebraic-combinatorics × 16

catalan-numbers × 15

trees × 13

discrete-geometry × 12

asymptotics × 12

binomial-coefficients × 12

integer-sequences × 11

algorithms × 10

finite-fields × 10

matrices × 9

sequences-and-series × 9

convex-polytopes × 9