A371698 Number of partial order-preserving or -reversing transformations of a chain of length n.

2, 9, 54, 323, 1848, 10293, 56738, 312327, 1723692, 9549785, 53121654, 296593547, 1661423104, 9333552509, 52565738570, 296696569871, 1677887732820, 9505147063713, 53928737011358, 306393222740883, 1742919983985192, 9925790283119429, 56584658970159474, 322879453747840023

Offset: 1

Author

James Mitchell, Apr 03 2024

Keywords

• nonn

Links

• V. H. Fernandes, G. M. S. Gomes, and M. M. Jesus, Presentations for some monoids of partial transformations on a finite chain, Communications in Algebra, 33 (2005), 587-604, 2005.

Crossrefs

Cf. A002003.

Programs

GAP

List([1..40], n -> 4 * Sum([0 .. n - 1], k ->  Binomial(n - 1, k) * Binomial(n + k, k)) - (1 + n * (2 ^ n - 1)));

PARI

a(n) = 4 * sum(k=0, n-1, binomial(n -1, k)*binomial(n + k, k)) - (1 + n * (2 ^ n - 1)); \\ Michel Marcus, Apr 03 2024

Formula

a(n) = 4*Sum_{k=0..n-1} binomial(n-1, k)*binomial(n+k, k) - (1 + n*(2 ^ n - 1)).

a(n) = 2*A002003(n) - (1 + n*(2^n - 1)).