A365554 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.

2, 10, 60, 396, 2976, 25056, 234720, 2423520, 27371520, 335819520, 4449150720, 63318931200, 963548006400, 15614378035200, 268480048435200, 4882321001779200, 93627018326016000, 1888394741194752000, 39963486306078720000, 885457095215616000000

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.

Links

Table of n, a(n) for n=2..21.

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

Cf. A067331.

Sequence in context: A350665 A004981 A214764 * A137571 A215002 A301625

Adjacent sequences: A365551 A365552 A365553 * A365555 A365556 A365557

Keyword

nonn

Author

Brian Darrow, Jr. and Joe Fields, Feb 20 2024

Status

approved