Combinatorial proofs of some properties of tangent and Genocchi numbers
Guo-Niu Han Jing-Yi Liu
math.CO


 
The tangent number T_2n+1 is equal to the number of
	increasing labelled complete binary trees with 2n+1 vertices.
This combinatorial interpretation immediately proves that T_2n+1 is divisible by 2^n.
However, a stronger divisibility property is known in the studies
of Bernoulli and Genocchi numbers, namely, the divisibility of
(n+1)T_2n+1 by 2^2n. 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.


The Caccioppoli Ultrafunctions 
    Vieri Benci, Luigi Carlo Bersellicorresponding author,
and Carlo Romano Grisanti
    
====================================================================================







§ INTRODUCTION
  
The tangent numbers 
[Some mathematical literature uses a slightly different notation where tan x is written T_1 x + T_2 x^3/3! + T_3 x^5/5! + ⋯ 
(See <cit.>)]
(T_2n+1)_n≥ 0
appear in the Taylor expansion of tan(x):

    tan x = ∑_n≥ 0 T_2n+1x^2n+1/(2n+1)!.

It is known that the tangent number T_2n+1 is equal to the number of
all alternating permutations of length 2n+1  
(see <cit.>).
Also, T_2n+1 counts the number of
increasing labelled complete binary trees  with 2n+1 vertices.
This combinatorial interpretation immediately implies 
that T_2n+1 is divisible by 2^n.
However, a stronger divisibility property is known related to the study of Bernoulli and Genocchi numbers <cit.>, as stated in the following theorem.

The number (n+1)T_2n+1 is divisible by 2^2n, and the quotient
is an odd number.

The quotient is called Genocchi number and denoted by 

    G_2n+2:=(n+1)T_2n+1/2^2n.


Let

    g(x):=∑_n≥ 0G_2n+2x^2n+2/(2n+2)!

be the exponential generating function for the Genocchi numbers. Then, (<ref>) is
equivalent to

    g(x)=xtanx/2.




The initial values of the tangent and Genocchi numbers are listed below:

    n    0     1     2     3     4     5     6 
    T_2n+1    1     2     16     272     7936     353792     22368256
    G_2n+2    1     1     3     17     155     2073     38227




The fact that the Genocchi numbers are odd integers
is traditionally proved by using the von Staudt-Clausen theorem on Bernoulli numbers and the little Fermat theorem 
<cit.>.
Barsky <cit.> gave a different proof by using the Laplace transform.
To the best of the authors' knowledge, no simple combinatorial proof has been derived yet and it is the purpose of this paper to provide one.

Our approach is based on the geometry of the
so-called
leaf-labelled tree
and the fact that the hook length h_v of such a tree is always an odd integer
(see Sections <ref> and <ref>).

In Section <ref>
we consider the k-ary trees
instead of the binary trees
and
obtain a new generalization of the Genocchi numbers.
For each integer k≥ 2, let L_kn+1^(k) be the number of increasing labelled complete k-ary trees with kn+1 vertices. 
Thus, L^(k)_kn+1 will appear to be a natural generalization 
of the tangent number.
The general result is stated next.

	(a) For each integer k≥ 2, the integer
	
    (k^2 n-kn+k)! L^(k)_kn+1/ (kn+1)!

is divisible by (k!)^kn+1.

	(b) Moreover, the quotient

    M^(k)_k^2 n-kn+k:=
    	(k^2 n-kn+k)!  L^(k)_kn+1/(k!)^kn+1(kn+1)!≡
    	1k,    k=p, 
    
    	1p^2,    k=p^t, t≥ 2, 
    
    	0k,    otherwise,

where n≥ 1 and p is a prime number.


We can
 realize that Theorem <ref> is a direct generalization of Theorem <ref>,
if we restate the problem in terms of generating functions.
Let ϕ^(k)(x) and ψ^(k)(x) denote the exponential generating functions for 
L^(k)_kn+1 and M^(k)_k^2n-kn+k, respectively, that is,

    ϕ^(k)(x)   =∑_n≥ 0L^(k)_kn+1x^kn+1/(kn+1)!; 
    ψ^(k)(x)   =∑_n≥ 0M^(k)_k^2n-kn+kx^k^2n-kn+k/(k^2n-kn+k)!.

If k is clear from the context, the superscript (k) will be omitted.
Thus, we will write  L_kn+1:=L^(k)_kn+1, 
	M_k^2 n-kn+k := M^(k)_k^2 n-kn+k, ϕ(x):=ϕ^(k)(x), ψ(x):=ϕ^(k)(x).
