A278984 -id:A278984 - cp's OEIS frontend

A383253 Number of compositions of n with parts in standard order.

1, 1, 1, 2, 3, 5, 9, 16, 29, 53, 98, 182, 340, 638, 1202, 2273, 4312, 8204, 15650, 29925, 57344, 110101, 211771, 407987, 787174, 1520851, 2942030, 5697842, 11046881, 21438881, 41645541, 80967881, 157547508, 306791828, 597847686, 1165828440, 2274890125

Offset: 0

John Tyler Rascoe, May 06 2025

A composition with parts in standard order satisfies the condition that for any part p > 1, the part p - 1 has already appeared. All compositions of this kind have first part 1.

			a(6) = 9 counts: (1,1,1,1,1,1), (1,1,1,1,2), (1,1,1,2,1), (1,1,2,1,1), (1,2,1,1,1), (1,1,2,2), (1,2,1,2), (1,2,2,1), (1,2,3).

Alois P. Heinz, Table of n, a(n) for n = 0..3333

Cf. A000110, A011782, A047998, A107429, A126347, A278984, (row sums of A383713).

b:= proc(n, i) option remember; `if`(n=0, 1, add(
      b(n-j, max(i, j)), j=1..min(n, i+1)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..36);  # Alois P. Heinz, May 08 2025

A_x(N) = {my(x='x+O('x^(N+1))); Vec(1 + sum(i=1,(N/2)+1, x^(i*(i+1)/2)/prod(j=1,i, 1 - (x-x^(j+1))/(1-x))))}
A_x(40)

G.f.: 1 + Sum_{i>0} x^(i*(i+1)/2) / Product_{j=1..i} 1 - (x - x^(j+1))/(1 - x).

A137855 Triangle read by rows: T(n,k) = Sum_{j=1..n-k+1} Stirling2(k, j).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 5, 8, 1, 1, 2, 5, 14, 16, 1, 1, 2, 5, 15, 41, 32, 1, 1, 2, 5, 15, 51, 122, 64, 1, 1, 2, 5, 15, 52, 187, 365, 128, 1, 1, 2, 5, 15, 52, 202, 715, 1094, 256, 1, 1, 2, 5, 15, 52, 203, 855, 2795, 3281, 512, 1

Offset: 1

Gary W. Adamson, Feb 16 2008

Rows of the array tend to A000110 starting (1, 2, 5, 15, 52, ...).

			First few rows of the array:
  1, 1, 1,  1,  1, ...
  1, 2, 4,  8, 16, ...
  1, 2, 5, 14, 41, ...
  1, 2, 5, 14, 51, ...
  1, 2, 5, 14, 52, ...
  ...
First few rows of the triangle:
  1;
  1, 1;
  1, 2, 1;
  1, 2, 4,  1;
  1, 2, 5,  8,  1;
  1, 2, 5, 14, 16,   1;
  1, 2, 5, 15, 41,  32,   1;
  1, 2, 5, 15, 51, 122,  64,    1;
  1, 2, 5, 15, 52, 187, 365,  128,   1;
  1, 2, 5, 15, 52, 202, 715, 1094, 256, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Row sums are A137856.

Cf. A008277, A000110, A203647, A278984.

T(n,k)={sum(j=1, n-k+1, stirling(k,j,2))} \\ Andrew Howroyd, Aug 09 2018

Take antidiagonals of an array formed by A000012 * A008277(transform), where A000012 = (1; 1,1; 1,1,1; ...) and A008277 = the Stirling2 triangle.

Name changed by Andrew Howroyd, Aug 09 2018

A273977 Words over an alphabet of size 9 that are in standard order with at least one letter repeated.

Original entry on oeis.org

11, 111, 112, 121, 122, 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1221, 1222, 1223, 1231, 1232, 1233, 11111, 11112, 11121, 11122, 11123, 11211, 11212, 11213, 11221, 11222, 11223, 11231, 11232, 11233, 11234, 12111, 12112, 12113, 12121, 12122, 12123, 12131, 12132, 12133, 12134, 12211, 12212

Offset: 1

Daniel Devatman Hromada, Nov 10 2016

