Unsigned Stirling numbers of the first kind

[dodo]

While toying with the factorial function, I stumbled with the following definition:

Let P_k^{\,n} be the sum of all possible products of k different factors, taken from {1,2,3,...n}.

For example, P_3^{\,4} = 1.2.3 + 1.2.4 + 1.3.4 + 2.3.4 = 50

Now, according to the Sloane site, this guys turn to be the (unsigned) Stirling numbers of the first kind (with the indexes shifted; actually, P_k^{\,n} = |S1(n+1,n+1-k)|), but I fail to see an immediate relation between the above statement and the usual definition.

A possible route might involve proving that "my" numbers follow the recurrence relation |S1(n,k)| = |S1(n-1,k-1)| + n . |S1(n-1,k)|.

But, before I start scribbling (I'm lazy), can somebody provide a hint, or a link? Thanks! Contribute to avoid the reinvention of the wheel!

 

[dodo]

Too late. I already did the scribbling:

Let P be the power set of {1,2,3,...,n}. Let C be the collection of all sets S in P with cardinality exactly k.

Let f(S) be the product of all integers in the set S. Let F(X) be the sum of all f(S), for all sets S in X.

Partition C in two: let C1 be the subset of C made of all sets that actually contain the number n, and C0 be the other sets, those which do not contain n. Note that F(C) = F(C0) + F(C1), since C0 and C1 are a partition of C.

C0 can be seen as the collection of all subsets of {1,2,3,...n-1} with cardinality exactly k, since the number n was not in any of these subsets.

Now think 'taking out the common factor n from F(C1)'. Let R be the collection of all sets from C1, but with the number n removed from each set. R can now be seen as the collection of all subsets of {1,2,3,...,n-1} with cardinality exactly k-1.

Clearly, F(C1) = n F(R); thus, F(C) = F(C0) + n F(R). Ta da!

(Note that, with respect to the Stirling numbers of the first kind, the index k runs here in the opposite direction, that's why the factor n seems in the wrong place.)

I still fail to see any conceptual relationship, though. What has this to do with permutation cycles, beats me.

 

[Provol]

I stumbled with the same algorithm while untwisting the Taylor expansion of (ln(1-x))^-m , whose nth coefficient is known to be m!/n! St1(n,m), and where St1(n,m) is the unsigned Stirling N. of the first kind.
Actually, from that expansion it turns out that for an exact match with St1(n,m) one shall consider the following version of the construction:
St1(n,m) is the sum of all possible products of n-m factors taken from {0,1,2,...,n-1}, while convening of assigning the value of 1 to the empty condition n=m, also in the case n=m=0.
Then it is easy to verify that this scheme (canceling m factors out of the product of the n terms) satisfies the classical recurrence for the unsigned Stirling N. of the first kind, i.e.:
St1(n,m) = St1(n-1,m-1) (last term canceled) + (n-1)*St1(n-1,m) (last term included).
with the same contour conditions.
But then, what is the conceptual relation between this scheme and the permutation cycles puzzles me as well.
And to make the whole more intriguing, there is a further scheme to be included in the bundle, which stems out of the mth-power of the Taylor series for -ln(1-x) and which gives:
St1(n,m) = n! / m! * sum of the inverses of all possible products of m integers >=1 summing to n (repetitions and permutations allowed).
e.g. St1(4,3) = 4!/3! *((1/(1*1*2))+1/(1*2*1)+1/(2*1*1)) = 4*3/2 = 6.
In the literature I found it to be called the "generalized power series" for Stirling N. of the first kind.