A216695 -id:A216695 - cp's OEIS frontend

A351637 Triangle read by rows: T(n,k) is the number of length n word structures with all distinct run-lengths using exactly k different symbols, n >= 0, k = 0..floor(sqrt(8*n+1)-1/2).

1, 0, 1, 0, 1, 0, 1, 2, 0, 1, 2, 0, 1, 4, 0, 1, 10, 6, 0, 1, 12, 6, 0, 1, 18, 12, 0, 1, 26, 18, 0, 1, 56, 96, 24, 0, 1, 64, 102, 24, 0, 1, 100, 186, 48, 0, 1, 132, 264, 72, 0, 1, 192, 420, 120, 0, 1, 350, 1344, 864, 120, 0, 1, 434, 1572, 936, 120

Offset: 0

Andrew Howroyd, Feb 15 2022

Permuting the symbols will not change the structure.

Equivalently, T(n,k) is the number of restricted growth strings [s(0), s(1), ..., s(n-1)] where s(0)=0 and s(i) <= 1 + max(prefix) for i >= 1, the maximum value is k and every run has a different length.

			Triangle begins:
  1;
  0, 1;
  0, 1;
  0, 1,   2;
  0, 1,   2;
  0, 1,   4;
  0, 1,  10,   6;
  0, 1,  12,   6;
  0, 1,  18,  12;
  0, 1,  26,  18;
  0, 1,  56,  96, 24;
  0, 1,  64, 102, 24;
  0, 1, 100, 186, 48;
  0, 1, 132, 264, 72;
  ...
The T(6,1) = 1 word is 111111.
The T(6,2) = 10 words are 111112, 111122, 111211, 111221, 112111, 112221, 112222, 122111, 122211, 122222.
The T(6,3) = 6 words are 111223, 111233, 112333, 112223, 122333, 122233.

Andrew Howroyd, Table of n, a(n) for n = 0..958 (rows 0..100)

Row sums are A351638.
Partial row sums include A000007, A000012, A032020, A351639.
Column k=2 is A216695.
Cf. A000142, A000217, A003056, A008289, A350824, A351641.

P(n) = {Vec(-1 + prod(k=1, n, 1 + y*x^k + O(x*x^n)))}
R(u, k) = {k*[subst(serlaplace(p)/y, y, k-1) | p<-u]}
T(n)={my(u=P(n), v=concat([1], sum(k=1, n, R(u, k)*sum(r=k, n, y^r*binomial(r, k)*(-1)^(r-k)/r!) ))); [Vecrev(p) | p<-v]}
{ my(A=T(16)); for(n=1, #A, print(A[n])) }

T(n,k) = Sum_{j=1..k} R(n,j)*binomial(k, j)*(-1)^(k-j)/k! for n > 0, where R(n,k) = Sum_{j=1..A003056(n)} k*(k-1)^(j-1) * j! * A008289(n,j).
T(n,k) = A350824(n,k)/k!.
T(A000217(n),n) = A000142(n). - Alois P. Heinz, Feb 15 2022

A216708 Number of compositions (ordered partitions) of n into 2 or more distinct nonnegative parts.

Original entry on oeis.org

0, 2, 2, 10, 10, 18, 48, 56, 86, 124, 298, 336, 540, 722, 1070, 2122, 2614, 3810, 5316, 7496, 9986, 18940, 22558, 33336, 44568, 63074, 82034, 114754, 187642, 234690, 328536, 441872, 602006, 794020, 1072546, 1389408, 2207532, 2706266, 3752462, 4900474, 6681022, 8574906

Offset: 0

César Eliud Lozada, Sep 16 2012

nonn

If permutations are considered equivalent then a(n)=A087135(n)=2*A000009(n) for n>0.

All terms are even. - Alois P. Heinz, Aug 18 2018

			a(2)=2 because 2 = 0+2 = 2+0 (2 ways)
a(3)=10 because 3 = 0+3 = 1+2 = 2+1 = 3+0 = 0+1+2 = 0+2+1 = 1+0+2 = 1+2+0 = 2+0+1 = 2+1+0 (10 ways)

Alois P. Heinz, Table of n, a(n) for n = 0..5000
César Eliud Lozada, Illustration for terms up to n=9

Cf. A216695, A087135, A000009, A032020.

b:= proc(n, i, p) option remember; (m-> `if`(m b(n$2, 0):
seq(a(n), n=0..42);  # Alois P. Heinz, Aug 18 2018

b[n_, i_, p_] := b[n, i, p] = With[{m = i(i+1)/2}, If[m < n, 0, If[n == 0,
     If[p == 0, 0, If[p == 1, 2, p! (p+2)]], b[n, i-1, p] +
     b[n-i, Min[n-i, i-1], p+1]]]];
a[n_] := b[n, n, 0];
a /@ Range[0, 42] (* Jean-François Alcover, Mar 05 2021, after Alois P. Heinz *)

N=66;  x='x+O('x^N);
gf=sum(k=0,N, (k+1)!*x^((k^2+k)/2) / prod(j=1,k+1, 1-x^j)) - 1/(1-x);
v=Vec(gf);
vector(#v+1,n,if(n==1,0,v[n-1]))
/* Joerg Arndt, Sep 17 2012 */

From Joerg Arndt, Sep 17 2012: (Start)
G.f. sum(k>=0, (k+1)!*x^((k^2+k)/2) / prod(j=1..k+1, 1-x^j)) - 1/(1-x);
explanation: the g.f. for partitions into at least two positive parts (A111133) is
sum(k>=0, x^((k^2+k)/2) / prod(j=1..k, 1-x^j)) - 1/(1-x)
(i.e., the g.f. of A000009 minus the g.f. 1/(1-x) for the constant sequence a(n)=1 that counts the single partition n = [n]);
the factor (k+1)! in the g.f. of this function provides for the permutations of the parts, including a zero.
(End)

More terms, Joerg Arndt, Sep 17 2012

cp's OEIS Frontend

A351637 Triangle read by rows: T(n,k) is the number of length n word structures with all distinct run-lengths using exactly k different symbols, n >= 0, k = 0..floor(sqrt(8*n+1)-1/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula