A032020
Number of compositions (ordered partitions) of n into distinct parts.
Original entry on oeis.org
1, 1, 1, 3, 3, 5, 11, 13, 19, 27, 57, 65, 101, 133, 193, 351, 435, 617, 851, 1177, 1555, 2751, 3297, 4757, 6293, 8761, 11305, 15603, 24315, 30461, 41867, 55741, 74875, 98043, 130809, 168425, 257405, 315973, 431065, 558327, 751491, 958265, 1277867, 1621273
Offset: 0
a(6) = 11 because 6 = 5+1 = 4+2 = 3+2+1 = 3+1+2 = 2+4 = 2+3+1 = 2+1+3 = 1+5 = 1+3+2 = 1+2+3.
From _Gus Wiseman_, Jun 25 2020: (Start)
The a(0) = 1 through a(7) = 13 strict compositions:
() (1) (2) (3) (4) (5) (6) (7)
(1,2) (1,3) (1,4) (1,5) (1,6)
(2,1) (3,1) (2,3) (2,4) (2,5)
(3,2) (4,2) (3,4)
(4,1) (5,1) (4,3)
(1,2,3) (5,2)
(1,3,2) (6,1)
(2,1,3) (1,2,4)
(2,3,1) (1,4,2)
(3,1,2) (2,1,4)
(3,2,1) (2,4,1)
(4,1,2)
(4,2,1)
(End)
- Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.
- Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
- C. G. Bower, Transforms (2)
- Martin Klazar, What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I, arXiv:1808.08449 [math.CO], 2018.
- B. Richmond and A. Knopfmacher, Compositions with distinct parts, Aequationes Mathematicae 49 (1995), pp. 86-97.
- B. Richmond and A. Knopfmacher, Compositions with distinct parts, Aequationes Mathematicae 49 (1995), pp. 86-97. (free access)
- Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Dominated by
A003242 (anti-run compositions).
These compositions are ranked by
A233564.
(1,1)-avoiding patterns are counted by
A000142.
Numbers with strict prime signature are
A130091.
(1,1,1)-avoiding compositions are counted by
A232432.
(1,1)-matching compositions are counted by
A261982.
Inseparable partitions are counted by
A325535.
Patterns matched by compositions are counted by
A335456.
Strict permutations of prime indices are counted by
A335489.
-
b:= proc(n, i) b(n, i):= `if`(n=0, [1], `if`(i<1, [], zip((x, y)
-> x+y, b(n, i-1), `if`(i>n, [], [0, b(n-i, i-1)[]]), 0))) end:
a:= proc(n) local l; l:=b(n, n): add((i-1)! *l[i], i=1..nops(l)) end:
seq(a(n), n=0..50); # Alois P. Heinz, Dec 12 2012
# second Maple program:
T:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
`if`(k=0, `if`(n=0, 1, 0), T(n-k, k) +k*T(n-k, k-1)))
end:
a:= n-> add(T(n, k), k=0..floor((sqrt(8*n+1)-1)/2)):
seq(a(n), n=0..60); # Alois P. Heinz, Sep 04 2015
-
f[list_]:=Length[list]!; Table[Total[Map[f, Select[IntegerPartitions[n], Sort[#] == Union[#] &]]], {n, 0,30}]
T[n_, k_] := T[n, k] = If[k<0 || n<0, 0, If[k==0, If[n==0, 1, 0], T[n-k, k] + k*T[n-k, k-1]]]; a[n_] := Sum[T[n, k], {k, 0, Floor[(Sqrt[8*n + 1] - 1) / 2]}]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Sep 22 2015, after Alois P. Heinz *)
-
N=66; q='q+O('q^N);
gf=sum(n=0,N, n!*q^(n*(n+1)/2) / prod(k=1,n, 1-q^k ) );
Vec(gf)
/* Joerg Arndt, Oct 20 2012 */
-
Q(N) = { \\ A008289
my(q = vector(N)); q[1] = [1, 0, 0, 0];
for (n = 2, N,
my(m = (sqrtint(8*n+1) - 1)\2);
q[n] = vector((1 + (m>>2)) << 2); q[n][1] = 1;
for (k = 2, m, q[n][k] = q[n-k][k] + q[n-k][k-1]));
return(q);
};
seq(N) = concat(1, apply(q -> sum(k = 1, #q, q[k] * k!), Q(N)));
seq(43) \\ Gheorghe Coserea, Sep 09 2018
A261836
Number T(n,k) of compositions of n into distinct parts where each part i is marked with a word of length i over a k-ary alphabet whose letters appear in alphabetical order and all k letters occur at least once in the composition; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
Original entry on oeis.org
1, 0, 1, 0, 1, 1, 0, 3, 10, 7, 0, 3, 15, 21, 9, 0, 5, 40, 96, 92, 31, 0, 11, 183, 832, 1562, 1305, 403, 0, 13, 266, 1539, 3908, 4955, 3090, 757, 0, 19, 549, 4281, 14791, 26765, 26523, 13671, 2873, 0, 27, 1056, 10902, 50208, 124450, 178456, 148638, 66904, 12607
Offset: 0
T(3,2) = 10: (matrices and corresponding marked compositions are given)
[2] [1] [2 0] [0 2] [1 0] [0 1] [1 1] [1 1] [1 0] [0 1]
[1] [2] [0 1] [1 0] [0 2] [2 0] [1 0] [0 1] [1 1] [1 1]
3aab, 3abb, 2aa1b, 1b2aa, 1a2bb, 2bb1a, 2ab1a, 1a2ab, 2ab1b, 1b2ab.
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 3, 10, 7;
0, 3, 15, 21, 9;
0, 5, 40, 96, 92, 31;
0, 11, 183, 832, 1562, 1305, 403;
0, 13, 266, 1539, 3908, 4955, 3090, 757;
0, 19, 549, 4281, 14791, 26765, 26523, 13671, 2873;
Columns k=0-10 give:
A000007,
A032020 (for n>0),
A261853,
A261854,
A261855,
A261856,
A261857,
A261858,
A261859,
A261860,
A261861.
-
b:= proc(n, i, p, k) option remember;
`if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
end:
T:= (n, k)-> add(b(n$2, 0, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..12);
-
b[n_, i_, p_, k_] := b[n, i, p, k] = If[i*(i+1)/2n, 0, b[n-i, i-1, p+1, k]*Binomial[i+k-1, k-1]]]]; T[n_, k_] := Sum[b[n, n, 0, k-i]*(-1)^i*Binomial[k, i], {i, 0, k}]; Table[ Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 21 2016, after Alois P. Heinz *)
A261837
Number of compositions of n into distinct parts where each part i is marked with a word of length i over an n-ary alphabet whose letters appear in alphabetical order.
Original entry on oeis.org
1, 1, 3, 46, 195, 1876, 51114, 322764, 3644355, 43916950, 2427338628, 18277511616, 272107762602, 3507931293608, 62485721142820, 5810222040368296, 53025343448015811, 913540133071336044, 13871534219465464002, 253750203721349071650, 5307815745011707670820
Offset: 0
-
b:= proc(n, i, p, k) option remember;
`if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
end:
a:= n-> b(n$2, 0, n):
seq(a(n), n=0..30);
-
b[n_, i_, p_, k_] := b[n, i, p, k] =
If[i (i + 1)/2 < n, 0, If[n == 0, p!, b[n, i - 1, p, k] +
If[i > n, 0, b[n - i, i - 1, p + 1, k]*Binomial[i + k - 1, k - 1]]]];
a[n_] := b[n, n, 0, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jul 12 2021, after Alois P. Heinz *)
A261840
Number of compositions of n into distinct parts where each part i is marked with a word of length i over a binary alphabet whose letters appear in alphabetical order.
Original entry on oeis.org
1, 2, 3, 16, 21, 50, 205, 292, 587, 1110, 4535, 5980, 12447, 20910, 40195, 142520, 196291, 372042, 635081, 1128872, 1873245, 6537466, 8553639, 16333532, 26470861, 46629886, 73222631, 127947300, 385293581, 518212198, 939401193, 1516760160, 2564361235
Offset: 0
-
b:= proc(n, i, p) option remember;
`if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1)*(i+1))))
end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..40);
A261841
Number of compositions of n into distinct parts where each part i is marked with a word of length i over a ternary alphabet whose letters appear in alphabetical order.
Original entry on oeis.org
1, 3, 6, 46, 75, 231, 1414, 2376, 5985, 14151, 89454, 135330, 343677, 697017, 1657212, 9439826, 14381055, 33119667, 66361286, 141451860, 283907499, 1642516411, 2346737106, 5367877296, 10093521943, 20923900623, 38428831710, 80538197724, 416229711735
Offset: 0
-
b:= proc(n, i, p) option remember;
`if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1)*binomial(i+2, 2))))
end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..40);
A261842
Number of compositions of n into distinct parts where each part i is marked with a word of length i over a quaternary alphabet whose letters appear in alphabetical order.
Original entry on oeis.org
1, 4, 10, 100, 195, 736, 6032, 11712, 35285, 100260, 871386, 1492820, 4438573, 10525720, 29825140, 241360728, 405645867, 1086289116, 2489722574, 6158961820, 14573822743, 123303661384, 192326074572, 504783599080, 1073240557055, 2539006453740, 5337585654950
Offset: 0
-
b:= proc(n, i, p) option remember;
`if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1)*binomial(i+3, 3))))
end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..40);
A261843
Number of compositions of n into distinct parts where each part i is marked with a word of length i over a quinary alphabet whose letters appear in alphabetical order.
Original entry on oeis.org
1, 5, 15, 185, 420, 1876, 19320, 42610, 149115, 495205, 5516001, 10570145, 35897010, 97383790, 320607680, 3412039628, 6292069835, 19106603405, 49239854095, 138462457915, 378598491878, 4312038483490, 7316190877970, 21527078513430, 50933081112485
Offset: 0
-
b:= proc(n, i, p) option remember;
`if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1)*binomial(i+4, 4))))
end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..30);
A261844
Number of compositions of n into distinct parts where each part i is marked with a word of length i over a senary alphabet whose letters appear in alphabetical order.
Original entry on oeis.org
1, 6, 21, 308, 798, 4116, 51114, 126288, 502947, 1912318, 26074881, 55301652, 210871038, 643901916, 2416831656, 32128430000, 64611765009, 218800524222, 625968110257, 1971079800312, 6127902153366, 88805517515284, 163129580373222, 530136843388056
Offset: 0
-
b:= proc(n, i, p) option remember;
`if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1)*binomial(i+5, 5))))
end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..30);
A261845
Number of compositions of n into distinct parts where each part i is marked with a word of length i over a septenary alphabet whose letters appear in alphabetical order.
Original entry on oeis.org
1, 7, 28, 476, 1386, 8106, 117936, 322764, 1440579, 6172495, 99773646, 232110704, 981073576, 3329628176, 14040114012, 224848217580, 490210909629, 1828885568055, 5750093241172, 20040621544916, 69910543160794, 1238596672832718, 2451410591056280, 8705347941656016
Offset: 0
-
b:= proc(n, i, p) option remember;
`if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1)*binomial(i+6, 6))))
end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..25);
A261846
Number of compositions of n into distinct parts where each part i is marked with a word of length i over an octonary alphabet whose letters appear in alphabetical order.
Original entry on oeis.org
1, 8, 36, 696, 2250, 14712, 245508, 737352, 3644355, 17376832, 325225824, 823612736, 3820113552, 14264475648, 66782014272, 1254553664640, 2949123559125, 12008271483720, 41150373332932, 157262062899640, 608878151760410, 12804954311547288, 27181470392583156
Offset: 0
-
b:= proc(n, i, p) option remember;
`if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1)*binomial(i+7, 7))))
end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..25);
Showing 1-10 of 12 results.
Comments