A261981 -id:A261981 - cp's OEIS frontend

A261982 Number of compositions of n with some part repeated.

0, 0, 1, 1, 5, 11, 21, 51, 109, 229, 455, 959, 1947, 3963, 7999, 16033, 32333, 64919, 130221, 260967, 522733, 1045825, 2093855, 4189547, 8382315, 16768455, 33543127, 67093261, 134193413, 268404995, 536829045, 1073686083, 2147408773, 4294869253, 8589803783

Offset: 0

Alois P. Heinz, Sep 07 2015

nonn

Also compositions matching the pattern (1,1). - Gus Wiseman, Jun 23 2020

			a(2) = 1: 11.
a(3) = 1: 111.
a(4) = 5: 22, 211, 121, 112, 1111.

Alois P. Heinz, Table of n, a(n) for n = 0..3322
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Row sums of A261981 and of A262191.
Cf. A262047.
The version for patterns is A019472.
The (1,1)-avoiding version is A032020.
The case of partitions is A047967.
(1,1,1)-matching compositions are counted by A335455.
Patterns matched by compositions are counted by A335456.
(1,1)-matching compositions are ranked by A335488.
Cf. A011782, A056986, A106356, A181796, A238279, A269134, A333755.

b:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
      `if`(k=0, `if`(n=0, 1, 0), b(n-k, k) +k*b(n-k, k-1)))
    end:
a:= n-> ceil(2^(n-1))-add(b(n, k), k=0..floor((sqrt(8*n+1)-1)/2)):
seq(a(n), n=0..40);

