OFFSET
2,1
COMMENTS
These are the numerators in calculating an expected value. The expectation of the number of steps one takes in marking the elements of a predetermined list before reaching a state where only isolated unmarked entries remain.
FORMULA
a(n) = Sum_{k=floor(n/2)..n-1} k*(binomial(k+1,n-k)-binomial(k-1,n-k))*k!*(n-k)!.
EXAMPLE
For n=5, an example vector of isolated 0's is 01011, which has k=3 1's.
For n=3, the following paths (from 000 to 111) reach isolated 0's at k=1 many 1's (010):
000,010,011,111
000,010,110,111
The following paths reach isolated 0's only at k=2 1's:
000,100,110,111
000,100,101,111
000,001,101,111
000,001,011,111
So 2 paths of k=1 and 4 paths of k=2 are weighted total a(3) = 2*1 + 4*2 = 10.
PROG
(SageMath)
k, n = var('k, n')
sum((binomial(k+1, n-k)-binomial(k-1, n-k))*factorial(k)*factorial(n-k), k, floor(n/2), n-1)
(PARI) a(n) = sum(k=n\2, n-1, k*(binomial(k+1, n-k)-binomial(k-1, n-k))*k!*(n-k)!) \\ Andrew Howroyd, Feb 23 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Brian Darrow, Jr. and Joe Fields, Feb 20 2024
STATUS
approved