Ron L.J. van den Burg - cp's OEIS frontend

User: Ron L.J. van den Burg

Ron L.J. van den Burg has authored 4 sequences.

A375254 Number of distinct ways to erect n semicircles of distinct diameters in [n] on the number line from 1 to 2n using 2 colors where all semicircles of the same color are mutually noncrossing. Two ways are regarded the same if the number line is reversed or the colors are exchanged.

0, 0, 0, 6, 4, 0, 0, 60, 186, 0, 0, 1248, 2590, 0, 0, 22820, 46384, 0, 0, 365392, 730456

Offset: 1

Ron L.J. van den Burg and Daniël Kuckartz, Aug 07 2024

a(n) is also half the number of ways to partition [2n] in n pairs, divided over two indistinct nonempty buckets such that the differences of all numbers in the pairs (the pair sizes) are distinct and all pairs in a bucket are mutually noncrossing.
a(n) is zero for n mod 4 equals 2 or 3.
Proof: (Start)
Fix n. The list of semicircle endpoint pairs { {1,2}, {3,4}, {5,6}, {7,8}, ..., {2n-1,2n} } is not a valid way, since the diameters of the n semicircles are all 1 and we need them to be distinct in [n].
However, the parity of the sum of the n diameters is the parity of n itself.
Every valid way can be retrieved by pairwise exchanges of two semicircle endpoints 1 and 2, or 2 and 3, or 3 and 4, ... or n-1 and n. The parity of the sum of the diamaters is an invariant in these pairwise exchanges.
Therefore the parity of the sum of the n diameters of all valid ways is also the same as the parity of n itself.
On the other hand, the sum of the n distings diameters is n(n+1)/2 and therefore has a parity of n(n+1)/2. Comparing the parity of n with the parity of n(n+1)/2 rules out the possibility of n being congruent to 2 or 3 mod 4.
(End)
a(n) is nonzero for n mod 4 equals 1 and n>=5.
Proof (partly by T. Skolem, Theorem 2, see link): (Start)
For n=5, an example is (2,3,red), (6,8,red), (7,10,blue), (1,5,blue), (4,9,red).
For n=4m+1 with m>=2 the following way is valid:
1) all semicircles (4m+2+r, 8m+2-r,red) for r=0..2m-1,
2) the semicircles (r,4m+1-r,red) for r=1..m,
3) the semicircle (m+1,m+2,red),
4) the semicirles (m+2+r,3m+1-r,red) for r=1..m-2,
5) two semicircles (2m+1,6m+2,blue) and (2m+2,4m+1,blue).
(End)
a(n) is also the number of planar solutions of order n for the Nickerson variant of Langford (or Langford-Skolem) problem where counting different colorings separately and considering reverse solutions and color exchanges the same. Compare with A004075 which doesn't restrict to planar solutions. Do note that here Skolem sequences can be counted multiple times. Take Skolem sequence 4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6 as an example, then these four solutions are counted separately. The numbers 1 and 3 are colored differently here:
            +---------------+
            |       +-----+ |
+-------+   |       | +-+ | |
4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
  | | +---+   | | +-----------+
  | +---------+ |
  +-------------+
            +---------------+
+-------+   |       +-----+ |
4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
  | | +---+   | | |   +-+     |
  | +---------+ | +-----------+
  +-------------+
            +---------------+
+-------+   |         +-+   |
4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
  | | +---+   | | | +-----+   |
  | +---------+ | +-----------+
  +-------------+
+-------+   +---------------+
4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
  | | +---+   | | | | +-+ |   |
  | +---------+ | | +-----+   |
  +-------------+ +-----------+
However, the following four solutions are considered the same (horizontal or vertical mirroring):
            +---------------+
            |       +-----+ |
+-------+   |       | +-+ | |
4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
  | | +---+   | | +-----------+
  | +---------+ |
  +-------------+
  +---------------+
  |       +-----+ |
  |       | +-+ | |   +-------+
6 8 3 1 1 3 6 7 5 8 2 4 2 5 7 4
+-----------+ | | +---+   | |
              | +---------+ |
              +-------------+
  +-------------+
  | +---------+ |
  | | +---+   | | +-----------+
4 7 5 2 4 2 8 5 7 6 3 1 1 3 8 6
+-------+   |       | +-+ | |
            |       +-----+ |
            +---------------+
              +-------------+
              | +---------+ |
