A056823 -id:A056823 - cp's OEIS frontend

A237272 Number of overcompositions of n that contain at least two parts in increasing order and that contain at least one overlined part.

0, 0, 0, 3, 9, 27, 83, 211, 522, 1222, 2874, 6496, 14593, 32185, 70423, 153024, 330195, 708933, 1514821, 3224134, 6836547, 14455648, 30475210, 64096487, 134493519, 281642590, 588642240, 1228160742, 2558300338, 5321065857, 11051923912, 22925167566

Offset: 0

Omar E. Pol, Feb 09 2014

nonn

Number of overcompositions of n minus the number of overpartitions of n plus the number of partitions of n minus the number of compositions of n.

Cf. A000041, A011782, A015128, A056823, A230441, A236002, A236633, A237044, A237045.

a(n) = A236002(n) - A015128(n) + A000041(n) - A011782(n) = A236002(n) - A230441(n) - A011782(n) = A237045(n) - A056823(n).

A332871 Number of compositions of n whose run-lengths are not weakly increasing.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 8, 24, 55, 128, 282, 625, 1336, 2855, 6000, 12551, 26022, 53744, 110361, 225914, 460756, 937413, 1902370, 3853445, 7791647, 15732468, 31725191, 63907437, 128613224, 258626480, 519700800, 1043690354, 2094882574, 4202903667, 8428794336, 16897836060

Offset: 0

Gus Wiseman, Feb 29 2020

nonn

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

Also compositions whose run-lengths are not weakly decreasing.

			The a(4) = 1 through a(6) = 8 compositions:
  (112)  (113)   (114)
         (221)   (1113)
         (1112)  (1131)
         (1121)  (1221)
                 (2112)
                 (11112)
                 (11121)
                 (11211)
For example, the composition (2,1,1,2) has run-lengths (1,2,1), which are not weakly increasing, so (2,1,1,2) is counted under a(6).

Andrew Howroyd, Table of n, a(n) for n = 0..1000