From Theorem <ref> we have

    ϕ'(x)=1+ϕ^k(x);


    ψ(x)=x ·ϕ(x^k-1/k!).

The last relation becomes the well-known formula (<ref>) when k=2.


Several generalizations of the Genocchi numbers
have been studied in recent decades.
They are based on
 the Gandhi polynomials <cit.>,
Seidel triangles <cit.>,
continued fractions <cit.>, combinatorial models <cit.>, etc.
Our generalization seems to be the first extension
dealing with
 the divisibility of
(n+1)T_2n+1 by 2^2n. It also raises the following open problems.



Problem 1. Find a proof of Theorem <ref> à la Carlitz, or à la Barsky.


Problem 2. Find the Gandhi polynomials, Seidel triangles, continued fractions and a combinatorial model for the new generalization of Genocchi numbers M_k^2n-kn+k à la Dumont.


Problem 3. Evaluate m_n:=M_k^2n-kn+k k for k=p^t, where p is a prime number and t≥ 3. It seems that the sequence (m_n)_n≥ 0 is always periodic for any p and t. 
Computer calculation has provided the initial values:

    (m_n)_n≥ 0   = (1,1,5,5,1,1,5,5,⋯)     for  k=2^3,
    
     	(m_n)_n≥ 0   = (1,1,10,1,1,10,1,1,10⋯)     for  k=3^3,
    
        (m_n)_n≥ 0   = (1,1,126,376,126,1,1,126,376,126,⋯)     for  k=5^4, 
    
        (m_n)_n≥ 0   = (1,1,13,5,9,9,5,13,1,1,13,5,9,9,5,13,⋯)     for  k=2^4.






§ INCREASING LABELLED BINARY TREES
 
In this section we recall some basic notions on 
increasing labelled binary trees.
Consider the set 𝒯(n) of all (unlabelled) binary trees with n vertices.
For each t∈𝒯(n)
let ℒ(t) denote the set of all
increasing labelled binary trees of shape t, 
obtained from t by labeling its n vertices with {1,2,…,n} in such a way
that the label of each vertex is less than that of its descendants.
For each vertex v of t, the hook length of v,
denoted by h_v(t) or h_v, is
the number of descendants of v (including v).
The hook length formula (<cit.>)
claims that
the number of increasing labelled binary trees of shape t
is equal to n! divided by the product of the h_v's (v∈ t)

    #ℒ(t)=n!/∏_v∈ t h_v.


Let 𝒮(2n+1) denote
the set of all
complete binary trees s with 2n+1 vertices, which are defined to be
the binary trees such that the two
subtrees of each vertex are, either both empty, or both non-empty.
For example, there are five complete binary trees with 2n+1=7 vertices,
labelled by their hook lengths in Fig. 1.





beginfig(1, "1.5mm");
setLegoUnit([3,3])
#showgrid([0,0], [20,14])  # show grid
r=0.15
rtext=r+0.5  # distance between text and the point

def ShowPoint(ptL, labelL, dir, fill=True):
	[circle(p[z-1], r, fill=fill) for z in ptL]
	[label(p[ptL[z]-1], labelL[z], dist=[rtext, rtext], dist_direction=dir) for z in range(len(ptL))]

dist=[1,1,1,1]
p=btree([6,4,7,2,5,1,3], [4,8], dist=dist, dot="fill", dotradius=r)
ShowPoint([6,7,5,3], [1,1,1,1], 270)
ShowPoint([4,2,1], [3,5,7],135)
label(addpt(p[0],[0,1.6]), "s_1")

p=btree([4,2,6,5,7,1,3], [8.2,8], dist=dist, dot="fill", dotradius=r)
ShowPoint([4,6,7], [1,1,1], 270)
ShowPoint([2,1], [5,7],135)
ShowPoint([5,3], [3,1],45)
label(addpt(p[0],[0,1.6]), "s_2")

p=btree([2,1,6,4,7,3,5], [12.4,8], dist=dist, dot="fill", dotradius=r)
ShowPoint([5,6,7], [1,1,1], 270)
ShowPoint([4,2,1], [3,1,7],135)
ShowPoint([3], [5],45)
label(addpt(p[0],[0,1.6]), "s_3")

p=btree([2,1,4,3,6,5,7], [16.6,8], dist=dist, dot="fill", dotradius=r)
ShowPoint([2,4,6,7], [1,1,1,1], 270)
ShowPoint([5,3,1], [3,5,7],45)
label(addpt(p[0],[0,1.6]), "s_4")

