[seqfan] Re: strangeness in A008290 : Triangle T(n, k) of rencontres numbers

[Max Alekseyev]

Here is one possible approach:

O.g.f. for the n-th row of A008290(n,k) is
n!*\sum_{i=0}^n (-1)^i/i!*(1-x)^i.
So
\sum_{k=1}^n k^w * A008290(n,k) ) = (x*d/dx)^w n!*\sum_{i=0}^n
(-1)^i/i!*(1-x)^i   at  x=1.

At the same time, (x*d/dx)^w (1-x)^i at x=1 equals S(w,i)*(-1)^i*i!,
where S(,) are Stirling numbers of 2nd kind.

Therefore,
\sum_{k=1}^n k^w * A008290(n,k) ) = n!*\sum_{i=0}^n S(w,i) = n! * B(w).

P.S. There may be a simpler way to prove the same, e.g., from formula
(8) at http://mathworld.wolfram.com/BellNumber.html

Regards,
Max



On Sun, Sep 8, 2013 at 1:32 PM, Wouter Meeussen
<wouter.meeussen at telenet.be> wrote:
> call for help/explanation/insight :   sum(k=1 ..n;  k^w  A008290(n,k) ) =
> B(w) n!  for n>=w
>
> with B(w) = 1,2,5,15,52,203,877,4140,21147,115975,578570,... (A000110 : Bell
> or exponential numbers)
> why should this be?
>
> For those who wonder what happens for n<w, look at
> sum(k=1 ..n;  k^w/n!  A008290(n,k) ) for different values of n (within rows)
> and k (successive rows)
>
>
> 0    1    1    1    1    1    1    1    1    1    1    1    1
> 0    1    2    2    2    2    2    2    2    2    2    2    2
> 0    1    4    5    5    5    5    5    5    5    5    5    5
> 0    1    8    14    15    15    15    15    15    15    15    15    15
> 0    1    16    41    51    52    52    52    52    52    52    52    52
> 0    1    32    122    187    202    203    203    203    203    203    203
> 203
> 0    1    64    365    715    855    876    877    877    877    877    877
> 877
> 0    1    128    1094    2795    3845    4111    4139    4140    4140 4140
> 4140    4140
> 0    1    256    3281    11051    18002    20648    21110    21146    21147
> 21147    21147    21147
> 0    1    512    9842    43947    86472    109299    115179    115929 115974
> 115975    115975    115975
> 0    1    1024    29525    175275    422005    601492    665479    677359
> 678514    678569    678570    678570
> 0    1    2048    88574    700075    2079475    3403127    4030523 4189550
> 4211825    4213530    4213596    4213597
>
> If we dig a bit deeper, and look at the deficits of these rows versus their
> ultimate limit, we get a new surprise:
>
> 1    0    0    0    0    0    0    0
> 2    1    0    0    0    0    0    0
> 5    4    1    0    0    0    0    0
> 15    14    7    1    0    0    0    0
> 52    51 36 11 1 0 0 0
> 203    202    171    81    16    1    0    0
> 877    876    813    512    162    22    1    0
> 4140    4139    4012    3046    1345    295    29    1
>
> with row sums = A005493 : a(n) = number of partitions of [n+1] with a
> distinguished block.
> which calculates as Sum(k=1..n; k StirlingS2[n, k] ) for n=1 .. 16
>
> It is A137650 : Triangle read by rows, A008277 * A000012.
> calculated as
> Sum(j=0..k; Binomial[k, j] BellB[n - k + j] ) for n=0..7 and k=0..n
>
> So, a closed formula for sum(k=1 ..n;  k^w  A008290(n,k) ) is up for grabs.
> No?
> Is this new?
>
> Wouter.
>
> --------------------------- for my record --------------------------
> Table[Tr/@Table[k^w /n!
> Binomial[n,k]If[n-k==0,1,Round[(n-k)!/E]],{n,0,16},{k,0,n}],{w,16}];
> Table[ BellB[w]-Tr/@Table[k^w /n!
> Binomial[n,k]If[n-k==0,1,Round[(n-k)!/E]],{n,0,15},{k,0,n}],{w,16}];
> Table[ Sum[ StirlingS2[n,n-j],{j,0,n-k}],{n,7},{k, n}];
>
>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/