We study words made of letters from an alphabet of size b, where b >= 1. (Here b=9.) We assume the letters are labeled {1,2,3,...,b}. There are b^n possible words of length n.
We say that a word is in "standard order" if it has the property that whenever a letter i appears, the letter i-1 has already appeared in the word. This implies that all words begin with the letter 1.
These are the words described in row b=9 of the array in A278986.
This sequence can be potentially expanded by a much more efficient algorithm than the brute-force one presented in the program section.

Daniel Devatman Hromada, Integer-based nomenclature for the ecosystem of repetitive expressions in complete works of William Shakespeare, submitted to special issue of Argument and Computation on Rhetorical Figures in Computational Argument Studies, 2016.

Daniel Devatman Hromada, List of n, a(n) for n = 1..142407 (All words with at most 10 digits.)
Daniel Devatman Hromada, Integer-based nomenclature for the ecosystem of repetitive expressions in complete works of William Shakespeare, August 2018.
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"

Cf. A278987.

Select[Range[2*10^4], And[Max[DigitCount@ #] >= 2, Range@ Length@ Union@ # == DeleteDuplicates@ # &@ IntegerDigits@ #] &] (* Michael De Vlieger, Nov 10 2016 *)

Edited by N. J. A. Sloane, Dec 06 2016

Duplicated terms removed from b-file by Andrew Howroyd, Feb 27 2018

A278985 List of words of length n over an alphabet of size 3 that are in standard order.

Original entry on oeis.org

1, 11, 12, 111, 112, 121, 122, 123, 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1221, 1222, 1223, 1231, 1232, 1233, 11111, 11112, 11121, 11122, 11123, 11211, 11212, 11213, 11221, 11222, 11223, 11231, 11232, 11233, 12111, 12112, 12113, 12121, 12122

Offset: 1

N. J. A. Sloane, Dec 05 2016

We study words made of letters from an alphabet of size b, where b >= 1. We assume the letters are labeled {1,2,3,...,b}. There are b^n possible words of length n.
We say that a word is in "standard order" if it has the property that whenever a letter i appears, the letter i-1 has already appeared in the word.  This implies that all words begin with the letter 1.
These are the words described in row b=3 of the array in A278984.
A007051(n-1) gives the number of n-digit terms in this sequence. - Rémy Sigrist, Dec 18 2016

Rémy Sigrist and N. J. A. Sloane, Table of n, a(n) for n = 1..14767 [Terms 1 through 185 by N. J. A. Sloane]
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"

Cf. A278984, A007051.

Similar to but different from A071159.

b:= proc(n) option remember; `if`(n=1, [[1]], map(x->
      seq([x[], i], i=1..min(3, max(x[])+1)), b(n-1)))
    end:
T:= n-> map(x-> parse(cat(x[])), b(n))[]:
seq(T(n), n=1..5);  # Alois P. Heinz, Jan 02 2022

Table[FromDigits /@ Select[Tuples[Range@ 3, n], And[Times @@ Boole@ MapIndexed[#1 <= First@ #2 &, #] > 0, Max@ Differences@ # <= 1] &], {n, 5}] // Flatten (* Michael De Vlieger, Dec 18 2016 *)

gen(n, len, mx) = if (len==0, print1 (n ", "), for (d=1, min(mx+1, 3), gen(10*n + d, len-1, max(mx, d))))
for (len=1, 5, gen(0, len, 0)) \\ Rémy Sigrist, Dec 18 2016

A273978 List of words of length n over an alphabet of size 9 that are in standard order and which have the property that every letter that appears in the word is repeated.

Original entry on oeis.org

11, 111, 1111, 1122, 1212, 1221, 11111, 11122, 11212, 11221, 11222, 12112, 12121, 12122, 12211, 12212, 12221, 111111, 111122, 111212, 111221, 111222, 112112

Offset: 1

Daniel Devatman Hromada, Nov 10 2016

We study words made of letters from an alphabet of size b, where b >= 1. (Here b=9.) We assume the letters are labeled {1,2,3,...,b}. There are b^n possible words of length n.
We say that a word is in "standard order" if it has the property that whenever a letter i appears, the letter i-1 has already appeared in the word. This implies that all words begin with the letter 1.
These are the words described in row b=9 of the array in A278987.

D. D. Hromada, Integer-based nomenclature for the ecosystem of repetitive expressions in complete works of William Shakespeare, submitted to special issue of Argument and Computation on Rhetorical Figures in Computational Argument Studies, 2016.

Daniel Devatman Hromada, Table of n, a(n) for n = 1..4360
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"

Subset of A273977.

Cf. A278987.

Edited by N. J. A. Sloane, Dec 06 2016

A380822 Triangle read by rows: T(n,k) is the number of compositions of n with k pairs of equal adjacent parts and all parts in standard order.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 3, 1, 0, 1, 2, 1, 4, 1, 0, 1, 3, 3, 3, 5, 1, 0, 1, 2, 10, 5, 4, 6, 1, 0, 1, 5, 9, 17, 8, 5, 7, 1, 0, 1, 8, 16, 22, 26, 10, 6, 8, 1, 0, 1, 10, 35, 33, 37, 37, 12, 7, 9, 1, 0, 1, 19, 44, 80, 59, 56, 48, 14, 8, 10, 1, 0, 1

Offset: 1

John Tyler Rascoe, May 08 2025

A composition with parts in standard order satisfies the condition that for any part p > 1, the part p - 1 has already appeared. All compositions of this kind have first part 1.

			Triangle begins:
     k=0   1   2   3   4  5  6  7  8  9
 n=1  [1],
 n=2  [0,  1],
 n=3  [1,  0,  1],
 n=4  [1,  1,  0,  1],
 n=5  [0,  3,  1,  0,  1],
 n=6  [2,  1,  4,  1,  0, 1],
 n=7  [3,  3,  3,  5,  1, 0, 1],
 n=8  [2, 10,  5,  4,  6, 1, 0, 1],
 n=9  [5,  9, 17,  8,  5, 7, 1, 0, 1],
 n=10 [8, 16, 22, 26, 10, 6, 8, 1, 0, 1],
...
Row n = 6 counts:
 T(6,0) = 2: (1,2,1,2), (1,2,3).
 T(6,1) = 1: (1,2,2,1).
 T(6,2) = 4: (1,1,1,2,1), (1,1,2,1,1), (1,1,2,2), (1,2,1,1,1).
 T(6,3) = 1: (1,1,1,1,2).
 T(6,4) = 0: .
 T(6,5) = 1: (1,1,1,1,1,1).

Alois P. Heinz, Rows n = 1..200, flattened

Cf. A000110, A003242, A047998, A106356, A107429, A126347, A278984, A383253 (row sums).

b:= proc(n, l, i) option remember; expand(`if`(n=0, 1, add(
      `if`(j=l, x, 1)*b(n-j, j, max(i, j)), j=1..min(n, i+1))))
    end:
T:= (n, k)-> coeff(b(n, 0$2), x, k):
seq(seq(T(n, k), k=0..n-1), n=1..12);  # Alois P. Heinz, May 08 2025

G(k,N) = {my(x='x+O('x^N)); if(k<1,1, G(k-1,N) * x^k * (1 + (1/(1 - sum(j=1,k, x^j/(1-(z-1)*x^j)))) * sum(j=1,k, z^(if(j==k,1,0)) * x^j/(1-(z-1)*x^j))))}
T_xz(max_row) = {my(N = max_row+1, x='x+O('x^N), h = sum(i=1,N/2+1, G(i,N))); vector(N-1, n, Vecrev(polcoeff(h, n)))}
T_xz(10)

G.f.: Sum_{i>0} G(i) where G(k) = G(k-1) * x*k * (1 + 1/(1 - Sum_{j=1..k} ( x^j/(1 - (z-1)*x^j) )) * Sum_{j=1..k} ( z^[j=k] * x^j/(1 - (z-1)*x^j) )) and G(0) = 1.

A383713 Triangle read by rows: T(n,k) is the number of compositions of n with k parts all in standard order.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 1, 0, 0, 0, 1, 3, 1, 0, 0, 0, 1, 3, 4, 1, 0, 0, 0, 0, 4, 6, 5, 1, 0, 0, 0, 0, 2, 10, 10, 6, 1, 0, 0, 0, 0, 1, 9, 20, 15, 7, 1, 0, 0, 0, 0, 1, 7, 25, 35, 21, 8, 1, 0, 0, 0, 0, 0, 7, 26, 55, 56, 28, 9, 1, 0, 0, 0, 0, 0, 4, 29, 71, 105, 84, 36, 10, 1

Offset: 0

John Tyler Rascoe, May 06 2025

A composition with parts in standard order satisfies the condition that for any part p > 1, the part p - 1 has already appeared. All compositions of this kind have first part 1.

			Triangle begins:
     k=0  1  2  3  4   5   6   7   8  9 10
 n=0  [1],
 n=1  [0, 1],
 n=2  [0, 0, 1],
 n=3  [0, 0, 1, 1],
 n=4  [0, 0, 0, 2, 1],
 n=5  [0, 0, 0, 1, 3,  1],
 n=6  [0, 0, 0, 1, 3,  4,  1],
 n=7  [0, 0, 0, 0, 4,  6,  5,  1],
 n=8  [0, 0, 0, 0, 2, 10, 10,  6,  1],
 n=9  [0, 0, 0, 0, 1,  9, 20, 15,  7, 1],
 n=10 [0, 0, 0, 0, 1,  7, 25, 35, 21, 8, 1],
 ...
Row n = 6 counts:
 T(6,3) = 1: (1,2,3).
 T(6,4) = 3: (1,1,2,2), (1,2,1,2), (1,2,2,1).
 T(6,5) = 4: (1,1,1,1,2), (1,1,1,2,1), (1,1,2,1,1), (1,2,1,1,1).
 T(6,6) = 1: (1,1,1,1,1,1).

Cf. A000110 (column sums), A047998, A107429, A126347 (triangle transposed with no zeros), A278984, A383253 (row sums).

T_xy(max_row) = {my(N = max_row+1, x='x+O('x^N), h = 1 + sum(i=1,1+(N/2), y^i * x^(i*(i+1)/2)/prod(j=1,i, 1 - y*(x-x^(j+1))/(1-x)))); vector(N, n, Vecrev(polcoeff(h, n-1)))}
T_xy(10)

G.f.: 1 + Sum_{i>0} y^i * x^(i*(i+1)/2) / Product_{j=1..i} 1 - y*(x - x^(j+1))/(1 - x).

A278986 Array read by antidiagonals downwards: T(b,n) = number of words of length n over an alphabet of size b that are in standard order and which have the property that at least one letter is repeated.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 4, 1, 0, 1, 8, 4, 1, 0, 1, 16, 14, 4, 1, 0, 1, 32, 41, 14, 4, 1, 0, 1, 64, 122, 51, 14, 4, 1, 0, 1, 128, 365, 187, 51, 14, 4, 1, 0, 1, 256, 1094, 715, 202, 51, 14, 4, 1, 0, 1, 512, 3281, 2795, 855, 202, 51, 14, 4, 1, 0, 1, 1024, 9842, 11051, 3845, 876, 202, 51, 14, 4, 1

Offset: 1

Joerg Arndt and N. J. A. Sloane, Dec 05 2016

We study words made of letters from an alphabet of size b, where b >= 1. We assume the letters are labeled {1,2,3,...,b}. There are b^n possible words of length n.

We say that a word is in "standard order" if it has the property that whenever a letter i appears, the letter i-1 has already appeared in the word. This implies that all words begin with the letter 1.

			The array begins:
0,.1,..1,...1,...1,...1,...1,....1..; b=1,
0,.1,..4,...8,..16,..32,..64,..128..; b=2,
0,.1,..4,..14,..41,.122,.365,.1094..; b=3,
0,.1,..4,..14,..51,.187,.715,.2795..; b=4,
0,.1,..4,..14,..51,.202,.855,.3845..; b=5,
0,.1,..4,..14,..51,.202,.876,.4111..; b=6,
...

Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"

See A278984 for a closely related array.
The words for b=3 are listed in A278985, except that the words 1, 12, and 123 must be omitted from that list.
The words for b=9 are listed in A273977.

with(combinat);
f2:=proc(L,b) local t1;i;
t1:=add(stirling2(L,i),i=1..b); if L <= b then t1:=t1-1; fi; t1; end;
Q2:=b->[seq(f2(L,b), L=1..20)];
for b from 1 to 6 do lprint(Q2(b)); od:

The number of words of length n over an alphabet of size b that are in standard order and in which at least one symbol is repeated is Sum_{j = 1..b} Stirling2(n,j), except we must subtract 1 if and only if n <= b.

So this array is obtained from the array in A278984 by subtracting 1 from the first b entries in row b, for b = 1,2,3,...

A278988 a(n) is the number of words of length n over an alphabet of size 3 that are in standard order and which have the property that every letter that appears in the word is repeated.

Original entry on oeis.org

0, 0, 1, 1, 4, 11, 41, 162, 610, 2165, 7327, 23948, 76352, 239175, 739909, 2268710, 6912430, 20966441, 63390587, 191220048, 575888044, 1732382363, 5207108161, 15642295562, 46970926394, 141005053341, 423208097431, 1270026944852, 3810919694680, 11434503913775, 34307135619197

Offset: 0

N. J. A. Sloane, Dec 06 2016

nonn

Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"

A row of the array in A278987.

Conjectures from Colin Barker, Nov 25 2017: (Start)
G.f.: x^2*(1 - 9*x + 34*x^2 - 71*x^3 + 100*x^4 - 97*x^5 + 52*x^6 - 12*x^7) / ((1 - x)^3*(1 - 2*x)^2*(1 - 3*x)).
a(n) = (2*(3+3^n) - 3*(2+2^n)*n + 6*n^2) / 12 for n>3.
a(n) = 10*a(n-1) - 40*a(n-2) + 82*a(n-3) - 91*a(n-4) + 52*a(n-5) - 12*a(n-6) for n>9.
(End)

A278989 a(n) is the number of words of length n over an alphabet of size 4 that are in standard order and which have the property that every letter that appears in the word is repeated.

Original entry on oeis.org

0, 0, 1, 1, 4, 11, 41, 162, 715, 3425, 16777, 80928, 379347, 1726375, 7654817, 33219630, 141692075, 596122477, 2480969257, 10237751324, 41963944275, 171103765747, 694775280993, 2812004330666, 11352134320523, 45736973060601, 183981143571721, 739167464021912, 2966826380664595, 11899055223201855

Offset: 0

N. J. A. Sloane, Dec 06 2016

nonn

Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"

A row of the array in A278987.

Conjectures from Colin Barker, Nov 25 2017: (Start)
G.f.: x^2*(1 - 19*x + 159*x^2 - 776*x^3 + 2474*x^4 - 5498*x^5 + 8993*x^6 - 11471*x^7 + 11815*x^8 - 9478*x^9 + 5348*x^10 - 1848*x^11 + 288*x^12) / ((1 - x)^4*(1 - 2*x)^3*(1 - 3*x)^2*(1 - 4*x)).
a(n) = 20*a(n-1) - 175*a(n-2) + 882*a(n-3) - 2835*a(n-4) + 6072*a(n-5) - 8777*a(n-6) + 8458*a(n-7) - 5204*a(n-8) + 1848*a(n-9) - 288*a(n-10) for n > 14.
(End)

cp's OEIS Frontend

A383253 Number of compositions of n with parts in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A137855 Triangle read by rows: T(n,k) = Sum_{j=1..n-k+1} Stirling2(k, j).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A273977 Words over an alphabet of size 9 that are in standard order with at least one letter repeated.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A278985 List of words of length n over an alphabet of size 3 that are in standard order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A273978 List of words of length n over an alphabet of size 9 that are in standard order and which have the property that every letter that appears in the word is repeated.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A380822 Triangle read by rows: T(n,k) is the number of compositions of n with k pairs of equal adjacent parts and all parts in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A383713 Triangle read by rows: T(n,k) is the number of compositions of n with k parts all in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A278986 Array read by antidiagonals downwards: T(b,n) = number of words of length n over an alphabet of size b that are in standard order and which have the property that at least one letter is repeated.

Views