Julien Rouyer - cp's OEIS frontend

A373760 Number of noncrossing partitions of the n-set including a part containing both 1 and n (with n different from 1), with no pair of singletons {i} and {j} that can be merged into {i,j} and leave the partition a noncrossing partition.

0, 0, 1, 2, 4, 11, 30, 88, 266, 825, 2613, 8408, 27421, 90422, 300987, 1010008, 3413027, 11604237, 39668334, 136258178, 470060495, 1627913941, 5657649569, 19725571728, 68975054956, 241834515725, 849993720642, 2994348927858, 10570741932441, 37390372928207, 132497284947463

Offset: 0

Julien Rouyer, Jun 17 2024

nonn

			For n=3, the a(3)=2 partitions are {{1,3},{2}} and {{1,2,3}}.
For n=4, the a(4)=4 partitions are {{1,4},{2,3}}, {{1,2,4},{3}}, {{1,3,4},{2}} and {{1,2,3,4}}.

Julien Rouyer, Table of n, a(n) for n = 0..47

Cf. A363448 (lonely singles partitions), A363449 (marriageable singles partitions), A000108 (noncrossing partitions).

t, P, Q = var('t, P, Q')
P = Q / ( 1 - Q ) + t / ( 1 - Q )^2 + 1
solQ=solve([Q == t / (1 - t * P) - t],Q)
q=solQ[1].rhs()
n = 47
DL_Q = (taylor(q, t,0,n)).simplify_full()
Qn = DL_Q.list()
# Julien Rouyer, Wenjie Fang, and Alain Ninet, Jun 17 2024

With P the generating function of A363448, the generating function Q of (a(n)) is a solution of the system of two equations
P(t)=Q(t)/(1-Q(t))+t/(1-Q(t))^2+1
Q(t)=t/(1-tP(t))-t.

A372342 Number of noncrossing partitions of [n] that contain exactly one singleton.

Original entry on oeis.org

0, 1, 0, 3, 4, 15, 36, 105, 288, 819, 2320, 6633, 19020, 54769, 158172, 458055, 1329552, 3867075, 11267856, 32884953, 96111900, 281267469, 824083260, 2417052267, 7096175856, 20852160525, 61324675776, 180488550375, 531581605828, 1566658748079, 4620016882740, 13632008884201, 40244583972480

Offset: 0

Julien Rouyer, Apr 28 2024

Similar to A005043 and linked to A363448.

			For n=3 the a(3)=3 partitions with exactly one singleton are {{12},{3}}, {{13},{2}}, and {{1},{23}}.

Julien Rouyer, Table of n, a(n) for n = 0..299
Julien Rouyer and A. Ninet, Two New Integer Sequences Related to Crossroads and Catalan Numbers, hal-04281025, 2023. See also arXiv:2311.07181 [math.CO], 2023.

Cf. A005043, A363448.

a:= proc(n) option remember; `if`(n<2, n,
      2*(n-2)*a(n-1)/(n-1)+3*a(n-2))
    end:
seq(a(n), n=0..32);  # Alois P. Heinz, Jun 25 2024

a[n_]:=Sum[Binomial[n, m-1]*Binomial[n-m-1, m-2], {m, Floor[(n+1)/2]}]; Array[a,30,0] (* Stefano Spezia, Apr 28 2024 *)
a[n_] := (-1)^(1 - n) n Hypergeometric2F1[1 - n, 1/2, 2, 4];
Table[a[n], {n, 0, 32}]  (* Peter Luschny, Jun 25 2024 *)

seq = [0,1]
for n in range(2,20):
    up = (n+1) // 2
    s = 0
    for m in range(1,up+1):
        s += binomial(n,m-1) * binomial(n-m-1,m-2)
    seq.append(s)

a(n) = Sum_{m=1..floor((n+1)/2)} binomial(n, m-1)*binomial(n-m-1, m-2) for n != 1.

a(n) = n*A005043(n-1) for n>=1. - Ira M. Gessel, Jun 25 2024

A362137 Smallest size of an n-paradoxical tournament built as a directed Paley graph.

Original entry on oeis.org

1, 3, 7, 19, 67, 331, 1163