+-----------+ | | +---+   | |
6 8 3 1 1 3 6 7 5 8 2 4 2 5 7 4
  |       | +-+ | |   +-------+
  |       +-----+ |
  +---------------+

			For n=4 the a(4)=6 ways are as follows.
If the notation for the semicircle of diameter 4 connecting 2 to 6 colored red is ({2,6},red), then the six ways are (in descending diameters 4, 3, 2, 1):
{ ({1,5},red), ({3,6},blue), ({2,4},red), ({7,8},red) },
{ ({1,5},red), ({4,7},blue), ({6,8},red), ({2,3},red) },
{ ({2,6},red), ({1,4},blue), ({3,5},red), ({7,8},red) },
{ ({1,5},blue), ({3,6},red), ({2,4},blue), ({7,8},red) },
{ ({1,5},blue), ({4,7},red), ({6,8},blue), ({2,3},red) } and
{ ({2,6},blue), ({1,4},red), ({3,5},blue), ({7,8},red) }.
The way { ({1,5},blue), ({3,6},red), ({2,4},blue), ({7,8},blue) } is considered the same as the first one listed above by exchanging red and blue.
The way { ({4,8},red), ({3,6},blue), ({5,7},red), ({1,2},red) } is also considered the same as the first one listed above by mirroring the number line (1 becomes 8, 2 becomes 7, ..., 8 becomes 1).

T. Skolem, On certain distributions of integers in pairs with given differences, Math. Scand., Vol. 5 (1957), pp. 57-68.
Wikipedia, Noncrossing partition

A348702 Square array T(n, k) (n>=1, k>=1) read by antidiagonals upwards. T(n, k) is the number of partitions of the set [n] into lists of k noncrossing sets.

Original entry on oeis.org

1, 1, 2, 1, 4, 3, 1, 8, 9, 4, 1, 14, 27, 16, 5, 1, 22, 75, 64, 25, 6, 1, 32, 183, 244, 125, 36, 7, 1, 44, 393, 844, 605, 216, 49, 8, 1, 58, 759, 2584, 2725, 1266, 343, 64, 9, 1, 74, 1347, 6976, 11105, 7026, 2359, 512, 81, 10, 1, 92, 2235, 16804, 40325, 35976, 15547, 4040, 729, 100, 11, 1, 112, 3513, 36724, 129925, 166956, 95977

Offset: 1

Ron L.J. van den Burg, Dec 13 2021

The sets may be empty. A list is an ordered set. The lists may even contain multiple empty sets.
As a square, the rows are the weighted partial sums of the rows of triangle A089231.
Given a partition P of the set {1, 2, ..., n} in a list of sets, a crossing in P are four integers [a, b, c, d] with 1 <= a < b < c < d <= n for which a, c are together in a set, and b, d are together in a different set. A list of noncrossing sets is a partition with no crossings.

			T(4, 3) = 75.
There are 3 lists with set sizes 4, 0 and 0: ({1, 2, 3, 4}, {}, {}), ..., ({}, {}, {1, 2, 3, 4}).
There are 4*6 lists with set sizes 3, 1 and 0: ({1, 2, 3}, {4}, {}), ..., ({}, {1}, {2, 3, 4}).
There are 6 lists with set sizes 2, 2 and 0 where 1 and 2 are in the same set: ({1, 2}, {3, 4}, {}), ..., ({}, {3, 4}, {1, 2}).
There are 6 lists with set sizes 2, 2 and 0 where 1 and 4 are in the same set: ({1, 4}, {2, 3}, {}), ..., ({}, {2, 3}, {1, 4}).
There are 6*6 lists with set sizes 2, 1 and 1: ({1, 2}, {3}, {4}), ..., ({2}, {1}, {3, 4}).
When adding the 6 list of crossing sets, lists with set sizes 2, 2 and 0 where 1 and 3 are in the same set, ({1, 3}, {2, 4}, {}), ..., ({}, {2, 4}, {1, 3}), then we have 81 partitions of {1, 2, 3, 4} into lists of sets. This is found in A089072(4, 3) = 81.

David Callan, Sets, Lists and Noncrossing Partitions, arXiv:0711.4841 [math.CO], 2007-2008.

