A335455
Number of compositions of n with some part appearing more than twice.
Original entry on oeis.org
0, 0, 0, 1, 1, 5, 11, 30, 69, 142, 334, 740, 1526, 3273, 6840, 14251, 29029, 59729, 122009, 248070, 500649, 1012570, 2040238, 4107008, 8257466, 16562283, 33229788, 66621205, 133478437, 267326999, 535146239, 1071183438, 2143604313, 4289194948, 8581463248
Offset: 0
The a(3) = 1 through a(6) = 11 compositions:
(111) (1111) (1112) (222)
(1121) (1113)
(1211) (1131)
(2111) (1311)
(11111) (3111)
(11112)
(11121)
(11211)
(12111)
(21111)
(111111)
The (1,1)-matching version is
A261982.
The version for patterns is
A335508.
The version for prime indices is
A335510.
These compositions are ranked by
A335512.
Compositions are counted by
A011782.
Combinatory separations are counted by
A269134.
Normal patterns matched by compositions are counted by
A335456.
-
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Max@@Length/@Split[Sort[#]]>=3&]],{n,0,10}]
A374690
Number of integer compositions of n whose leaders of strictly increasing runs are weakly increasing.
Original entry on oeis.org
1, 1, 2, 3, 6, 10, 19, 34, 63, 115, 211, 387, 710, 1302, 2385, 4372, 8009, 14671, 26867, 49196, 90069, 164884, 301812, 552406, 1011004, 1850209, 3385861, 6195832, 11337470, 20745337, 37959030, 69454669, 127081111, 232517129, 425426211, 778376479, 1424137721
Offset: 0
The composition (1,1,3,2,3,2) has strictly increasing runs ((1),(1,3),(2,3),(2)), with leaders (1,1,2,2), so is counted under a(12).
The a(0) = 1 through a(6) = 19 compositions:
() (1) (2) (3) (4) (5) (6)
(11) (12) (13) (14) (15)
(111) (22) (23) (24)
(112) (113) (33)
(121) (122) (114)
(1111) (131) (123)
(1112) (132)
(1121) (141)
(1211) (222)
(11111) (1113)
(1122)
(1131)
(1212)
(1311)
(11112)
(11121)
(11211)
(12111)
(111111)
Ranked by positions of weakly increasing rows in
A374683.
Types of runs (instead of strictly increasing):
- For leaders of identical runs we have
A000041.
- For leaders of anti-runs we have
A374681.
- For leaders of weakly increasing runs we have
A374635.
- For leaders of weakly decreasing runs we have
A188900.
- For leaders of strictly decreasing runs we have
A374764.
Types of run-leaders (instead of weakly increasing):
- For strictly increasing leaders we have
A374688.
- For strictly decreasing leaders we have
A374689.
- For weakly decreasing leaders we have
A374697.
A335456 counts patterns matched by compositions.
A374700 counts compositions by sum of leaders of strictly increasing runs.
Cf.
A000009,
A106356,
A188920,
A189076,
A238343,
A261982,
A333213,
A374629,
A374630,
A374632,
A374679.
-
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],LessEqual@@First/@Split[#,Less]&]],{n,0,15}]
A374765
Number of integer compositions of n whose leaders of strictly decreasing runs are weakly decreasing.
Original entry on oeis.org
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 88, 141, 225, 357, 565, 891, 1399, 2191, 3420, 5321, 8256, 12774, 19711, 30339, 46584, 71359, 109066, 166340, 253163, 384539, 582972, 882166, 1332538, 2009377, 3024969, 4546562, 6822926, 10223632, 15297051, 22855872, 34103117
Offset: 0
The composition (3,1,2,2,1) has strictly decreasing runs ((3,1),(2),(2,1)), with leaders (3,2,2), so is counted under a(9).
The a(0) = 1 through a(6) = 13 compositions:
() (1) (2) (3) (4) (5) (6)
(11) (21) (22) (32) (33)
(111) (31) (41) (42)
(211) (212) (51)
(1111) (221) (222)
(311) (312)
(2111) (321)
(11111) (411)
(2121)
(2211)
(3111)
(21111)
(111111)
Other types of runs (instead of strictly decreasing):
- For leaders of identical runs we have
A000041.
- For leaders of weakly increasing runs we appear to have
A189076.
- For leaders of anti-runs we have
A374682.
- For leaders of strictly increasing runs we have
A374697.
- For leaders of weakly decreasing runs we have
A374747.
Other types of run-leaders (instead of weakly decreasing):
- For strictly increasing leaders we have
A374762.
- For strictly decreasing leaders we have
A374763.
- For weakly increasing leaders we have
A374764.
Cf.
A106356,
A188900,
A188920,
A238343,
A261982,
A333213,
A374635,
A374636,
A374689,
A374742,
A374743,
A375133.
-
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],GreaterEqual@@First/@Split[#,Greater]&]],{n,0,15}]
-
dfs(m, r, u) = 1 + sum(s=r, min(m, u), dfs(m-s, s, s)*x^s + sum(t=1, min(s-1, m-s), dfs(m-s-t, t, s)*x^(s+t)*prod(i=t+1, s-1, 1+x^i)));
lista(nn) = Vec(dfs(nn, 1, nn) + O(x^(1+nn))); \\ Jinyuan Wang, Feb 13 2025
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
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;
-
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 *)
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.
Original entry on oeis.org
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
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;
-
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 *)
A363224
Number of integer compositions of n in which the least part appears more than once.
Original entry on oeis.org
0, 1, 1, 5, 8, 21, 44, 94, 197, 416, 857, 1766, 3621, 7392, 15032, 30493, 61708, 124646, 251359, 506203, 1018279, 2046454, 4109534, 8246985, 16540791, 33160051, 66451484, 133122753, 266612828, 533839069, 1068701695, 2139110054, 4281063708, 8566862025
Offset: 1
The a(1) = 0 through a(6) = 21 compositions:
. (11) (111) (22) (113) (33)
(112) (131) (114)
(121) (311) (141)
(211) (1112) (222)
(1111) (1121) (411)
(1211) (1113)
(2111) (1122)
(11111) (1131)
(1212)
(1221)
(1311)
(2112)
(2121)
(2211)
(3111)
(11112)
(11121)
(11211)
(12111)
(21111)
(111111)
The complement is counted by
A105039.
For partitions instead of compositions we have
A117989.
Row sums of columns k > 1 of
A238342.
If all parts appear more than once we have
A240085, for partitions
A007690.
If the least part appears exactly twice we have
A241862.
A032020 counts strict compositions.
A261982 counts compositions with some part appearing more than once.
-
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],Count[#,Min@@#]>1&]],{n,15}]
-
C_x(N)={my(x='x+O('x^N), h=sum(i=1,N,(x^(2*i)*(x-1)^3)/((x^i+x-1)*(x^(i+1)+x-1)^2))); concat([0],Vec(h))}
C_x(35) \\ John Tyler Rascoe, Jul 06 2024
A374521
Triangle read by rows where T(n,k) is the number of integer compositions of n whose leaders of anti-runs sum to k.
Original entry on oeis.org
1, 0, 1, 0, 0, 2, 0, 1, 1, 2, 0, 2, 1, 2, 3, 0, 2, 5, 3, 4, 2, 0, 5, 7, 8, 3, 5, 4, 0, 9, 12, 11, 17, 5, 8, 2, 0, 14, 26, 23, 22, 24, 6, 9, 4, 0, 25, 42, 54, 41, 36, 36, 7, 12, 3, 0, 46, 76, 88, 107, 60, 60, 48, 9, 14, 4
Offset: 0
Triangle begins:
1
0 1
0 0 2
0 1 1 2
0 2 1 2 3
0 2 5 3 4 2
0 5 7 8 3 5 4
0 9 12 11 17 5 8 2
0 14 26 23 22 24 6 9 4
0 25 42 54 41 36 36 7 12 3
0 46 76 88 107 60 60 48 9 14 4
0 78 144 166 179 176 101 83 68 10 17 2
0 136 258 327 339 311 299 139 122 81 12 18 6
0 242 457 602 704 591 544 447 198 165 109 12 23 2
Row n = 6 counts the following compositions:
. (15) (24) (321) (42) (51) (6)
(141) (114) (312) (1122) (411) (33)
(132) (231) (1113) (11112) (3111) (222)
(123) (213) (2112) (2211) (111111)
(1212) (1311) (1221) (21111)
(1131) (12111)
(2121) (11211)
(11121)
Column n = k is
A000005, except a(0) = 1.
For length instead of sum we have
A106356.
Other types of runs (instead of anti-):
- For leaders of identical runs we have
A373949.
- For leaders of weakly increasing runs we have
A374637.
- For leaders of strictly increasing runs we have
A374700.
- For leaders of weakly decreasing runs we have
A374748.
- For leaders of strictly decreasing runs we have
A374766.
A003242 counts anti-run compositions.
-
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],Total[First/@Split[#,UnsameQ]]==k&]],{n,0,15},{k,0,n}]
A375140
Number of integer compositions of n whose leaders of weakly increasing runs are not strictly decreasing.
Original entry on oeis.org
0, 0, 0, 1, 3, 10, 26, 65, 151, 343, 750, 1614, 3410, 7123, 14724, 30220, 61639, 125166, 253233, 510936, 1028659, 2067620, 4150699, 8324552, 16683501, 33417933, 66910805, 133931495, 268023257, 536279457, 1072895973, 2146277961, 4293254010, 8587507415
Offset: 1
The a(1) = 0 through a(6) = 10 compositions:
. . . (121) (131) (132)
(1121) (141)
(1211) (1131)
(1212)
(1221)
(1311)
(2121)
(11121)
(11211)
(12111)
For leaders of identical runs we have
A056823.
The complement is counted by
A188920.
For leaders of weakly decreasing runs we have the complement of
A374746.
A106356 counts compositions by number of maximal anti-runs.
A238424 counts partitions whose first differences are an anti-run.
A335456 counts patterns matched by compositions.
A374637 counts compositions by sum of leaders of weakly increasing runs.
-
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],!Greater@@First/@Split[#,LessEqual]&]],{n,15}]
- or -
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],MatchQ[#,{_,x_,_,z_,y_,_}/;x<=y
A321773
Number of compositions of n into parts with distinct multiplicities and with exactly three parts.
Original entry on oeis.org
1, 3, 6, 4, 9, 9, 10, 12, 15, 13, 18, 18, 19, 21, 24, 22, 27, 27, 28, 30, 33, 31, 36, 36, 37, 39, 42, 40, 45, 45, 46, 48, 51, 49, 54, 54, 55, 57, 60, 58, 63, 63, 64, 66, 69, 67, 72, 72, 73, 75, 78, 76, 81, 81, 82, 84, 87, 85, 90, 90, 91, 93, 96, 94, 99, 99
Offset: 3
From _Gus Wiseman_, Nov 11 2020: (Start)
Also the number of 3-part non-strict compositions of n. For example, the a(3) = 1 through a(11) = 15 triples are:
111 112 113 114 115 116 117 118 119
121 122 141 133 161 144 181 155
211 131 222 151 224 171 226 191
212 411 223 233 225 244 227
221 232 242 252 262 272
311 313 323 333 334 335
322 332 414 343 344
331 422 441 424 353
511 611 522 433 434
711 442 443
622 515
811 533
551
722
911
(End)
A235451 counts 3-part compositions with distinct run-lengths
A001399(n-6) counts 3-part compositions in the complement.
A261982 counts non-strict compositions of any length.
A032020 counts strict compositions.
A242771 counts triples that are not strictly increasing.
-
Table[Length[Join@@Permutations/@Select[IntegerPartitions[n,{3}],!UnsameQ@@#&]],{n,0,100}] (* Gus Wiseman, Nov 11 2020 *)
A335488
Numbers k such that the k-th composition in standard order (A066099) matches the pattern (1,1).
Original entry on oeis.org
3, 7, 10, 11, 13, 14, 15, 19, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 35, 36, 39, 42, 43, 45, 46, 47, 49, 51, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 67, 71, 73, 74, 75, 76, 77, 78, 79, 82, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 97, 99, 100, 101
Offset: 1
The sequence of terms together with the corresponding compositions begins:
3: (1,1)
7: (1,1,1)
10: (2,2)
11: (2,1,1)
13: (1,2,1)
14: (1,1,2)
15: (1,1,1,1)
19: (3,1,1)
21: (2,2,1)
22: (2,1,2)
23: (2,1,1,1)
25: (1,3,1)
26: (1,2,2)
27: (1,2,1,1)
28: (1,1,3)
The complement
A233564 is the avoiding version.
Patterns matching this pattern are counted by
A019472 (by length).
Permutations of prime indices matching this pattern are counted by
A335487.
These compositions are counted by
A261982 (by sum).
Non-unimodal compositions are counted by
A115981 and ranked by
A335373.
Combinatory separations are counted by
A269134.
Patterns matched by standard compositions are counted by
A335454.
Minimal patterns avoided by a standard composition are counted by
A335465.
The (1,1,1)-matching case is
A335512.
-
stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],MatchQ[stc[#],{_,x_,_,x_,_}]&]
Comments