A225084 -id:A225084 - cp's OEIS frontend

A238130 Triangle read by rows: T(n,k) is the number of compositions into nonzero parts with k parts directly followed by a different part, n>=0, 0<=k<=n.

1, 1, 0, 2, 0, 0, 2, 2, 0, 0, 3, 4, 1, 0, 0, 2, 10, 4, 0, 0, 0, 4, 12, 14, 2, 0, 0, 0, 2, 22, 29, 10, 1, 0, 0, 0, 4, 26, 56, 36, 6, 0, 0, 0, 0, 3, 34, 100, 86, 31, 2, 0, 0, 0, 0, 4, 44, 148, 200, 99, 16, 1, 0, 0, 0, 0, 2, 54, 230, 374, 278, 78, 8, 0, 0, 0, 0, 0, 6, 58, 322, 680, 654, 274, 52, 2, 0, 0, 0, 0, 0

Offset: 0

Joerg Arndt and Alois P. Heinz, Feb 21 2014

First column (k=0) is A000005, second column (k=1) is 2*A002133.

Row sums are A011782.

			Triangle starts:
00:  1,
01:  1, 0,
02:  2, 0, 0,
03:  2, 2, 0, 0,
04:  3, 4, 1, 0, 0,
05:  2, 10, 4, 0, 0, 0,
06:  4, 12, 14, 2, 0, 0, 0,
07:  2, 22, 29, 10, 1, 0, 0, 0,
08:  4, 26, 56, 36, 6, 0, 0, 0, 0,
09:  3, 34, 100, 86, 31, 2, 0, 0, 0, 0,
10:  4, 44, 148, 200, 99, 16, 1, 0, 0, 0, 0,
11:  2, 54, 230, 374, 278, 78, 8, 0, 0, 0, 0, 0,
12:  6, 58, 322, 680, 654, 274, 52, 2, 0, 0, 0, 0, 0,
13:  2, 74, 446, 1122, 1390, 814, 225, 22, 1, 0, 0, 0, 0, 0,
...
Row 5 is [2, 10, 4, 0, 0, 0] because in the 16 compositions of 5
##:  [composition]  no. of changes
01:  [ 1 1 1 1 1 ]   0
02:  [ 1 1 1 2 ]   1
03:  [ 1 1 2 1 ]   2
04:  [ 1 1 3 ]   1
05:  [ 1 2 1 1 ]   2
06:  [ 1 2 2 ]   1
07:  [ 1 3 1 ]   2
08:  [ 1 4 ]   1
09:  [ 2 1 1 1 ]   1
10:  [ 2 1 2 ]   2
11:  [ 2 2 1 ]   1
12:  [ 2 3 ]   1
13:  [ 3 1 1 ]   1
14:  [ 3 2 ]   1
15:  [ 4 1 ]   1
16:  [ 5 ]   0
there are 2 with no changes, 10 with one change, and 4 with two changes.

Joerg Arndt and Alois P. Heinz, Rows n = 0..140, flattened

Cf. A238279 (same sequence with zeros omitted).
Cf. A106356 (compositions with k successive parts same).
Cf. A225084 (compositions with maximal up-step k).

b:= proc(n, v) option remember; `if`(n=0, 1, expand(
      add(b(n-i, i)*`if`(v=0 or v=i, 1, x), i=1..n)))
    end:
T:= n-> seq(coeff(b(n, 0), x, i), i=0..n):
seq(T(n), n=0..14);

b[n_, v_] := b[n, v] = If[n == 0, 1, Sum[b[n-i, i]*If[v == 0 || v == i, 1, x], {i, 1, n}]]; T[n_] := Table[Coefficient[b[n, 0], x, i], {i, 0, n}]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Jan 12 2015, translated from Maple *)

A059570 Number of fixed points in all 231-avoiding involutions in S_n.

Original entry on oeis.org

1, 2, 6, 14, 34, 78, 178, 398, 882, 1934, 4210, 9102, 19570, 41870, 89202, 189326, 400498, 844686, 1776754, 3728270, 7806066, 16311182, 34020466, 70837134, 147266674, 305718158, 633805938, 1312351118, 2714180722, 5607318414, 11572550770, 23860929422

Offset: 1

Emeric Deutsch, Feb 16 2001

