A363448 - OEIS

%I #83 Jan 27 2025 11:35:05

%S 1,1,1,4,9,26,77,232,725,2299,7415,24223,79983,266553,895333,3028093,

%T 10303085,35243330,121128329,418080561,1448564695,5036434577,

%U 17566314287,61445833012,215503978367,757666696926,2669811026147,9427368738487,33353695100085,118217920021287

%N 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.

%C 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.

%H Julien Rouyer, <a href="/A363448/b363448.txt">Table of n, a(n) for n = 0..87</a>

%H Julien Rouyer and Alain Ninet, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL28/Rouyer/rouyer5.html">Two New Integer Sequences Related to Crossroads and Catalan Numbers</a>, Article 25.1.1, Journal of Integer Sequences, Vol. 28 (2025). See also <a href="https://arxiv.org/abs/2311.07181">arXiv:2311.07181</a> [math.CO], 2023.

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

%e 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}].

%o (Sage)

%o def join_singles(sp, i, j):

%o     spl = [e for e in list(sp) if i not in e and j not in e]

%o     spl.append(frozenset([i, j]))

%o     return SetPartition(spl)

%o def get_singles(sp):

%o     return [list(e)[0] for e in sp if len(e) == 1]

%o def is_single_unjoinable(sp):

%o     sgl = get_singles(sp)

%o     k = len(sgl)

%o     for i in range(k):

%o         for j in range(i + 1, k):

%o             if join_singles(sp, sgl[i], sgl[j]).is_noncrossing():

%o                 return False

%o     return True

%o def count_single_unjoinable(n):

%o     accu = 0

%o     res = []

%o     for dw in DyckWords(n):

%o         sp = dw.to_noncrossing_partition()

%o         if is_single_unjoinable(sp):

%o             accu += 1

%o             res += sp

%o     return accu, res

%o [count_single_unjoinable(n) for n in range(15)]

%o # _Julien Rouyer_ and _Wenjie Fang_, Apr 05 2024

%o (Sage)

%o t, P, Q = var('t, P, Q')

%o Q=t/(1-t*P)-t

%o sol=solve([P==Q/(1-Q)+t/(1-Q)^2+1],P)

%o 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)

%o n = 30 # change n to obtain more terms of the formal power series

%o (taylor(f, t,0,n)).simplify_full()

%o # _Julien Rouyer_, _Wenjie Fang_, and Alain Ninet, Apr 23 2024

%Y Cf. A000108 (noncrossing partitions), A363449.

%K nonn,hard

%O 0,4

%A _Julien Rouyer_, Jun 02 2023

%E Extended by _Julien Rouyer_, Apr 23 2024