A137742 -id:A137742 - cp's OEIS frontend

A135473 a(n) = number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring in place.

0, 0, 1, 3, 8, 21, 54, 138, 355, 924, 2432, 6461, 17301, 46657, 126656, 345972, 950611, 2626253, 7292268, 20342805, 56993909, 160317859, 452642235, 1282466920, 3645564511, 10395117584, 29727982740, 85251828792, 245120276345, 706529708510, 2041260301955, 5910531770835, 17149854645474, 49859456251401, 145223624492108, 423722038708874, 1238318400527185

Offset: 1

Max Alekseyev, Jan 07 2008

nonn

The problem can be restated as follows: look at the language L over {1,2,3}* which contains 123 and is closed under duplication. What is the growth function of L (or its subword complexity function)?
It is known that the language L is not regular [Wang]
Several generalizations suggest themselves: What if we start with k different letters (here k=3)? What if we start with k different letters and fix the number of duplications d? See A137739, A137740, A137741, A137742, A137743, A137744, A137745, A137746, A137747, A137748.

			n=3: abc
n=4: aabc, abbc, abcc
n=5: aaabc, abbbc, abccc, aabbc, aabcc, abbcc, ababc, abcbc

D. P. Bovet and S. Varricchio, On the regularity of languages on a binary alphabet generated by copying systems, Information Processing Letters, 44 (1992), 119-123.
Juergen Dassow, Victor Mitrana and Gheorghe Paun: On the Regularity of Duplication Closure. Bulletin of the EATCS 69 (1999), 133-136.
Ming-wei Wang, On the Irregularity of the Duplication Closure, Bulletin of the EATCS, Vol. 70, 2000, 162-163.

Martin Fuller, Table of n, a(n) for n = 1..44
Index entries for doubling substrings

Cf. A135017, A135156, A135157, A135475, A135479, A130838.

Cf. also A137739, A137740, A137741, A137742, A137743, A137744, A137745, A137746, A137747, A137748.

Binomial transform of A135017. - Martin Fuller, Jun 06 2025

Empirically, grows like 3^n.

a(19) - a(33) from David Applegate, Feb 12 2008
Extended to 37 terms by David Applegate, Feb 16 2008
Thanks to Robert Mercas and others for comments and references - N. J. A. Sloane, Apr 26 2013

A137743 Number T(m,n) of different strings of length n obtained from "123...m" by iteratively duplicating any substring; formatted as upper right triangle.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 8, 8, 4, 1, 1, 16, 21, 13, 5, 1, 1, 32, 54, 40, 19, 6, 1, 1, 64, 138, 119, 66, 26, 7, 1, 1, 128, 355, 348, 218, 100, 34, 8, 1, 1, 256, 924, 1014, 700, 360, 143, 43, 9, 1, 1, 512, 2432, 2966, 2218, 1246, 555, 196, 53, 10, 1

Offset: 1

M. F. Hasler, Feb 10 2008

The sequence T(m,m+3) = 1,8,21,40,66,100,143,196,260,... = A137742.

			The full matrix is:
[ 1, 1, 1, 1, 1, 1, 1,_ 1,_ 1,__ 1,__ 1,...] (= A000012)
[[], 1, 2, 4, 8,16,32, 64,128, 256, 512,...] (= A000079)
[[],[], 1, 3, 8,21,54,138,355, 924,2432,...] (= A135473)
[[],[],[], 1, 4,13,40,119,348,1014,2966,...] (= A137744)
[[],[],[],[], 1, 5,19, 66,218, 700,2218,...] (= A137745)
[[],[],[],[],[], 1, 6, 26,100, 360,1246,...] (= A137746)
[[],[],[],[],[],[], 1,_ 7, 34, 143, 555,...] (= A137747)
...

Index entries for doubling substrings

Cf. A135473, A137740-A137742, A137744-A137748.

