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>> x^{k}/ /____ k=0 n ____ \ \ = / {{n+k,k}} x^{k-1}(1-x)^{n-k}/ /____ k=1

n ____ \ \ / <<n,k>> (1+x)^{n-k-1}x^{k}/ /____ k=0 n ____ \ \ = / {{n+k,k}} x^{k-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 Last modified: Wed Nov 21 03:23:23 AKST 2001