p=btree([4,2,5,1,6,3,7], [22.8,8], dist=[1.2, 0.8], dot="fill", dotradius=r)
ShowPoint([5,4,6,7], [1,1,1,1], 270)
ShowPoint([1,2], [7,3],135)
ShowPoint([3], [3],45)
label(addpt(p[0],[0,1.6]), "s_5")

endfig();



    < g r a p h i c s >



Fig. 1. Complete binary trees with 7 vertices


We now define an equivalence relation on 𝒮(2n+1), called pivoting.
A basic pivoting  is an exchange of
the two subtrees of a non-leaf vertex v.
For s_1, s_2∈𝒮(2n+1), if s_1 can be changed to s_2 by a finite sequence of basic pivotings, we write s_1∼ s_2.
It's routine to check that ∼ is an equivalence relation. Let 𝒮̅(2n+1) = 𝒮(2n+1)/∼.
Since s_1∼ s_2 implies that #ℒ(s_1)=#ℒ(s_2),
we define #ℒ(s̅)=#ℒ(s) for s∈s̅.
Then

    T_2n+1 = ∑_s̅∈𝒮̅(2n+1) T(s̅),

where

    T(s̅)=∑_s ∈s̅#ℒ(s) =
    #s̅×#ℒ(s̅).

For example, consider 𝒮(7) (see Fig. 1), we have

    [      shape        s_1        s_2        s_3        s_4        s_5;    ∏_v h_v    3· 5· 7    3· 5· 7    3· 5· 7    3· 5· 7    3· 3· 7; n!/∏_v h_v         48         48         48         48         80 ]

Trees s_1, s_2, s_3 and s_4 belong to the same equivalence class s_1, while s_5 is in another equivalence class
s_5.
Thus T(s_1)=4× 48=192, T(s_5)=80 and
T_7=T(s_1)+T(s_5)=272.



The pivoting can also be viewed as an  equivalence relation on
the set ∪_s∈s̅ℒ(s), that is,
all increasing labelled trees of shape s with s∈s̅.
Since the number of non-leaf vertices
is n in s,
there are exactly 2^n labelled trees in each equivalence class.
Hence, T(s̅) is divisible by 2^n.
Take again the example above, T(s_1)/2^3=24, T(s_5)/2^3=10,
and T_7/2^3 = 24+10=34.



This is not enough to derive that 2^2n| (n+1)T_2n+1. However, the above process
leads us to reconsider the question in each equivalence class.
We can show that the divisibility actually holds in
each s̅, as stated below.




	For each s̅∈𝒮(2n+1), the integer
(n+1)T(s̅) is divisible by 2^2n.




Let G(s̅):= (n+1)T(s̅)/2^2n. Proposition <ref> implies that G(s̅) is an integer.
By (<ref>) and (<ref>),

    G_2n+2 = ∑_s̅∈𝒮̅(2n+1) G(s̅).

We give an example here and present the proof in the next section.

For n=4, there are three equivalence classes.




beginfig(2, "1.6mm");
setLegoUnit([3,3])
#showgrid([0,0], [20,14])  # show grid
r=0.15
rtext=r+0.5  # distance between text and the point

def ShowPoint(ptL, labelL, dir, fill=True):
	[circle(p[z-1], r, fill=fill) for z in ptL]
	[label(p[ptL[z]-1], labelL[z], dist=[rtext, rtext], dist_direction=dir) for z in range(len(ptL))]

dist=[1,1,1,1]
p=btree([8,6,9,4,7,2,5,1,3], [4,8], dist=dist, dot="fill", dotradius=r)
ShowPoint([8,9,7,5,3], [1,1,1,1,1], 270)
ShowPoint([6,4,2,1], [3,5,7,9],135)
label(addpt(p[0],[0,1.6]), "s_1∈s_1")

dist=[1.6,1.6,1,1]
p=btree([6,4,7,2,8,5,9,1,3], [11,8], dist=dist, dot="fill", dotradius=r)
ShowPoint([8,9,7,6,3], [1,1,1,1,1], 270)
ShowPoint([4,2,1], [3,7,9],135)
ShowPoint([5], [3],45)
label(addpt(p[0],[0,1.6]), "s_2∈s_2")


dist=[1.6,1,1,1]
p=btree([6,4,7,2,5,1, 8,3,9], [18,8], dist=dist, dot="fill", dotradius=r)
ShowPoint([8,9,7,6,5], [1,1,1,1,1], 270)
ShowPoint([4,2,1], [3,5,9],135)
ShowPoint([3], [3],45)
label(addpt(p[0],[0,1.6]), "s_3∈s_3")