b[n_, k_] := b[n, k] = If[k<0 || n<0, 0, If[k==0, If[n==0, 1, 0], b[n-k, k] + k*b[n-k, k-1]]]; a[n_] := Ceiling[2^(n-1)]-Sum[b[n, k], {k, 0, Floor[ (Sqrt[8n+1]-1)/2]}]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 08 2017, translated from Maple *)
Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],Length[#]>Length[Split[#]]&]],{n,0,10}] (* Gus Wiseman, Jun 24 2020 *)

a(n) = A011782(n) - A032020(n).

G.f.: (1 - x) / (1 - 2*x) - Sum_{k>=0} k! * x^(k*(k + 1)/2) / Product_{j=1..k} (1 - x^j). - Ilya Gutkovskiy, Jan 30 2020

A261983 Number of compositions of n such that at least two adjacent parts are equal.

Original entry on oeis.org

0, 0, 1, 1, 4, 9, 18, 41, 89, 185, 388, 810, 1670, 3435, 7040, 14360, 29226, 59347, 120229, 243166, 491086, 990446, 1995410, 4016259, 8076960, 16231746, 32599774, 65437945, 131293192, 263316897, 527912140, 1058061751, 2120039885, 4246934012, 8505864640

Offset: 0

Alois P. Heinz, Sep 07 2015

nonn

			a(5) = 9: 311, 113, 221, 122, 2111, 1211, 1121, 1112, 11111.
From _Gus Wiseman_, Jul 07 2020: (Start)
The a(2) = 1 through a(6) = 18 compositions:
  (1,1)  (1,1,1)  (2,2)      (1,1,3)      (3,3)
                  (1,1,2)    (1,2,2)      (1,1,4)
                  (2,1,1)    (2,2,1)      (2,2,2)
                  (1,1,1,1)  (3,1,1)      (4,1,1)
                             (1,1,1,2)    (1,1,1,3)
                             (1,1,2,1)    (1,1,2,2)
                             (1,2,1,1)    (1,1,3,1)
                             (2,1,1,1)    (1,2,2,1)
                             (1,1,1,1,1)  (1,3,1,1)
                                          (2,1,1,2)
                                          (2,2,1,1)
                                          (3,1,1,1)
                                          (1,1,1,1,2)
                                          (1,1,1,2,1)
                                          (1,1,2,1,1)
                                          (1,2,1,1,1)
                                          (2,1,1,1,1)
                                          (1,1,1,1,1,1)
(End)

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

Column k=1 of A261981.
Cf. A011782, A262046.
The complement A003242 counts anti-runs.
Sum of positive-indexed terms of row n of A106356.
Row sums of A131044.
The (1,1,1) matching case is A335464.
Strict compositions are A032020.
Compositions with adjacent parts coprime are A167606.
Compositions with equal parts contiguous are A274174.
Cf. A114901, A178470, A242882, A244164, A325534, A335448, A335452.

b:= proc(n, i) option remember; `if`(n=0, 0, add(
      `if`(i=j, ceil(2^(n-j-1)), b(n-j, j)), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],MatchQ[#,{_,x_,x_,_}]&]],{n,0,10}] (* Gus Wiseman, Jul 06 2020 *)
b[n_, i_] := b[n, i] = If[n == 0, 0, Sum[If[i == j, Ceiling[2^(n-j-1)], b[n-j, j]], {j, 1, n}]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 20 2023, after Alois P. Heinz's Maple code *)

a(n) ~ 2^(n-1). - Vaclav Kotesovec, Sep 08 2015

a(n) = A011782(n) - A003242(n). - Emeric Deutsch, Jul 03 2020

A262191 Number T(n,k) of compositions of n such that k is the maximal distance between two identical parts; triangle T(n,k), n>=2, 1<=k<=n-1, read by rows.

Original entry on oeis.org

1, 0, 1, 3, 1, 1, 4, 4, 2, 1, 5, 6, 6, 3, 1, 12, 13, 12, 9, 4, 1, 21, 23, 25, 21, 13, 5, 1, 36, 42, 46, 46, 34, 18, 6, 1, 43, 68, 88, 92, 80, 52, 24, 7, 1, 88, 119, 152, 180, 172, 132, 76, 31, 8, 1, 133, 197, 267, 330, 352, 304, 208, 107, 39, 9, 1

Offset: 2

Alois P. Heinz, Sep 14 2015

			T(6,1) = 5: 33, 114, 411, 1122, 2211.
T(6,2) = 6: 141, 222, 1113, 1212, 2121, 3111.
T(6,3) = 6: 1131, 1221, 1311, 2112, 11112, 21111.
T(6,4) = 3: 11121, 11211, 12111.
T(6,5) = 1: 111111.
Triangle T(n,k) begins:
n\k:   1    2    3    4    5    6    7    8   9  10  11
---+----------------------------------------------------
02 :   1;
03 :   0,   1;
04 :   3,   1,   1;
05 :   4,   4,   2,   1;
06 :   5,   6,   6,   3,   1;
07 :  12,  13,  12,   9,   4,   1;
08 :  21,  23,  25,  21,  13,   5,   1;
09 :  36,  42,  46,  46,  34,  18,   6,   1;
10 :  43,  68,  88,  92,  80,  52,  24,   7,  1;
11 :  88, 119, 152, 180, 172, 132,  76,  31,  8,  1;
12 : 133, 197, 267, 330, 352, 304, 208, 107, 39,  9,  1;

Alois P. Heinz, Rows n = 2..20, flattened

Column k=1-5 gives A262192, A262194, A262196, A262197, A262200.
Row sums give A261982.
Cf. A261981.

b:= proc(n, s, l) option remember; `if`(n=0, 1, add(
      `if`(j in s, 0, b(n-j, s union {`if`(l=[], j, l[1])},
      `if`(l=[], [], [subsop(1=NULL, l)[], j]))), j=1..n))
    end:
T:= (n, k)-> b(n, {}, [0$k]) -b(n, {}, [0$(k-1)]):
seq(seq(T(n, k), k=1..n-1), n=2..14);

b[n_, s_, l_] := b[n, s, l] = If[n==0, 1, Sum[If[MemberQ[s, j], 0, b[n-j, s ~Union~ {If[l=={}, j, l[[1]]]}, If[l=={}, {}, Append[Rest[l], j]]]], {j, 1, n}]]; T[n_, k_] := b[n, {}, Array[0&, k]] - b[n, {}, Array[0&, k-1]]; Table[T[n, k], {n, 2, 14}, { k, 1, n-1}] // Flatten (* Jean-François Alcover, Feb 08 2017, translated from Maple *)

A261960 Number A(n,k) of compositions of n such that no part equals any of its k immediate predecessors; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 1, 1, 1, 3, 8, 1, 1, 1, 3, 4, 16, 1, 1, 1, 3, 3, 7, 32, 1, 1, 1, 3, 3, 5, 14, 64, 1, 1, 1, 3, 3, 5, 11, 23, 128, 1, 1, 1, 3, 3, 5, 11, 15, 39, 256, 1, 1, 1, 3, 3, 5, 11, 13, 23, 71, 512, 1, 1, 1, 3, 3, 5, 11, 13, 19, 37, 124, 1024

Offset: 0

Alois P. Heinz, Sep 06 2015

			Square array A(n,k) begins:
:  1,  1,  1,  1,  1,  1,  1, ...
:  1,  1,  1,  1,  1,  1,  1, ...
:  2,  1,  1,  1,  1,  1,  1, ...
:  4,  3,  3,  3,  3,  3,  3, ...
:  8,  4,  3,  3,  3,  3,  3, ...
: 16,  7,  5,  5,  5,  5,  5, ...
: 32, 14, 11, 11, 11, 11, 11, ...

Alois P. Heinz, Antidiagonals n = 0..50, flattened

Columns k=0-2 give: A011782, A003242, A261962.
Main diagonal gives A032020.
Cf. A261959, A261981.

b:= proc(n, l) option remember;
      `if`(n=0, 1, add(`if`(j in l, 0, b(n-j,
      `if`(l=[], [], [subsop(1=NULL, l)[], j]))), j=1..n))
    end:
A:= (n, k)-> b(n, [0$min(n, k)]):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[n_, l_] := b[n, l] = If[n==0, 1, Sum[If[MemberQ[l, j], 0, b[n-j, If[l == {}, {}, Append[Rest[l], j]]]], {j, 1, n}]]; A[n_, k_] := b[n, Array[0&, Min[n, k]]]; Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Feb 08 2017, translated from Maple *)

A261984 Number of compositions of n such that the minimal distance between two identical parts equals two.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 3, 8, 16, 34, 57, 113, 213, 396, 733, 1333, 2419, 4400, 7934, 14321, 25687, 45947, 82085, 146410, 260547, 463021, 821669, 1456296, 2578051, 4559972, 8057373, 14225124, 25096606, 44246087, 77958821, 137283534, 241626535, 425079358, 747501363

Offset: 0

Alois P. Heinz, Sep 07 2015

nonn

			a(4) = 1: 121.
a(5) = 2: 131, 212.
a(6) = 3: 141, 1212, 2121.
a(7) = 8: 151, 232, 313, 1213, 1312, 2131, 3121, 12121.
a(8) = 16: 161, 242, 323, 1214, 1232, 1313, 1412, 2123, 2141, 2321, 3131, 3212, 4121, 12131, 13121, 21212.

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

Column k=2 of A261981.

g:= proc(n, i) option remember; `if`(n=0, 1, add(
     `if`(i=j, 0, g(n-j, j)), j=1..n))
    end:
b:= proc(n, i, m) option remember; `if`(n=0, 0, add(
     `if`(i=j, 0, `if`(j=m, g(n-j, j), b(n-j, j, i))), j=1..n))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..45);

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

a(n) ~ A003242(n). - Vaclav Kotesovec, Sep 08 2015

cp's OEIS Frontend

A261982 Number of compositions of n with some part repeated.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A261983 Number of compositions of n such that at least two adjacent parts are equal.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A262191 Number T(n,k) of compositions of n such that k is the maximal distance between two identical parts; triangle T(n,k), n>=2, 1<=k<=n-1, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A261960 Number A(n,k) of compositions of n such that no part equals any of its k immediate predecessors; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A261984 Number of compositions of n such that the minimal distance between two identical parts equals two.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula