# Young Tableaux

Emeric Deutsch (RP)[M} deutsch at magnus.poly.edu
Wed May 12 21:14:10 CEST 1999

```Hi,
By sheer coincidence, I am reading a paper where the
sequence A000085 (1,1,2,4,10,26,76, ...) comes up
(Duluck and Penaud; Discrete Math., 117, 1993, 89-105).
Defined as number of involutions (i. e. self-inverse
permutations) on n letters, one can easily derive

floor(1/2 n)
-----
\               n!
J := n ->      )       ----------------
/                       k
-----     k! (n - 2 k)! 2
k = 0
(authors refer to Lucas' Theorie des Nombres, Vol. 1).
Indeed, Maple gives
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504,
2390480, 10349536, 46206736, 211799312, 997313824, 4809701440,

I couldn't resist the simple exercise of deriving the ordinary
generating function G(z). It is defined by
> deq:=z^3*diff(G(z),z)-(1-z-z^2)*G(z)+1 = 0;

3 /d      \             2
deq := z  |-- G(z)| - (1 - z - z ) G(z) + 1 = 0
\dz     /

ic := G(0) = 1
Maple gives the solution I couldn't decipher:
1
sol := G(z) = signum(exp(- 1/2 ----)) infinity
2
z
However, with the "series" command
> sol:=dsolve({deq,ic},G(z),series);
we obtain
2      3       4       5       6        7
sol := G(z) = 1 + z + 2 z  + 4 z  + 10 z  + 26 z  + 76 z  + 232 z

8         9         10          11           12
+ 764 z  + 2620 z  + 9496 z   + 35696 z   + 140152 z   +

13            14             15             16
568504 z   + 2390480 z   + 10349536 z   + 46206736 z   +

17              18               19      20
211799312 z   + 997313824 z   + 4809701440 z   + O(z  )

Emeric

```