Combinatorial proofs of some properties of tangent and Genocchi numbers

The tangent number T2n+1 is equal to the number of increasing labelled complete binary trees with 2n+1 vertices. This combinatorial interpretation immediately proves that T2n+1 is divisible by 2n. However, a stronger divisibility property is known in the studies of Bernoulli and Genocchi numbers, namely, the divisibility of (n+1)T2n+1 by 22n. The traditional proofs of this fact need significant calculations. In the present paper, we provide a combinatorial proof of the latter divisibility by using the hook length formula for trees. Furthermore, our method is extended to k-ary trees, leading to a new generalization of the Genocchi numbers.