[go: up one dir, main page]

login
Search: a374253 -id:a374253
     Sort: relevance | references | number | modified | created      Format: long | short | data
Irregular triangle listing the leaders of maximal weakly increasing runs in the n-th composition in standard order.
+10
87
1, 2, 1, 3, 2, 1, 1, 1, 4, 3, 1, 2, 2, 1, 1, 1, 1, 1, 1, 5, 4, 1, 3, 2, 3, 1, 2, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 5, 1, 4, 2, 4, 1, 3, 3, 2, 1, 3, 1, 3, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1
OFFSET
0,2
COMMENTS
The leaders of maximal weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.
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.
EXAMPLE
The 58654th composition in standard order is (1,1,3,2,4,1,1,1,2), with maximal weakly increasing runs ((1,1,3),(2,4),(1,1,1,2)), so row 58654 is (1,2,1).
The nonnegative integers, corresponding compositions, and leaders of maximal weakly increasing runs begin:
0: () -> () 15: (1,1,1,1) -> (1)
1: (1) -> (1) 16: (5) -> (5)
2: (2) -> (2) 17: (4,1) -> (4,1)
3: (1,1) -> (1) 18: (3,2) -> (3,2)
4: (3) -> (3) 19: (3,1,1) -> (3,1)
5: (2,1) -> (2,1) 20: (2,3) -> (2)
6: (1,2) -> (1) 21: (2,2,1) -> (2,1)
7: (1,1,1) -> (1) 22: (2,1,2) -> (2,1)
8: (4) -> (4) 23: (2,1,1,1) -> (2,1)
9: (3,1) -> (3,1) 24: (1,4) -> (1)
10: (2,2) -> (2) 25: (1,3,1) -> (1,1)
11: (2,1,1) -> (2,1) 26: (1,2,2) -> (1)
12: (1,3) -> (1) 27: (1,2,1,1) -> (1,1)
13: (1,2,1) -> (1,1) 28: (1,1,3) -> (1)
14: (1,1,2) -> (1) 29: (1,1,2,1) -> (1,1)
MATHEMATICA
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[First/@Split[stc[n], LessEqual], {n, 0, 100}]
CROSSREFS
Row-leaders are A065120.
Row-lengths are A124766.
Row-sums are A374630.
Positions of constant rows are A374633, counted by A374631.
Positions of strict rows are A374768, counted by A374632.
For other types of runs we have A374251, A374515, A374683, A374740, A374757.
Positions of non-weakly decreasing rows are A375137.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A335456 counts patterns matched by compositions.
All of the following pertain to compositions in standard order:
- Length is A000120.
- Sum is A029837(n+1).
- Leader is A065120.
- Parts are listed by A066099, reverse A228351.
- Number of adjacent equal pairs is A124762, unequal A333382.
- Number of max runs: A124765, A124766, A124767, A124768, A124769, A333381.
- Ranks of anti-run compositions are A333489, counted by A003242.
- Run-length transform is A333627, length A124767, sum A070939.
- Run-compression transform is A373948, sum A373953, excess A373954.
- Ranks of contiguous compositions are A374249, counted by A274174.
- Ranks of non-contiguous compositions are A374253, counted by A335548.
KEYWORD
nonn,tabf
AUTHOR
Gus Wiseman, Jul 20 2024
STATUS
approved
Numbers k such that the k-th composition in standard order has its equal parts contiguous.
+10
70
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 26, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 47, 48, 50, 52, 56, 58, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 78, 79, 80, 81, 83, 84, 85
OFFSET
1,3
COMMENTS
These are compositions avoiding the patterns (1,2,1) and (2,1,2).
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.
FORMULA
Equals A335467 /\ A335469.
EXAMPLE
The terms together with their standard compositions begin:
0: ()
1: (1)
2: (2)
3: (1,1)
4: (3)
5: (2,1)
6: (1,2)
7: (1,1,1)
8: (4)
9: (3,1)
10: (2,2)
11: (2,1,1)
12: (1,3)
14: (1,1,2)
15: (1,1,1,1)
16: (5)
See A374253 for the complement: 13, 22, 25, 27, 29, ...
MATHEMATICA
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Select[Range[0, 100], UnsameQ@@First/@Split[stc[#]]&]
CROSSREFS
The strict (also anti-run) case is A233564, counted by A032020.
Compositions of this type are counted by A274174.
Permutations of prime indices of this type are counted by A333175.
The complement is A374253 (anti-run A374254), counted by A335548.
A003242 counts anti-run compositions, ranks A333489.
A011782 counts compositions.
A066099 lists compositions in standard order.
A124767 counts runs in standard compositions, anti-runs A333381.
A333755 counts compositions by number of runs.
A335454 counts patterns matched by standard compositions.
A335462 counts (1,2,1)- and (2,1,2)-matching permutations of prime indices.
- A335470 counts (1,2,1)-matching compositions, ranks A335466.
- A335471 counts (1,2,1)-avoiding compositions, ranks A335467.
- A335472 counts (2,1,2)-matching compositions, ranks A335468.
- A335473 counts (2,1,2)-avoiding compositions, ranks A335469.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jul 13 2024
STATUS
approved
Number of integer compositions of n whose leaders of weakly increasing runs are themselves weakly increasing.
+10
42
1, 1, 2, 3, 6, 10, 20, 36, 69, 130, 247, 467, 890, 1689, 3213, 6110, 11627, 22121, 42101, 80124, 152512, 290300, 552609, 1051953, 2002583, 3812326
OFFSET
0,3
COMMENTS
The leaders of weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.
EXAMPLE
The composition (1,3,3,2,4,2) has weakly increasing runs ((1,3,3),(2,4),(2)), with leaders (1,2,2), so is counted under a(15).
The a(0) = 1 through a(6) = 20 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)
(1221)
(1311)
(11112)
(11121)
(11211)
(12111)
(111111)
MATHEMATICA
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n], LessEqual@@First/@Split[#, LessEqual]&]], {n, 0, 15}]
CROSSREFS
Ranked by positions of weakly increasing rows in A374629 (sums A374630).
Types of runs (instead of weakly increasing):
- For leaders of constant runs we have A000041.
- For leaders of weakly decreasing runs we have A188900.
- For leaders of anti-runs we have A374681.
- For leaders of strictly increasing runs we have A374690.
- For leaders of strictly decreasing runs we have A374764.
Types of run-leaders (instead of weakly increasing):
- For strictly decreasing leaders we appear to have A188920.
- For weakly decreasing leaders we appear to have A189076.
- For identical leaders we have A374631.
- For distinct leaders we have A374632, ranks A374768.
- For strictly increasing leaders we have A374634.
A003242 counts anti-run compositions.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A274174 counts contiguous compositions, ranks A374249.
A335456 counts patterns matched by compositions.
A335548 counts non-contiguous compositions, ranks A374253.
A374637 counts compositions by sum of leaders of weakly increasing runs.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Jul 23 2024
STATUS
approved
Irregular triangle read by rows where row n lists the leaders of strictly increasing runs in the n-th composition in standard order.
+10
41
1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 1, 4, 3, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 4, 1, 3, 2, 3, 1, 1, 2, 2, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 5, 1, 4, 2, 4, 1, 1, 3, 3, 3, 2, 1, 3, 1, 3, 1, 1, 1
OFFSET
0,2
COMMENTS
The leaders of strictly increasing runs in a sequence are obtained by splitting it into maximal strictly increasing subsequences and taking the first term of each.
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.
EXAMPLE
The maximal strictly increasing subsequences of the 1234567th composition in standard order are ((3),(2),(1,2),(2),(1,2,5),(1),(1),(1)), so row 1234567 is (3,2,1,2,1,1,1,1).
The nonnegative integers, corresponding compositions, and leaders of strictly increasing runs begin:
0: () -> () 15: (1,1,1,1) -> (1,1,1,1)
1: (1) -> (1) 16: (5) -> (5)
2: (2) -> (2) 17: (4,1) -> (4,1)
3: (1,1) -> (1,1) 18: (3,2) -> (3,2)
4: (3) -> (3) 19: (3,1,1) -> (3,1,1)
5: (2,1) -> (2,1) 20: (2,3) -> (2)
6: (1,2) -> (1) 21: (2,2,1) -> (2,2,1)
7: (1,1,1) -> (1,1,1) 22: (2,1,2) -> (2,1)
8: (4) -> (4) 23: (2,1,1,1) -> (2,1,1,1)
9: (3,1) -> (3,1) 24: (1,4) -> (1)
10: (2,2) -> (2,2) 25: (1,3,1) -> (1,1)
11: (2,1,1) -> (2,1,1) 26: (1,2,2) -> (1,2)
12: (1,3) -> (1) 27: (1,2,1,1) -> (1,1,1)
13: (1,2,1) -> (1,1) 28: (1,1,3) -> (1,1)
14: (1,1,2) -> (1,1) 29: (1,1,2,1) -> (1,1,1)
MATHEMATICA
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[First/@Split[stc[n], Less], {n, 0, 100}]
CROSSREFS
Row-leaders are A065120.
Row-lengths are A124768.
Other types of runs: A374251, A374515, A374740.
The weak version is A374629, sum A374630, length A124766.
Row-sums are A374684.
Positions of identical rows are A374685, counted by A374686.
Positions of distinct (strict) rows are A374698, counted by A374687.
The opposite version is A374757, sum A374758, length A124769.
All of the following pertain to compositions in standard order:
- Length is A000120.
- Sum is A029837(n+1) (or sometimes A070939).
- Parts are listed by A066099.
- Number of adjacent equal pairs is A124762, unequal A333382.
- Number of max runs: A124765, A124767, A333381.
- Run-length transform is A333627, sum A070939.
- Run-compression transform is A373948, sum A373953, excess A373954.
- Ranks of contiguous compositions are A374249, counted by A274174.
- Ranks of non-contiguous compositions are A374253, counted by A335548.
KEYWORD
nonn,tabf
AUTHOR
Gus Wiseman, Jul 26 2024
STATUS
approved
Irregular triangle read by rows where row n lists the leaders of weakly decreasing runs in the n-th composition in standard order.
+10
39
1, 2, 1, 3, 2, 1, 2, 1, 4, 3, 2, 2, 1, 3, 1, 2, 1, 2, 1, 5, 4, 3, 3, 2, 3, 2, 2, 2, 2, 1, 4, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 6, 5, 4, 4, 3, 3, 3, 2, 3, 2, 4, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 2, 1, 5, 1, 4, 1, 3, 1, 3, 1, 2, 3, 1, 2, 1, 2, 2, 1, 2, 1, 4
OFFSET
0,2
COMMENTS
The leaders of weakly decreasing runs in a sequence are obtained by splitting it into maximal weakly decreasing subsequences and taking the first term of each.
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.
EXAMPLE
The maximal weakly decreasing subsequences of the 1234567th composition in standard order are ((3,2,1),(2,2,1),(2),(5,1,1,1)), so row 1234567 is (3,2,2,5).
The nonnegative integers, corresponding compositions, and leaders of weakly decreasing runs begin:
0: () -> () 15: (1,1,1,1) -> (1)
1: (1) -> (1) 16: (5) -> (5)
2: (2) -> (2) 17: (4,1) -> (4)
3: (1,1) -> (1) 18: (3,2) -> (3)
4: (3) -> (3) 19: (3,1,1) -> (3)
5: (2,1) -> (2) 20: (2,3) -> (2,3)
6: (1,2) -> (1,2) 21: (2,2,1) -> (2)
7: (1,1,1) -> (1) 22: (2,1,2) -> (2,2)
8: (4) -> (4) 23: (2,1,1,1) -> (2)
9: (3,1) -> (3) 24: (1,4) -> (1,4)
10: (2,2) -> (2) 25: (1,3,1) -> (1,3)
11: (2,1,1) -> (2) 26: (1,2,2) -> (1,2)
12: (1,3) -> (1,3) 27: (1,2,1,1) -> (1,2)
13: (1,2,1) -> (1,2) 28: (1,1,3) -> (1,3)
14: (1,1,2) -> (1,2) 29: (1,1,2,1) -> (1,2)
MATHEMATICA
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[First/@Split[stc[n], GreaterEqual], {n, 0, 100}]
CROSSREFS
Row-leaders are A065120.
Row-lengths are A124765.
Other types of runs are A374251, A374515, A374683, A374757.
The opposite is A374629.
Positions of distinct (strict) rows are A374701, counted by A374743.
Row-sums are A374741, opposite A374630.
Positions of identical rows are A374744, counted by A374742.
All of the following pertain to compositions in standard order:
- Length is A000120.
- Sum is A029837(n+1) (or sometimes A070939).
- Parts are listed by A066099.
- Number of adjacent equal pairs is A124762, unequal A333382.
- Number of max runs: A124765, A124766, A124767, A124768, A124769, A333381.
- Ranks of anti-run compositions are A333489, counted by A003242.
- Run-length transform is A333627, sum A070939.
- Run-compression transform is A373948, sum A373953, excess A373954.
- Ranks of contiguous compositions are A374249, counted by A274174.
- Ranks of non-contiguous compositions are A374253, counted by A335548.
KEYWORD
nonn,tabf
AUTHOR
Gus Wiseman, Jul 24 2024
STATUS
approved
Triangle read by rows where T(n,k) is the number of integer compositions of n whose leaders of strictly increasing runs sum to k.
+10
31
1, 0, 1, 0, 0, 2, 0, 1, 0, 3, 0, 1, 2, 0, 5, 0, 1, 3, 5, 0, 7, 0, 2, 4, 6, 9, 0, 11, 0, 2, 7, 10, 13, 17, 0, 15, 0, 3, 8, 20, 23, 24, 28, 0, 22, 0, 3, 14, 26, 47, 47, 42, 47, 0, 30, 0, 5, 17, 45, 66, 101, 92, 71, 73, 0, 42, 0, 5, 27, 61, 124, 154, 201, 166, 116, 114, 0, 56
OFFSET
0,6
COMMENTS
The leaders of strictly increasing runs in a sequence are obtained by splitting it into maximal strictly increasing subsequences and taking the first term of each.
EXAMPLE
Triangle begins:
1
0 1
0 0 2
0 1 0 3
0 1 2 0 5
0 1 3 5 0 7
0 2 4 6 9 0 11
0 2 7 10 13 17 0 15
0 3 8 20 23 24 28 0 22
0 3 14 26 47 47 42 47 0 30
0 5 17 45 66 101 92 71 73 0 42
0 5 27 61 124 154 201 166 116 114 0 56
0 7 33 101 181 300 327 379 291 182 170 0 77
0 8 48 138 307 467 668 656 680 488 282 253 0 101
Row n = 6 counts the following compositions:
. (15) (24) (231) (312) . (6)
(123) (141) (213) (2121) (51)
(114) (132) (2112) (42)
(1212) (1311) (1221) (411)
(1131) (1122) (33)
(1113) (12111) (321)
(11211) (3111)
(11121) (222)
(11112) (2211)
(21111)
(111111)
MATHEMATICA
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n], Total[First/@Split[#, Less]]==k&]], {n, 0, 15}, {k, 0, n}]
CROSSREFS
Column n = k is A000041.
Column k = 1 is A096765.
Column k = 2 is A374705.
Row-sums are A011782.
For length instead of sum we have A333213.
Leaders of strictly increasing runs in standard compositions are A374683.
The corresponding rank statistic is A374684.
Other types of runs (instead of strictly increasing):
- For leaders of constant runs we have A373949.
- For leaders of anti-runs we have A374521.
- For leaders of weakly increasing runs we have A374637.
- For leaders of weakly decreasing runs we have A374748.
- For leaders of strictly decreasing runs we have A374766.
A003242 counts anti-run compositions.
A238130, A238279, A333755 count compositions by number of runs.
A274174 counts contiguous compositions, ranks A374249.
A335548 counts non-contiguous compositions, ranks A374253.
KEYWORD
nonn,tabl
AUTHOR
Gus Wiseman, Jul 27 2024
STATUS
approved
Number of integer compositions of n whose leaders of weakly increasing runs are strictly increasing.
+10
29
1, 1, 2, 3, 5, 7, 12, 17, 28, 43, 67, 103, 162, 245, 374, 569, 854, 1278, 1902, 2816, 4148, 6087, 8881, 12926, 18726, 27042
OFFSET
0,3
COMMENTS
The leaders of weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.
EXAMPLE
The composition (1,3,3,2,4,3) has weakly increasing runs ((1,3,3),(2,4),(3)), with leaders (1,2,3), so is counted under a(16).
The a(0) = 1 through a(7) = 17 compositions:
() (1) (2) (3) (4) (5) (6) (7)
(11) (12) (13) (14) (15) (16)
(111) (22) (23) (24) (25)
(112) (113) (33) (34)
(1111) (122) (114) (115)
(1112) (123) (124)
(11111) (132) (133)
(222) (142)
(1113) (223)
(1122) (1114)
(11112) (1123)
(111111) (1132)
(1222)
(11113)
(11122)
(111112)
(1111111)
MATHEMATICA
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n], Less@@First/@Split[#, LessEqual]&]], {n, 0, 15}]
CROSSREFS
Ranked by positions of strictly increasing rows in A374629 (sums A374630).
Types of runs (instead of weakly increasing):
- For leaders of constant runs we have A000041.
- For leaders of anti-runs we have A374679.
- For leaders of strictly increasing runs we have A374688.
- For leaders of strictly decreasing runs we have A374762.
Types of run-leaders (instead of strictly increasing):
- For strictly decreasing leaders we appear to have A188920.
- For weakly decreasing leaders we appear to have A189076.
- For identical leaders we have A374631.
- For distinct leaders we have A374632, ranks A374768.
- For weakly increasing leaders we have A374635.
A003242 counts anti-run compositions.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A274174 counts contiguous compositions, ranks A374249.
A335456 counts patterns matched by compositions.
A335548 counts non-contiguous compositions, ranks A374253.
A374637 counts compositions by sum of leaders of weakly increasing runs.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Jul 23 2024
STATUS
approved
Number of integer compositions of n whose leaders of weakly increasing runs are identical.
+10
27
1, 1, 2, 3, 6, 10, 19, 34, 63, 116, 218, 405, 763, 1436, 2714, 5127, 9718, 18422, 34968, 66397, 126168, 239820, 456027, 867325, 1649970, 3139288, 5973746, 11368487, 21636909, 41182648, 78389204, 149216039, 284046349, 540722066, 1029362133, 1959609449
OFFSET
0,3
COMMENTS
The leaders of weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.
LINKS
FORMULA
G.f.: 1 + Sum_{i>0} A(x,i) where A(x,i) = 1/(1-x^i) * (x^i + Sum_{z>0} ( ((x^i)/(1-x^i) * (-1 + Product_{j>i} (1/(1-x^j))))^z )) is the g.f. for compositions of this kind with all leaders equal to i. - John Tyler Rascoe, Jul 25 2024
EXAMPLE
The composition (1,3,1,4,1,2,2,1) has maximal weakly increasing subsequences ((1,3),(1,4),(1,2,2),(1)), with leaders (1,1,1,1), so is counted under a(15).
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) (141)
(1121) (222)
(1211) (1113)
(11111) (1122)
(1131)
(1212)
(1221)
(1311)
(11112)
(11121)
(11211)
(12111)
(111111)
MATHEMATICA
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n], SameQ@@First/@Split[#, LessEqual]&]], {n, 0, 15}]
PROG
(PARI)
C_x(N) = {my(x='x+O('x^N), h=1+sum(i=1, N, 1/(1-x^i)*(x^i+sum(z=1, N-i+1, (x^i/(1-x^i)*(-1+(1/prod(j=i+1, N-i, 1-x^j))))^z)))); Vec(h)}
C_x(40) \\ John Tyler Rascoe, Jul 25 2024
CROSSREFS
Ranked by A374633 = positions of identical rows in A374629 (sums A374630).
Types of runs (instead of weakly increasing):
- For leaders of identical runs we have A000005 for n > 0, ranks A272919.
- For leaders of anti-runs we have A374517, ranks A374519.
- For leaders of strictly increasing runs we have A374686, ranks A374685.
- For leaders of weakly decreasing runs we have A374742, ranks A374744.
- For leaders of strictly decreasing runs we have A374760, ranks A374759.
Types of run-leaders (instead of identical):
- For strictly decreasing leaders we appear to have A188920.
- For weakly decreasing leaders we appear to have A189076.
- For distinct leaders we have A374632, ranks A374768.
- For strictly increasing leaders we have A374634.
- For weakly increasing leaders we have A374635.
A003242 counts anti-run compositions.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A274174 counts contiguous compositions, ranks A374249.
A335456 counts patterns matched by compositions.
A335548 counts non-contiguous compositions, ranks A374253.
A374637 counts compositions by sum of leaders of weakly increasing runs.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jul 23 2024
EXTENSIONS
a(26) onwards from John Tyler Rascoe, Jul 25 2024
STATUS
approved
Irregular triangle read by rows where row n lists the leaders of strictly decreasing runs in the n-th composition in standard order.
+10
27
1, 2, 1, 1, 3, 2, 1, 2, 1, 1, 1, 4, 3, 2, 2, 2, 1, 1, 3, 1, 2, 1, 1, 2, 1, 1, 1, 1, 5, 4, 3, 3, 1, 2, 3, 2, 2, 2, 2, 2, 1, 1, 1, 4, 1, 3, 1, 2, 2, 1, 2, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 6, 5, 4, 4, 1, 3, 3, 3, 3, 2, 3, 1, 1, 2, 4, 2, 3
OFFSET
0,2
COMMENTS
The leaders of strictly decreasing runs in a sequence are obtained by splitting it into maximal strictly decreasing subsequences and taking the first term of each.
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.
EXAMPLE
the 1234567th composition in standard order is (3,2,1,2,2,1,2,5,1,1,1), with strictly decreasing runs ((3,2,1),(2),(2,1),(2),(5,1),(1),(1)), so row 1234567 is (3,2,2,2,5,1,1).
The nonnegative integers, corresponding compositions, and leaders of strictly decreasing runs begin:
0: () -> () 15: (1,1,1,1) -> (1,1,1,1)
1: (1) -> (1) 16: (5) -> (5)
2: (2) -> (2) 17: (4,1) -> (4)
3: (1,1) -> (1,1) 18: (3,2) -> (3)
4: (3) -> (3) 19: (3,1,1) -> (3,1)
5: (2,1) -> (2) 20: (2,3) -> (2,3)
6: (1,2) -> (1,2) 21: (2,2,1) -> (2,2)
7: (1,1,1) -> (1,1,1) 22: (2,1,2) -> (2,2)
8: (4) -> (4) 23: (2,1,1,1) -> (2,1,1)
9: (3,1) -> (3) 24: (1,4) -> (1,4)
10: (2,2) -> (2,2) 25: (1,3,1) -> (1,3)
11: (2,1,1) -> (2,1) 26: (1,2,2) -> (1,2,2)
12: (1,3) -> (1,3) 27: (1,2,1,1) -> (1,2,1)
13: (1,2,1) -> (1,2) 28: (1,1,3) -> (1,1,3)
14: (1,1,2) -> (1,1,2) 29: (1,1,2,1) -> (1,1,2)
MATHEMATICA
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[First/@Split[stc[n], Greater], {n, 0, 100}]
CROSSREFS
Row-leaders of nonempty rows are A065120.
Row-lengths are A124769.
The opposite version is A374683, sum A374684, length A124768.
The weak version is A374740, sum A374741, length A124765.
Row-sums are A374758.
Positions of identical rows are A374759 (counted by A374760).
Positions of distinct (strict) rows are A374767 (counted by A374761).
All of the following pertain to compositions in standard order:
- Length is A000120.
- Sum is A029837(n+1).
- Parts are listed by A066099.
- Number of adjacent equal pairs is A124762, unequal A333382.
- Run-length transform is A333627, sum A070939.
- Run-compression transform is A373948, sum A373953, excess A373954.
- Ranks of contiguous compositions are A374249, counted by A274174.
- Ranks of non-contiguous compositions are A374253, counted by A335548.
Six types of runs:
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jul 29 2024
STATUS
approved
Number of integer compositions of n whose leaders of weakly decreasing runs are identical.
+10
24
1, 1, 2, 3, 5, 8, 13, 21, 34, 54, 87, 138, 220, 349, 556, 881, 1403, 2229, 3551, 5653, 9019, 14387, 22988, 36739, 58785, 94100, 150765, 241658, 387617, 622002, 998658, 1604032, 2577512, 4143243, 6662520, 10716931, 17243904, 27753518, 44680121, 71947123, 115880662
OFFSET
0,3
COMMENTS
The weakly decreasing run-leaders of a sequence are obtained by splitting into maximal weakly decreasing subsequences and taking the first term of each.
EXAMPLE
The composition (3,1,3,2,1,3,3) has maximal weakly decreasing subsequences ((3,1),(3,2,1),(3,3)), with leaders (3,3,3), so is counted under a(16).
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) (321)
(2111) (411)
(11111) (2112)
(2121)
(2211)
(3111)
(21111)
(111111)
MATHEMATICA
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n], SameQ@@First/@Split[#, GreaterEqual]&]], {n, 0, 15}]
CROSSREFS
Ranked by A374744 = positions of identical rows in A374740, cf. A374629.
Types of runs (instead of weakly decreasing):
- For leaders of identical runs we have A000005 for n > 0, ranks A272919.
- For leaders of anti-runs we have A374517, ranks A374519.
- For leaders of strictly increasing runs we have A374686, ranks A374685.
- For leaders of weakly increasing runs we have A374631, ranks A374633.
- For leaders of strictly decreasing runs we have A374760, ranks A374759.
Types of run-leaders (instead of identical):
- For strictly decreasing leaders we have A374746.
- For weakly decreasing leaders we have A374747.
- For distinct leaders we have A374743, ranks A374701.
- For weakly increasing leaders we appear to have A188900.
A003242 counts anti-run compositions, ranks A333489.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A274174 counts contiguous compositions, ranks A374249.
A335456 counts patterns matched by compositions.
A335548 counts non-contiguous compositions, ranks A374253.
A373949 counts compositions by run-compressed sum, opposite A373951.
A374748 counts compositions by sum of leaders of weakly decreasing runs.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jul 25 2024
EXTENSIONS
a(24)-a(40) from Alois P. Heinz, Jul 26 2024
STATUS
approved

Search completed in 0.182 seconds