# Carlitz-Riordan Identities

The associated Stirling numbers of the second kind were developed in J. Riordan's book, "An Introduction to Combinatorial Analysis" (Wiley, 1958). Now denoted by {{n,k}}, they count the ways in which n distinct objects may be partitioned into exactly k true heaps (a true heap has more than one object).

The second-order Eulerian numbers were introduced in the article "The Coefficients in an Asymptotic Expansion" by L. Carlitz (Proc. Amer. Math. Soc. 16 (1965), 248-252). They are now denoted by <<n,k>> and were shown to answer some counting problems for permutations of multisets.

The identities of the title arose recently in connection with some formal power series calculations of L. Smiley, [E-print].

```
n
____
\
\
/    <<n,k>> xk
/
/____
k=0

n
____
\
\
=  /   {{n+k,k}} xk-1 (1-x)n-k
/
/____
k=1

```
```
n
____
\
\
/    <<n,k>> (1+x)n-k-1xk
/
/____
k=0

n
____
\
\
=  /   {{n+k,k}} xk-1
/
/____
k=1

```

Whether or not Carlitz or Riordan ever wrote these down, they would certainly have come as no surprise to either. Of course we may specialize these to any complex number for x, thus deriving combinatorial identities, some known, some perhaps not. The binomial theorem and regrouping allow us to express either named number in terms of the other.

Here are some tables for small indices.

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2027025 0 0 0 0 0 0 0 0 0 0 0 0 0 135135 4729725 94594500 0 0 0 0 0 0 0 0 0 0 0 10395 270270 4099095 47507460 466876410 0 0 0 0 0 0 0 0 0 945 17325 190575 1636635 12122110 81431350 510880370 0 0 0 0 0 0 0 105 1260 9450 56980 302995 1487200 6914908 30950920 134779645 0 0 0 0 0 15 105 490 1918 6825 22935 74316 235092 731731 2252341 6879678 0 0 0 3 10 25 56 119 246 501 1012 2035 4082 8177 16368 32751 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

 0 0 0 0 0 0 0 0 0 0 0 39916800 0 0 0 0 0 0 0 0 0 0 3628800 568356480 0 0 0 0 0 0 0 0 0 362880 44339040 2507481216 0 0 0 0 0 0 0 0 40320 3733920 162186912 4642163952 0 0 0 0 0 0 0 5040 341136 11026296 238904904 4002695088 0 0 0 0 0 0 720 33984 785304 12440064 155357384 1648384304 0 0 0 0 0 120 3708 58140 644020 5765500 44765000 314369720 0 0 0 0 24 444 4400 32120 195800 1062500 5326160 25243904 0 0 0 6 58 328 1452 5610 19950 67260 218848 695038 0 0 2 8 22 52 114 240 494 1004 2026 4072 1 1 1 1 1 1 1 1 1 1 1 1

 0 0 0 0 0 0 0 2027025 91891800 2343240900 44346982680 694740296250 9540421090200 118885395048420 0 0 0 0 0 0 135135 4729725 94594500 1422280860 17892864990 199124936010 2026763158420 19282395272140 0 0 0 0 0 10395 270270 4099095 47507460 466876410 4104160060 33309926650 254752658160 1861763348445 0 0 0 0 945 17325 190575 1636635 12122110 81431350 510880370 3049616570 17539336815 98049492723 0 0 0 105 1260 9450 56980 302995 1487200 6914908 30950920 134779645 575156036 2417578670 0 0 15 105 490 1918 6825 22935 74316 235092 731731 2252341 6879678 20900922 0 3 10 25 56 119 246 501 1012 2035 4082 8177 16368 32751 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sheared Shifted Second-order Stirling - F(n,k)={{n+k+1,k+1}} (lower left is F(1,0))

We display the last table and its two captions so that we may note the following "inverse pair" (hommage to Riordan's book "Combinatorial Identities"):

```
n
____
\
\
F(n,k)  =  /    <<n,j>> C(n-j-1,k-j)
/
/____
j=0

n
____
\
\
<<n,k>> =  /   (-1)k-j F(n,j) C(n-j-1,k-j)
/
/____
k=1

```

where C(p,q) is the binomial coefficient.

Len Smiley