OFFSET
0,4
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.
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.
EXAMPLE
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}].
PROG
(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
CROSSREFS
KEYWORD
nonn,hard
AUTHOR
Julien Rouyer, Jun 02 2023
EXTENSIONS
Extended by Julien Rouyer, Apr 23 2024
STATUS
approved