A395133 Number of monotone and order decreasing transformations on an n-chain.

2, 6, 23, 97, 425, 1918, 8920, 42680, 209265, 1046627, 5318019, 27364584, 142258794, 745868514, 3938883787, 20930550229, 111826991357, 600342487474, 3236786514604, 17518782803900, 95150084502117, 518433001933511, 2832926305367623, 15521475394062732, 85249962886873550

Offset

1,1

Comments

The number a(n) is obtained as the order of "the monoid of all monotone and order decreasing transformations of an n-chain". The Schroeder monoid is a subsemigroup of this monoid. This has demonstrated the relationship between a(n) and the sequence A006318.

Links

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

M. M. Zubairu, A. Umar, and F. S. Al-Kharousi, The monoid of monotone and decreasing partial transformations on a finite chain, arXiv:2512.21134 [math.GR], 2025.

Formula

a(n) = (Sum_{p=2..ceiling(n/2)} Sum_{r=p..n-p+1} binomial(r-1, p-1) * binomial(n+1, r+p)) + (1/(n+1)) * (Sum_{r=0..n} binomial(n+1, n-r) * binomial(n+r, r)).

a(n) = 1 + n - 2^(n + 1) + A000045(2n + 1) + A006318(n) = 1 + n - 2^(n + 1) + A122367(n) + A006318(n). - Robert P. P. McKone, Apr 21 2026

Mathematica

a[n_]:=(Sum[ Sum[Binomial[r-1, p-1]*Binomial[n+1, r+p], {r, p, n-p+1}], {p, 2, Ceiling[n/2]}])+(1/(n+1))*(Sum[ Binomial[n+1, n-r]*Binomial[n+r, r], {r, 0, n}]); a/@Range[1, 25] (* Robert P. P. McKone, Apr 21 2026 *)

Prog

(PARI) a395133(n) = sum(p=2, ceil(n/2), sum(r=p, n-p+1, binomial(r-1, p-1)*binomial(n+1, r+p))) + sum(r=0, n, binomial(n+1, n-r)*binomial(n+r, r))/(n+1) \\ Hugo Pfoertner, Apr 15 2026

Crossrefs

Cf. A047790 (first differences of double sum).

Cf. A006318 (added sum)/(n+1).

Cf. A000045, A122367.

Sequence in context: A389404 A150298 A391522 * A280768 A389694 A370183

Adjacent sequences: A395130 A395131 A395132 * A395134 A395135 A395136

Keyword

nonn

Author

Mansur Zubairu, Apr 10 2026

Status

approved