|
| |
|
|
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.
|
|
5
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
FORMULA
|
|
|
|
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)]
(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()
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,hard
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|