endfig();



    < g r a p h i c s >



Fig. 2. Three equivalence classes for n=4


	

	In this case, Proposition <ref> and relation (<ref>) can be verified by
	the following table.





s̅     #s̅     ∏ h_v     #ℒ(s̅)     T(s̅)     G(s̅) 

s_1     8     3· 5· 7· 9     384     3072     60 

	s_2     2     3· 3· 7· 9     640     1280     25 

	s_3     4     3· 3· 5· 9     896     3584     70 

sum     14                7936     155






§ COMBINATORIAL PROOF OF THEOREM <REF>
  
Let n be a nonnegative integer and
s̅∈𝒮̅(2n+1) be an equivalence class in the set of
increasing labelled complete binary trees.
The key of the proof is the fact that
the hook length h_v is always an odd integer.
For each complete binary tree s,
we denote the product of all hook lengths by H(s)=∏_v∈ s h_v.
Also, let H(s̅)=H(s) for s∈s̅, since all trees in the
equivalence class s̅ share the same product of all hook lengths.


For each complete binary tree s,
the product of all hook lengths
H(s) is an odd integer.


By Lemma <ref>,
Proposition <ref> has the following equivalent form.


	For each s̅∈𝒮̅(2n+1), the integer
	(2n+2)H(s̅)T(s̅) is divisible by 2^2n.




	By identities (<ref>) and (<ref>) we have

    (2n+2)H(s̅)T(s̅)   =(2n+2)H(s̅)×#s̅×#ℒ(s̅) 
       =(2n+2)×#s̅× (2n+1)! 
       =(2n+2)!×#s̅.


Suppose that s is a complete binary tree with 2n+1 vertices,
then s has n+1 leaves.
Let s^+ be the complete binary tree with 4n+3 vertices obtained
from s by replacing each leaf of s by the complete binary tree
with 3 vertices. So s^+ has 2n+2 leaves.
Let ℒ^+(s^+)
be the set of all leaf-labelled trees of shape s^+, 
obtained from s^+ by labeling its 2n+2 leaves 
 with {1,2,…, 2n+2}.
It is clear that #ℒ^+(s^+)=(2n+2)!. By (<ref>) we have
	the following
combinatorial interpretation:

For each s̅∈𝒮̅(2n+1), the number of all leaf-labelled trees of shape s^+ such that s∈s̅
is equal to (2n+2)H(s̅)T(s̅).
	



This time we take the pivoting for an equivalence equation
on the set of leaf-labelled trees
	∪_s∈s̅ℒ^+(s^+).
Since a leaf-labelled tree s^+ has 2n+1 non-leaf vertices, and each non-trivial sequence of
	pivotings will make a difference on the labels of leaves, every equivalence class contains 2^2n+1 elements.
Hence,
we can conclude
	that (2n+2)H(s̅)T(s̅) is divisible by 2^2n+1.




For example, in Fig. 3, we reproduce a labelled tree with 9 vertices
	and a leaf-labelled tree with 19 vertices.
	There are 4 non-leaf vertices
	in the labelled tree and the 9 non-leaf vertices
	in the leaf-labelled tree, as indicated by the fat dot symbol “∙”.
	Comparing with the traditional combinatorial model,  our method
	increases the number of non-leaf vertices. Consequently, we
	establish a stronger divisibility property.




beginfig(3, "1.6mm");
setLegoUnit([3,3])
#showgrid([0,0], [20,14])  # show grid
dist=[1.6, 1.6, 1]
r=0.15
rtext=r+0.5  # distance between text and the point

def ShowPoint(ptL, labelL, dir, fill=True):
	[circle(p[z-1], r, fill=fill) for z in ptL]
	[label(p[ptL[z]-1], labelL[z], dist=[rtext, rtext], dist_direction=dir) for z in range(len(ptL))]



p=btree([6,4,7,2,8,5,9,1,3],pt=[7,0], dist=dist, dot="frame", dotradius=r, labeled=False)
ShowPoint([1,2,4], [1,2,4], 135, fill=True)
ShowPoint([6,7,8,9,3], [8,5,7,9,3], 270, fill=False)
ShowPoint([5], [6], 60, fill=True)
label(addpt(p[0],[0,2.2]), "Labeled tree")
label(addpt(p[0],[0,1.4]), "n=4 non-leaf vertices")