T(n, k) is a rowwise weighted sum of A089231.
T(n, k) is a rowwise weighted sum of A001263.
Cf. A349740. Sets of <= k noncrossing sets.

T(n, k) = Sum_{j=1..k} binomial(k, j) k! N(n, k), for 1 <= k <= n. Where N(n, k) are the Narayana numbers of A001263.

T(n, k) = Sum_{j=1..k} binomial(k, j) A089231, for 1 <= k <= n; the rowwise weighted partial sum of the number of lists of k nonempty noncrossing sets of [n].

A349776 Triangle read by rows: T(n,k) is the number of partitions of set [n] into a set of at most k lists, with 0 <= k <= n. Also called broken permutations.

Original entry on oeis.org

1, 0, 1, 0, 2, 3, 0, 6, 12, 13, 0, 24, 60, 72, 73, 0, 120, 360, 480, 500, 501, 0, 720, 2520, 3720, 4020, 4050, 4051, 0, 5040, 20160, 32760, 36960, 37590, 37632, 37633, 0, 40320, 181440, 322560, 381360, 393120, 394296, 394352, 394353

Offset: 0

Ron L.J. van den Burg, Nov 29 2021

List means an ordered subset.

			For n=3 the T(3, 2)=12 broken permutations are {(1, 2, 3)}, {(1, 3, 2)}, {(2, 1, 3)}, {(2, 3, 1)}, {(3, 1, 2)}, {(3, 2, 1)}, {(1, 2), (3)}, {(2, 1), (3)}, {(1, 3), (2)}, {(3, 1), (2)}, {(2, 3), (1)}, {(3, 2), (1)}.
If you add the set of 3 lists {(1), (2), (3)}, you get T(3, 3) = 13 = A000262(3).
Triangle begins:
  1;
  0,   1;
  0,   2,    3;
  0,   6,   12,   13;
  0,  24,   60,   72,   73;
  0, 120,  360,  480,  500,  501;
  0, 720, 2520, 3720, 4020, 4050, 4051;
  ...

Kenneth P. Bogart, Combinatorics Through Guided Discovery, Kenneth P. Bogart, 2004, 57-58.

David Callan, Sets, Lists and Noncrossing Partitions, arXiv:0711.4841 [math.CO], 2007-2008. Also Sets, Lists and Noncrossing Partitions, Journal of Integer Sequences, Vol. 11 (2008), Article 08.1.3.
Wikipedia, The twentyfold way

Columns k=0-2 give (for n>=k): A000007, A000142, A001710.
Partial sums of A271703 per row.
Main diagonal is A000262.
Row sums give A062147(n-1) for n>=1.
Cf. A096965.

T:= proc(n, k) option remember; `if`(k<0, 0,
      binomial(n-1, k-1)*n!/k! +T(n, k-1))
    end:
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Dec 01 2021

T[n_, k_] := Sum[Binomial[n-1, n-j] n!/j!, {j, 0, k}];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 27 2023 *)

Lah(n, k) = if (n==0, 1, binomial(n-1, k-1)*n!/k!); \\ A271703
T(n, k) = sum(j=0, k, Lah(n, j)); \\ Michel Marcus, Nov 30 2021

def T(n, k):
    return sum(binomial(n, i)*falling_factorial(n-1, n-i) for i in (0..k))
print([[T(n, k) for k in (0..n)] for n in (0..9)])  # Peter Luschny, Dec 01 2021

T(n, k) = Sum_{j=0..k} A271703(n, j) for n >= 0.
T(n, n) = A000262(n).
T(n, k) = Sum_{j=0..k} binomial(n-1, n-j)*n!/j!.
T(n, k) = A000262(n) - A271703(n, k + 1) * hypergeom([1, k - n + 1], [k + 1, k + 2], -1). - Peter Luschny, Nov 30 2021
|Sum_{k=0..n} (-1)^k * T(n,k)| = A096965(n). - Alois P. Heinz, Dec 01 2021

A349740 Number of partitions of set [n] in a set of <= k noncrossing subsets. Number of Dyck n-paths with at most k peaks. Both with 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 4, 5, 0, 1, 7, 13, 14, 0, 1, 11, 31, 41, 42, 0, 1, 16, 66, 116, 131, 132, 0, 1, 22, 127, 302, 407, 428, 429, 0, 1, 29, 225, 715, 1205, 1401, 1429, 1430, 0, 1, 37, 373, 1549, 3313, 4489, 4825, 4861, 4862, 0, 1, 46, 586, 3106, 8398, 13690, 16210, 16750, 16795, 16796

