A365554 - OEIS

%I #60 Feb 24 2024 15:31:44

%S 2,10,60,396,2976,25056,234720,2423520,27371520,335819520,4449150720,

%T 63318931200,963548006400,15614378035200,268480048435200,

%U 4882321001779200,93627018326016000,1888394741194752000,39963486306078720000,885457095215616000000

%N Number of increasing paths from the bottom to the top of the n-hypercube (as a graded poset) which first encounter a vector of isolated zeros at stage k, weighted by k.

%C 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.

%F a(n) = Sum_{k=floor(n/2)..n-1} k*(binomial(k+1,n-k)-binomial(k-1,n-k))*k!*(n-k)!.

%e For n=5, an example vector of isolated 0's is 01011, which has k=3 1's.

%e For n=3, the following paths (from 000 to 111) reach isolated 0's at k=1 many 1's (010):

%e   000,010,011,111

%e   000,010,110,111

%e The following paths reach isolated 0's only at k=2 1's:

%e   000,100,110,111

%e   000,100,101,111

%e   000,001,101,111

%e   000,001,011,111

%e So 2 paths of k=1 and 4 paths of k=2 are weighted total a(3) = 2*1 + 4*2 = 10.

%o (SageMath)

%o k, n = var('k,n')

%o sum((binomial(k+1,n-k)-binomial(k-1,n-k))*factorial(k)*factorial(n-k), k, floor(n/2),n-1)

%o (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

%Y Cf. A067331.

%K nonn

%O 2,1

%A _Brian Darrow, Jr._ and Joe Fields, Feb 20 2024