Number of odd parts in all compositions (ordered partitions) of n: a(3)=6 because in 3=2+1=1+2=1+1+1 we have 6 odd parts. Number of even parts in all compositions (ordered partitions) of n+1: a(3)=6 because in 4=3+1=1+3=2+2=2+1+1=1+2+1=1+1+2=1+1+1+1 we have 6 even parts.
Convolved with (1, 2, 2, 2, ...) = A001787: (1, 4, 12, 32, 80, ...). - Gary W. Adamson, May 23 2009
An elephant sequence, see A175654. For the corner squares 36 A[5] vectors, with decimal values between 15 and 480, lead to this sequence. For the central square these vectors lead to the companion sequence 4*A172481, for n>=-1. - Johannes W. Meijer, Aug 15 2010
a(n) is the total number of runs of equal parts in the compositions of n. a(5) = 34 because there are 34 runs of equal parts in the compositions of 5, with parentheses enclosing each run: (5), (4)(1), (1)(4), (3)(2), (2)(3), (3)(1,1), (1)(3)(1), (1,1)(3), (2,2)(1), (2)(1)(2), (1)(2,2), (2)(1,1,1), (1)(2)(1,1), (1,1)(2)(1), (1,1,1)(2), (1,1,1,1,1). - Gregory L. Simay, Apr 28 2017
a(n) - a(n-2) is the number of 1's in all compositions of n and more generally, the number of k's in all compositions of n+k-1. - Gregory L. Simay, May 01 2017

			a(3) = 6 because in the 231-avoiding involutions of {1,2,3}, i.e., in 123, 132, 213, 321, we have altogether 6 fixed points (3+1+1+1).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015.
S. Heubach and T. Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.
Brian Hopkins, Andrew V. Sills, Thotsaporn "Aek" Thanatipanonda, and Hua Wang, Parts and subword patterns in compositions, Preprint 2015.
Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021. See p. 30.
Index entries for linear recurrences with constant coefficients, signature (3,0,-4).

Cf. A001787, A027934, A045623, A127984, A128255, A172481, A225084.

[(3*n+4)*2^n/18-2*(-1)^n/9: n in [1..40]]; // Vincenzo Librandi, May 01 2017

LinearRecurrence[{3,0,-4},{1,2,6},30] (* Harvey P. Dale, Dec 29 2013 *)
Table[(3 n + 4) 2^n/18 - 2 (-1)^n/9, {n, 30}] (* Vincenzo Librandi, May 01 2017 *)

a(n) = (3*n+4)*2^n/18 - 2*(-1)^n/9.
G.f.: z*(1-z)/((1+z)*(1-2*z)^2).
a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(n-k, k+j)*2^k. - Paul Barry, Aug 29 2004
a(n) = Sum_{k=0..n+1} (-1)^(k+1)*binomial(n+1, k+j)*A001045(k). - Paul Barry, Jan 30 2005
Convolution of "Expansion of (1-x)/(1-x-2*x^2)" (A078008) with "Powers of 2" (A000079), treating the result as if offset=1. - Graeme McRae, Jul 12 2006
Convolution of "Difference sequence of A045623" (A045891) with "Positive integers repeated" (A008619), treating the result as if offset=1. - Graeme McRae, Jul 12 2006
a(n) = 3*a(n-1)-4*a(n-3); a(1)=1,a(2)=2,a(3)=6. - Philippe Deléham, Aug 30 2006
Equals row sums of A128255. (1, 2, 6, 14, 34, ...) - (0, 0, 1, 2, 6, 14, 34, ...) = A045623: (1, 2, 5, 12, 28, 64, ...). - Gary W. Adamson, Feb 20 2007
Equals triangle A059260 * [1, 2, 3, ...] as a vector. - Gary W. Adamson, Mar 06 2012
a(n) + a(n-1) = A001792(n-1). - Gregory L. Simay, Apr 30 2017
a(n) - a(n-2) = A045623(n-1). - Gregory L. Simay, May 01 2017
a(n) = A045623(n-1) + A045623(n-3) + A045623(n-5) + ... - Gregory L. Simay, Feb 19 2018
a(n) = A225084(2n,n). - Alois P. Heinz, Aug 30 2018

More terms from Eugene McDonnell (eemcd(AT)mac.com), Jan 13 2005

A224959 Number of compositions [p(1), p(2), ..., p(k)] of n such that p(j) - p(j-1) <= 2.

Original entry on oeis.org

1, 1, 2, 4, 8, 15, 29, 55, 105, 199, 378, 716, 1358, 2572, 4873, 9229, 17480, 33102, 62688, 118709, 224795, 425676, 806068, 1526371, 2890338, 5473125, 10363871, 19624925, 37161558, 70368705, 133249369, 252319408, 477788980, 904735349, 1713195705, 3244086145

Offset: 0

Joerg Arndt, Apr 21 2013

nonn

			There are a(5) = 15 such compositions of 5:
01:  [ 1 1 1 1 1 ]
02:  [ 1 1 1 2 ]
03:  [ 1 1 2 1 ]
04:  [ 1 1 3 ]
05:  [ 1 2 1 1 ]
06:  [ 1 2 2 ]
07:  [ 1 3 1 ]
08:  [ 2 1 1 1 ]
09:  [ 2 1 2 ]
10:  [ 2 2 1 ]
11:  [ 2 3 ]
12:  [ 3 1 1 ]
13:  [ 3 2 ]
14:  [ 4 1 ]
15:  [ 5 ]
(the single forbidden composition is [ 1 4 ]).

Alois P. Heinz, Table of n, a(n) for n = 0..3607

Cf. A003116 (compositions such that p(j) - p(j-1) <= 1).
Cf. A225084 (triangle: compositions of n such that max(p(j) - p(j-1)) = k).
Cf. A225085 (triangle: compositions of n such that max(p(j) - p(j-1)) <= k).

b:= proc(n, i) option remember;
      `if`(n=0, 1, add(b(n-j, max(1, j-2)), j=i..n))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..40);  # Alois P. Heinz, May 02 2013

b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, Max[1, j-2]], {j, i, n}]];
a[n_] := b[n, 1];
a /@ Range[0, 40] (* Jean-François Alcover, Dec 19 2020, after Alois P. Heinz *)

a(n) ~ c * d^n, where d=1.893587506319686491635881459546948770530553555112342985931092896452453511... and c=0.6398882559654423774981963082429746674258714212085034829366885993226... - Vaclav Kotesovec, May 01 2014

A225085 Triangle read by rows: T(n,k) is the number of compositions of n with maximal up-step <= k; n>=1, 0<=k

Original entry on oeis.org

1, 2, 2, 3, 4, 4, 5, 7, 8, 8, 7, 13, 15, 16, 16, 11, 23, 29, 31, 32, 32, 15, 41, 55, 61, 63, 64, 64, 22, 72, 105, 119, 125, 127, 128, 128, 30, 127, 199, 233, 247, 253, 255, 256, 256, 42, 222, 378, 455, 489, 503, 509, 511, 512, 512, 56, 388, 716, 889, 967, 1001, 1015, 1021, 1023, 1024, 1024

Offset: 1

Joerg Arndt, Apr 27 2013

T(n,k) is the number of compositions [p(1), p(2), ..., p(k)] of n such that max(p(j) - p(j-1)) <= k.
Rows are partial sums of rows of A225084.
The first column is A000041 (partition numbers), the second column is A003116, and the third column is A224959.
The diagonal is A011782.

			Triangle begins
01: 1,
02: 2, 2,
03: 3, 4, 4,
04: 5, 7, 8, 8,
05: 7, 13, 15, 16, 16,
06: 11, 23, 29, 31, 32, 32,
07: 15, 41, 55, 61, 63, 64, 64,
08: 22, 72, 105, 119, 125, 127, 128, 128,
09: 30, 127, 199, 233, 247, 253, 255, 256, 256,
10: 42, 222, 378, 455, 489, 503, 509, 511, 512, 512,
...
The fifth row corresponds to the following statistics:
#:  M   composition
01:  0  [ 1 1 1 1 1 ]
02:  1  [ 1 1 1 2 ]
03:  1  [ 1 1 2 1 ]
04:  2  [ 1 1 3 ]
05:  1  [ 1 2 1 1 ]
06:  1  [ 1 2 2 ]
07:  2  [ 1 3 1 ]
08:  3  [ 1 4 ]
09:  0  [ 2 1 1 1 ]
10:  1  [ 2 1 2 ]
11:  0  [ 2 2 1 ]
12:  1  [ 2 3 ]
13:  0  [ 3 1 1 ]
14:  0  [ 3 2 ]
15:  0  [ 4 1 ]
16:  0  [ 5 ]
There are 7 compositions with no up-step (M<=0), 13 with M<=1, 15 with M<=2, 16 with M<=3, and 16 with M<=4.

Joerg Arndt and Alois P. Heinz, Rows n = 1..141, flattened

cp's OEIS Frontend

A238130 Triangle read by rows: T(n,k) is the number of compositions into nonzero parts with k parts directly followed by a different part, n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A059570 Number of fixed points in all 231-avoiding involutions in S_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A224959 Number of compositions [p(1), p(2), ..., p(k)] of n such that p(j) - p(j-1) <= 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A225085 Triangle read by rows: T(n,k) is the number of compositions of n with maximal up-step <= k; n>=1, 0<=k

Views

Author

Keywords

Comments

Examples

Links