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