0
$\begingroup$

I am in the middle of a development and I stumbled on recursively defined numbers. They don't ring a bell for me, but maybe they were already studied. Anybody has a hint?

$$ \kappa^{(k+1)}_{\delta} = \sum_{\beta = 1}^{\delta-k}\kappa^{(k)}_{\delta - \beta}\binom{\delta}{\beta} = \sum_{\beta' = k}^{\delta-1}\kappa^{(k)}_{\beta'}\binom{\delta}{\beta'} $$

with $\kappa^{(1)}_{\delta}=1$ for all $\delta$. At the beginning, they are pretty manageable. E.g. $$ \kappa^{(2)}_{\delta} = 2^{\delta} - 2 $$ $$ \kappa^{(3)}_{\delta} = 3(3^{\delta-1} - 2^{\delta} + 1 ) $$

I'm still working on finding a general solution for those numbers but I was wondering if they looked familiar to anybody.

A straightforward consequence of their definition is $$ \kappa^{(\delta)}_{\delta} = \delta\kappa^{(\delta - 1)}_{\delta - 1} = \delta! $$

I suspect they have the property $$ \sum_{k = 1}^{\delta} (-)^k\kappa^{(k)}_{\delta} = (-1)^\delta $$

edit: Those counts appear in the powers of mapping of subsets of a range $[0, D]$. You define $K^{(\alpha\beta)}$ with $\alpha > \beta$ as the function taking a pair of sets of size $\alpha$ and $\beta$ respectively and returning 1 when they intersect and 0 otherwise. Then you arrange all subsets of $[0, D]$ in a basis set so that you define $K$ as the matrix mapping all the subsets together (it is a triangular matrix). It is composed of many $K^{(\alpha\beta)}$ blocks. Those coefficient $\kappa^{(k)}_{\alpha-\beta}$ appear when you take the $k^{th}$ power of $K$. More precisely, using a kinda of notation shortcut $$ K = \sum_{\alpha = 2}^D\sum_{\beta=1}^{\alpha-1} K^{(\alpha\beta)} $$ and $$ K^k = \sum_{\alpha = k+1}^D\sum_{\beta=1}^{\alpha-k} \kappa^{(k)}_{\alpha-\beta} K^{(\alpha\beta)} $$

For two subsets $S, S'$ of the range $[0, D]$ with $S \subset S'$, $K^k(S, S')$ counts the number of ways you can split $S'\setminus S$ in $k$ subsets exactly.

$\endgroup$
4
  • 1
    $\begingroup$ Often, combinatorial identities are obtained by counting something in two different ways. Thus, if you would explain what you are counting you would increase the chance that someone would offer a good solution. $\endgroup$
    – whuber
    Commented Apr 7, 2020 at 20:24
  • $\begingroup$ I added a description of where those coefficients come from $\endgroup$
    – Wilmerton
    Commented Apr 7, 2020 at 20:41
  • $\begingroup$ Ok, your comment clearly led me somewhere (thanks!), now I am not certain how to handle this question - is it still relevant or should I delete it? $\endgroup$
    – Wilmerton
    Commented Apr 7, 2020 at 21:18
  • $\begingroup$ @Wilmerton If you have found a solution to your own question I would recommend answering your own question, for the future reference of other people. See: meta.stackexchange.com/questions/17845/… $\endgroup$
    – ajax2112
    Commented Apr 7, 2020 at 22:12

1 Answer 1

0
$\begingroup$

Following the advice @whuber of describing the combinatoric interpretation of $\kappa^{(k)}_{\alpha-\beta}$, I figured out the answer.

They corresponds to the Stirling numbers, $S(n, k)$, with an extra factorial for the ordering of the partition selection $$ \kappa^{(k)}_{\alpha-\beta} = k! S(n, k) $$

It corresponds to the definition of Triangle numbers, and are similar to the the Worpitzky numbers.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.