Offset: 0

Ron L.J. van den Burg, Nov 28 2021

Given a partition P of the set {1,2,...,n}, a crossing in P are four integers [a, b, c, d] with 1 <= a < b < c < d <= n for which a, c are together in a block, and b, d are together in a different block. A noncrossing partition is a partition with no crossings.

			For n=4 the T(4,3)=13 partitions are {{1,2,3,4}}, {{1,2,3},{4}}, {{1,2,4},{3}}, {{1,3,4},{2}}, {{2,3,4},{1}}, {{1,2},{3,4}}, {{1,4},{2,3}}, {{1,2},{3},{4}}, {{1,3},{2},{4}}, {{1,4},{2},{3}}, {{1},{2,3},{4}}, {{1},{2,4},{3}}, {{1},{2},{3,4}}.
The set of sets {{1,3},{2,4}} is missing because it is crossing. If you add the set of 4 sets, {{1},{2},{3},{4}}, you get T(4, 4) = 14 = A000108(4), the 4th Catalan number.
Triangle begins:
  1;
  0, 1;
  0, 1,  2;
  0, 1,  4,   5;
  0, 1,  7,  13,   14;
  0, 1, 11,  31,   41,   42;
  0, 1, 16,  66,  116,  131,  132;
  0, 1, 22, 127,  302,  407,  428,  429;
  0, 1, 29, 225,  715, 1205, 1401, 1429, 1430;
  0, 1, 37, 373, 1549, 3313, 4489, 4825, 4861, 4862;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
David Callan, Sets, Lists and Noncrossing Partitions, Journal of Integer Sequences, Vol. 11 (2008), Article 08.1.3; also on arXiv, arXiv:0711.4841 [math.CO], 2007-2008.

Columns k=0-4 give (for n>=k): A000007, A000012, A000124(n-1), A116701, A116844.
Partial sums of A090181 per row.
Main diagonal is A000108.
Row sums give A088218.
T(2*n,n) gives A065097.
T(n,n-1) gives A001453 for n >= 2.
Cf. A106396, A137940.

b:= proc(x, y, t) option remember; expand(`if`(y<0
      or y>x, 0, `if`(x=0, 1, add(b(x-1, y+j, j)*
     `if`(t=1 and j<1, z, 1), j=[-1, 1]))))
    end:
T:= proc(n, k) option remember; `if`(k<0, 0,
      T(n, k-1)+coeff(b(2*n, 0$2), z, k))
    end:
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Nov 28 2021

T[n_, k_] := If[n == 0, 1, Sum[j Binomial[n, j]^2 / (n - j + 1), {j, 0, k}] / n];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Peter Luschny, Nov 29 2021 *)

T(n,k) = Sum_{j=0..k} A090181(n,j), the partial sum of the Narayana numbers.
T(n,n) = A000108(n), the n-th Catalan number.
G.f.: (1 + x - x*y - sqrt((1-x*(1+y))^2 - 4*y*x^2))/(2*x*(1-y)).
T(n,k) = (1/n)*Sum_{j=0..k} j*binomial(n,j)^2 / (n-j+1) for n >= 1. - Peter Luschny, Nov 29 2021

cp's OEIS Frontend

User: Ron L.J. van den Burg

A375254 Number of distinct ways to erect n semicircles of distinct diameters in [n] on the number line from 1 to 2n using 2 colors where all semicircles of the same color are mutually noncrossing. Two ways are regarded the same if the number line is reversed or the colors are exchanged.

Views

Author

Keywords

Comments

Examples

Links

A348702 Square array T(n, k) (n>=1, k>=1) read by antidiagonals upwards. T(n, k) is the number of partitions of the set [n] into lists of k noncrossing sets.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A349776 Triangle read by rows: T(n,k) is the number of partitions of set [n] into a set of at most k lists, with 0 <= k <= n. Also called broken permutations.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

SageMath

Formula

A349740 Number of partitions of set [n] in a set of <= k noncrossing subsets. Number of Dyck n-paths with at most k peaks. Both with 0 <= k <= n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula