A363448 Number of noncrossing partitions of the n-set with no pair of singletons {i} and {j} that can be merged into {i,j} and leave the partition a noncrossing partition.

1, 1, 1, 4, 9, 26, 77, 232, 725, 2299, 7415, 24223, 79983, 266553, 895333, 3028093, 10303085, 35243330, 121128329, 418080561, 1448564695, 5036434577, 17566314287, 61445833012, 215503978367, 757666696926, 2669811026147, 9427368738487, 33353695100085, 118217920021287

Offset: 0

Author

Julien Rouyer, Jun 02 2023

Keywords

• nonn
• hard

Comments

a(n) is the number of maximal sets of noncrossing lanes in a road intersection where U-turns are forbidden and where n entries and n exits are alternated.

Examples

			The a(4)=9 noncrossing partitions of the 4-set {1,2,3,4} with no pair of singletons that can be merged (so that we still have a noncrossing partition) are [{1234}], [{12},{34}], [{23},{14}], [{4},{123}], [{3},{124}], [{2},{134}], [{1},{234}], [{13},{2},{4}], [{24},{1},{3}].
		

Links

• Julien Rouyer, Table of n, a(n) for n = 0..87
• Julien Rouyer and Alain Ninet, Two New Integer Sequences Related to Crossroads and Catalan Numbers, Article 25.1.1, Journal of Integer Sequences, Vol. 28 (2025). See also arXiv:2311.07181 [math.CO], 2023.

Crossrefs

Cf. A000108 (noncrossing partitions), A363449.

Programs

Sage

def join_singles(sp, i, j):
    spl = [e for e in list(sp) if i not in e and j not in e]
    spl.append(frozenset([i, j]))
    return SetPartition(spl)
def get_singles(sp):
    return [list(e)[0] for e in sp if len(e) == 1]
def is_single_unjoinable(sp):
    sgl = get_singles(sp)
    k = len(sgl)
    for i in range(k):
        for j in range(i + 1, k):
            if join_singles(sp, sgl[i], sgl[j]).is_noncrossing():
                return False
    return True
def count_single_unjoinable(n):
    accu = 0
    res = []
    for dw in DyckWords(n):
        sp = dw.to_noncrossing_partition()
        if is_single_unjoinable(sp):
            accu += 1
            res += sp
    return accu, res
[count_single_unjoinable(n) for n in range(15)]
# Julien Rouyer and Wenjie Fang, Apr 05 2024

Sage

t, P, Q = var('t, P, Q')
Q=t/(1-t*P)-t
sol=solve([P==Q/(1-Q)+t/(1-Q)^2+1],P)
f=sol[1].rhs()  # the generating function of the lonely singles sequence (Ln) is this solution of the cubic equation solved above (coefficients depend on t)
n = 30 # change n to obtain more terms of the formal power series
(taylor(f, t,0,n)).simplify_full()
# Julien Rouyer, Wenjie Fang, and Alain Ninet, Apr 23 2024

Formula

a(n) = A000108(n) - A363449(n).

Extensions

Extended by Julien Rouyer, Apr 23 2024