A351202
Number of permutations of the multiset of prime factors of n (or ordered prime factorizations of n) with all distinct runs.
Original entry on oeis.org
1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 4, 1, 2, 1, 2, 1, 6, 1, 1, 2, 2, 2, 2, 1, 2, 2, 4, 1, 6, 1, 2, 2, 2, 1, 4, 1, 2, 2, 2, 1, 4, 2, 4, 2, 2, 1, 6, 1, 2, 2, 1, 2, 6, 1, 2, 2, 6, 1, 4, 1, 2, 2, 2, 2, 6, 1, 4, 1, 2, 1, 6, 2, 2, 2
Offset: 1
The a(36) = 2 permutations are (1,1,2,2), (2,2,1,1). Missing are: (1,2,1,2), (1,2,2,1), (2,1,1,2), (2,1,2,1). Here we use prime indices instead of factors.
The maximum number of possible permutations is
A008480.
A005811 counts runs in binary expansion.
A044813 lists numbers whose binary expansion has distinct run-lengths.
A098859 counts partitions with distinct multiplicities, ordered
A242882.
A283353 counts normal multisets with a permutation without distinct runs.
A297770 counts distinct runs in binary expansion.
A351014 counts distinct runs in standard compositions, firsts
A351015.
A351204 = partitions whose perms. have distinct runs, complement
A351203.
Counting words with all distinct runs:
-
Table[Length[Select[Permutations[Join@@ ConstantArray@@@FactorInteger[n]],UnsameQ@@Split[#]&]],{n,100}]
A373951
Triangle read by rows where T(n,k) is the number of integer compositions of n such that replacing each run of repeated parts with a single part (run-compression) yields a composition of n - k.
Original entry on oeis.org
1, 1, 0, 1, 1, 0, 3, 0, 1, 0, 4, 2, 1, 1, 0, 7, 4, 4, 0, 1, 0, 14, 5, 6, 5, 1, 1, 0, 23, 14, 10, 10, 6, 0, 1, 0, 39, 26, 29, 12, 14, 6, 1, 1, 0, 71, 46, 54, 40, 19, 16, 9, 0, 1, 0, 124, 92, 96, 82, 64, 22, 22, 8, 1, 1, 0, 214, 176, 204, 144, 137, 82, 30, 26, 10, 0, 1, 0
Offset: 0
Triangle begins:
1
1 0
1 1 0
3 0 1 0
4 2 1 1 0
7 4 4 0 1 0
14 5 6 5 1 1 0
23 14 10 10 6 0 1 0
39 26 29 12 14 6 1 1 0
71 46 54 40 19 16 9 0 1 0
124 92 96 82 64 22 22 8 1 1 0
Row n = 6 counts the following compositions:
(6) (411) (3111) (33) (222) (111111) .
(51) (114) (1113) (2211)
(15) (1311) (1221) (1122)
(42) (1131) (12111) (21111)
(24) (2112) (11211) (11112)
(141) (11121)
(321)
(312)
(231)
(213)
(132)
(123)
(2121)
(1212)
For example, the composition (1,2,2,1) with compression (1,2,1) is counted under T(6,2).
Column k = 0 is
A003242 (anti-runs or compressed compositions).
Same as
A373949 with rows reversed.
A114901 counts compositions with no isolated parts.
A116861 counts partitions by compressed sum, by compressed length
A116608.
A240085 counts compositions with no unique parts.
A333755 counts compositions by compressed length.
A373948 represents the run-compression transformation.
Cf.
A037201 (halved
A373947),
A106356,
A124762,
A238130,
A238279,
A238343,
A285981,
A333213,
A333382,
A333489,
A373952.
-
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n], Total[First/@Split[#]]==n-k&]],{n,0,10},{k,0,n}]
A374251
Irregular triangle read by rows where row n is the run-compression of the n-th composition in standard order.
Original entry on oeis.org
1, 2, 1, 3, 2, 1, 1, 2, 1, 4, 3, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 2, 1, 5, 4, 1, 3, 2, 3, 1, 2, 3, 2, 1, 2, 1, 2, 2, 1, 1, 4, 1, 3, 1, 1, 2, 1, 2, 1, 1, 3, 1, 2, 1, 1, 2, 1, 6, 5, 1, 4, 2, 4, 1, 3, 3, 2, 1, 3, 1, 2, 3, 1, 2, 4, 2, 3, 1, 2, 2, 1, 2, 1, 3
Offset: 1
The standard compositions and their run-compressions begin:
0: () --> ()
1: (1) --> (1)
2: (2) --> (2)
3: (1,1) --> (1)
4: (3) --> (3)
5: (2,1) --> (2,1)
6: (1,2) --> (1,2)
7: (1,1,1) --> (1)
8: (4) --> (4)
9: (3,1) --> (3,1)
10: (2,2) --> (2)
11: (2,1,1) --> (2,1)
12: (1,3) --> (1,3)
13: (1,2,1) --> (1,2,1)
14: (1,1,2) --> (1,2)
15: (1,1,1,1) --> (1)
Row n has
A334028(n) distinct elements.
Rows are ranked by
A373948 (standard order).
A003242 counts run-compressed compositions, i.e., anti-runs, ranks
A333489.
A007947 (squarefree kernel) represents run-compression of multisets.
A066099 lists the parts of compositions in standard order.
A116861 counts partitions by sum of run-compression.
A373949 counts compositions by sum of run-compression, opposite
A373951.
Cf.
A000120,
A070939,
A106356,
A124762,
A233564,
A238130,
A238343,
A272919,
A333381,
A333382,
A333627,
A373954,
A374250.
-
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[First/@Split[stc[n]],{n,100}]
A374700
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.
Original entry on oeis.org
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
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)
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.
-
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],Total[First/@Split[#,Less]]==k&]],{n,0,15},{k,0,n}]
A382857
Number of ways to permute the prime indices of n so that the run-lengths are all equal.
Original entry on oeis.org
1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 2, 1, 0, 1, 2, 1, 1, 1, 6, 1, 1, 2, 2, 2, 4, 1, 2, 2, 0, 1, 6, 1, 1, 1, 2, 1, 0, 1, 1, 2, 1, 1, 0, 2, 0, 2, 2, 1, 6, 1, 2, 1, 1, 2, 6, 1, 1, 2, 6, 1, 1, 1, 2, 1, 1, 2, 6, 1, 0, 1, 2, 1, 6, 2, 2
Offset: 0
The prime indices of 216 are {1,1,1,2,2,2} and we have permutations:
(1,1,1,2,2,2)
(1,2,1,2,1,2)
(2,1,2,1,2,1)
(2,2,2,1,1,1)
so a(216) = 4.
The prime indices of 25920 are {1,1,1,1,1,1,2,2,2,2,3} and we have permutations:
(1,2,1,2,1,2,1,2,1,3,1)
(1,2,1,2,1,2,1,3,1,2,1)
(1,2,1,2,1,3,1,2,1,2,1)
(1,2,1,3,1,2,1,2,1,2,1)
(1,3,1,2,1,2,1,2,1,2,1)
so a(25920) = 5.
For distinct instead of equal run-lengths we have
A382771.
For run-sums instead of run-lengths we have
A382877, distinct
A382876.
Positions of first appearances are
A382878.
Positions of terms > 1 are
A383089.
A003963 gives product of prime indices.
A005811 counts runs in binary expansion.
A044813 lists numbers whose binary expansion has distinct run-lengths.
A164707 lists numbers whose binary expansion has all equal run-lengths, distinct
A328592.
A353744 ranks compositions with equal run-lengths, counted by
A329738.
Cf.
A000720,
A000961,
A001221,
A001222,
A003242,
A008480,
A047966,
A238130,
A238279,
A351201,
A351293,
A351295.
-
Table[Length[Select[Permutations[Join@@ConstantArray@@@FactorInteger[n]], SameQ@@Length/@Split[#]&]],{n,0,100}]
A351017
Number of binary words of length n with all distinct run-lengths.
Original entry on oeis.org
1, 2, 2, 6, 6, 10, 22, 26, 38, 54, 114, 130, 202, 266, 386, 702, 870, 1234, 1702, 2354, 3110, 5502, 6594, 9514, 12586, 17522, 22610, 31206, 48630, 60922, 83734, 111482, 149750, 196086, 261618, 336850, 514810, 631946, 862130, 1116654, 1502982, 1916530, 2555734, 3242546
Offset: 0
The a(0) = 1 through a(6) = 22 words:
{} 0 00 000 0000 00000 000000
1 11 001 0001 00001 000001
011 0111 00011 000011
100 1000 00111 000100
110 1110 01111 000110
111 1111 10000 001000
11000 001110
11100 001111
11110 011000
11111 011100
011111
100000
100011
100111
110000
110001
110111
111001
111011
111100
111110
111111
Using binary expansions instead of words gives
A032020, ranked by
A044813.
The version for partitions is
A098859.
The complement is counted by twice
A261982.
A005811 counts runs in binary expansion.
A011782 counts integer compositions.
A242882 counts compositions with distinct multiplicities.
A297770 counts distinct runs in binary expansion.
A325545 counts compositions with distinct differences.
A329767 counts binary words by runs-resistance.
A351014 counts distinct runs in standard compositions.
A351204 counts partitions where every permutation has all distinct runs.
A351290 ranks compositions with all distinct runs.
-
Table[Length[Select[Tuples[{0,1},n],UnsameQ@@Length/@Split[#]&]],{n,0,10}]
-
from itertools import groupby, product
def adrl(s):
runlens = [len(list(g)) for k, g in groupby(s)]
return len(runlens) == len(set(runlens))
def a(n):
if n == 0: return 1
return 2*sum(adrl("1"+"".join(w)) for w in product("01", repeat=n-1))
print([a(n) for n in range(20)]) # Michael S. Branicky, Feb 08 2022
A374761
Number of integer compositions of n whose leaders of strictly decreasing runs are distinct.
Original entry on oeis.org
1, 1, 1, 3, 5, 7, 13, 27, 45, 73, 117, 205, 365, 631, 1061, 1711, 2777, 4599, 7657, 12855, 21409, 35059, 56721, 91149, 146161, 234981, 379277, 612825, 988781, 1587635, 2533029, 4017951, 6342853, 9985087, 15699577, 24679859, 38803005, 60979839, 95698257, 149836255
Offset: 0
The composition (3,1,4,3,2,1,2,8) has strictly decreasing runs ((3,1),(4,3,2,1),(2),(8)), with leaders (3,4,2,8), so is counted under a(24).
The a(0) = 1 through a(6) = 13 compositions:
() (1) (2) (3) (4) (5) (6)
(12) (13) (14) (15)
(21) (31) (23) (24)
(121) (32) (42)
(211) (41) (51)
(131) (123)
(311) (132)
(141)
(213)
(231)
(312)
(321)
(411)
For identical instead of distinct leaders we have
A374760, ranks
A374759.
For partitions instead of compositions we have
A375133.
Other types of runs:
- For leaders of identical runs we have
A000005 for n > 0, ranks
A272919.
Other types of run-leaders:
- For strictly increasing leaders we have
A374762.
- For strictly decreasing leaders we have
A374763.
- For weakly increasing leaders we have
A374764.
- For weakly decreasing leaders we have
A374765.
A374700 counts compositions by sum of leaders of strictly increasing runs.
Cf.
A034296,
A106356,
A188920,
A189076,
A238343,
A333213,
A374517,
A374631,
A374640,
A374686,
A374742.
-
Table[Length[Select[Join @@ Permutations/@IntegerPartitions[n],UnsameQ@@First/@Split[#,Greater]&]],{n,0,15}]
-
dfs(m, r, v) = 1 + sum(s=r, m, if(!setsearch(v, s), dfs(m-s, s, setunion(v, [s]))*x^s + sum(t=1, min(s-1, m-s), dfs(m-s-t, t, setunion(v, [s]))*x^(s+t)*prod(i=t+1, s-1, 1+x^i))));
lista(nn) = Vec(dfs(nn, 1, []) + O(x^(1+nn))); \\ Jinyuan Wang, Feb 13 2025
A374768
Numbers k such that the leaders of weakly increasing runs in the k-th composition in standard order (A066099) are distinct.
Original entry on oeis.org
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48, 50, 52, 56, 58, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81
Offset: 1
The 4444th composition in standard order is (4,2,2,1,1,3), with weakly increasing runs ((4),(2,2),(1,1,3)), with leaders (4,2,1), so 4444 is in the sequence.
These are the positions of strict rows in
A374629 (which has sums
A374630).
Identical instead of distinct leaders are
A374633, counted by
A374631.
For leaders of strictly increasing runs we have
A374698, counted by
A374687.
For leaders of weakly decreasing runs we have
A374701, counted by
A374743.
For leaders of strictly decreasing runs we have
A374767, counted by
A374761.
All of the following pertain to compositions in standard order:
- Ranks of strict compositions are
A233564.
- Ranks of constant compositions are
A272919.
Cf.
A065120,
A188920,
A189076,
A238343,
A333213,
A335449,
A373949,
A274174,
A374249,
A374635,
A374637.
-
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,166],UnsameQ@@First/@Split[stc[#],LessEqual]&]
A358836
Number of multiset partitions of integer partitions of n with all distinct block sizes.
Original entry on oeis.org
1, 1, 2, 4, 8, 15, 28, 51, 92, 164, 289, 504, 871, 1493, 2539, 4290, 7201, 12017, 19939, 32911, 54044, 88330, 143709, 232817, 375640, 603755, 966816, 1542776, 2453536, 3889338, 6146126, 9683279, 15211881, 23830271, 37230720, 58015116, 90174847, 139820368, 216286593
Offset: 0
The a(1) = 1 through a(5) = 15 multiset partitions:
{1} {2} {3} {4} {5}
{1,1} {1,2} {1,3} {1,4}
{1,1,1} {2,2} {2,3}
{1},{1,1} {1,1,2} {1,1,3}
{1,1,1,1} {1,2,2}
{1},{1,2} {1,1,1,2}
{2},{1,1} {1},{1,3}
{1},{1,1,1} {1},{2,2}
{2},{1,2}
{3},{1,1}
{1,1,1,1,1}
{1},{1,1,2}
{2},{1,1,1}
{1},{1,1,1,1}
{1,1},{1,1,1}
From _Gus Wiseman_, Aug 21 2024: (Start)
The a(0) = 1 through a(5) = 15 compositions whose leaders of maximal weakly decreasing runs are strictly increasing:
() (1) (2) (3) (4) (5)
(11) (12) (13) (14)
(21) (22) (23)
(111) (31) (32)
(112) (41)
(121) (113)
(211) (122)
(1111) (131)
(221)
(311)
(1112)
(1121)
(1211)
(2111)
(11111)
(End)
The version for set partitions is
A007837.
For sums instead of sizes we have
A271619.
For constant instead of distinct sizes we have
A319066.
These multiset partitions are ranked by
A326533.
For odd instead of distinct sizes we have
A356932.
The version for twice-partitions is
A358830.
The case of distinct sums also is
A358832.
Ranked by positions of strictly increasing rows in
A374740, opposite
A374629.
A001970 counts multiset partitions of integer partitions.
A335456 counts patterns matched by compositions.
-
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
Table[Length[Select[Join@@mps/@IntegerPartitions[n],UnsameQ@@Length/@#&]],{n,0,10}]
(* second program *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Less@@First/@Split[#,GreaterEqual]&]],{n,0,15}] (* Gus Wiseman, Aug 21 2024 *)
-
P(n,y) = {1/prod(k=1, n, 1 - y*x^k + O(x*x^n))}
seq(n) = {my(g=P(n,y)); Vec(prod(k=1, n, 1 + polcoef(g, k, y) + O(x*x^n)))} \\ Andrew Howroyd, Dec 31 2022
A374634
Number of integer compositions of n whose leaders of weakly increasing runs are strictly increasing.
Original entry on oeis.org
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, 38894, 55789, 79733, 113632, 161426, 228696, 323049, 455135, 639479, 896249, 1252905, 1747327, 2431035, 3374603, 4673880, 6459435, 8908173
Offset: 0
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)
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 weakly increasing leaders we have
A374635.
A003242 counts anti-run compositions.
A335456 counts patterns matched by compositions.
A374637 counts compositions by sum of leaders of weakly increasing runs.
-
Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],Less@@First/@Split[#,LessEqual]&]],{n,0,15}]
-
dfs(m, r, u) = 1 + sum(s=u+1, min(m, r-1), x^s/(1-x^s) + sum(t=s+1, m-s, dfs(m-s-t, t, s)*x^(s+t)/prod(i=s, t, 1-x^i)));
lista(nn) = Vec(dfs(nn, nn+1, 0) + O(x^(1+nn))); \\ Jinyuan Wang, Feb 13 2025
Comments