A261983 -id:A261983 - cp's OEIS frontend

A261981 Number T(n,k) of compositions of n such that k is the minimal distance between two identical parts; triangle T(n,k), n>=2, 1<=k<=floor((sqrt(8*n-7)-1)/2), read by rows.

1, 1, 4, 1, 9, 2, 18, 3, 41, 8, 2, 89, 16, 4, 185, 34, 10, 388, 57, 10, 810, 113, 30, 6, 1670, 213, 52, 12, 3435, 396, 104, 28, 7040, 733, 176, 50, 14360, 1333, 278, 62, 29226, 2419, 512, 152, 24, 59347, 4400, 878, 246, 48, 120229, 7934, 1492, 458, 108

Offset: 2

Alois P. Heinz, Sep 07 2015

			T(5,1) = 9: 311, 113, 221, 122, 2111, 1211, 1121, 1112, 11111.
T(5,2) = 2: 131, 212.
T(7,2) = 8: 151, 313, 232, 3121, 1213, 2131, 1312, 12121.
T(7,3) = 2: 1231, 1321.
Triangle T(n,k) begins:
n\k:     1     2    3    4   5
---+---------------------------
02 :     1;
03 :     1;
04 :     4,    1;
05 :     9,    2;
06 :    18,    3;
07 :    41,    8,   2;
08 :    89,   16,   4;
09 :   185,   34,  10;
10 :   388,   57,  10;
11 :   810,  113,  30,   6;
12 :  1670,  213,  52,  12;
13 :  3435,  396, 104,  28;
14 :  7040,  733, 176,  50;
15 : 14360, 1333, 278,  62;
16 : 29226, 2419, 512, 152, 24;

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

Columns k=1-2 give: A261983, A261984.
Row sums give A261982.
Cf. A000142, A261960, A262191.

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:
T:= (n, k)-> b(n, [0$(k-1)])-b(n, [0$k]):
seq(seq(T(n, k), k=1..floor((sqrt(8*n-7)-1)/2)), n=2..20);

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]]];
T[n_, k_] := A[n, k-1] - A[n, k];
Table[T[n, k], {n, 2, 20}, {k, 1, Floor[(Sqrt[8*n-7]-1)/2]}] // Flatten (* Jean-François Alcover, Apr 13 2017, after Alois P. Heinz *)

T(n,k) = A261960(n,k-1) - A261960(n,k).

T((n+1)*(n+2)/2+1,n+1) = A000142(n) for n>=0.

A353428 Number of integer compositions of n with all parts and all run-lengths > 2.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 2, 1, 0, 2, 0, 2, 4, 0, 0, 8, 3, 0, 10, 4, 4, 15, 4, 8, 24, 7, 8, 42, 16, 10, 59, 31, 27, 87, 37, 52, 149, 62, 66, 233, 121, 111, 342, 207, 204, 531, 308, 351, 864, 487, 536, 1373, 864, 865, 2057, 1440, 1509, 3232

Offset: 0

Gus Wiseman, May 16 2022

nonn

			The a(n) compositions for selected n:
  n=16:   n=18:     n=20:    n=21:      n=24:
----------------------------------------------------
  (4444)  (666)     (5555)   (777)      (888)
          (333333)  (44444)  (333444)   (6666)
                             (444333)   (333555)
                             (3333333)  (444444)
                                        (555333)
                                        (3333444)
                                        (4443333)
                                        (33333333)

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

Allowing any multiplicities gives A078012, partitions A008483.
The version for no (instead of all) parts or run-lengths > 2 is A137200.
Allowing any parts gives A353400, partitions A100405.
The version for partitions is A353501, ranked by A353502.
The version for > 1 instead of > 2 is A353508, partitions A339222.
A003242 counts anti-run compositions, ranked by A333489.
A008466 counts compositions with some part > 2.
A011782 counts compositions.
A114901 counts compositions with no runs of length 1, ranked by A353427.
A128695 counts compositions with no run-lengths > 2.
A261983 counts non-anti-run compositions.
A335464 counts compositions with a run-length > 2.
Cf. A032020, A044813, A098859, A165413, A318928, A329738, A329739, A333755, A353390, A353429.

b:= proc(n, h) option remember; `if`(n=0, 1, add(
     `if`(i=h, 0, add(b(n-i*j, i), j=3..n/i)), i=3..n/3))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..80);  # Alois P. Heinz, May 18 2022

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[#,1|2]&&!MemberQ[Length/@Split[#],1|2]&]],{n,0,15}]

a(26)-a(66) from Alois P. Heinz, May 17 2022

A232580 Number of binary sequences of length n that contain at least one contiguous subsequence 011.

Original entry on oeis.org

0, 0, 0, 1, 4, 12, 31, 74, 168, 369, 792, 1672, 3487, 7206, 14788, 30185, 61356, 124308, 251199, 506578, 1019920, 2050785, 4119280, 8267216, 16580799, 33236622, 66594636, 133385689, 267089188, 534692604, 1070217247, 2141780762, 4285739832, 8575004241

Offset: 0

Geoffrey Critzer, Nov 26 2013

From Gus Wiseman, Jun 26 2022: (Start)
Also the number of integer compositions of n + 1 with an even part other than the first or last. For example, the a(3) = 1 through a(5) = 12 compositions are:
  (121)  (122)   (123)
         (221)   (141)
         (1121)  (222)
         (1211)  (321)
                 (1122)
                 (1212)
                 (1221)
                 (2121)
                 (2211)
                 (11121)
                 (11211)
                 (12111)
The odd version is A274230.
(End)

			a(4) = 4 because we have: 0011, 0110, 0111, 1011.

Colin Barker, Table of n, a(n) for n = 0..1000
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 34.
Index entries for linear recurrences with constant coefficients, signature (4,-4,-1,2).

The complement is counted by A000071(n) = A001911(n) + 1.
For the contiguous pattern (1,1) or (0,0) we have A000225.
For the contiguous pattern (1,0,1) or (0,1,0) we have A000253.
For the contiguous pattern (1,0) or (0,1) we have A000295.
Numbers whose binary expansion is of this type are A004750.
For the contiguous pattern (1,1,1) or (0,0,0) we have A050231.
The not necessarily contiguous version is A324172.
Cf. A034691, A261983, A274230, A335455, A335457, A335458, A335516.

nn=40;a=x/(1-x);CoefficientList[Series[a^2 x/(1-a x)/(1-2x),{x,0,nn}],x]
(* second program *)
Table[Length[Select[Tuples[{0,1},n],MatchQ[#,{_,0,1,1,_}]&]],{n,0,10}] (* Gus Wiseman, Jun 26 2022 *)

concat(vector(3), Vec(x^3/(-2*x^4+x^3+4*x^2-4*x+1) + O(x^40))) \\ Colin Barker, Nov 03 2016

O.g.f.: x^3/( (1-x)^2*(1-x^2/(1-x))*(1-2x) ).
a(n) ~ 2^n.
From Colin Barker, Nov 03 2016: (Start)
a(n) = (1 + 2^n - (2^(-n)*((1-sqrt(5))^n*(-2+sqrt(5)) + (1+sqrt(5))^n*(2+sqrt(5))))/sqrt(5)).
a(n) = 4*a(n-1) - 4*a(n-2) - a(n-3) + 2*a(n-4) for n > 3. (End)
a(n) = 2^n - Fibonacci(n+3) + 1. - Ehren Metcalfe, Dec 27 2018
E.g.f.: 2*exp(x/2)*(5*exp(x)*cosh(x/2) - 5*cosh(sqrt(5)*x/2) - 2*sqrt(5)*sinh(sqrt(5)*x/2))/5. - Stefano Spezia, Apr 06 2022

A348616 Number of ordered factorizations of n with adjacent equal factors.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 2, 0, 0, 0, 4, 0, 2, 0, 2, 0, 0, 0, 6, 1, 0, 1, 2, 0, 0, 0, 9, 0, 0, 0, 9, 0, 0, 0, 6, 0, 0, 0, 2, 2, 0, 0, 19, 1, 2, 0, 2, 0, 6, 0, 6, 0, 0, 0, 8, 0, 0, 2, 18, 0, 0, 0, 2, 0, 0, 0, 31, 0, 0, 2, 2, 0, 0, 0, 19, 4, 0, 0, 8, 0, 0

Offset: 1

Gus Wiseman, Nov 08 2021

nonn

First differs from A348613 at a(24) = 6, A348613(24) = 8.

An ordered factorization of n is a finite sequence of positive integers > 1 with product n.

			The a(n) ordered factorizations with at least one pair of adjacent equal factors for n = 12, 24, 36, 60:
   2*2*3    2*2*6      6*6        15*2*2
   3*2*2    6*2*2      2*2*9      2*2*15
            2*2*2*3    3*3*4      2*2*3*5
            2*2*3*2    4*3*3      2*2*5*3
            2*3*2*2    9*2*2      3*2*2*5
            3*2*2*2    2*2*3*3    3*5*2*2
                       2*3*3*2    5*2*2*3
                       3*2*2*3    5*3*2*2
                       3*3*2*2
See also examples in A348611.

Positions of 0's are A005117.
Positions of 4's appear to be A030514.
Positions of 2's appear to be A054753.
Positions of 1's appear to be A168363.
The additive version (compositions) is A261983, complement A003242.
Factorizations with a permutation of this type are counted by A333487.
Factorizations without a permutation of this type are counted by A335434.
The complement is counted by A348611.
As compositions these are ranked by A348612, complement A333489.
Dominated by A348613 (non-alternating ordered factorizations).
A001055 counts factorizations, strict A045778, ordered A074206.
A335452 counts anti-run permutations of prime indices, complement A336107.
A339846 counts even-length factorizations.
A339890 counts odd-length factorizations.
Cf. A001250, A025047, A122181, A138364, A347050, A347463, A347706, A348379, A348380, A348382, A348610.

ordfacs[n_]:=If[n<=1,{{}},Join@@Table[Prepend[#,d]&/@ordfacs[n/d],{d,Rest[Divisors[n]]}]];
antirunQ[y_]:=Length[y]==Length[Split[y]]
Table[Length[Select[ordfacs[n],!antirunQ[#]&]],{n,100}]

a(n) = A074206(n) - A348611(n).

A353508 Number of integer compositions of n with no ones or runs of length 1.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 2, 0, 2, 1, 4, 0, 8, 2, 11, 4, 21, 5, 37, 12, 57, 25, 104, 38, 177, 79, 292, 149, 513, 251, 876, 482, 1478, 871, 2562, 1533, 4387, 2815, 7473, 5036, 12908, 8935, 22135, 16085, 37940, 28611, 65422, 50731, 112459, 90408, 193386, 160119, 333513

Offset: 0

Gus Wiseman, May 17 2022

nonn

			The a(0) = 1 through a(14) = 11 compositions (empty columns indicated by dots, 0 is the empty composition):
  0  .  .  .  22  .  33   .  44    333  55     .  66      22333  77
                     222     2222       2233      444     33322  2255
                                        3322      2244           3344
                                        22222     3333           4433
                                                  4422           5522
                                                  22233          22244
                                                  33222          44222
                                                  222222         222233
                                                                 223322
                                                                 332222
                                                                 2222222

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

The version for partitions is A339222.
Compositions counted by their run-lengths:
- For run-lengths <= 1 we have A003242, ranked by A333489.
- For run-lengths = 2 we have A003242 aerated.
- For run-lengths > 1 we have A114901, ranked by A353427.
- For run-lengths <= 2 we have A128695 matching A335464.
- For run-lengths > 2 we have A353400, partitions A100405.
- For run-lengths all prime we have A353401.
- For run-lengths and parts > 2 we have A353428.
A008466 counts compositions with some part > 2.
A011782 counts compositions.
A106356 counts compositions by number of adjacent equal parts.
A261983 counts non-anti-run compositions.
A274174 counts compositions with equal parts contiguous.
Cf. A005811, A078012, A238279, A329739, A333755, A351013, A353390.

b:= proc(n,h) option remember; `if`(n=0, 1, add(
     `if`(i<>h, add(b(n-i*j, i), j=2..n/i), 0), i=2..n/2))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..60);  # Alois P. Heinz, May 17 2022

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[#,1]&&!MemberQ[Length/@Split[#],1]&]],{n,0,15}]

a(41)-a(52) from Alois P. Heinz, May 17 2022

A353856 Triangle read by rows where T(n,k) is the number of integer compositions of n with run-sum trajectory (condensation) ending in a composition of length k.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 0, 2, 2, 0, 0, 5, 2, 1, 0, 0, 2, 12, 2, 0, 0, 0, 8, 10, 12, 2, 0, 0, 0, 2, 32, 23, 6, 1, 0, 0, 0, 20, 26, 51, 28, 3, 0, 0, 0, 0, 5, 66, 109, 52, 22, 2, 0, 0, 0, 0, 8, 108, 144, 188, 53, 10, 1, 0, 0, 0, 0, 2, 134, 358, 282, 196, 48, 4, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Jun 01 2022

Every sequence can be uniquely split into a sequence of non-overlapping runs. For example, the runs of (2,2,1,1,1,3,2,2) are ((2,2),(1,1,1),(3),(2,2)), with sums (4,3,3,4). The run-sum trajectory is obtained by repeatedly taking the run-sums transformation (or condensation, represented by A353847) until an anti-run is reached. For example, the trajectory (2,1,1,3,1,1,2,1,1,2,1) -> (2,2,3,2,2,2,2,1) -> (4,3,8,1) is counted under T(15,4).

			Triangle begins:
   1
   0   1
   0   2   0
   0   2   2   0
   0   5   2   1   0
   0   2  12   2   0   0
   0   8  10  12   2   0   0
   0   2  32  23   6   1   0   0
   0  20  26  51  28   3   0   0   0
   0   5  66 109  52  22   2   0   0   0
   0   8 108 144 188  53  10   1   0   0   0
   0   2 134 358 282 196  48   4   0   0   0   0
For example, row n = 6 counts the following compositions:
  .  (6)       (15)     (123)    (1212)  .  .
     (33)      (24)     (132)    (2121)
     (222)     (42)     (141)
     (1113)    (51)     (213)
     (2112)    (114)    (231)
     (3111)    (411)    (312)
     (11211)   (1122)   (321)
     (111111)  (2211)   (1131)
               (11112)  (1221)
               (21111)  (1311)
                        (11121)
                        (12111)

Row sums are A011782.
Row-lengths without zeros appear to be A131737.
The version for partitions is A353843.
The length of the trajectory is A353854, firsts A072639, partitions A353841.
The last part of the same trajectory is A353855.
Column k = 1 is A353858.
A066099 lists compositions in standard order.
A318928 gives runs-resistance of binary expansion.
A325268 counts partitions by omicron, rank statistic A304465.
A333489 ranks anti-runs, counted by A003242 (complement A261983).
A333627 ranks the run-lengths of standard compositions.
A353840-A353846 pertain to partition run-sum trajectory.
A353847 represents the run-sums of a composition, partitions A353832.
A353853-A353859 pertain to composition run-sum trajectory.
A353932 lists run-sums of standard compositions.
Cf. A237685, A238279, A304442, A325277, A333755, A353848, A353850, A353852.

Table[Length[Select[Join@@Permutations/@ IntegerPartitions[n],Length[FixedPoint[Total/@Split[#]&,#]]==k&]],{n,0,15},{k,0,n}]

A354908 Numbers k such that the k-th composition in standard order (graded reverse-lexicographic, A066099) is collapsible.

Original entry on oeis.org

1, 2, 3, 4, 7, 8, 10, 11, 14, 15, 16, 31, 32, 36, 39, 42, 43, 46, 47, 58, 59, 60, 62, 63, 64, 127, 128, 136, 138, 139, 142, 143, 168, 170, 171, 174, 175, 184, 186, 187, 190, 191, 232, 234, 235, 238, 239, 248, 250, 251, 254, 255, 256, 292, 295, 316, 319, 484

Offset: 1

Gus Wiseman, Jun 23 2022

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

If a collapse is an adding together of some partial run of an integer composition c, we say c is collapsible iff by some sequence of collapses it can be reduced to a single part. An example of such a sequence of collapses is (11132112) -> (332112) -> (33222) -> (6222) -> (66) -> (n), which shows that (11132112) is a collapsible composition of 12.

			The terms together with their corresponding compositions begin:
  1:(1)  2:(2)   4:(3)     8:(4)     16:(5)      32:(6)
         3:(11)  7:(111)  10:(22)    31:(11111)  36:(33)
                          11:(211)               39:(3111)
                          14:(112)               42:(222)
                          15:(1111)              43:(2211)
                                                 46:(2112)
                                                 47:(21111)
                                                 58:(1122)
                                                 59:(11211)
                                                 60:(1113)
                                                 62:(11112)
                                                 63:(111111)

The standard compositions used here are A066099, run-sums A353847/A353932.
The version for Heinz numbers of partitions is A300273, counted by A275870.
These compositions are counted by A353860.
A003242 counts anti-run compositions, ranked by A333489, complement A261983.
A011782 counts compositions.
A124767 counts runs in standard compositions.
A238279 and A333755 count compositions by number of runs.
A334968 counts distinct sums of subsequences of standard compositions.
A351014 counts distinct runs of standard compositions, firsts A351015.
A353853-A353859 pertain to composition run-sum trajectory.
A354582 counts distinct partial runs of standard compositions, sums A354907.
Cf. A005811, A029837, A072639, A124771, A274174, A318928, A333381, A353848, A353849, A353850.

repcams[q_List]:=repcams[q]=Union[{q},If[UnsameQ@@q,{},Union@@repcams/@Union[Insert[Drop[q,#],Plus@@Take[q,#],First[#]]&/@Select[Tuples[Range[Length[q]],2],And[Less@@#,SameQ@@Take[q,#]]&]]]];
stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],MemberQ[repcams[stc[#]],{_}]&]

A330028 Number of compositions of n with cuts-resistance <= 2.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 23, 45, 86, 159, 303, 568, 1069, 2005, 3769, 7066, 13251, 24821, 46482, 86988, 162758

Offset: 0

Gus Wiseman, Nov 27 2019

A composition of n is a finite sequence of positive integers summing to n.

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

			The a(0) = 1 through a(5) = 13 compositions:
  ()  (1)  (2)    (3)    (4)      (5)
           (1,1)  (1,2)  (1,3)    (1,4)
                  (2,1)  (2,2)    (2,3)
                         (3,1)    (3,2)
                         (1,1,2)  (4,1)
                         (1,2,1)  (1,1,3)
                         (2,1,1)  (1,2,2)
                                  (1,3,1)
                                  (2,1,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,2,1)
                                  (1,2,1,1)

Sum of first three columns of A329861.
Compositions with cuts-resistance 1 are A003242.
Compositions with cuts-resistance 2 are A329863.
Compositions with runs-resistance 2 are A329745.
Numbers whose binary expansion has cuts-resistance 2 are A329862.
Binary words with cuts-resistance 2 are A027383.
Cuts-resistance of binary expansion is A319416.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A000975, A003242, A032020, A114901, A240085, A261983, A319420, A329738, A329744, A329864.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],degdep[#]<=2&]],{n,0,10}]

cp's OEIS Frontend

A261981 Number T(n,k) of compositions of n such that k is the minimal distance between two identical parts; triangle T(n,k), n>=2, 1<=k<=floor((sqrt(8*n-7)-1)/2), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A353428 Number of integer compositions of n with all parts and all run-lengths > 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A232580 Number of binary sequences of length n that contain at least one contiguous subsequence 011.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A348616 Number of ordered factorizations of n with adjacent equal factors.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A353508 Number of integer compositions of n with no ones or runs of length 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A353856 Triangle read by rows where T(n,k) is the number of integer compositions of n with run-sum trajectory (condensation) ending in a composition of length k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A354908 Numbers k such that the k-th composition in standard order (graded reverse-lexicographic, A066099) is collapsible.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A330028 Number of compositions of n with cuts-resistance <= 2.

Views

Author

Keywords

Comments

Examples