A129715 -id:A129715 - cp's OEIS frontend

A241701 Number T(n,k) of Carlitz compositions of n with exactly k descents; triangle T(n,k), n>=0, 0<=k<=floor(n/3), read by rows.

1, 1, 1, 2, 1, 2, 2, 3, 4, 4, 8, 2, 5, 13, 5, 6, 21, 12, 8, 33, 27, 3, 10, 50, 53, 11, 12, 73, 98, 31, 15, 106, 174, 78, 5, 18, 150, 296, 175, 22, 22, 209, 486, 363, 72, 27, 289, 781, 715, 204, 8, 32, 393, 1222, 1342, 510, 43, 38, 529, 1874, 2421, 1168, 159

Offset: 0

Alois P. Heinz, Apr 27 2014

No two adjacent parts of a Carlitz composition are equal.

			T(6,0) = 4: [6], [1,5], [2,4], [1,2,3].
T(6,1) = 8: [4,2], [5,1], [3,1,2], [1,3,2], [1,4,1], [2,3,1], [2,1,3], [1,2,1,2].
T(6,2) = 2: [3,2,1], [2,1,2,1].
T(7,0) = 5: [7], [3,4], [1,6], [2,5], [1,2,4].
T(7,1) = 13: [4,3], [6,1], [5,2], [2,1,4], [4,1,2], [1,4,2], [2,3,2], [3,1,3], [1,5,1], [2,4,1], [1,2,3,1], [1,3,1,2], [1,2,1,3].
T(7,2) = 5: [4,2,1], [2,1,3,1], [3,1,2,1], [1,3,2,1], [1,2,1,2,1].
Triangle T(n,k) begins:
00:   1;
01:   1;
02:   1;
03:   2,   1;
04:   2,   2;
05:   3,   4;
06:   4,   8,   2;
07:   5,  13,   5;
08:   6,  21,  12;
09:   8,  33,  27,   3;
10:  10,  50,  53,  11;
11:  12,  73,  98,  31;
12:  15, 106, 174,  78,   5;
13:  18, 150, 296, 175,  22;
14:  22, 209, 486, 363,  72;
15:  27, 289, 781, 715, 204, 8;

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

Columns k=0-10 give: A000009, A241691, A241692, A241693, A241694, A241695, A241696, A241697, A241698, A241699, A241700.
Row sums give A003242.
T(3n,n) = A000045(n+1).
T(3n+1,n) = A129715(n) for n>0.
Cf. A238344, A285994.

b:= proc(n, i) option remember; `if`(n=0, 1, expand(
      add(`if`(j=i, 0, b(n-j, j)*`if`(j (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..20);

b[n_, i_] := b[n, i] = If[n == 0, 1, Expand[Sum[If[j == i, 0, b[n-j, j]*If[jJean-François Alcover, Feb 13 2015, after Alois P. Heinz *)

Sum_{k=0..floor(n/3)} (k+1) * T(n,k) = A285994(n) (for n>0).

A129714 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k runs (0<=k<=n). A Fibonacci binary word is a binary word having no 00 subword. A run is a maximal sequence of consecutive identical letters.

Original entry on oeis.org

1, 0, 2, 0, 1, 2, 0, 1, 2, 2, 0, 1, 2, 3, 2, 0, 1, 2, 4, 4, 2, 0, 1, 2, 5, 6, 5, 2, 0, 1, 2, 6, 8, 9, 6, 2, 0, 1, 2, 7, 10, 14, 12, 7, 2, 0, 1, 2, 8, 12, 20, 20, 16, 8, 2, 0, 1, 2, 9, 14, 27, 30, 30, 20, 9, 2, 0, 1, 2, 10, 16, 35, 42, 50, 40, 25, 10, 2, 0, 1, 2, 11, 18, 44, 56, 77, 70, 55, 30, 11, 2

Offset: 0

Emeric Deutsch, May 12 2007

Row sums are the Fibonacci numbers (A000045).

			T(5,3)=4 because we have 10111, 11011, 11101 and 01110.
Triangle starts:
  1;
  0,2;
  0,1,2;
  0,1,2,2;
  0,1,2,3,2;
  0,1,2,4,4,2;

M. Henk, J. Richter-Gebert and G. M. Ziegler, Basic properties of convex polytopes, Discrete and Computational Geometry, J.E. Goodman and J. O'Rourke eds., CRC Press, Boca Raton, Florida, 1997, Second Edition, 2004, 355-383.

Cf. A000045, A065941, A073044, A129715.

T:=proc(n,k): if k<0 then 0 elif k=0 and n=0 then 1 elif k=0 then 0 elif n=1 and k=1 then 2 elif n=2 and k=1 then 1 elif n=2 and k=2 then 2 elif k>n then 0 else T(n-1,k)+T(n-2,k-2) fi end: for n from 0 to 14 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

T[n_, k_] := T[n, k] = Which[k < 0, 0, k == 0 && n == 0, 1, k == 0, 0, n == 1 && k == 1, 2, n == 2 && k == 1, 1, n == 2 && k == 2, 2, k > n, 0, True, T[n-1, k] + T[n-2, k-2]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Aug 23 2024, after Maple program *)

T(n,k) = A073044(n,n-k) (since in each Fibonacci binary word of length n the number of runs plus the number of 11's is equal to n).
Sum_{k=0..n} k*T(n,k) = A129715(n).
G.f.: G(t,z)=(1+tz)(1-z+tz)/(1-z-t^2*z^2).
T(n,k) = T(n-1,k)+T(n-2,k-2) for n>=3, k>=1 (see the Maple program).
For n >=1, T(n+1,k+1) = binomial(n-floor((k+1)/2),floor(k/2)) + binomial(n-1-floor(k/2),floor((k-1)/2)) = A065941(n,k) + A065941(n-1,k-1). T(n+1,2k) = 2*binomial(n-k,k-1) and T(n+1,2k+1) = n/(n-k)*binomial(n-k,k). For 0 <= k < n and n >=1, T(n+1,k+1) equals the number of facets of the k-dimensional cyclic polytope C_k(n), defined as the convex hull of the n points (1,1^2,...,1^k),...,(n,n^2,...n^k) in R^k [see Henk et al., p.11]. [Peter Bala, Sep 25 2008]

cp's OEIS Frontend

A241701 Number T(n,k) of Carlitz compositions of n with exactly k descents; triangle T(n,k), n>=0, 0<=k<=floor(n/3), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula