# Tag Info

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

### 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
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
Accepted

• 91.9k

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