# third tree is composed by 2 trees, because dist is not equal: (9–4) small
dist=[2.2, 2, 1, 0.5]
pa=[19,0]
p=btree([10,6,11,4,12,7,13,2,14,8,15,5,16,9,17,1,3],pt=pa, dist=dist, dot="frame", dotradius=r)
[circle(p[z-1], r, fill=True) for z in [1,2,3,4,5,6,7,8,9]]
ShowPoint([10,11,12,13,14,15,16,17], [5,8,2,6,1,7,10,3], 270, fill=False)

p=btree([2,1,3], pt=p[2], dist=[dist[3]], dot="frame", dotradius=r)
ShowPoint([2,3], [9,4], 270, fill=False)
label(addpt(pa,[-0.8,2.2]), "Leaf-labelled tree")
label(addpt(pa,[-0.8,1.4]), "2n+1=9 non-leaf vertices")


endfig();



    < g r a p h i c s >



Fig. 3. Trees, non-leaf vertices and divisibilities




For proving Theorem <ref>, it remains to show that
G_2n+2=∑ G(s̅) is an odd number.
Since H(s̅) is odd, we need only to
prove that the weighted Genocchi number

    f(n)=∑_s̅∈𝒮̅(2n+1) H(s̅)G(s̅)

is odd.

For example, in Fig. 2.,
G_10=G(s_1)+G(s_2)+G(s_3)=60+25+70=155,
and

    f(4)   = H(s_1)G(s_1)+H(s_2)G(s_2)+H(s_3)G(s_3)    =3·5·7·9·60
    +3·3·7·9·25+3·3·5·9·70   =(3·5·7)^2· 9.

The weighted Genocchi number f(n) is more convenient for us to study, since
it has an explicit simple expression.




	Let f(n) be the weighted Genocchi number defined in (<ref>).
	Then,

    f(n)=(1· 3 · 5 · 7 ⋯ (2n-1))^2 · (2n+1)=(2n-1)!!· (2n+1)!!.




	We successively have

    f(n)   = ∑_s̅ H(s̅)G(s̅)  
       = ∑_s̅H(s̅) (n+1) T(s̅)/2^2n
       = ∑_s̅(2n+2)! ×#s̅/2^2n+1
       = (2n+2)!/2^2n+1∑_s̅#s̅
       = (2n+2)!/2^2n+1·#𝒮(2n+1).


While #𝒮(2n+1) equals to the Catalan number C_n, we can calculate
that

    f(n)   = (2n+2)!/2^2n+1· C_n  
       = (2n+2)!/2^2n+1·1/n+12nn
       = (2n-1)!!· (2n+1)!!.



From  Theorem <ref>, the weighted Genocchi number f(n) is an odd number.
Therefore, the normal Genocchi number G_2n+2 is also odd.
This achieves the proof of Theorem <ref>.




§ GENERALIZATIONS TO K-ARY TREES
  



In this section we assume that k≥ 2 is an integer.


Recall the hook length formula for binary trees
described in Section 2.
For general rooted trees t (see <cit.>),
we also have


    #ℒ(t)=n!/∏_v∈ t h_v,

where ℒ(t) denote the set of all
increasing labelled trees of shape t.




Let L_kn+1 be the number of increasing labelled complete k-ary trees with kn+1 vertices. Then,

    L_kn+1=∑_n_1+⋯+n_k=n-1knkn_1+1, ⋯, kn_k+1L_kn_1+1⋯ L_kn_k+1.

Equivalently, the exponential generating function ϕ(x) for L_kn+1

    ϕ(x)=∑_n≥ 0L_kn+1x^kn+1/(kn+1)!

is the solution of the differential equation

    ϕ'(x)=1+ϕ^k(x)

such that ϕ(0)=0.

Let ψ(x) be the exponential generating function for
M_k^2 n-kn+k which is defined in Theorem <ref>,

    ψ(x):=
    ∑_n≥ 0M_k^2 n-kn+kx^k^2n-kn+k/(k^2n-kn+k)!.

Then

    ψ(x)=x ·ϕ(x^k-1/k!).


From identities (<ref>) and (<ref>), Theorem <ref> can be restated in the form of power series and differential equations:

Let  ψ(x) be a power series satisfying the following differential equation

    xψ'(x)-ψ(x)=k-1/k!(x^k+ψ^k(x)),

with ψ(0)=0.
Then, for each n≥ 1, the coefficient of
	x^k^2n-kn+k/(k^2n-kn+k)! in ψ(x) is an integer.
Moreover, it is congruent to

	(i)  1  k, if k=p;

	(ii) 1 p^2, if k=p^t with t≥ 2;

 (iii) 0  k, otherwise.




