A372342 Number of noncrossing partitions of [n] that contain exactly one singleton.

0, 1, 0, 3, 4, 15, 36, 105, 288, 819, 2320, 6633, 19020, 54769, 158172, 458055, 1329552, 3867075, 11267856, 32884953, 96111900, 281267469, 824083260, 2417052267, 7096175856, 20852160525, 61324675776, 180488550375, 531581605828, 1566658748079, 4620016882740, 13632008884201, 40244583972480

Offset

0,4

Comments

Similar to A005043 and linked to A363448.

Links

Julien Rouyer, Table of n, a(n) for n = 0..299

Julien Rouyer and A. Ninet, Two New Integer Sequences Related to Crossroads and Catalan Numbers, hal-04281025, 2023. See also arXiv:2311.07181 [math.CO], 2023.

Formula

a(n) = Sum_{m=1..floor((n+1)/2)} binomial(n, m-1)*binomial(n-m-1, m-2) for n != 1.

a(n) = n*A005043(n-1) for n>=1. - Ira M. Gessel, Jun 25 2024

Example

For n=3 the a(3)=3 partitions with exactly one singleton are {{12},{3}}, {{13},{2}}, and {{1},{23}}.

Maple

a:= proc(n) option remember; `if`(n<2, n,
      2*(n-2)*a(n-1)/(n-1)+3*a(n-2))
    end:
seq(a(n), n=0..32);  # Alois P. Heinz, Jun 25 2024

Mathematica

a[n_]:=Sum[Binomial[n, m-1]*Binomial[n-m-1, m-2], {m, Floor[(n+1)/2]}]; Array[a, 30, 0] (* Stefano Spezia, Apr 28 2024 *)
a[n_] := (-1)^(1 - n) n Hypergeometric2F1[1 - n, 1/2, 2, 4];
Table[a[n], {n, 0, 32}]  (* Peter Luschny, Jun 25 2024 *)

Prog

(SageMath)
seq = [0, 1]
for n in range(2, 20):
    up = (n+1) // 2
    s = 0
    for m in range(1, up+1):
        s += binomial(n, m-1) * binomial(n-m-1, m-2)
    seq.append(s)

Crossrefs

Cf. A005043, A363448.

Sequence in context: A055486 A041665 A052133 * A332051 A209479 A209338

Adjacent sequences: A372339 A372340 A372341 * A372343 A372344 A372345

Keyword

nonn,easy

Author

Julien Rouyer, Apr 28 2024

Status

approved