A368579 -id:A368579 - cp's OEIS frontend

A368279 a(n) is the number of compositions of n where the first part is the largest part and the last part is not 1. Row sums of A368579.

1, 0, 1, 1, 2, 3, 6, 10, 19, 34, 63, 116, 216, 402, 754, 1417, 2674, 5061, 9608, 18286, 34888, 66706, 127798, 245284, 471561, 907964, 1750695, 3379992, 6533458, 12643162, 24491796, 47490688, 92170704, 179040096, 348064190, 677174709, 1318429534, 2568691317

Offset: 0

Peter Luschny, Jan 04 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.

The compositions considered here can also be understood as perfectly balanced, ordered trees. See the linked illustrations. - Peter Luschny, Feb 26 2024

			a(0) = card({[0]}) = 1.
a(1) = card({}) = 0.
a(2) = card({[2]}) = 1.
a(3) = card({[3]}) = 1.
a(4) = card({[2, 2], [4]}) = 2.
a(5) = card({[2, 1, 2], [3, 2], [5]}) = 3.
a(6) = card({[2, 2, 2], [2, 1, 1, 2], [3, 3], [3, 1, 2], [4, 2], [6]}) = 6.
a(7) = card({[2, 2, 1, 2], [2, 1, 2, 2], [2, 1, 1, 1, 2], [3, 2, 2], [3, 1, 3], [3, 1, 1, 2], [4, 3], [4, 1, 2], [5, 2], [7]}) = 10.
a(8) = card({[2, 2, 2, 2],  [2, 2, 1, 1, 2], [2, 1, 2, 1, 2], [2, 1, 1, 2, 2], [2, 1, 1, 1, 1, 2], [3, 3, 2], [3, 2, 3], [3, 2, 1, 2], [3, 1, 2, 2], [3, 1, 1, 3], [3, 1, 1, 1, 2], [4, 4], [4, 2, 2], [4, 1, 3], [4, 1, 1, 2], [5, 3], [5, 1, 2], [6, 2], [8]}) = 19.

Peter Luschny, A generator for the A368279 compositions.
Peter Luschny, Some perfectly balanced, ordered trees illustrating A368279.

Cf. A368579, A369492, A007059, A092921, A188541.

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

gf := (1 - x)*sum(x^j / (1 - sum(x^k, k = 1..j)), j = 0..42):
ser := series(gf, x, 40): seq(coeff(ser, x, n), n = 0..37);
# Peter Luschny, Jan 19 2024

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 a(n): return sum(F(k+1, n+1-k) - F(k+1, n-k) for k in range(n+1))
print([a(n) for n in range(38)])

def C(n): return sum(Compositions(n, max_part=k, inner=[k]).cardinality()
                 for k in (0..n))
def a(n): return C(n) - C(n-1) if n > 1 else 1 - n
print([a(n) for n in (0..28)])

a(n) = Sum_{k=0..n} (F(k+1, n+1-k) - F(k+1, n-k)) where F(k, n) = Sum_{j=1..min(k, n)} F(k, n-j) if n > 1 and otherwise n. F(k, n) refers to the generalized Fibonacci number A092921.
a(n) = A007059(n+1) - A007059(n).
G.f.: (1 - x)*(Sum_{j>=0} (x^j / (1 - Sum_{k=1..j} x^k ))) = (1 - x) * GfA079500. - Peter Luschny, Jan 20 2024

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.

Original entry on oeis.org

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)

cp's OEIS Frontend

A368279 a(n) is the number of compositions of n where the first part is the largest part and the last part is not 1. Row sums of A368579.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

SageMath

Formula