Associated Stirling Number of the First Kind

Author

Eric W. Weisstein
December 29, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/AssociatedStirlingNumberoftheFirstKind.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/AssociatedStirlingNumberoftheFirstKind.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Code

MakeBoxes[AssociatedStirlingS1[n_,k_],TraditionalForm]:=RowBox[{SubscriptBox["d","2"],"(",RowBox[{MakeBoxes[n,TraditionalForm],",",MakeBoxes[k,TraditionalForm]}],")"}]

AssociatedStirlingS1::usage="AssociatedStirlingS1[n,k] gives the associated Stirling number for the number of permutations of n having exactly k cycles, all of length >=2."

PermutationCyclesD::usage="PermutationCyclesD[r,n,k] gives the number of permutations of {1, 2, ..., n} having exactly k cycles, each of which is of length >=r."

PermutationCyclesD2::usage="PermutationCyclesD2[r,n,k] gives the number of permutations of {1, 2, ..., n} having exactly k cycles, each of which is of length >=r
by explicitly counting them."

(*
AssociatedStirlingS1[n_,k_]:=PermutationCyclesD[2,n,k]
*)

AssociatedStirlingS1[0,0]:=1
AssociatedStirlingS1[n_,k_]:=n!SeriesCoefficient[Exp[-t u](((1-t))^(-u)),{t,0,n},{u,0,k}]

(*Permutation Cycles*)
(*PermutationCyclesD[r_,0,0]:=1*)
PermutationCyclesD[r_,n_,k_]:=0/;n≤k r-1
PermutationCyclesD[r_,n_,1]:=(n-1)!
PermutationCyclesD[r_,n_,k_]:=PermutationCyclesD[r,n,k]=(n-1)PermutationCyclesD[r,n-1,k]+(-1)^(r-1)Pochhammer[-(n-1),r-1]*PermutationCyclesD[r,n-r,k-1]

(*Explicitly compute them; VERY inefficient but useful for checking*)

PermutationCyclesD2[r_,n_,k_]:=Module[{c=Map[Length,ToCycles/@Permutations[Range[n]],{2}]},Length[Select[c,Min[#]≥r&&Length[#]==k&]]]

Enumeration

Table[AssociatedStirlingS1[n,k],{n,0,7},{k,n}]

Table[n!SeriesCoefficient[Exp[-t u](((1-t))^(-u)),{t,0,n},{u,0,k}],{n,0,7},{k,n}]

Table[Sum[(-1)^(k-1) AssociatedStirlingS1[n,k],{k,n}],{n,10}]

Generating Function

Series[Exp[-t u](((1-t))^(-u)),{t,0,6},{u,0,6}]

Normal[%]//Expand

1+Sum[AssociatedStirlingS1[n,k]((t^n)/(n!))(u^k),{n,6},{k,6}]

SeriesCoefficient[Exp[-t u](((1-t))^(-u)),{t,0,n},{u,0,k}]

Primes

Table[Mod[AssociatedStirlingS1[Prime[n],k],Prime[n](Prime[n]-1)],{k,2,5},{n,10}]

Special Cases

(Subscript[d, 2])(n,1)==(n-1)!

Table[AssociatedStirlingS1[n,1],{n,10}]

Table[(n-1)!,{n,10}]

Simplify[SeriesCoefficient[Exp[-t u](((1-t))^(-u)),{u,0,1},{t,0,n}]]

FullSimplify[n! %,n>1&&n∈Integers]

FullSimplify[Gamma[n]-(n-1)!]

SeriesCoefficient[Exp[-t u](((1-t))^(-u)),{t,0,n},{u,0,1}]

Table[n!SeriesCoefficient[Exp[-t u](((1-t))^(-u)),{t,0,n},{u,0,1}],{n,10}]

(Subscript[d, 2])(2 k,k)==(2 k-1)!!

Table[AssociatedStirlingS1[2k,k],{k,10}]

Table[(2k-1)!!,{k,10}]

SeriesCoefficient[Exp[-t u](((1-t))^(-u)),{u,0,k},{t,0,2k}]

(Subscript[d, 2])(2 k+1,k)==(2/3) n (2 n+1)!!

SeriesCoefficient[Exp[-t u](((1-t))^(-u)),{u,0,k},{t,0,2k+1}]

Table[AssociatedStirlingS1[2k+1,k],{k,10}]

FindSequenceFunction[%,n]

FullSimplify[FunctionExpand[%],n∈Integers&&n>0]

<<Utilities`Simplify`

GammaSimplify[(((2^(2+n)) n Gamma[(1/2)+m])/(3 (Sqrt[π])))]/.m->n+1

FullSimplify[%]

Table[(2/3) k(1+2 k)!!,{k,10}]

(Subscript[d, 2])(2 k+2,k)==(((4 k+5) (2 k+2)!)/(18 (2^k) (k-1)!))

SeriesCoefficient[Exp[-t u](((1-t))^(-u)),{u,0,k},{t,0,2k+2}]

Table[AssociatedStirlingS1[2k+2,k],{k,10}]

Table[(4k+5)/18(2k+2)!/(k-1)!/2^k,{k,10}]

Recurrence

RSolve[{d[n+1,k]==n(d[n,k]+d[n-1,k-1]),d[0,0]==1},d[n,k],n]

Sum

(∑_m^l)(((-1))^m) (Subscript[d, 2])(l+m,m)==(((-1))^l)

Table[Sum[(((-1))^m)AssociatedStirlingS1[l+m,m],{m,l}],{l,10}]

(∑_m^l)(((((-1))^m) (Subscript[d, 2])(l+m,m))/(l+m-1))==0

Table[Sum[(((((-1))^m)AssociatedStirlingS1[l+m,m])/(l+m-1)),{m,l}],{l,10}]