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,1

Links

Table of n, a(n) for n=1..24.

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.

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

Prog

(GAP) 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

Crossrefs

Cf. A002003.

Sequence in context: A360454 A073986 A223943 * A241125 A370474 A089436

Adjacent sequences: A371695 A371696 A371697 * A371699 A371700 A371701

Keyword

nonn

Author

James Mitchell, Apr 03 2024

Status

approved