0
$\begingroup$

I'm trying to find an explicit number theory definition of the Stirling numbers of the first kind in reverse as $|s(n,k)|$ not $|s(n,n-k)|$, not the way it's usually written. Here is the typical definition in most books

$$ |s(n,n-k)|=\prod_{l=1}^{k} \sum_{i_l=0}^{i_{l-1}-1} i_l , \quad i_o=n $$

Or alternatively

$$ |s(n,n-k)|=\sum_{0 \leq i_1 < i_2 < ... < i_k < n} i_1 i_2 ... i_k =\sum_{i_1=0}^{n-1}i_1\sum_{i_2=0}^{i_1-1}i_2...\sum_{i_k=0}^{i_{k-1}-1}i_k $$

In Gould's book on Stirling numbers, he cites a reverse formula, but it doesn't really enumerate into the same result, or seems either shifted or incorrect $$ |s(n,k)|=\prod_{l=1}^{k} \sum_{i_l=i_{l+1}+1}^{n-l+1} i_l , \quad i_{k+1}=0 $$

Or

$$ |s(n,k)|=\sum_{i_k=1}^{n-k+1} i_k \sum_{i_{k-1}=i_k+1}^{n-k+2}i_{k-1}...\sum_{i_2=i_3+1}^{n-1} i_2 \sum_{i_1=i_2+1}^{n}i_1 $$

where it is known that for some index $l$ and positive integers $s,m$

$$ \sum_{k=l+s}^{m} k=-(\sum_{k=0}^{l+s-1} k - \sum_{k=0}^{m} k) $$

For example, this result for $|s(n,k)|$ in the case of $n=5,k=2$ gives

$$ \sum_{i_2=1}^{4} i_2 \sum_{i_1=i_2+1}^{5} i_1 = \sum_{i_2=1}^{4} i_2(-{i_2 \choose 2}+15)=85=|s(6,4)| $$

I'm not trying to find an easy way to compute Stirling numbers, or use recurrence relations on a computer. The question is about specifically the formula for $|s(n,k)|$ any help would be appreciated

$\endgroup$

2 Answers 2

1
$\begingroup$

For ease of writing, for any $S\subseteq \{1,\dots,n-1\}$, define $\pi_S$ to be the product of the elements in $S$. The first formula you have can be written $$ |s(n,n-k)]=\sum_{|S|=k}\pi_S, $$ where the sum ranges over subsets of $\{1,\dots,n-1\}$ with size $k$.

One such formula is $$ \boxed{|s(n,k)|=\sum_{|S|=k}\frac{(n-1)!}{\pi_S}} $$ Proof: For any $S\subseteq \{1,\dots,n-1\}$, whose comeplement is $S'$, we have $$ \pi_S\cdot \pi_{S'}=(n-1)!. $$ Therefore, $$ |s(n,k)|=\sum_{|S|=n-k}\pi_S=\sum_{|S|=n-k}\frac{(n-1)!}{\pi_{S'}}=\sum_{|S|=k}\frac{(n-1)!}{\pi_S} $$

$\endgroup$
0
$\begingroup$

From computing more values, looks like the answer is this, for $0 \leq k \leq n-1$

$$ |s(n,k)|=\sum_{i_{n-k}=1}^{0} i_{n-k} \sum_{i_{n-k-1}=i_{n-k}+1}^{1}i_{n-k-1}...\sum_{i_2=i_3+1}^{k-1}i_2 \sum_{i_1=i_2+1}^{k}i_1 $$

$$ |s(n,k)|=\sum_{i_{n-k}=1}^{k} i_{n-k} \sum_{i_{n-k-1}=i_{n-k}+1}^{k-1}i_{n-k-1}...\sum_{i_2=i_3+1}^{n-2}i_2 \sum_{i_1=i_2+1}^{n-1}i_1 $$

or

$$ |s(n,k)|=\sum_{0 \leq i_1 < i_2 < ... < i_{n-k} \leq k} i_1 i_2 ... i_{n-k}=\prod_{l=1}^{n-k}\sum_{i_l=i_{l+1}+1}^{k-l+1}i_l, \quad i_{n-k+1}=0 $$

and $|s(n,n)|=1$

If anyone has a better way this is re-written, it would be interesting to know

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .