A331330 -id:A331330 - cp's OEIS frontend

A331332 Sparse ruler statistics: T(n,k) (0 <= k <= n) is the number of rulers with length n where the length of the first segment appears k times. Triangle read by rows.

1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 4, 3, 0, 1, 0, 8, 4, 3, 0, 1, 0, 14, 9, 4, 4, 0, 1, 0, 26, 16, 12, 4, 5, 0, 1, 0, 46, 34, 21, 15, 5, 6, 0, 1, 0, 85, 64, 45, 28, 20, 6, 7, 0, 1, 0, 155, 124, 90, 64, 36, 27, 7, 8, 0, 1, 0, 286, 236, 183, 128, 90, 48, 35, 8, 9, 0, 1, 0, 528, 452, 361, 269, 185, 126, 63, 44, 9, 10, 0, 1

Offset: 0

Peter Luschny, Jan 24 2020

A sparse ruler, or simply a ruler, is a strict increasing finite sequence of nonnegative integers starting from 0 called marks. See A103294 for more definitions.

			Triangle starts:
[ 0][1]
[ 1][0,   1]
[ 2][0,   1,   1]
[ 3][0,   3,   0,  1]
[ 4][0,   4,   3,  0,  1]
[ 5][0,   8,   4,  3,  0,  1]
[ 6][0,  14,   9,  4,  4,  0,  1]
[ 7][0,  26,  16, 12,  4,  5,  0, 1]
[ 8][0,  46,  34, 21, 15,  5,  6, 0, 1]
[ 9][0,  85,  64, 45, 28, 20,  6, 7, 0, 1]
[10][0, 155, 124, 90, 64, 36, 27, 7, 8, 0, 1]

Alois P. Heinz, Rows n = 0..200, flattened

Columns k=0-1 give: A000007, A331330.
Row sums give A011782.
Row sums over even columns give A331609 (for n>0).
Row sums over odd columns give A331606 (for n>0).
T(2n,n) gives A332051.
Cf. A103294, A175656.

b:= proc(n, i) option remember; `if`(n=0, x, add(expand(
     `if`(i=j, x, 1)*b(n-j, `if`(n (p-> seq(coeff(p, x, i), i=0..degree(p)))(
            `if`(n=0, 1, add(b(n-j, j), j=1..n))):
seq(T(n), n=0..12);  # Alois P. Heinz, Feb 06 2020

b[n_, i_] := b[n, i] = If[n == 0, x, Sum[Expand[If[i == j, x, 1] b[n - j, If[n < i + j, 0, i]]], {j, 1, n}]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ If[n == 0, 1, Sum[b[n - j, j], {j, 1, n}]]];
T /@ Range[0, 12] // Flatten (* Jean-François Alcover, Nov 08 2020, after Alois P. Heinz *)

def A331332_row(n):
    if n == 0: return [1]
    L = [0 for k in (0..n)]
    for c in Compositions(n):
        L[list(c).count(c[0])] += 1
    return L
for n in (0..10): print(A331332_row(n))

Sum_{k=1..n} k * T(n,k) = A175656(n-1) for n>0. - Alois P. Heinz, Feb 07 2020

A355387 Number of ways to choose a distinct subsequence of an integer composition of n.

Original entry on oeis.org

1, 2, 5, 14, 37, 98, 259, 682, 1791, 4697, 12303, 32196, 84199, 220087, 575067, 1502176, 3923117, 10244069, 26746171, 69825070, 182276806, 475804961, 1241965456, 3241732629, 8461261457, 22084402087, 57640875725, 150442742575, 392652788250, 1024810764496

Offset: 0

Gus Wiseman, Jul 04 2022

nonn

By "distinct" we mean equal subsequences are counted only once. For example, the pair (1,1)(1) is counted only once even though (1) is a subsequence of (1,1) in two ways. The version with multiplicity is A025192.

			The a(3) = 14 pairings of a composition with a chosen subsequence:
  (3)()     (3)(3)
  (21)()    (21)(1)   (21)(2)    (21)(21)
  (12)()    (12)(1)   (12)(2)    (12)(12)
  (111)()   (111)(1)  (111)(11)  (111)(111)

Christian Sievers, Table of n, a(n) for n = 0..2000

For partitions we have A000712, composable A339006.
The homogeneous version is A011782, without containment A000302.
With multiplicity we have A025192, for partitions A070933.
The strict case is A032005.
The case of strict subsequences is A236002.
The composable case is A355384, homogeneous without containment A355388.
A075900 counts compositions of each part of a partition.
A304961 counts compositions of each part of a strict partition.
A307068 counts strict compositions of each part of a composition.
A336127 counts compositions of each part of a strict composition.
Cf. A011782, A022811, A032020, A063834, A133494, A181591, A323583, A331330, A336128, A336130, A336139, A355382, A355383.

Table[Sum[Length[Union[Subsets[y]]],{y,Join@@Permutations/@IntegerPartitions[n]}],{n,0,6}]

lista(n)=my(f=sum(k=1,n,(x^k+x*O(x^n))/(1-x/(1-x)+x^k)));Vec((1-x)/((1-2*x)*(1-f))) \\ Christian Sievers, May 06 2025

G.f.: (1-x)/((1-2*x)*(1-f)) where f = Sum_{k>=1} x^k/(1-x/(1-x)+x^k) is the generating function for A331330. - Christian Sievers, May 06 2025

a(16) and beyond from Christian Sievers, May 06 2025

cp's OEIS Frontend

A331332 Sparse ruler statistics: T(n,k) (0 <= k <= n) is the number of rulers with length n where the length of the first segment appears k times. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

Formula