Displaying 1-10 of 18 results found.
Number of compositions of n with distinct differences.
+10
55
1, 1, 2, 3, 7, 13, 17, 34, 59, 105, 166, 279, 442, 730, 1157, 1927, 3045, 4741, 7527, 11667, 18048, 27928, 43334, 65861, 101385, 153404, 232287, 347643, 523721, 780083, 1165331, 1725966, 2561625, 3773838, 5561577, 8151209, 11920717, 17364461, 25269939, 36635775
COMMENTS
A composition of n is a finite sequence of positive integers summing to n.
The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (3,1,2) are (-2,1).
EXAMPLE
The a(1) = 1 through a(6) = 17 compositions:
(1) (2) (3) (4) (5) (6)
(11) (12) (13) (14) (15)
(21) (22) (23) (24)
(31) (32) (33)
(112) (41) (42)
(121) (113) (51)
(211) (122) (114)
(131) (132)
(212) (141)
(221) (213)
(311) (231)
(1121) (312)
(1211) (411)
(1131)
(1221)
(1311)
(2112)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@Differences[#]&]], {n, 0, 15}]
CROSSREFS
Cf. A000079, A000740, A008965, A059966, A070211, A175342, A242882, A325325, A325352, A325546, A325547, A325548, A325551, A325554.
Number of arithmetic progressions (where the difference between adjacent terms is either positive, 0, or negative) of positive integers that sum to n.
+10
43
1, 2, 4, 5, 6, 10, 8, 10, 15, 14, 12, 22, 14, 18, 28, 21, 18, 34, 20, 28, 38, 28, 24, 46, 31, 32, 48, 38, 30, 62, 32, 40, 58, 42, 46, 73, 38, 46, 68, 58, 42, 84, 44, 56, 90, 56, 48, 94, 55, 70, 90, 66, 54, 106, 70, 74, 100, 70, 60, 130, 62, 74, 118, 81, 82, 130, 68, 84, 120
FORMULA
G.f.: x/(1-x) + Sum_{k>=2} x^k * (1 + x^(k(k-1)/2)) / (1 - x^(k(k-1)/2)) / (1 -x^k).
EXAMPLE
The a(1) = 1 through a(8) = 10 compositions with equal differences:
(1) (2) (3) (4) (5) (6) (7) (8)
(11) (12) (13) (14) (15) (16) (17)
(21) (22) (23) (24) (25) (26)
(111) (31) (32) (33) (34) (35)
(1111) (41) (42) (43) (44)
(11111) (51) (52) (53)
(123) (61) (62)
(222) (1111111) (71)
(321) (2222)
(111111) (11111111)
(End)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], SameQ@@Differences[#]&]], {n, 0, 15}] (* returns a(0) = 1, Gus Wiseman, May 15 2019*)
CROSSREFS
Cf. A000005, A000079, A049980, A049981, A049982, A049983, A049986, A049987, A049988, A049989, A049990, A070211, A127938, A175327, A325328, A325407, A325545, A325546, A325547, A325548, A325557, A325558.
Number of log-concave compositions (ordered partitions) of n.
+10
34
1, 1, 2, 4, 6, 9, 14, 20, 26, 36, 47, 60, 80, 102, 127, 159, 194, 236, 291, 355, 425, 514, 611, 718, 856, 1009, 1182, 1381, 1605, 1861, 2156, 2496, 2873, 3299, 3778, 4301, 4902, 5574, 6325, 7176, 8116, 9152, 10317, 11610, 13028, 14611, 16354, 18259, 20365
COMMENTS
These are compositions with weakly decreasing first quotients, where the first quotients of a sequence are defined as if the sequence were an increasing divisor chain, so for example the first quotients of (6,3,1) are (1/2,1/3). - Gus Wiseman, Mar 16 2021
EXAMPLE
Out of the 8 compositions of 4, only 2+1+1 and 1+1+2 are not log-concave, so a(4)=6.
The a(1) = 1 through a(6) = 14 compositions:
(1) (2) (3) (4) (5) (6)
(11) (12) (13) (14) (15)
(21) (22) (23) (24)
(111) (31) (32) (33)
(121) (41) (42)
(1111) (122) (51)
(131) (123)
(221) (132)
(11111) (141)
(222)
(231)
(321)
(1221)
(111111)
(End)
MATHEMATICA
(* This program is not suitable for computing a large number of terms *)
compos[n_] := Permutations /@ IntegerPartitions[n] // Flatten[#, 1]&;
logConcaveQ[p_] := And @@ Table[p[[i]]^2 >= p[[i-1]]*p[[i+1]], {i, 2, Length[p]-1}]; a[n_] := Count[compos[n], p_?logConcaveQ]; Table[an = a[n]; Print["a(", n, ") = ", an]; a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 29 2016 *) Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], GreaterEqual@@Divide@@@Reverse/@Partition[#, 2, 1]&]], {n, 0, 15}] (* Gus Wiseman, Mar 15 2021 *)
PROG
(Sage) def A069916(n) : return sum(all(p[i]^2 >= p[i-1] * p[i+1] for i in range(1, len(p)-1)) for p in Compositions(n)) # Eric M. Schmidt, Sep 29 2013
CROSSREFS
The version for differences instead of quotients is A070211. A000005 counts constant compositions.
A000009 counts strictly increasing (or strictly decreasing) compositions.
A000041 counts weakly increasing (or weakly decreasing) compositions.
A002843 counts compositions with adjacent parts x <= 2y.
A003238 counts chains of divisors summing to n-1, with strict case A122651.
A003242 counts anti-run compositions.
A074206 counts ordered factorizations.
A167865 counts strict chains of divisors summing to n.
Number of compositions with alternating parts weakly decreasing (or weakly increasing).
+10
23
1, 1, 2, 4, 7, 12, 20, 32, 51, 79, 121, 182, 272, 399, 582, 839, 1200, 1700, 2394, 3342, 4640, 6397, 8771, 11955, 16217, 21878, 29386, 39285, 52301, 69334, 91570, 120465, 157929, 206313, 268644, 348674, 451185, 582074, 748830, 960676, 1229208, 1568716, 1997064
COMMENTS
These are finite sequences q of positive integers summing to n such that q(i) >= q(i+2) for all possible i.
The strict case (alternating parts are strictly decreasing) is A000041. Is there a bijective proof? Yes. Construct a Ferrers diagram by placing odd parts horizontally and even parts vertically in a fishbone pattern. The resulting Ferrers diagram will be for an ordinary partition and the process is reversible. It does not appear that this method can be applied to give a formula for this sequence. - Andrew Howroyd, Mar 25 2021
FORMULA
G.f.: Sum_{k>=0} ([y^k] P(x,y))*([y^k] (1 + y)*P(x,y)), where P(x,y) = Product_{k>=1} 1/(1 - y*x^k). - Andrew Howroyd, Jan 16 2025
EXAMPLE
The a(1) = 1 through a(6) = 20 compositions:
(1) (2) (3) (4) (5) (6)
(11) (12) (13) (14) (15)
(21) (22) (23) (24)
(111) (31) (32) (33)
(121) (41) (42)
(211) (131) (51)
(1111) (212) (141)
(221) (222)
(311) (231)
(1211) (312)
(2111) (321)
(11111) (411)
(1212)
(1311)
(2121)
(2211)
(3111)
(12111)
(21111)
(111111)
MAPLE
b:= proc(n, i, j) option remember; `if`(n=0, 1, `if`(i<1, 0,
b(n, i-1, j)+b(n-i, min(n-i, j), min(n-i, i))))
end:
a:= n-> b(n$3):
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], GreaterEqual@@Plus@@@Reverse/@Partition[#, 2, 1]&]], {n, 0, 15}]
PROG
(PARI) seq(n)={my(p=1/prod(k=1, n, 1-y*x^k + O(x*x^n))); Vec(1+sum(k=1, n, polcoef(p, k, y)*(polcoef(p, k-1, y) + polcoef(p, k, y))))} \\ Andrew Howroyd, Mar 24 2021
CROSSREFS
The version with alternating parts unequal is A224958 (unordered: A000726). The version with alternating parts equal is A342527. A000041 counts weakly increasing (or weakly decreasing) compositions.
A002843 counts compositions with all adjacent parts x <= 2y.
A003242 counts anti-run compositions.
Cf. A001522, A008965, A048004, A059966, A062968, A064410, A064428, A065608, A167606, A325557, A342519.
Number of compositions of n with equal differences up to sign.
+10
20
1, 1, 2, 4, 6, 8, 13, 12, 20, 24, 25, 29, 49, 40, 50, 64, 86, 80, 105, 102, 164, 175, 186, 208, 325, 316, 382, 476, 624, 660, 814, 961, 1331, 1500, 1739, 2140, 2877, 3274, 3939, 4901, 6345, 7448, 9054, 11157, 14315, 17181, 20769, 25843, 32947, 39639, 48257, 60075
COMMENTS
A composition of n is a finite sequence of positive integers summing to n.
The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (3,1,2) are (-2,1).
EXAMPLE
The a(1) = 1 through a(8) = 20 compositions:
(1) (2) (3) (4) (5) (6) (7) (8)
(11) (12) (13) (14) (15) (16) (17)
(21) (22) (23) (24) (25) (26)
(111) (31) (32) (33) (34) (35)
(121) (41) (42) (43) (44)
(1111) (131) (51) (52) (53)
(212) (123) (61) (62)
(11111) (141) (151) (71)
(222) (232) (161)
(321) (313) (242)
(1212) (12121) (323)
(2121) (1111111) (1232)
(111111) (1313)
(2123)
(2222)
(2321)
(3131)
(3212)
(21212)
(11111111)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], SameQ@@Abs[Differences[#]]&]], {n, 0, 15}]
PROG
(PARI)
step(R, n, s)={matrix(n, n, i, j, if(i>j, if(j>s, R[i-j, j-s]) + if(j+s<=n, R[i-j, j+s])) )}
w(n, s)={my(R=matid(n), t=0); while(R, R=step(R, n, s); t+=vecsum(R[n, ])); t}
a(n) = {numdiv(max(1, n)) + sum(s=1, n-1, w(n, s))} \\ Andrew Howroyd, Aug 22 2019
CROSSREFS
Cf. A000079, A047966, A049988, A070211, A098504, A173258, A175342, A325545, A325546, A325547, A325548, A325552, A325558.
Number of unimodal compositions of n+2 where the maximal part appears exactly twice.
+10
15
1, 0, 1, 2, 4, 6, 11, 16, 27, 40, 63, 92, 141, 202, 299, 426, 614, 862, 1222, 1694, 2362, 3242, 4456, 6054, 8229, 11072, 14891, 19872, 26477, 35050, 46320, 60866, 79827, 104194, 135703, 176008, 227791, 293702, 377874, 484554, 620011, 790952, 1006924
COMMENTS
Old name was: Expansion of a q-series.
a(n) is also the number of 2-colored partitions of n with the same number of parts in each color. - Shishuo Fu, May 30 2017 Also the number of even-length compositions of n with alternating parts weakly decreasing. Allowing odd lengths also gives A342528. The version with alternating parts strictly decreasing appears to be A064428. The a(2) = 1 through a(7) = 16 compositions are: (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)
(2,1) (2,2) (2,3) (2,4) (2,5)
(3,1) (3,2) (3,3) (3,4)
(1,1,1,1) (4,1) (4,2) (4,3)
(1,2,1,1) (5,1) (5,2)
(2,1,1,1) (1,2,1,2) (6,1)
(1,3,1,1) (1,3,1,2)
(2,1,2,1) (1,4,1,1)
(2,2,1,1) (2,2,1,2)
(3,1,1,1) (2,2,2,1)
(1,1,1,1,1,1) (2,3,1,1)
(3,1,2,1)
(3,2,1,1)
(4,1,1,1)
(1,2,1,1,1,1)
(2,1,1,1,1,1)
(End)
FORMULA
G.f.: 1 + Sum_{k>0} (x^k / ((1-x)(1-x^2)...(1-x^k)))^2 = (1 + Sum_{k>0} 2 (-1)^k x^((k^2+k)/2) ) / (Product_{k>0} (1 - x^k))^2.
G.f.: 1 + x*(1 - G(0))/(1-x) where G(k) = 1 - x/(1-x^(k+1))^2/(1-x/(x-1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 23 2013 a(n) ~ Pi * exp(2*Pi*sqrt(n/3)) / (16 * 3^(5/4) * n^(7/4)). - Vaclav Kotesovec, Oct 24 2018
EXAMPLE
There are a(7)=16 such compositions of 7+2=9 where the maximal part appears twice:
01: [ 1 1 1 1 1 2 2 ]
02: [ 1 1 1 1 2 2 1 ]
03: [ 1 1 1 2 2 1 1 ]
04: [ 1 1 1 3 3 ]
05: [ 1 1 2 2 1 1 1 ]
06: [ 1 1 3 3 1 ]
07: [ 1 2 2 1 1 1 1 ]
08: [ 1 2 3 3 ]
09: [ 1 3 3 1 1 ]
10: [ 1 3 3 2 ]
11: [ 1 4 4 ]
12: [ 2 2 1 1 1 1 1 ]
13: [ 2 3 3 1 ]
14: [ 3 3 1 1 1 ]
15: [ 3 3 2 1 ]
16: [ 4 4 1 ]
(End)
MATHEMATICA
max = 50; s = (1+Sum[2*(-1)^k*q^(k(k+1)/2), {k, 1, max}])/QPochhammer[q]^2+ O[q]^max; CoefficientList[s, q] (* Jean-François Alcover, Nov 30 2015, from 1st g.f. *) wdw[q_]:=And@@Table[q[[i]]>=q[[i+2]], {i, Length[q]-2}];
Table[Length[Select[Join@@Permutations/@Select[IntegerPartitions[n], EvenQ[Length[#]]&], wdw]], {n, 0, 15}] (* Gus Wiseman, Mar 25 2021 *)
PROG
(PARI) {a(n) = if( n<0, 0, polcoeff( sum(k=0, n\2, x^(2*k) / prod(i=1, k, 1 - x^i, 1 + x * O(x^n))^2), n))};
(PARI) {a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( sum(k=1, sqrtint(8*n + 1)\2, 2*(-1)^k * x^((k^2+k)/2), 1 + A) / eta(x + A)^2, n))};
CROSSREFS
Cf. A226541 (max part appears three times), A188674 (max part m appears m times), A001523 (max part appears any number of times). A000041 counts weakly increasing (or weakly decreasing) compositions.
A002843 counts compositions with all adjacent parts x <= 2y.
A003242 counts anti-run compositions.
A034008 counts even-length compositions.
A065608 counts even-length compositions with alternating parts equal.
A342528 counts compositions with alternating parts weakly decreasing.
A342532 counts even-length compositions with alternating parts unequal.
Cf. A000726, A001522, A008965, A062968, A064410, A064428, A069916, A070211, A175342, A224958, A342495, A342527.
Number of compositions of n with weakly increasing differences.
+10
13
1, 1, 2, 4, 7, 11, 19, 28, 41, 62, 87, 120, 170, 228, 303, 408, 534, 689, 899, 1145, 1449, 1842, 2306, 2863, 3571, 4398, 5386, 6610, 8039, 9716, 11775, 14157, 16938, 20293, 24166, 28643, 33995, 40134, 47199, 55540, 65088, 75994, 88776, 103328, 119886, 139126
COMMENTS
Also compositions of n whose plot is concave-up.
A composition of n is a finite sequence of positive integers summing to n.
The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (3,1,2) are (-2,1).
EXAMPLE
The a(1) = 1 through a(6) = 19 compositions:
(1) (2) (3) (4) (5) (6)
(11) (12) (13) (14) (15)
(21) (22) (23) (24)
(111) (31) (32) (33)
(112) (41) (42)
(211) (113) (51)
(1111) (212) (114)
(311) (123)
(1112) (213)
(2111) (222)
(11111) (312)
(321)
(411)
(1113)
(2112)
(3111)
(11112)
(21111)
(111111)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], LessEqual@@Differences[#]&]], {n, 0, 15}]
PROG
(PARI) \\ Row sums of R(n) give A007294 (=breakdown by width). R(n)={my(L=List(), v=vectorv(n, i, 1), w=1, t=1); while(v, listput(L, v); w++; t+=w; v=vectorv(n, i, sum(k=1, (i-w-1)\t + 1, v[i-w-(k-1)*t]))); Mat(L)}
seq(n)={my(M=R(n)); Vec(1 + sum(i=1, n, my(p=sum(w=1, min(#M, n\i), x^(w*i)*sum(j=1, n-i*w, x^j*M[j, w]))); x^i/(1 - x^i)*(1 + p + O(x*x^(n-i)))^2))} \\ Andrew Howroyd, Aug 28 2019
CROSSREFS
Cf. A000079, A000740, A007294, A008965, A070211 (concave-down compositions), A173258, A175342, A240026, A325360, A325545, A325547, A325548, A325552, A325557.
Number of strict integer partitions of n with no pair of consecutive parts relatively prime.
+10
13
1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 3, 1, 5, 1, 5, 4, 6, 3, 10, 3, 11, 7, 12, 3, 19, 5, 18, 12, 23, 9, 36, 11, 33, 21, 40, 20, 58, 19, 58, 35, 70, 31, 98, 36, 101, 65, 112, 56, 155, 64, 164, 97, 188, 88, 250, 112, 256, 157, 293, 145, 392, 163, 399, 241, 461, 242
EXAMPLE
The a(2) = 1 through a(20) = 11 partitions (A..K = 10..20):
2 3 4 5 6 7 8 9 A B C D E F G H I J K
42 62 63 64 84 86 96 A6 863 A8 964 C8
82 93 A4 A5 C4 962 C6 A63 E6
A2 C2 C3 E2 E4 F5
642 842 862 F3 G4
A42 G2 I2
864 A64
963 A82
A62 C62
C42 E42
8642
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&!MatchQ[#, {___, x_, y_, ___}/; GCD[x, y]==1]&]], {n, 0, 30}]
CROSSREFS
Partitions with all consecutive parts relatively prime are A328172, with strict case A328188. Strict partitions with relatively prime parts are A078374. Partitions with no consecutive divisibilities are A328171.
Number of compositions of n with strictly increasing differences.
+10
12
1, 1, 2, 3, 6, 8, 11, 18, 24, 30, 45, 57, 71, 96, 120, 148, 192, 235, 286, 354, 431, 518, 628, 752, 893, 1063, 1262, 1482, 1744, 2046, 2386, 2775, 3231, 3733, 4305, 4977, 5715, 6536, 7507, 8559, 9735, 11112, 12608, 14252, 16177, 18265, 20553, 23204, 26090, 29223
COMMENTS
A composition of n is a finite sequence of positive integers summing to n.
The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (3,1,2) are (-2,1).
EXAMPLE
The a(1) = 1 through a(6) = 11 compositions:
(1) (2) (3) (4) (5) (6)
(11) (12) (13) (14) (15)
(21) (22) (23) (24)
(31) (32) (33)
(112) (41) (42)
(211) (113) (51)
(212) (114)
(311) (213)
(312)
(411)
(2112)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Less@@Differences[#]&]], {n, 0, 15}]
PROG
(PARI) \\ Row sums of R(n) give A179269 (breakdown by width) R(n)={my(L=List(), v=vectorv(n, i, 1), w=1, t=1); while(v, listput(L, v); w++; t+=w; v=vectorv(n, i, sum(k=1, (i-1)\t, v[i-k*t]))); Mat(L)}
seq(n)={my(M=R(n)); Vec(1 + sum(i=1, n, my(p=sum(w=1, min(#M, n\i), x^(w*i)*sum(j=1, n-i*w, x^j*M[j, w]))); x^i*(1 + x^i)*(1 + p + O(x*x^(n-i)))^2))} \\ Andrew Howroyd, Aug 27 2019
CROSSREFS
Cf. A000079, A000740, A008965, A034297, A070211, A175342, A179269, A179254, A240027, A325545, A325546, A325548, A325552, A325557.
Number of compositions of n with strictly decreasing differences.
+10
12
1, 1, 2, 3, 5, 8, 10, 13, 19, 23, 29, 38, 46, 55, 69, 80, 96, 115, 132, 154, 183, 207, 238, 276, 314, 356, 405, 455, 513, 579, 647, 724, 809, 897, 998, 1107, 1225, 1350, 1486, 1639, 1805, 1973, 2166, 2374, 2586, 2824, 3084, 3346, 3646, 3964, 4286, 4655, 5047
COMMENTS
A composition of n is a finite sequence of positive integers summing to n.
The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (3,1,2) are (-2,1).
EXAMPLE
The a(1) = 1 through a(8) = 19 compositions:
(1) (2) (3) (4) (5) (6) (7) (8)
(11) (12) (13) (14) (15) (16) (17)
(21) (22) (23) (24) (25) (26)
(31) (32) (33) (34) (35)
(121) (41) (42) (43) (44)
(122) (51) (52) (53)
(131) (132) (61) (62)
(221) (141) (133) (71)
(231) (142) (134)
(1221) (151) (143)
(232) (152)
(241) (161)
(331) (233)
(242)
(251)
(332)
(341)
(431)
(1331)
MAPLE
b:= proc(n, l, d) option remember; `if`(n=0, 1, add(`if`(l=0 or
j-l<d, b(n-j, j, `if`(l=0, infinity, j-l)), 0), j=1..n))
end:
a:= n-> b(n, 0$2):
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Greater@@Differences[#]&]], {n, 0, 15}]
CROSSREFS
Cf. A011782, A000740, A008965, A070211, A175342, A179254, A320470, A325457, A325545, A325546, A325547, A325552, A325557.
Search completed in 0.013 seconds
|