When k=2, L_2n+1 is just the tangent number T_2n+1 and M_2n+2 is the Genocchi number G_2n+2.
For k=3 and 4, the initial values of L_kn+1 and M_k^2 n-kn+k are
reproduced below:




    n   L_3n+1   M_6n+3
    
    	0     1     1 
    
    	1     6      70 
    
    	2     540     500500 
    
    	3     184680     43001959000
    
    	4     157600080     21100495466050000 
    
    	5     270419925600     39781831724228093500000


Table for k=3




    n   L_4n+1   M_12n+4
    
    	0     1     1  
    
    	1     24     525525  
    
    	2     32256     10258577044340625  
    
    	3     285272064     42645955937142729593062265625 
    
    	4     8967114326016     6992644904557760596067178252404694486328125

Table for k=4







Now we define an equivalence relation (k-pivoting) on the set of all (unlabelled) complete k-ary trees ℛ(kn+1).
	A basic k-pivoting  is a rearrangement of
	the k subtrees of a non-leaf vertex v.




Let r_1, r_2 be two complete k-ary trees, if r_1 can be changed to r_2 by a finite sequence of basic k-pivotings, we write r_1∼ r_2.
Hence the set of all complete k-ary trees can be partitioned into several equivalence classes. Let ℛ̅(kn+1) = ℛ(kn+1)/∼, define #ℒ(r̅) = #ℒ(r) for r ∈r̅,
then we have

    ∑_r̅∈ℛ̅(kn+1) L(r̅)= L_kn+1,

where

    L(r̅)=∑_r∈r̅#ℒ(r) = #r̅×#ℒ(r̅).




Similar to the case of the tangent numbers,
this equivalence relation implies that L(r̅) is divisible by (k!)^n.
There is still a stronger divisibility, stated as below:


	For each r̅∈ℛ̅(kn+1),
the number (k^2 n-kn+k)!L(r̅)/(kn+1)! is divisible by (k!)^kn+1.



First, we show that the coefficient (k^2 n-kn+k)!/(kn+1)! is divisible by (k-1)!^kn+1. In fact,
	
    (k^2 n-kn+k)!/(kn+1)!· (k-1)!^kn+1
    		=  (k^2n-kn+k)·∏_i=1^kn+1i(k-1)-1k-2.

	It remains to prove

    k^kn+1|(k^2 n-kn+k)! L(r̅)/(kn+1)!· (k-1)!^kn+1.


For each vertex v in a complete k-ary tree r,
we observe that the hook length h_v satisfies h_v≡ 1 k.
Thus,

    H(r̅)=∏_v∈ rh_v≡ 1 k.

Consequently, relation (<ref>) is equivalent to
	
    k^kn+1|(k^2 n-kn+k)! L(r̅)H(r̅)/(kn+1)!· (k-1)!^kn+1,

which can be rewritten  as
	
    (k!)^kn+1| (k^2 n-kn+k)! ×L(r̅)H(r̅)/(kn+1)!.


We will prove this divisibility using the following combinatorial model.
Let r be a complete k-ary tree with kn+1 vertices. It is easy to show that r has (k-1)n+1 leaves.
Replacing all leaves of r by the complete k-ary tree with k+1 vertices, we get a new tree with k^2 n-kn+k leaves, denoted by r^+.
	Let ℒ^+(r^+) be the set of all leaf-labelled tree of shape r^+, 
	obtained from r^+ by labeling all the leaves
with 1,2,…, k^2 n-kn+k.
It is clear that #ℒ^+(r^+)=(k^2 n-kn+k)!.
On the other hand,
by the hook length formula we have

    L(r̅)H(r̅)/(kn+1)!
    	= H(r̅)×#r̅×#ℒ(r)/(kn+1)!
        = #r̅.

Thus,
	the right-hand side of (<ref>) is equal to
	(k^2 n-kn+k)! ×#r̅, that is,
the number of all leaf-labelled trees of shape r^+ such that r∈r̅.







Translate the k-pivoting to the set of all leaf-labelled trees of shape r^+ such that r∈r̅. It is easy to check that the k-pivoting is still an
equivalence relation.
Since a leaf-labelled tree has kn+1 non-leaf vertices, there are (k!)^kn+1 leaf-labelled trees in each equivalence class, which
	implies that
	the right-hand side of (<ref>)
	is divisible by (k!)^kn+1.


The following two lemmas will be used for proving Theorem <ref>.