The version for the compositions themselves (not run-lengths) is A056823.
The version for unsorted prime signature is A112769, with dual A071365.
The case without weakly decreasing run-lengths either is A332833.
The complement is counted by A332836.
Compositions that are not unimodal are A115981.
Compositions with equal run-lengths are A329738.
Compositions whose run-lengths are not unimodal are A332727.
Cf. A001523, A072704, A100883, A181819, A329744, A329766, A332641, A332669, A332726, A332745, A332746, A332834, A332835.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!LessEqual@@Length/@Split[#]&]],{n,0,10}]

a(n) = 2^(n - 1) - A332836(n).

Terms a(21) and beyond from Andrew Howroyd, Dec 30 2020

A375297 Number of integer compositions of n matching both of the dashed patterns 23-1 and 1-32.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 21, 68, 199, 545, 1410, 3530, 8557, 20255, 46968, 107135, 240927, 535379, 1177435, 2566618, 5551456

Offset: 0

Gus Wiseman, Aug 23 2024

Also the number of integer compositions of n whose leaders of maximal weakly increasing runs are not weakly decreasing and whose reverse satisfies the same condition.

			The a(0) = 0 through a(11) = 21 compositions:
  .  .  .  .  .  .  .  .  .  (12321)  (1342)    (1352)
                                      (2431)    (2531)
                                      (12421)   (11342)
                                      (13231)   (12431)
                                      (112321)  (12521)
                                      (123211)  (13241)
                                                (13421)
                                                (14231)
                                                (23132)
                                                (24311)
                                                (112421)
                                                (113231)
                                                (122321)
                                                (123212)
                                                (123221)
                                                (124211)
                                                (132311)
                                                (212321)
                                                (1112321)
                                                (1123211)
                                                (1232111)

Wikipedia, Permutation pattern.
Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

For leaders of identical runs we have A332834.
For just one of the two conditions we have A374636, ranks A375137/A375138.
These compositions are ranked by A375407.
A003242 counts anti-runs, ranks A333489.
A011782 counts compositions.
A106356 counts compositions by number of maximal anti-runs.
A238130, A238279, A333755 count compositions by number of runs.
A274174 counts contiguous compositions, ranks A374249.
A335456 counts patterns matched by compositions.
Cf. A000041, A056823, A188920, A189076, A238343, A333213, A335514, A374631, A374632, A374635, A374681.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], MatchQ[#,{_,y_,z_,_,x_,_}/;x_,x_,_,z_,y_,_}/;x

A375406 Number of integer compositions of n that match the dashed pattern 3-12.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 4, 14, 41, 110, 278, 673, 1576, 3599, 8055, 17732, 38509, 82683, 175830, 370856, 776723, 1616945, 3348500, 6902905, 14174198, 29004911, 59175625, 120414435, 244468774, 495340191, 1001911626, 2023473267, 4081241473, 8222198324, 16548146045, 33276169507

Offset: 0

Gus Wiseman, Aug 22 2024

nonn

First differs from the non-dashed version A335514 at a(9) = 41, A335514(9) = 42, due to the composition (3,1,3,2).

Also the number of integer compositions of n whose leaders of weakly decreasing runs are not weakly increasing. For example, the composition q = (1,1,2,1,2,2,1,3) has maximal weakly decreasing runs ((1,1),(2,1),(2,2,1),(3)), with leaders (1,2,2,3), which are weakly increasing, so q is not counted under a(13); also q does not match 3-12. On the other hand, the reverse is (3,1,2,2,1,2,1,1), with maximal weakly decreasing runs ((3,1),(2,2,1),(2,1,1)), with leaders (3,2,2), which are not weakly increasing, so it is counted under a(13); meanwhile it matches 3-12, as required.

			The a(0) = 0 through a(8) = 14 compositions:
  .  .  .  .  .  .  (312)  (412)   (413)
                           (1312)  (512)
                           (3112)  (1412)
                           (3121)  (2312)
                                   (3122)
                                   (3212)
                                   (4112)
                                   (4121)
                                   (11312)
                                   (13112)
                                   (13121)
                                   (31112)
                                   (31121)
                                   (31211)

Wikipedia, Permutation pattern.
Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

For leaders of identical runs we have A056823.
The complement is counted by A188900.
The non-dashed version is A335514, ranks A335479.
Ranks are positions of non-weakly increasing rows in A374740.
A003242 counts anti-run compositions, ranks A333489.
A011782 counts compositions.
Counting compositions by number of runs: A238130, A238279, A333755.
A373949 counts compositions by run-compressed sum, opposite A373951.
Cf. A106356, A188920, A189076, A189077, A238343, A333213, A335548, A374629, A374637, A374679, A374748.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !LessEqual@@First/@Split[#,GreaterEqual]&]],{n,0,15}]
- or -
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], MatchQ[#,{_,z_,_,x_,y_,_}/;x

a(n>0) = 2^(n-1) - A188900(n).

A376263 Number of strict integer compositions of n whose leaders of increasing runs are increasing.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 5, 6, 8, 11, 18, 21, 30, 38, 52, 77, 96, 126, 167, 217, 278, 402, 488, 647, 822, 1073, 1340, 1747, 2324, 2890, 3695, 4690, 5924, 7469, 9407, 11718, 15405, 18794, 23777, 29507, 37188, 45720, 57404, 70358, 87596, 110672, 135329, 167018, 206761, 254200, 311920

Offset: 0

Gus Wiseman, Sep 18 2024

nonn

The leaders of increasing runs of a sequence are obtained by splitting it into maximal increasing subsequences and taking the first term of each.

			The a(1) = 1 through a(9) = 11 compositions:
 (1) (2) (3)   (4)   (5)   (6)     (7)     (8)     (9)
         (1,2) (1,3) (1,4) (1,5)   (1,6)   (1,7)   (1,8)
                     (2,3) (2,4)   (2,5)   (2,6)   (2,7)
                           (1,2,3) (3,4)   (3,5)   (3,6)
                           (1,3,2) (1,2,4) (1,2,5) (4,5)
                                   (1,4,2) (1,3,4) (1,2,6)
                                           (1,4,3) (1,3,5)
                                           (1,5,2) (1,5,3)
                                                   (1,6,2)
                                                   (2,3,4)
                                                   (2,4,3)

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

For less-greater or greater-less we have A294617.
This is a strict case of A374688, weak version A374635.
The strict less-greater version is A374689, weak version A189076.
A003242 counts anti-run compositions, ranks A333489.
A011782 counts compositions, strict A032020.
A238130, A238279, A333755 count compositions by number of runs.
A373949 counts compositions by run-compressed sum, opposite A373951.
A374700 counts compositions by sum of leaders of strictly increasing runs.
Cf. A000110, A008289, A056823, A106356, A188920, A238343, A261982, A274174, A333213, A374634, A374683, A374698, A374763.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@#&&Less@@First/@Split[#,Less]&]],{n,0,15}]

\\ here Q(n) gives n-th row of A008289.
Q(n)={Vecrev(polcoef(prod(k=1, n, 1 + y*x^k, 1 + O(x*x^n)), n)/y)}
a(n)={if(n==0, 1, my(r=Q(n), s=Vec(serlaplace(exp(exp(x+O(x^#r))- 1)))); sum(k=1, #r, r[k]*s[k]))} \\ Andrew Howroyd, Sep 18 2024

a(n) = Sum_{k>=1} A008289(n,k)*A000110(k-1) for n > 0. - Andrew Howroyd, Sep 18 2024

a(26) onwards from Andrew Howroyd, Sep 18 2024

A174523 Triangle T(n,1) = A117989(n+1) in the first column and recursively T(n,k) = 2*T(n-1,k-1).

Original entry on oeis.org

1, 1, 2, 3, 2, 4, 3, 6, 4, 8, 7, 6, 12, 8, 16, 8, 14, 12, 24, 16, 32, 14, 16, 28, 24, 48, 32, 64, 18, 28, 32, 56, 48, 96, 64, 128, 28, 36, 56, 64, 112, 96, 192, 128, 256, 35, 56, 72, 112, 128, 224, 192, 384, 256, 512, 53, 70, 112, 144, 224, 256

Offset: 1

Alford Arnold, Mar 30 2010

			1;
1,2;
3,2,4;
3,6,4,8;
7,6,12,8,16;
8,14,12,24,16,32;
14,16,28,24,48,32,64;
18,28,32,56,48,96,64,128;
28,36,56,64,112,96,192,128,256;
35,56,72,112,128,224,192,384,256,512;

Cf. A056823 (row sums).

A174523 := proc(n,k)
    option remember;
    if k = 1 then
        A117989(n+1) ;
    elif k > n then
        0;
    else
        2*procname(n-1,k-1) ;
    end if;
end proc: # R. J. Mathar, May 19 2016

Edited by R. J. Mathar, May 17 2016

A229935 Total number of parts in all compositions of n with at least two parts in increasing order.

Original entry on oeis.org

0, 0, 0, 2, 8, 28, 77, 202, 490, 1152, 2624, 5869, 12913, 28116, 60660, 130004, 277065, 587859, 1242540, 2617942, 5500394, 11528284, 24109349, 50321442, 104844426, 218086957, 452963310, 939496802, 1946122511, 4026488387, 8321444573, 17179801049, 35433395265

Offset: 0

Omar E. Pol, Oct 14 2013

nonn

Total number of parts in all compositions of n that are not partitions of n (see example).

			For n = 4 the table shows both the compositions and the partitions of 4. There are three compositions of 4 that are not partitions of 4.
----------------------------------------------------
Compositions       Partitions       Number of parts
----------------------------------------------------
[1, 1, 1, 1]   =   [1, 1, 1, 1]
[2, 1, 1]      =   [2, 1, 1]
[1, 2, 1]                                 3
[3, 1]         =   [3, 1]
[1, 1, 2]                                 3
[2, 2]         =   [2, 2]
[1, 3]                                    2
[4]            =   [4]
----------------------------------------------------
Total                                     8
.
A partition of a positive integer n is any nonincreasing sequence of positive integers which sum to n, ence the compositions of 4 that are not partitions of 4 are [1, 2, 1], [1, 1, 2] and [1, 3]. The total number of parts of these compositions is 3 + 3 + 2 = 8. On the other hand the total number of parts in all compositions of 4 is A001792(4-1) = 20, and the total number of parts in all partitions of 4 is A006128(4) = 12, so a(4) = 20 - 12 = 8.

Cf. A000041, A001792, A006128, A001782, A056823, A229936.

a(n) = A001792(n-1) - A006128(n), n >= 1.

A229936 Sum of all parts of all compositions of n with at least two parts in increasing order.

Original entry on oeis.org

0, 0, 0, 3, 12, 45, 126, 343, 848, 2034, 4700, 10648, 23652, 51935, 112798, 243120, 520592, 1109063, 2352366, 4971426, 10473220, 22003464, 46115300, 96440127, 201288792, 419381450, 872351896, 1811858058, 3757992280, 7784495839, 16105959240, 33285784442

Offset: 0

Omar E. Pol, Oct 14 2013

nonn

Sum of all parts of all compositions of n that are not partitions of n (see example).

			For n = 4 the table shows both the compositions and the partitions of 4. There are three compositions of 4 that are not partitions of 4.
----------------------------------------------------
Compositions       Partitions      Sum of all parts
----------------------------------------------------
[1, 1, 1, 1]   =   [1, 1, 1, 1]
[2, 1, 1]      =   [2, 1, 1]
[1, 2, 1]                                 4
[3, 1]         =   [3, 1]
[1, 1, 2]                                 4
[2, 2]         =   [2, 2]
[1, 3]                                    4
[4]            =   [4]
----------------------------------------------------
Total                                    12
.
A partition of a positive integer n is any nonincreasing sequence of positive integers which sum to n, ence the compositions of 4 that are not partitions of 4 are [1, 2, 1], [1, 1, 2] and [1, 3]. The sum of all parts of these compositions is 1+3+1+2+1+1+1+2 = 3*4 = 12. On the other hand the sum of all parts in all compositions of 4 is A001787(4) = 32, and the sum of all parts in all partitions of 4 is A066186(4) = 20, so a(4) = 32 - 20 = 12.

Cf. A000041, A001787, A011782, A056823, A066186, A229935.

a(n) = n*A056823(n) = n*(A011782(n) - A000041(n)).

a(n) = A001787(n) - A066186(n), n >= 1.

A337698 Number of compositions of n that are not strictly increasing.

Original entry on oeis.org

0, 0, 1, 2, 6, 13, 28, 59, 122, 248, 502, 1012, 2033, 4078, 8170, 16357, 32736, 65498, 131026, 262090, 524224, 1048500, 2097063, 4194200, 8388486, 16777074, 33554267, 67108672, 134217506, 268435200, 536870616, 1073741484, 2147483258, 4294966848, 8589934080

Offset: 0

Gus Wiseman, Oct 06 2020

nonn

			The a(2) = 1 through a(5) = 13 compositions:
  (11)  (21)   (22)    (32)
        (111)  (31)    (41)
               (112)   (113)
               (121)   (122)
               (211)   (131)
               (1111)  (212)
                       (221)
                       (311)
                       (1112)
                       (1121)
                       (1211)
                       (2111)
                       (11111)

A000009 counts the complement.
A047967 is the unordered version.
A056823 is the weak version.
A140106 counts the unordered case of length 3.
A242771 counts the case of length 3.
A333255 is the complement of a ranking sequence (using standard compositions A066099) for these compositions.
A337481 counts these compositions that are not strictly decreasing.
A337482 counts these compositions that are not weakly decreasing.
A001523 counts unimodal compositions, with complement A115981.
A007318 and A097805 count compositions by length.
A218004 counts strictly increasing or weakly decreasing compositions.
Cf. A000212, A128422, A332745, A332834, A332835, A337484.

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

a(n) = 2^(n-1) - A000009(n) for n > 0.

cp's OEIS Frontend

A237272 Number of overcompositions of n that contain at least two parts in increasing order and that contain at least one overlined part.

Views

Author

Keywords

Comments

Crossrefs

Formula

A332871 Number of compositions of n whose run-lengths are not weakly increasing.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A375297 Number of integer compositions of n matching both of the dashed patterns 23-1 and 1-32.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A375406 Number of integer compositions of n that match the dashed pattern 3-12.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A376263 Number of strict integer compositions of n whose leaders of increasing runs are increasing.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A174523 Triangle T(n,1) = A117989(n+1) in the first column and recursively T(n,k) = 2*T(n-1,k-1).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Extensions

A229935 Total number of parts in all compositions of n with at least two parts in increasing order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A229936 Sum of all parts of all compositions of n with at least two parts in increasing order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A337698 Number of compositions of n that are not strictly increasing.