A135473(Nmax,d=3 /* # digits in the initial string = row of the triangular matrix */)={ local( t,tt,ee,lsb, L=vector(Nmax,i,[]) /*store separately words of given length*/, w=log(d-.5)\log(2)+1/* bits required to code d distinct digits*/); L[d]=Set(sum(i=1,d-1,i<<(w*i))); for( i=d,Nmax-1, for( j=1, #t=eval(L[i]), forstep( ee=w,w*i,w, /*upper cutting point*/ forstep( len=w, min(ee,w*(Nmax-i)),w, /* length of substring */ lsb = bitand( tt=t[j], 1<A137743(10,d)))

T(m,n)=0 for n < m, T(m,m)=T(1,n)=1, T(m,m+1)=m, T(m,m+2)=C(m+2,2)-2 = A034856(m); T(2,2+n)=2^n.

For m > 3, T(m,m+2) = T(m-1,m+1) + T(m,m+1) + T(m+1,m+1). - Thomas Anton, Nov 05 2018

More terms from Alois P. Heinz, Aug 31 2011

A182533 A symmetrical triangle. Read by rows: T(n,k) = 2*C(n-2,k-1) - C(n-2,k) - C(n-2,k-2), n >= 2, 0 <= k <= n, with T(0,0) = 0, T(1,0) = T(1,1) = 1.

Original entry on oeis.org

0, 1, 1, -1, 2, -1, -1, 1, 1, -1, -1, 0, 2, 0, -1, -1, -1, 2, 2, -1, -1, -1, -2, 1, 4, 1, -2, -1, -1, -3, -1, 5, 5, -1, -3, -1, -1, -4, -4, 4, 10, 4, -4, -4, -1, -1, -5, -8, 0, 14, 14, 0, -8, -5, -1, -1, -6, -13, -8, 14, 28, 14, -8, -13, -6, -1, -1, -7, -19, -21, 6, 42, 42, 6, -21, -19, -7, -1

Offset: 1

Alzhekeyev Ascar M, May 04 2012

			Triangle begins
   0;
   1,  1;
  -1,  2, -1;
  -1,  1,  1, -1;
  -1,  0,  2,  0, -1;
  -1, -1,  2,  2, -1, -1;
  -1, -2,  1,  4,  1, -2, -1;
  -1, -3, -1,  5,  5, -1, -3, -1;
  -1, -4, -4,  4, 10,  4, -4, -4, -1;

Muniru A Asiru, Table of n, a(n) for n = 1..5151 (rows n=1..100)
Isabel Cação, Helmuth R. Malonek, Maria Irene Falcão, Graça Tomaz, Combinatorial Identities Associated with a Multidimensional Polynomial Sequence, J. Int. Seq., Vol. 21 (2018), Article 18.7.4.
Graphical representation

Cf. A000108, A120009, A137742.

T:=Concatenation([0,1,1],Flat(List([2..11],n->List([0..n],k->2*Binomial(n-2,k-1)-Binomial(n-2,k)-Binomial(n-2,k-2))))); # Muniru A Asiru, Nov 29 2018

Flatten[Join[{{0}, {1, 1}}, Table[2*Binomial[n - 2, k - 1] - Binomial[n - 2, k] - Binomial[n - 2, k - 2], {n, 2, 15}, {k, 0, n}]]] (* T. D. Noe, May 08 2012 *)

T(n,k) = 2*C(n-2,k-1) - C(n-2,k) - C(n-2,k-2).
Row sums = 0, for n >= 2.
T(2*n,n) = 2*A000108(n-1).
T(2*n+3,n) = -A120009(n).
T(n+10,3) = -A137742(n+2).
Sum_{k=0..n} T(n,k)*2^k = -(3^(n-2)) where n >= 2.
Sum_{k=0..n} T(n,k)*3^k = -(4^(n-1)) where n >= 2.
Sum_{k=0..n} T(n,k)*p^k = -((p+1)^(n-2))*((p-1)^2) where n >= 2.

A188843 T(n,k) is the number of n X k binary arrays without the pattern 0 1 diagonally or vertically.

Original entry on oeis.org

2, 4, 3, 8, 8, 4, 16, 21, 13, 5, 32, 55, 40, 19, 6, 64, 144, 121, 66, 26, 7, 128, 377, 364, 221, 100, 34, 8, 256, 987, 1093, 728, 364, 143, 43, 9, 512, 2584, 3280, 2380, 1288, 560, 196, 53, 10, 1024, 6765, 9841, 7753, 4488, 2108, 820, 260, 64, 11, 2048, 17711, 29524

Offset: 1

R. H. Hardin, Apr 12 2011

Table starts
4   8   16   32    64    128    256     512     1024     2048      4096
8  21   55  144   377    987   2584    6765    17711    46368    121393
13  40  121  364  1093   3280   9841   29524    88573   265720    797161
19  66  221  728  2380   7753  25213   81927   266110   864201   2806272
26 100  364 1288  4488  15504  53296  182688   625184  2137408   7303360
34 143  560 2108  7752  28101 100947  360526  1282735  4552624  16131656
43 196  820 3264 12597  47652 177859  657800  2417416  8844448  32256553
53 260 1156 4845 19551  76912 297275 1134705  4292145 16128061  60304951
64 336 1581 6954 29260 119416 476905 1874730  7283640 28048800 107286661
76 425 2109 9709 42504 179630 740025 2991495 11920740 46981740 183579396

			Some solutions for 5 X 3:
  0 0 1    1 1 0    1 1 1    0 1 0    1 1 0    1 1 0    1 1 1
  0 0 0    1 0 0    1 1 0    0 0 0    1 1 0    1 1 0    1 1 1
  0 0 0    0 0 0    1 1 0    0 0 0    1 0 0    1 1 0    0 1 1
  0 0 0    0 0 0    1 1 0    0 0 0    1 0 0    1 0 0    0 0 0
  0 0 0    0 0 0    0 0 0    0 0 0    0 0 0    0 0 0    0 0 0

R. H. Hardin, Table of n, a(n) for n = 1..1741

Diagonal is A143388.
Column 2 is A034856(n+1).
Column 3 is A137742(n+1).
Row 2 is A001906(n+1).
Row 3 is A003462(n+1).
Row 4 is A005021.
Row 5 is A005022.
Row 6 is A005023.
Row 7 is A005024.
Row 8 is A005025.

Row recurrence
Empirical: T(n,k) = Sum_{i=1..floor((n+2)/2)} binomial(n+2-i,i)*T(n,k-i)*(-1)^(i-1).
E.g.,
empirical: T(1,k) = 2*T(1,k-1),
empirical: T(2,k) = 3*T(2,k-1) -    T(2,k-2),
empirical: T(3,k) = 4*T(3,k-1) -  3*T(3,k-2),
empirical: T(4,k) = 5*T(4,k-1) -  6*T(4,k-2) +    T(4,k-3),
empirical: T(5,k) = 6*T(5,k-1) - 10*T(5,k-2) +  4*T(5,k-3),
empirical: T(6,k) = 7*T(6,k-1) - 15*T(6,k-2) + 10*T(6,k-3) -    T(6,k-4),
empirical: T(7,k) = 8*T(7,k-1) - 21*T(7,k-2) + 20*T(7,k-3) -  5*T(7,k-4),
empirical: T(8,k) = 9*T(8,k-1) - 28*T(8,k-2) + 35*T(8,k-3) - 15*T(8,k-4) + T(8,k-5).
Columns are polynomials for n > k-3.
Empirical: T(n,1) = n + 1.
Empirical: T(n,2) = (1/2)*n^2 + (5/2)*n + 1.
Empirical: T(n,3) = (1/6)*n^3 + 2*n^2 + (35/6)*n.
Empirical: T(n,4) = (1/24)*n^4 + (11/12)*n^3 + (155/24)*n^2 + (163/12)*n - 6 for n > 1.
Empirical: T(n,5) = (1/120)*n^5 + (7/24)*n^4 + (89/24)*n^3 + (473/24)*n^2 + (1877/60)*n - 33 for n > 2.
Empirical: T(n,6) = (1/720)*n^6 + (17/240)*n^5 + (203/144)*n^4 + (647/48)*n^3 + (2659/45)*n^2 + (1379/20)*n - 143 for n > 3.
Empirical: T(n,7) = (1/5040)*n^7 + (1/72)*n^6 + (143/360)*n^5 + (53/9)*n^4 + (33667/720)*n^3 + (12679/72)*n^2 + (9439/70)*n - 572 for n > 4.
Empirical: T(n,8) = (1/40320)*n^8 + (23/10080)*n^7 + (17/192)*n^6 + (269/144)*n^5 + (43949/1920)*n^4 + (228401/1440)*n^3 + (1054411/2016)*n^2 + (9941/56)*n - 2210 for n > 5.

A137746 Number of different strings of length n obtained from "abcdef" by iteratively duplicating any substring.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 6, 26, 100, 360, 1246, 4217, 14102, 46861, 155212, 513336, 1697264, 5614670, 18594258, 61671770, 204907302, 682110940, 2275141754, 7603690251, 25462152854, 85428752530, 287163766530, 967046587261, 3262356284310, 11024401089607, 37315689561280, 126506891234231

Offset: 0

M. F. Hasler, Feb 10 2008

nonn

See A137743 for more comments.

			a(k) = 0 for k<6, since no shorter string can be obtained by duplication
a(6) = 1 = # { abcdef },
a(7) = 6 = # { aabcdef, abbcdef, abccdef, abcddef, abcdeef, abcdeff },
a(8) = 26 = # { aaabcdef, aabbcdef, aabccdef, aabcddef, aabcdeef, aabcdeff, ababcdef, abbbcdef, abbccdef, abbcddef, abbcdeef, abbcdeff, abcbcdef, abcccdef, abccddef, abccdeef, abccdeff, abcdcdef, abcdddef, abcddeef, abcddeff, abcdedef, abcdeeef, abcdeeff, abcdefef, abcdefff }.

Index entries for doubling substrings

Cf. A137740, A137741, A137742, A137743, A135473, A137744, A137745, A137746, A137747, A137748.

A135473(14,6) /* function defined in A137743 ... */

a(15)-a(16) from Alois P. Heinz, Aug 31 2011
a(17)-a(19) from Lars Blomberg, Jan 12 2013
a(20)-a(21) from Michael S. Branicky, Jan 06 2021
a(22)-a(23) from Bert Dobbelaere, Jun 11 2024
a(24)-a(32) from Martin Fuller, Jun 07 2025

A275874 a(n) = (n-4)(n+1)(n+3)/6.

Original entry on oeis.org

0, 8, 21, 40, 66, 100, 143, 196, 260, 336, 425, 528, 646, 780, 931, 1100, 1288, 1496, 1725, 1976, 2250, 2548, 2871, 3220, 3596, 4000, 4433, 4896, 5390, 5916, 6475, 7068, 7696, 8360, 9061, 9800, 10578, 11396, 12255, 13156, 14100, 15088, 16121, 17200, 18326, 19500, 20723, 21996

Offset: 4

N. J. A. Sloane, Aug 14 2016

Colin Barker, Table of n, a(n) for n = 4..1000
Hilton, Peter John, and Jean Pedersen, Descartes, Euler, Poincaré, Pólya and Polyhedra, L'Enseign. Math., 27 (1981), 327-343. See Cor. 1.
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

A137742 is an essentially identical sequence.

a := n -> (n - 4)*(n + 1)*(n + 3)/6:
seq(a(n), n = 4..51); # Peter Luschny, Jan 25 2019

concat(0, Vec(x^5*(8-11*x+4*x^2)/(1-x)^4 + O(x^50))) \\ Colin Barker, Aug 15 2016

From Colin Barker, Aug 15 2016: (Start)
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) for n > 7.
G.f.: x^5*(8 - 11*x + 4*x^2) / (1 - x)^4.
(End)

A361952 Array read by antidiagonals: T(n,k) is the number of unlabeled posets with n elements together with a function rk mapping each element to a rank between 1 and k such that whenever v covers w in the poset then rk(v) = rk(w) + 1.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 4, 1, 0, 1, 4, 8, 8, 1, 0, 1, 5, 13, 21, 17, 1, 0, 1, 6, 19, 40, 58, 38, 1, 0, 1, 7, 26, 66, 126, 172, 94, 1, 0, 1, 8, 34, 100, 228, 420, 569, 258, 1, 0, 1, 9, 43, 143, 373, 816, 1537, 2148, 815, 1, 0, 1, 10, 53, 196, 571, 1412, 3140, 6342, 9538, 3038, 1, 0

Offset: 0

Andrew Howroyd, Mar 31 2023

A poset is counted once for each admissible ranking function. This is an intermediate step in the computation of A361953 where each graded poset is counted exactly once.

			Array begins:
============================================
n/k| 0 1   2    3    4     5     6     7 ...
---+----------------------------------------
0  | 1 1   1    1    1     1     1     1 ...
1  | 0 1   2    3    4     5     6     7 ...
2  | 0 1   4    8   13    19    26    34 ...
3  | 0 1   8   21   40    66   100   143 ...
4  | 0 1  17   58  126   228   373   571 ...
5  | 0 1  38  172  420   816  1412  2272 ...
6  | 0 1  94  569 1537  3140  5631  9351 ...
7  | 0 1 258 2148 6342 13383 24410 41097 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..860 (first 41 antidiagonals).

Columns k=0..2 are A000007, A000012, A049312.
Rows n=0..4 are A000012, A000027, A034856, A137742.
The labeled version is A361950.
Cf. A361953.

\\ See Links in A361953 for program.
{ my(A=A361952tabl(7)); for(i=1, #A, print(A[i,])) }

A137738 Coefficients of the polynomial giving the n-th diagonal of A137743 * n!, read as an upper right triangle.

Original entry on oeis.org

1, 0, 1, -2, 3, 1, -24, 14, 9, 1, -288, 54, 95, 18, 1, -4320, -136, 1110, 315, 30, 1, -80640, -12300, 15064, 5775, 775, 45, 1

Offset: 0

M. F. Hasler, Mar 18 2008

Let T(m,n) = number of different strings of length n obtained from "123...m" by iteratively duplicating any substring (A137743).
It can be shown that for given k>=0 and all n>k-2, T(n,n+k) = (1/k!) P[k](n), where P[k] is a monic polynomial of degree k with integer coefficients, whose coefficients are the k-th column of the upper right triangular array defined by present sequence A137738.
Here rows and columns start at 0 (which also motivated the chosen offset 0), i.e. a(0) = 1 means P[0] = 1, a(1..2) = 0,1 means P[1] = 0 + 1*X, a(3..6) = -2,3,1 means P[2] = -2 + 3*X + 1*X^2, etc.

			We have the following formulas for T(m,n) as given in A137743:
T(n,n) = 1, T(n,n+1) = n, T(n,n+2) = (n+1)(n+2)/2 - 2,
T(n,n+3) = A137742 = (1/6)*(n-1)*(n+6)*(n+4) for n>1, for n=1 this formula gives 0 instead of 1.
T(n,n+4) = A137741 = (1/24)*(n+3)*(n^3+15*n^2+50*n-96) for n>2, for n=2 this gives 15 instead of 16.
T(n,n+5) = A137740 = (1/5!)*(n+4)*(n^2+3*n-8)*(n^2+23*n+150)+4 for n>3, for n=3 this gives 137 instead of 138.
T(n,n+6) = A137739 = (1/6!)*(n+9)*(n^5+36*n^4+451*n^3+1716*n^2-380*n-8880)-1 for n>4, for n=4 this gives 1013 instead of 1014.
They satisfy the following relations:
T(n,n+2) = sum( T(k,k+1), k=0..n+1) - 2
T(n,n+3) = sum( T(k,k+2), k=1..n+1) - 5
T(n,n+4) = sum( T(k,k+3), k=2..n+1) - 12 - n
T(n,n+5) = sum( T(k,k+4), k=3..n+1) - 21 - 7n/2 - n^2/2
T(n,n+6) = sum( T(k,k+5), k=4..n+1) + 49 - 25n/3 - 5n^2/2 - n^3/6

M. F. Hasler, New topic: duplication of substrings, SeqFan mailing list, Feb 9-11, 2008.
Index entries for doubling substrings

Cf. A137739-A137743, A135473, A137744-A137748.

P[k](n) = k! T(n,n+k) for k>=0 and positive n>k-2, where T(m,n) is given in A137743.
P[k] = X^k + A045943(k) X^(k-1) + O(X^(k-2)) for k>=1.
For m>0, T(n,n+m+3) = sum( T(k,k+m+2), k=m+1..n+1) - (1/m!) Q[m](n), where Q[m] is a monic polynomial of degree <= m with integer coefficients (conjectured - see examples).

cp's OEIS Frontend

A135473 a(n) = number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring in place.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A137743 Number T(m,n) of different strings of length n obtained from "123...m" by iteratively duplicating any substring; formatted as upper right triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A182533 A symmetrical triangle. Read by rows: T(n,k) = 2*C(n-2,k-1) - C(n-2,k) - C(n-2,k-2), n >= 2, 0 <= k <= n, with T(0,0) = 0, T(1,0) = T(1,1) = 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

GAP

Mathematica

Formula

A188843 T(n,k) is the number of n X k binary arrays without the pattern 0 1 diagonally or vertically.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A137746 Number of different strings of length n obtained from "abcdef" by iteratively duplicating any substring.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A275874 a(n) = (n-4)*(n+1)*(n+3)/6.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A361952 Array read by antidiagonals: T(n,k) is the number of unlabeled posets with n elements together with a function rk mapping each element to a rank between 1 and k such that whenever v covers w in the poset then rk(v) = rk(w) + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A137738 Coefficients of the polynomial giving the n-th diagonal of A137743 * n!, read as an upper right triangle.

Views

Author

Keywords

Comments

A275874 a(n) = (n-4)(n+1)(n+3)/6.