cp's OEIS Frontend

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.

%I A363448 #83 Jan 27 2025 11:35:05
%S A363448 1,1,1,4,9,26,77,232,725,2299,7415,24223,79983,266553,895333,3028093,
%T A363448 10303085,35243330,121128329,418080561,1448564695,5036434577,
%U A363448 17566314287,61445833012,215503978367,757666696926,2669811026147,9427368738487,33353695100085,118217920021287
%N 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.
%C A363448 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 A363448 Julien Rouyer, <a href="/A363448/b363448.txt">Table of n, a(n) for n = 0..87</a>
%H A363448 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 A363448 a(n) = A000108(n) - A363449(n).
%e A363448 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 A363448 (Sage)
%o A363448 def join_singles(sp, i, j):
%o A363448     spl = [e for e in list(sp) if i not in e and j not in e]
%o A363448     spl.append(frozenset([i, j]))
%o A363448     return SetPartition(spl)
%o A363448 def get_singles(sp):
%o A363448     return [list(e)[0] for e in sp if len(e) == 1]
%o A363448 def is_single_unjoinable(sp):
%o A363448     sgl = get_singles(sp)
%o A363448     k = len(sgl)
%o A363448     for i in range(k):
%o A363448         for j in range(i + 1, k):
%o A363448             if join_singles(sp, sgl[i], sgl[j]).is_noncrossing():
%o A363448                 return False
%o A363448     return True
%o A363448 def count_single_unjoinable(n):
%o A363448     accu = 0
%o A363448     res = []
%o A363448     for dw in DyckWords(n):
%o A363448         sp = dw.to_noncrossing_partition()
%o A363448         if is_single_unjoinable(sp):
%o A363448             accu += 1
%o A363448             res += sp
%o A363448     return accu, res
%o A363448 [count_single_unjoinable(n) for n in range(15)]
%o A363448 # _Julien Rouyer_ and _Wenjie Fang_, Apr 05 2024
%o A363448 (Sage)
%o A363448 t, P, Q = var('t, P, Q')
%o A363448 Q=t/(1-t*P)-t
%o A363448 sol=solve([P==Q/(1-Q)+t/(1-Q)^2+1],P)
%o A363448 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 A363448 n = 30 # change n to obtain more terms of the formal power series
%o A363448 (taylor(f, t,0,n)).simplify_full()
%o A363448 # _Julien Rouyer_, _Wenjie Fang_, and Alain Ninet, Apr 23 2024
%Y A363448 Cf. A000108 (noncrossing partitions), A363449.
%K A363448 nonn,hard
%O A363448 0,4
%A A363448 _Julien Rouyer_, Jun 02 2023
%E A363448 Extended by _Julien Rouyer_, Apr 23 2024