Suppose that p is prime number.
For each positive integer k,
let α(k) be the highest power of p dividing k!
and β(k) be the sum of all digits of k in base p.
	Then,

    α(k)=∑_i≥ 1⌊k/p^i⌋
    	=k-β(k)/p-1.



For the proof of Lemma <ref>, see <cit.>.


Let p≥ 3 be a prime number, then

    (pk+1)(pk+2)⋯(pk+p-1)≡ (p-1)! p^2.




The left-hand side of (<ref>) is equal to

    (pk)^p-1e_0+⋯+(pk)^2e_p-3+(pk)e_p-2+e_p-1≡ (pk)e_p-2+(p-1)!p^2,

	where e_j:=e_j(1, 2, ⋯, p-1) are the elementary symmetric functions. See <cit.>.
Since

    e_p-2=(p-1)!∑_ii^-1≡ (p-1)!∑_ii≡(p-1)!p(p-1)/2≡ 0 p,

equality	(<ref>) is true.




We are ready to prove Theorem <ref>.


The first part (a) is an immediate consequence
of Lemma <ref> and (<ref>).
Let n≥ 1,
we construct the following weighted function
	
    f(n)=∑_r̅∈ℛ̅(kn+1)H(r̅)M(r̅),

where

    M(r̅)=(k^2 n-kn+k)!  L(r̅)/(k!)^kn+1  (kn+1)!.

Since H(r̅)≡ 1 k, we have
	
    f(n)≡∑_r̅∈ℛ̅(kn+1)M(r̅) = M_k^2 n-kn+k k.

Thus, we only need to calculate f(n).

    f(n)   = ∑_r̅ H(r̅)M(r̅)  
       = ∑_r̅H(r̅) × (k^2 n-kn+k)!  L(r̅)/(k!)^kn+1  (kn+1)!
       = ∑_r̅(k^2 n-kn+k)! ×#r̅/(k!)^kn+1
       = (k^2 n-kn+k)!/(k!)^kn+1 C_k(n),

	where  C_k(n) is the number of all (unlabelled) complete k-ary trees, that is equal to the Fuss-Catalan number <cit.>

    C_k(n)=(kn)!/n!(kn-n+1)!.

Consequently,

    f(n)
    	   = (k^2 n-kn+k)!/(k!)^kn-n+1(kn-n+1)!·(kn)!/(k!)^nn!
       = ∏_i=0^kn-nik+k-1k-1×∏_j=0^n-1jk+k-1k-1.


For proving the second part (b), there are three cases to be considered
depending on the value of k.

(b1) k=p is a prime integer. We have
	
    ip+p-1p-1
     =(ip+1)(ip+2)⋯(ip+p-1)/1× 2×⋯× (p-1)≡ 1p.

	Thus f(n)≡ 1  p by identity (<ref>).

	

(b2)
k=p^t  (t≥ 2) where p is a prime integer.
	If p≥ 3,
by Lemma <ref>, we have

    ip^t+p^t-1p^t-1   =∏_s=0^p^t-1-1(ip^t+sp+1)⋯(ip^t+sp+p-1)/(sp+1)⋯(sp+p-1)·∏_s=1^p^t-1-1ip^t+sp/sp
       ≡[(p-1)!/(p-1)!]^p^t-1·ip^t-1+p^t-1-1p^t-1-1p^2
       ≡ip^t-1+p^t-1-1p^t-1-1p^2
       ≡⋯
       ≡ip+p-1p-1p^2
        = (ip+1)(ip+2)⋯(ip+p-1)/1× 2×⋯× (p-1)
       ≡ 1p^2.



Thus f(n)≡ 1p^2 for k=p^t with p≥ 3 and t≥ 2.

Now suppose p=2 and k=2^t (t≥ 2). We have

    i2^t+2^t-12^t-1   =∏_s=0^2^t-1-1i· 2^t+2s+1/2s+1·∏_s=1^2^t-1-1i· 2^t+2s/2s
        = ∏_s=0^2^t-2-1(i· 2^t+4s+1)(i· 2^t +4s+3)/(4s+1)(4s+3)·∏_s=1^2^t-1-1i· 2^t-1+s/s
       ≡(-1/-1)^2^t-2·i· 2^t-1+2^t-1-12^t-1-14
       ≡i· 2^t-1+2^t-1-12^t-1-14
       ≡⋯
       ≡i· 2+2-12-14
        = 2i+1.

Therefore, by identity (<ref>), we can check that

    f(n)≡∏_i=0^(2^t-1)n(2i+1)×∏_j=0^n-1(2j+1) ≡ 1  4.



