A239903 -id:A239903 - cp's OEIS frontend

A244160 a(0)=0, and for n >= 1, a(n) = the largest k such that k-th Catalan number <= n.

0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6

Offset: 0

Antti Karttunen, Jun 23 2014

nonn

Apart from 0, each n occurs A000245(n) times.

For n >= 1, a(n) gives the largest k such that C(k) <= n, where C(k) stands for the k-th Catalan number, A000108(k).

			For n=1, the largest k such that C(k) <= 1 is 1, thus a(1) = 1.
For n=2, the largest k such that C(k) <= 2 is 2, thus a(2) = 2.
For n=3, the largest k such that C(k) <= 3 is 2, thus a(3) = 2.
For n=4, the largest k such that C(k) <= 4 is 2, thus a(4) = 2.
For n=5, the largest k such that C(k) <= 5 is 3, thus a(5) = 3.

Michael De Vlieger, Table of n, a(n) for n = 0..4861

After zero, one less than A081288.

Cf. A000108, A000245, A081290, A014418, A239903, A244215, A244159, A236859, A126307.

MapIndexed[ConstantArray[First@ #2 - 1, #1] &, Differences@ Array[CatalanNumber, 8, 0]] /. {} -> {0} // Flatten (* Michael De Vlieger, Jun 08 2017 *)
Join[{0},Table[PadRight[{},CatalanNumber[n+1]-CatalanNumber[n],n],{n,6}]// Flatten] (* Harvey P. Dale, Aug 23 2021 *)

from sympy import catalan
def a(n):
    if n==0: return 0
    i=1
    while True:
        if catalan(i)>n: break
        else: i+=1
    return i - 1
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 08 2017

(define (A244160 n) (if (zero? n) n (- (A081288 n) 1)))

a(0) = 0, and for n>=1, a(n) = A081288(n)-1.

For all n>=1, A000108(a(n)) = A081290(n).

A370222 Irregular triangle T(n,k) read by rows: row n gives the inversion table (see comments) of the permutation encoded by row n of A370221.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 2, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 2, 0, 1, 2, 0, 0, 1, 2, 1, 0, 1, 2, 2, 0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0

Offset: 1

Paolo Xausa, Feb 12 2024

Knuth (2011) uses the inversion table c_1, c_2, ..., c_k (defined so that exactly c_k elements to the right of k are less than k) to encode the permutation given by row n of A370221.
This way c_1 = 0 and 0 <= c_(k+1) <= c_k + 1 for 1 <= k < m, where m >= 1 is half the length of the corresponding properly nested string of parentheses (see example).
The concatenation of terms in each row from row n = 23714 to 82498 (corresponding to strings of length 22, excluding the last one) gives the A000108(11) - 1 = 58785 terms of the finite sequence A239903.

			The following table lists c_k values for properly nested strings having lengths up to 8, along with d_k, z_k and p_k values from related combinatorial objects (see related sequences for more information). Cf. Knuth (2011), p. 442, Table 1.
.
      | Properly |          | A370219 | A370220 | A370221 |
      | Nested   | A063171  | d d d d | z z z z | p p p p | c c c c
    n | String   |   (n)    | 1 2 3 4 | 1 2 3 4 | 1 2 3 4 | 1 2 3 4
  ----+----------+----------+---------+---------+---------+---------
    1 | ()       | 10       | 1       | 1       | 1       | 0
    2 | ()()     | 1010     | 1 1     | 1 3     | 1 2     | 0 0
    3 | (())     | 1100     | 0 2     | 1 2     | 2 1     | 0 1
    4 | ()()()   | 101010   | 1 1 1   | 1 3 5   | 1 2 3   | 0 0 0
    5 | ()(())   | 101100   | 1 0 2   | 1 3 4   | 1 3 2   | 0 0 1
    6 | (())()   | 110010   | 0 2 1   | 1 2 5   | 2 1 3   | 0 1 0
    7 | (()())   | 110100   | 0 1 2   | 1 2 4   | 2 3 1   | 0 1 1
    8 | ((()))   | 111000   | 0 0 3   | 1 2 3   | 3 2 1   | 0 1 2
    9 | ()()()() | 10101010 | 1 1 1 1 | 1 3 5 7 | 1 2 3 4 | 0 0 0 0
   10 | ()()(()) | 10101100 | 1 1 0 2 | 1 3 5 6 | 1 2 4 3 | 0 0 0 1
   11 | ()(())() | 10110010 | 1 0 2 1 | 1 3 4 7 | 1 3 2 4 | 0 0 1 0
   12 | ()(()()) | 10110100 | 1 0 1 2 | 1 3 4 6 | 1 3 4 2 | 0 0 1 1
   13 | ()((())) | 10111000 | 1 0 0 3 | 1 3 4 5 | 1 4 3 2 | 0 0 1 2
   14 | (())()() | 11001010 | 0 2 1 1 | 1 2 5 7 | 2 1 3 4 | 0 1 0 0
   15 | (())(()) | 11001100 | 0 2 0 2 | 1 2 5 6 | 2 1 4 3 | 0 1 0 1
   16 | (()())() | 11010010 | 0 1 2 1 | 1 2 4 7 | 2 3 1 4 | 0 1 1 0
   17 | (()()()) | 11010100 | 0 1 1 2 | 1 2 4 6 | 2 3 4 1 | 0 1 1 1
   18 | (()(())) | 11011000 | 0 1 0 3 | 1 2 4 5 | 2 4 3 1 | 0 1 1 2
   19 | ((()))() | 11100010 | 0 0 3 1 | 1 2 3 7 | 3 2 1 4 | 0 1 2 0
   20 | ((())()) | 11100100 | 0 0 2 2 | 1 2 3 6 | 3 2 4 1 | 0 1 2 1
   21 | ((()())) | 11101000 | 0 0 1 3 | 1 2 3 5 | 3 4 2 1 | 0 1 2 2
   22 | (((()))) | 11110000 | 0 0 0 4 | 1 2 3 4 | 4 3 2 1 | 0 1 2 3

Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, pp. 440-444.

Paolo Xausa, Table of n, a(n) for n = 1..15521 (rows 1..2055 of the triangle, flattened).

Cf. A000108, A063171, A072643 (row lengths), A239903.

Cf. A370219, A370220, A370221, A370292 (row sums).

clist[m_] := With[{r = 2*Range[2, m]-1}, Reverse[Map[Join[{0}, r-#] &, Select[Subsets[Range[2, 2*m-1], {m-1}], Min[r-#] >= 0 &]]]];
Array[Delete[clist[#], 0] &, 5]
(* 2nd program: uses Algorithm Z from Knuth's TAOCP section 7.2.1.6, exercise 2 *)
zlist[m_] := Block[{z = 2*Range[m] - 1, j},
    Reap[
    While[True,
        Sow[z];
        If[z[[m-1]] < z[[m]] - 1,
            z[[m]]--,
            j = m - 1; z[[m]] = 2*m - 1;
            While[j > 1 && z[[j-1]] == z[[j]] - 1, z[[j]] = 2*j - 1; j--];
            If[j == 1,Break[]];
            z[[j]]--]
    ]][[2]][[1]]];
Join[{{0}}, Table[Delete[Map[2*Range[n] - 1 - # &, zlist[n]], 0], {n, 2, 5}]] (* Paolo Xausa, Mar 25 2024 *)

T(n,k) = 2*k - 1 - A370220(n,k).

A237449 a(n) = n - A236855(n).

Original entry on oeis.org

0, 0, 1, 1, 1, 4, 4, 5, 5, 5, 7, 7, 7, 7, 13, 13, 14, 14, 14, 17, 17, 18, 18, 18, 20, 20, 20, 20, 25, 25, 26, 26, 26, 28, 28, 28, 28, 31, 31, 31, 31, 31, 41, 41, 42, 42, 42, 45, 45, 46, 46, 46, 48, 48, 48, 48, 54, 54, 55, 55, 55, 58, 58, 59, 59, 59, 61, 61, 61, 61

Offset: 0

Antti Karttunen, Apr 18 2014

nonn

Antti Karttunen, Table of n, a(n) for n = 0..16796

Cf. A236855, A239903, A236859.

Cf. also A011371, A219641, A219651, A227190, A227191, A236840.

A236855list[m_] := With[{r = 2*Range[2, m]-1}, Reverse[Map[Total[r-#] &, Select[Subsets[Range[2, 2*m-1], {m-1}], Min[r-#] >= 0 &]]]];
With[{m = 6}, Range[0, CatalanNumber[m]-1] - A236855list[m]] (* Generates C(m) terms *) (* Paolo Xausa, Feb 20 2024 *)

Scheme
```
(define (A237449 n) (- n (A236855 n)))
```

a(n) = n - A236855(n).

cp's OEIS Frontend

A244160 a(0)=0, and for n >= 1, a(n) = the largest k such that k-th Catalan number <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A370222 Irregular triangle T(n,k) read by rows: row n gives the inversion table (see comments) of the permutation encoded by row n of A370221.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A237449 a(n) = n - A236855(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Scheme

Formula