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>> x^k  
               /
              /____
               k=0



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


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

Associated Stirling (Second Kind) - {{n,k}} (lower left is {{1,1}})
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	135135	4729725	94594500
0	0	0	0	0	0	0	0	0	0	10395	270270	4099095	47507460	466876410
0	0	0	0	0	0	0	0	945	17325	190575	1636635	12122110	81431350	510880370
0	0	0	0	0	0	105	1260	9450	56980	302995	1487200	6914908	30950920	134779645
0	0	0	0	15	105	490	1918	6825	22935	74316	235092	731731	2252341	6879678
0	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	1

Second Order Eulerian Triangle - <<n,k>> - lower left is <<0,0>>
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

Sheared Second-order Stirling - A(n,k)={{n+k,k}} (lower left is A(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