A368279 -id:A368279 - cp's OEIS frontend

A369492 Triangle read by rows. An encoding of compositions of n where the first part is the largest part and the last part is not 1. The number of these compositions (the length of row n) is given by A368279.

1, 0, 2, 4, 8, 10, 16, 18, 22, 32, 34, 36, 38, 42, 46, 64, 66, 68, 70, 74, 76, 78, 86, 90, 94, 128, 130, 132, 134, 136, 138, 140, 142, 146, 148, 150, 154, 156, 158, 170, 174, 182, 186, 190, 256, 258, 260, 262, 264, 266, 268, 270, 274, 276, 278, 280, 282, 284, 286

Offset: 0

Peter Luschny, Jan 25 2024

The compositions are in reverse lexicographic order (see A066099).
For n = 0 we get the empty composition, which we encode by 1.
For n = 1 we get the no composition, which we encode by 0.
The definition uses two filter conditions: (a) 'the last part of the composition is not 1' and (b) 'the first part is the largest part'. By changing condition (b) to (b'), 'the parts are nonincreasing', one obtains A002865. Like the current sequence, A002865 has offset 0; the empty composition is nonincreasing (a(0) = 1), and there is no composition of 1, which has a last part that is not 1 (a(1) = 0).

			Encoding the composition as an integer, a binary string, a Dyck path, and a list.
[ n]
[ 0]    1 | 1        |  ()            | [()]
[ 1]    0 | 0        |  .             | []
[ 2]    2 | 10       |  (())          | [2]
[ 3]    4 | 100      |  ((()))        | [3]
[ 4]    8 | 1000     |  (((())))      | [4]
[ 5]   10 | 1010     |  (())(())      | [2, 2]
[ 6]   16 | 10000    |  ((((()))))    | [5]
[ 7]   18 | 10010    |  ((()))(())    | [3, 2]
[ 8]   22 | 10110    |  (())()(())    | [2, 1, 2]
[ 9]   32 | 100000   |  (((((())))))  | [6]
[10]   34 | 100010   |  (((())))(())  | [4, 2]
[11]   36 | 100100   |  ((()))((()))  | [3, 3]
[12]   38 | 100110   |  ((()))()(())  | [3, 1, 2]
[13]   42 | 101010   |  (())(())(())  | [2, 2, 2]
[14]   46 | 101110   |  (())()()(())  | [2, 1, 1, 2]
Sequence seen as table:
  [0]   1;
  [1]   0;
  [2]   2;
  [3]   4;
  [4]   8, 10;
  [5]  16, 18, 22;
  [6]  32, 34, 36, 38, 42, 46;
  [7]  64, 66, 68, 70, 74, 76, 78, 86, 90, 94;
       ...

Peter Luschny, A SageMath notebook for A368279 and A369492, Jan. 2024

Subsequences: A000079, A052548\{3,6}, A369491.

Cf. A066099, A002865, A368279, A368579.

# See the notebook in the links section, that includes a time and space efficient algorithm to generate the compositions. Alternatively, using SageMath's generator:
def pr(bw, w, dw, c):
    print(f"{bw:3d} | {str(w).ljust(7)} | {str(dw).ljust(14)} | {c}")
def Trow(n):
    row, count = [], 0
    for c in reversed(Compositions(n)):
        if c == []:
            count = 1
            pr(1, 1, "()", "[()]")
        elif c == [1]:
            pr(0, 0, ".", "[]")
        elif c[-1] != 1:
            if all(part <= c[0] for part in c):
                w = Words([0, 1])(c.to_code())
                dw = DyckWord(sum([[1]*a + [0]*a for a in c], []))
                bw = int(str(w), 2)
                row.append(bw)
                count += 1
                pr(bw, w, dw, c)
    # print(f"For n = {n} there are {count} composition of type A369492.")
    return row
for n in range(0, 7): Trow(n)

A369584 a(n) = 2^(n - 3) - A368279(n) for n >= 5, otherwise 0. Number of compositions of n whose first and last part is not equal to 1 and whose first part is not the largest part.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 2, 6, 13, 30, 65, 140, 296, 622, 1294, 2679, 5518, 11323, 23160, 47250, 96184, 195438, 396490, 803292, 1625591, 3286340, 6637913, 13397224, 27020974, 54465702, 109725932, 220944768, 444700208, 894701728, 1799419458, 3617792587, 7271505058

Offset: 0

Peter Luschny, Jan 29 2024

nonn

We consider a tripartition of the compositions of an integer n >= 1, which we sort in lexicographic order. For this purpose, we define three predicates for a composition C.
  (1) The first part of C is the largest part of C.
  (2) The first part of C is 1.
  (3) The last part of C is 1.
We thus define three classes of compositions:
  X(n): compositions for which (1) and not (3) applies;
  Y(n): compositions for which (2) or (3) applies;
  Z(n): compositions for which not (1) and not (2) and not (3) applies.
X(n), Y(n), and Z(n) are disjoint classes whose union comprises all compositions of n; they thus form a disjoint tripartition of the compositions of n. The number of these compositions are given by:
  card(Z(n)) = a(n); card(X(n)) = A368279(n); card(Y(n)) = A122391(n).

			The compositions of class Z(n) for n = 5..7 are:
  5: [2, 3];
  6: [2, 1, 3], [2, 4];
  7: [2, 1, 1, 3], [2, 1, 4], [2, 2, 3], [2, 3, 2], [2, 5], [3, 4].
The cardinalities of some tripartitions, |X(n)| + |Y(n)| + |Z(n)| = 2^(n - 1):
   5:  12 +  3 +  1 =  16;
   6:  24 +  6 +  2 =  32;
   7:  48 + 10 +  6 =  64;
   8:  96 + 19 + 13 = 128;
   9: 192 + 34 + 30 = 256;
  10: 384 + 63 + 65 = 512.

Cf. A011782, A122391, A368279.

gf := 1 + (x - 1)*(1 + x^2 / (2*x - 1) + sum(x^n / (1 - x*(1 - x^n)/(1 - x)),
n = 1..42)): ser := series(gf, x, 40): seq(coeff(ser, x, n), n = 0..36);

def A369584(n):
    if n < 5: return 0
    return 2^(n - 3) - A368279(n)
print([A369584(n) for n in range(37)])

a(n) = [x^n] (1 + (x - 1)*(1 + x^2/(2*x - 1) + Sum_{k>=1} x^k/(1 - x*(1 - x^k)/(1 - x)))).

card(X(n)) + card(Y(n)) + card(Z(n)) = A011782(n) = 2^(n - 1) for n > 0.

A368579 Triangle read by rows. T(n, k) is the number of compositions of n where the first part k is the largest part and the last part is not 1.

Original entry on oeis.org

1, -1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 2, 2, 1, 0, 1, 0, 0, 3, 3, 2, 1, 0, 1, 0, 0, 5, 6, 4, 2, 1, 0, 1, 0, 0, 8, 11, 7, 4, 2, 1, 0, 1, 0, 0, 13, 20, 14, 8, 4, 2, 1, 0, 1, 0, 0, 21, 37, 27, 15, 8, 4, 2, 1, 0, 1

Offset: 0

Peter Luschny, Jan 05 2024

			Triangle T(n, k) starts:
  [0] [ 1]
  [1] [-1, 1]
  [2] [ 0, 0, 1]
  [3] [ 0, 0, 0,  1]
  [4] [ 0, 0, 1,  0, 1]
  [5] [ 0, 0, 1,  1, 0, 1]
  [6] [ 0, 0, 2,  2, 1, 0, 1]
  [7] [ 0, 0, 3,  3, 2, 1, 0, 1]
  [8] [ 0, 0, 5,  6, 4, 2, 1, 0, 1]
  [9] [ 0, 0, 8, 11, 7, 4, 2, 1, 0, 1]
For instance, row 6 lists the compositions below:
  0  .
  1  .
  2 [2, 2, 2], [2, 1, 1, 2];
  3 [3, 3], [3, 1, 2];
  4 [4, 2];
  5  .
  6 [6].

Cf. A368279 (row sums), A092921 (generalized Fibonacci), A000045 (Fibonacci column k=2), A034008 (T(2n, n)).

from functools import cache
@cache
def F(k, n):
    return sum(F(k, n-j) for j in range(1, min(k, n))) if n > 1 else n
def Trow(n):
    return list(F(k+1, n+1-k) - F(k+1, n-k) for k in range(n+1))
print(flatten([Trow(n) for n in range(12)]))

T(n, k) = F(k+1, n+1-k) - F(k+1, n-k) where F(k, n) = Sum_{j=1..min(n, k)} F(k, n-j) if n > 1 and otherwise n. F(n, k) refers to the generalized Fibonacci numbers A092921.

A369115 Expansion of (1 - x)^(-2) * Sum_{j>=0} (x^j / (1 - Sum_{k=1..j} x^k)).

Original entry on oeis.org

1, 3, 7, 14, 26, 46, 80, 138, 239, 417, 735, 1309, 2355, 4275, 7823, 14416, 26728, 49820, 93300, 175454, 331170, 627154, 1191204, 2268604, 4330915, 8286101, 15884857, 30507175, 58686513, 113066033, 218137531, 421391695, 814999229, 1578000229, 3058458885, 5933549906

Offset: 0

Peter Luschny, Jan 21 2024

nonn

Considering more generally the family of generating functions (1 - x)^n * Sum_{j>=0} (x^j / (1 - Sum_{k=1..j} x^k)) one finds several sequences related to compositions as indicated in the cross-references.

Cf. This sequence (n=-2), A186537 left shifted (n=-1), A079500 (n=0), A368279 (n=1), A369116 (n=2).

gf := (1 - x)^(-2) * add(x^j / (1 - add(x^k, k = 1..j)), j = 0..42):
ser := series(gf, x, 40): seq(coeff(ser, x, k), k = 0..38);

Partial sums of A186537 starting at n = 1.

A369116 Expansion of (1 - x)^2 * Sum_{j>=0} (x^j / (1 - Sum_{k=1..j} x^k)).

Original entry on oeis.org

1, -1, 1, 0, 1, 1, 3, 4, 9, 15, 29, 53, 100, 186, 352, 663, 1257, 2387, 4547, 8678, 16602, 31818, 61092, 117486, 226277, 436403, 842731, 1629297, 3153466, 6109704, 11848634, 22998892, 44680016, 86869392, 169024094, 329110519, 641254825, 1250261783, 2439155631

Offset: 0

Peter Luschny, Jan 21 2024

sign

Cf. A369115 (n=-2), A186537 left shifted (n=-1), A079500 (n=0), A368279 (n=1), this sequence (n=2).

gf := (1 - x)^2 * add(x^j / (1 - add(x^k, k = 1..j)), j = 0..42):
ser := series(gf, x, 40): seq(coeff(ser, x, k), k = 0..38);

a(n) = A368279(n) - A368279(n-1) where A368279(-1) = 0.

cp's OEIS Frontend

A369492 Triangle read by rows. An encoding of compositions of n where the first part is the largest part and the last part is not 1. The number of these compositions (the length of row n) is given by A368279.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

A369584 a(n) = 2^(n - 3) - A368279(n) for n >= 5, otherwise 0. Number of compositions of n whose first and last part is not equal to 1 and whose first part is not the largest part.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

SageMath

Formula

A368579 Triangle read by rows. T(n, k) is the number of compositions of n where the first part k is the largest part and the last part is not 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python

Formula

A369115 Expansion of (1 - x)^(-2) * Sum_{j>=0} (x^j / (1 - Sum_{k=1..j} x^k)).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Formula

A369116 Expansion of (1 - x)^2 * Sum_{j>=0} (x^j / (1 - Sum_{k=1..j} x^k)).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Formula