Offset: 0

Julien Rouyer, Jun 12 2023

An n-paradoxical tournament consists of a complete oriented 1-graph (each pair of vertices are connected by exactly one directed edge) in which all possible groups of n vertices have a common predecessor.
A Paley graph is constructed from the members of a finite field F by connecting pairs of elements that differ by a quadratic residue.
In an n-paradoxical tournament built as a directed Paley graph, a vertex x is the predecessor of a vertex y if and only if y-x is a quadratic residue of F.
a(0)=1, a(1)=3, a(2)=7 and a(3)=19 are proved to be the smallest sizes of an n-paradoxical tournament. The following a(4)=67, a(5)=331 and a(6)=1163 are only the smallest sizes of the known solutions for an n-paradoxical tournament but they are the smallest sizes of an n-paradoxical tournament built as a directed Paley graph.
All known smallest sizes of an n-paradoxical tournament are primes congruent to 3 mod 4.
No reasonable values of a(n) for n > 6 are known.
Lower and upper bounds are given in the papers given in the references section.

			For n=1, a(1)=3 vertices, each one being the predecessor of exactly one of the other two.
For n=2, a(2)=7 vertices named 0,1,2,3,4,5,6, each vertex x being the predecessor of vertices x+1, x+2, x+4 mod 7.
For n=3, a(3)=19 vertices named 0,1,2,...,18, each vertex x being the predecessor of vertices x+1, x+4, x+5, x+6, x+7, x+9, x+11, x+16, x+17 mod 19.

P. Erdős, On a Problem in Graph Theory, The Mathematical Gazette, 47.361 (1963), 220-223.
R. L. Graham and J. H. S. Spencer, A Constructive Solution to a Tournament Problem, Canadian Mathematical Bulletin 14.1, (1971), 45-48.
K. B. Reid and A. A. McRae and S.M. Hedetniemi and S. T. Hedetniemi, Domination and irredundance in tournaments, Australas. J Comb., 29 (2004), 157-172.
E. Szekeres and G. Szekeres, On a Problem of Schütte and Erdős, The Mathematical Gazette 49.369 (1965), 290-293.

a(6) corrected by Nicholas Stefan Georgescu, Jul 03 2024

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

Original entry on oeis.org

0, 0, 1, 1, 5, 16, 55, 197, 705, 2563, 9381, 34563, 128029, 476347, 1779107, 6666752, 25054585, 94401460, 356510371, 1349182629, 5115555725, 19429832443, 73916249353, 281613780638, 1074400168957, 4104279704526, 15697542046005, 60106182177517, 230394256650275, 884024296630081, 3395269379129779

Offset: 0

Julien Rouyer, Jun 02 2023

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

			The 5 noncrossing partitions of the 4-set {1234} with some pair of singletons that can be merged and leave the partition a noncrossing-partition are [{1},{2},{3},{4}], [{12},{3},{4}], [{1},{23},{4}], [{2},{3},{14}], [{1},{2},{34}].
[{1},{23},{4}] can give [{14},{23}].

Julien Rouyer, Table of n, a(n) for n = 0..87
Julien Rouyer and A. Ninet, Two New Integer Sequences Related to Crossroads and Catalan Numbers, hal-04281025, 2023. See also arXiv:2311.07181 [math.CO], 2023.

Difference between A000108 and A363448.

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

Extended by Julien Rouyer, Apr 23 2024

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.

Original entry on oeis.org

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

Julien Rouyer, Jun 02 2023

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.

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

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.

Cf. A000108 (noncrossing partitions), A363449.

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

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

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

Extended by Julien Rouyer, Apr 23 2024

cp's OEIS Frontend

User: Julien Rouyer

A373760 Number of noncrossing partitions of the n-set including a part containing both 1 and n (with n different from 1), with no pair of singletons {i} and {j} that can be merged into {i,j} and leave the partition a noncrossing partition.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Sage

Formula

A372342 Number of noncrossing partitions of [n] that contain exactly one singleton.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

Formula

A362137 Smallest size of an n-paradoxical tournament built as a directed Paley graph.

Views

Author

Keywords

Comments

Examples

Links

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

Sage

Formula

Extensions