(b3) Suppose that k has more than one prime factors. We want to prove f(n)≡ 0 k.
Let p be a prime factor of k,  and write k=b p^m with b≥ 2 and p∤ b.
Notice that 

f(n)| f(n+1) by identity (<ref>). Thus, it suffices to show that

    f(1)=	(k^2)!/(k!)^k+1≡ 0p^m,

which is equivalent to

    α(b^2 p^2m) - (bp^m+1) α(b p^m) ≥ m.

By Legendre's formula (<ref>),
the left-hand side of (<ref>)  is equal to

    Δ   = 1/p-1( b^2 p^2m - β(b^2) -(b p^m+1) (bp^m -β(b)) ) 
       = 1/p-1( β(b) - β(b^2) +b p^m β(b) -b p^m ).

Since β(b^2) ≤ b β(b) and β(b)≥ 2,  b≥ 2, we have

    Δ   ≥1/p-1( (bp^m -b +1)β(b)  -b p^m )
       ≥1/p-1( b(p^m -2) +2  )
       ≥1/p-1( 2p^m -2 )
       ≥ m.

This completes the proof.








Acknowledgments. The first author would like to thank Zhi-Ying Wen for inviting me to Tsinghua University where the paper was finalized.




10

Andre1879
D. André.
Développement de x and tan x.
C. R. Math. Acad. Sci. Paris, 88:965–979, 1879.

Aval2008
Jean-Christophe Aval.
Multivariate Fuss-Catalan numbers.
Discrete Math., 308(20):4660–4669, 2008.

Barsky1980
D. Barsky.
Congruences pour les nombres de Genocchi de deuxième espèce.
Groupe d'études d'analyse ultramétrique, Paris, 34:1–13,
  1980-81.

Carlitz1960
L. Carlitz.
The Staudt-Clausen theorem.
Math. Mag., 34:131–146, 1960/1961.

Carlitz1971
L. Carlitz.
A conjecture concerning Genocchi numbers.
Norske Vid. Selsk. Skr. (Trondheim), (9):4, 1971.

Dickson1919
Leonard Eugene Dickson.
History of the theory of numbers. Vol. I: Divisibility and
  primality.
Chelsea Publishing Co., New York, 1966.

Domaratzki2004
Michael Domaratzki.
Combinatorial interpretations of a generalization of the Genocchi
  numbers.
J. Integer Seq., 7(3):Article 04.3.6, 11, 2004.

DumontRand1994
Dominique Dumont and Arthur Randrianarivony.
Dérangements et nombres de Genocchi.
Discrete Math., 132(1-3):37–49, 1994.

Euler1755
Leonhard Euler.
Institutiones calculi differentialis, Chap. 7, volume 10 of
  Opera Mathematica 1, 1913.
1755.

FoataHan2008
Dominique Foata and Guo-Niu Han.
Principes de combinatoire classique.
(on line), 2008.
(Cours et exercices corrigés). Niveau master de mathématiques.

HanZeng1999den
Guo-Niu Han and Jiang Zeng.
q-polynômes de Gandhi et statistique de Denert.
Discrete Math., 205(1-3):119–143, 1999.

Knuth1998Vol3
Donald E. Knuth.
The art of computer programming. Vol. 3.
Addison-Wesley, Reading, MA, 1998.
Sorting and searching, Second edition.

KnuthBuckholtz1967
Donald E. Knuth and Thomas J. Buckholtz.
Computation of tangent, Euler, and Bernoulli numbers.
Math. Comp., 21:663–688, 1967.

Macdonald1995
I. G. Macdonald.
Symmetric functions and Hall polynomials.
Oxford Mathematical Monographs. The Clarendon Press Oxford University
  Press, New York, second edition, 1995.
With contributions by A. Zelevinsky, Oxford Science Publications.

Nielsen1923
Niels Nielsen.
Traité élémentaire des nombres de Bernoulli.
Gauthier-Villars, Paris, 1923.

RiordanStein1973
John Riordan and Paul R. Stein.
Proof of a conjecture on Genocchi numbers.
Discrete Math., 5:381–388, 1973.

Viennot1982
Gérard Viennot.
Interprétations combinatoires des nombres d'Euler et de
  Genocchi.
In Seminar on Number Theory, 1981/1982, pages 94, Exp. No.
  11. Univ. Bordeaux I, Talence, 1982.

ZengZhou2006
Jiang Zeng and Jin Zhou.
A q-analog of the Seidel generation of Genocchi numbers.
European J. Combin., 27(3):364–381, 2006.



