Andrew Woods - cp's OEIS frontend

A288348 Spherical growth function of the Lamplighter group L_2 with respect to the standard generators a, t.

1, 3, 6, 12, 22, 40, 71, 123, 212, 360, 607, 1017, 1693, 2807, 4635, 7629, 12524, 20512, 33532, 54728, 89201, 145223, 236200, 383858, 623393, 1011813, 1641441, 2661767, 4314821, 6992417, 11328796, 18350552, 29719248, 48124026, 77916923, 126140917, 204193454

Offset: 0

Andrew Woods, Jun 08 2017

nonn

Here t and t^{-1} can be thought of as moves left and right, while a=a^{-1} represents the lighting or extinguishing of a lamp.

			Writing L and R for t and t^{-1}, there are 12 elements of the group which can be written as words of length 3, but not more briefly: LLL, LLa, LaL, LaR, aLL, aLa, aRa, aRR, RaL, RaR, RRa, and RRR.

Walter Parry, Growth series of some wreath products, Trans. Amer. Math. Soc., Vol. 331 (1992), No. 2, 751-759.
Index entries for linear recurrences with constant coefficients, signature (1, 3, 0, -5, -3, 2, 3, 1).

G.f.: (1+x)(1-x^2)^2*(1+x+x^2)/((1-x^2-x^3)^2*(1-x-x^2)).

A249665 The number of permutations p of {1,...,n} such that p(1)=1, p(n)=n, and |p(i)-p(i+1)| is in {1,2,3} for all i from 1 to n-1.

Original entry on oeis.org

1, 1, 1, 2, 6, 14, 28, 56, 118, 254, 541, 1140, 2401, 5074, 10738, 22711, 48001, 101447, 214446, 453355, 958395, 2025963, 4282685, 9053286, 19138115, 40456779, 85522862, 180789396, 382176531, 807895636, 1707837203, 3610252689, 7631830480

Offset: 1

Andrew Woods, Mar 06 2015

These partitions are qualified as 3-bounded and anchored. The number of 2-bounded anchored partitions of [1..n] is A000930(n). - Michel Marcus, Aug 13 2018

			For n = 5, the a(5) = 6 solutions are 123456, 132456, 134256, 135246, 142356, and 143256.

G. C. Greubel, Table of n, a(n) for n = 1..1000 (terms 1..250 from Andrew Woods).
Maria M. Gillespie, Kenneth G. Monks, and Kenneth M. Monks, Enumerating Anchored Permutations with Bounded Gaps, arXiv:1808.03573 [math.CO], 2018. Also Discrete Math.,343 (2020), #111957. (Proves the formulas and conjectures.)
Index entries for linear recurrences with constant coefficients, signature (2,-1,2,1,1,0,-1,-1).

Cf. A000930, A174700, A337654.

R:=PowerSeriesRing(Integers(), 41);
Coefficients(R!( x*(1-x-x^3)/(1-2*x+x^2-2*x^3-x^4-x^5+x^7+x^8) )); // G. C. Greubel, Sep 23 2024

(1-x-x^3)/(1 -2x +x^2 -2x^3 -x^4-x^5+x^7+x^8) + O[x]^33 // CoefficientList[#, x]& (* Jean-François Alcover, Sep 23 2018, after Colin Barker *)

Vec(x*(1 - x - x^3) / (1 - 2*x + x^2 - 2*x^3 - x^4 - x^5 + x^7 + x^8) + O(x^40)) \\ Colin Barker, Aug 13 2018

def A249665_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x*(1-x-x^3)/(1-2*x+x^2-2*x^3-x^4-x^5+x^7+x^8) ).list()
a=A249665_list(41); a[1:] # G. C. Greubel, Sep 23 2024

Let a(1)=1, g(1)=h(1)=0. For all n<1, let a(n)=g(n)=h(n)=0. Then:
a(n) = a(n-1) + g(n-1) + h(n-1),
g(n) = a(n-2) + a(n-3) + a(n-4) - a(n-6) + g(n-2) + g(n-4) + h(n-2),
h(n) = 2*a(n-3) + 2*a(n-4) + a(n-5) - a(n-7) + g(n-3) + g(n-5) + h(n-3).
Alternatively, let a(1)=1, a(n)=0 for n<1. Let b(1)=1, b(2)=0, b(3)=1, b(4)=3, b(5)=4, b(6)=5, b(7)=7, b(8)=10, and b(n)=b(n-1)+b(n-3) for n>8. Then:
a(n) = a(n-1)*b(1) + a(n-2)*b(2) + a(n-3)*b(3) + ... + a(1)*b(n-1).
From Colin Barker, Mar 07 2015 and Aug 13 2018: (Start)
a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) + a(n-4) + a(n-5) - a(n-7) - a(n-8).
G.f.: x*(1 - x - x^3) / (1 - 2*x + x^2 - 2*x^3 - x^4 - x^5 + x^7 + x^8).
(End)

A249019 Number of ternary words of length n in which all digits 0..2 occur in every 6 consecutive digits.

Original entry on oeis.org

1, 3, 9, 27, 81, 243, 540, 1440, 3804, 9960, 25908, 67344, 175884, 458832, 1196364, 3119304, 8134164, 21212832, 55316892, 144249168, 376159644, 980918904, 2557958964, 6670420704, 17394543180, 45359994336, 118285895244, 308455762488, 804364332180, 2097551985168, 5469815336796, 14263713072192

Offset: 0

Andrew Woods, Jan 12 2015

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,2,3,5,6,-1,-1,0,-1,-1).

Cf. A248959, A248960.

LinearRecurrence[{1,2,3,5,6,-1,-1,0,-1,-1},{1,3,9,27,81,243,540,1440,3804,9960,25908,67344,175884,458832,1196364,3119304},40] (* Harvey P. Dale, Feb 05 2019 *)

Vec(-12*x^6*(20*x^9 +27*x^8 +9*x^7 +23*x^6 +28*x^5 -110*x^4 -138*x^3 -107*x^2 -75*x -45) / (x^10 +x^9 +x^7 +x^6 -6*x^5 -5*x^4 -3*x^3 -2*x^2 -x +1) + O(x^100)) \\ Colin Barker, Jan 12 2015

a(n) = a(n-1) + 2*a(n-2) + 3*a(n-3) + 5*a(n-4) + 6*a(n-5) - a(n-6) - a(n-7) - a(n-9) - a(n-10), for n>=16.

G.f.: (1 + 2*x + 4*x^2 + 9*x^3 + 22*x^4 + 60*x^5 - 8*x^6 - 14*x^7 - 8*x^9 - 26*x^10 + 3*x^12 + 3*x^15)/(1 - x - 2*x^2 - 3*x^3 - 5* x^4 - 6*x^5 + x^6 + x^7 + x^9 + x^10). - Colin Barker, Jan 12 2015

A248960 Number of ternary words of length n in which all digits 0..2 occur in every 5 consecutive digits.

Original entry on oeis.org

1, 3, 9, 27, 81, 150, 366, 870, 2022, 4686, 10974, 25614, 59742, 139398, 325350, 759198, 1771590, 4134126, 9647262, 22512342, 52533750, 122590422, 286071414, 667563054, 1557794622, 3635198310, 8482932318, 19795382454, 46193598486, 107795266974, 251546100558, 586996465758, 1369788083022

Offset: 0

Andrew Woods, Jan 12 2015

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,2,2,2,-1,-1).

Cf. A242317, A249019.

Join[{1,3,9,27,81},LinearRecurrence[{1,2,2,2,-1,-1},{150,366,870,2022,4686,10974},30]] (* Harvey P. Dale, Apr 04 2015 *)

Vec((1+2*x+4*x^2+10*x^3+28*x^4-8*x^5-14*x^6-6*x^8+3*x^10)/((1+x)*(1-2*x-2*x^3+x^5)) + O(x^30)) \\ Colin Barker, Oct 27 2016

G.f.: (1+2*x+4*x^2+10*x^3+28*x^4-8*x^5-14*x^6-6*x^8+3*x^10) / ((1+x)*(1-2*x-2*x^3+x^5)). - Colin Barker, Oct 27 2016
a(n) = a(n-1) + 2*a(n-2) + 2*a(n-3) + 2*a(n-4) - a(n-5) - a(n-6).
a(n) = A242317(n-4) * 6.

Changed offset to 0. - N. J. A. Sloane, Jan 15 2015

A248959 Number of ternary words of length n in which all digits 0..2 occur in every subword of 4 consecutive digits.

Original entry on oeis.org

1, 3, 9, 27, 36, 72, 132, 240, 444, 816, 1500, 2760, 5076, 9336, 17172, 31584, 58092, 106848, 196524, 361464, 664836, 1222824, 2249124, 4136784, 7608732, 13994640, 25740156, 47343528, 87078324, 160162008, 294583860, 541824192, 996570060, 1832978112

Offset: 0

Andrew Woods, Jan 12 2015

For n < 4 the constraint is voidly satisfied: each of the n-digit words satisfies the definition since there is no subword of length 4. - M. F. Hasler, Jan 13 2015

Colin Barker, Table of n, a(n) for n = 0..1000 (corrected by _Georg Fischer_, Jan 20 2019)
Index entries for linear recurrences with constant coefficients, signature (1,1,1).

Cf. A001590, A196700.

Join[{1,3,9,27},LinearRecurrence[{1,1,1},{36,72,132},30]] (* Harvey P. Dale, Mar 12 2015 *)

Vec((1+2*x+5*x^2+14*x^3-3*x^4-3*x^6)/(1-x-x^2-x^3) + O(x^100)) \\ Colin Barker, Jan 12 2015; extended to indices 0..3 by M. F. Hasler, Jan 13 2015

G.f.: (1 + 2*x + 5*x^2 + 14*x^3 - 3*x^4 - 3*x^6)/(1 - x - x^2 - x^3). - Corrected by Colin Barker, Jan 12 2015
a(n) = a(n-1) + a(n-2) + a(n-3).
a(n) = A001590(n+1) * 12, for n>=4.
a(n) = A196700(n) * 6, for n>=4. - Alois P. Heinz, Jan 12 2015

a(0)-a(3) from M. F. Hasler, Jan 13 2015

A253409 The number of ways to write an n-bit binary string and then define each run of ones as an element in an equivalence relation, and each run of zeros as an element in a second equivalence relation.

Original entry on oeis.org

1, 2, 4, 10, 28, 86, 282, 984, 3630, 14138, 57904, 248854, 1118554, 5246980, 25619018, 129961850, 683561488, 3722029314, 20946195078, 121671375312, 728511702462, 4491224518274, 28475638336144, 185499720543262, 1240358846060122, 8505894459387628, 59771243719783410

Offset: 0

Andrew Woods, Jan 01 2015

nonn

Included are the cases in which there are no zeros or no ones, producing an empty relation.

			For n = 3, taking 3-bit binary strings and replacing zeros with ABC... and ones with 123... to represent equivalence relations, we have a(3) = 10 labeled-run binary strings: AAA, AA1, A1A, A1B, 1AA, A11, 11A, 111, 1A1, 1A2.

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

Cf. A000110, A247100.

Table[2 * Sum[Binomial[n-1,2k-1] * BellB[k]^2 + Binomial[n-1,2k-2] * BellB[k] * BellB[k-1],{k,1,Ceiling[n/2]}],{n,1,30}] (* Vaclav Kotesovec, Jan 08 2015 after Andrew Woods *)

a(n) = 2 * Sum_{k=1..ceiling(n/2)} C(n-1,2k-1)*Bell(k)^2 + C(n-1,2k-2)*Bell(k)*Bell(k-1), where C(x,y) refers to binomial coefficients and Bell(x) refers to Bell numbers (A000110).

a(0)=1 prepended by Alois P. Heinz, Aug 08 2015

A253511 Number of n-bit binary strings in which the length of any run of ones is a power of two.

Original entry on oeis.org

1, 2, 4, 7, 14, 26, 49, 93, 176, 333, 630, 1192, 2255, 4267, 8073, 15274, 28900, 54679, 103455, 195741, 370348, 700713, 1325774, 2508412, 4746007, 8979617, 16989761, 32145244, 60819967, 115073582, 217723390, 411940547, 779406450, 1474665262, 2790120139

Offset: 0

Andrew Woods, Jan 02 2015

nonn

			For n = 4, the a(4) = 14 solutions are 0000, 0001, 0010, 0100, 1000, 0101, 1001, 1010, 0011, 0110, 1100, 1011, 1101, and 1111.

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

Cf. A000079, A023359, A209229.

a:= proc(n) option remember; `if`(n<1, 1,
      a(n-1) +add(a(n-1-2^k), k=0..ilog2(n)))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jan 03 2015

terms = 35; h[x_] = Sum[x^2^k, {k, 0, Log[2, terms] // Floor}];
CoefficientList[(1 + h[x])/(1 - x - x h[x]) + O[x]^terms, x] (* Jean-François Alcover, Mar 22 2019, after Robert Israel *)

a(n) = a(n-1) + Sum_{k>=0} a(n-(1+2^k)), with a(-1) = a(0) = 1 and a(n) = 0 for n < -1.

G.f.: (1 + h(x))/(1 - x - x*h(x)) where h(x) = sum(k >= 0, x^(2^k)) is the g.f. of A209229. - Robert Israel, Jan 04 2015

A247100 The number of ways to write an n-bit binary string and then define each run of ones as an element in an equivalence relation.

Original entry on oeis.org

1, 2, 4, 9, 21, 51, 127, 324, 844, 2243, 6073, 16737, 46905, 133556, 386062, 1132107, 3365627, 10137559, 30920943, 95457178, 298128278, 941574417, 3006040523, 9697677885, 31602993021, 104001763258, 345524136076, 1158570129917, 3919771027105, 13377907523151

Offset: 0

Andrew Woods, Jan 01 2015

nonn

Also the number of partitions of subsets of {1,...,n}, where consecutive integers are required to be in the same part. Example: For n=3 the a(3)=9 partitions are {}, 1, 2, 3, 12, 23, 13, 1|3, 123. - Don Knuth, Aug 07 2015

			The labeled-run binary strings can be written as follows.
For n=1: 0, 1.
For n=2: 00, 01, 10, 11.
For n=3: 000, 001, 010, 100, 011, 110, 111, 101, 102.
For n=4: 0000, 0001, 0010, 0100, 1000, 0011, 0110, 1100, 0111, 1110, 1111, 0101, 0102, 1001, 1002, 1010, 1020, 1011, 1022, 1101, 1102.
For n=5, the original binary string 10101 can be written as 10101, 10102, 10201, 10202, or 10203 because there are 3 runs of ones and Bell(3)=5.

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

Cf. A000110, A243634, A253409, A255706, A261041, A261134, A261489, A261492.

with(combinat):
a:= n-> (t-> add(binomial(t, 2*j)*bell(j), j=0..t/2))(n+1):
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 10 2015

Table[1 + Sum[Binomial[n+1,2*k] * BellB[k],{k,1,Ceiling[n/2]}],{n,1,40}] (* Vaclav Kotesovec, Jan 08 2015 after Andrew Woods *)

a(n) = 1 + Sum_{k=1..ceiling(n/2)} binomial(n+1, 2k)*Bell(k), where Bell(x) refers to Bell numbers (A000110).

a(0)=1 prepended by Alois P. Heinz, Aug 08 2015

A253207 a(n) = number of permutations of (1,2,...,n) producible by an ordered quadruple of distinct transpositions.

Original entry on oeis.org

11, 59, 359, 1799, 7091, 22995, 64143, 159093, 359348, 752180, 1478204, 2754752, 4906202, 8402522, 13907394, 22337388, 34933761, 53348561, 79746821, 116926733, 168459797, 238853045, 333735545, 460071495, 626402322, 843120306, 1122776354

Offset: 4

Andrew Woods, Dec 28 2014

Colin Barker, Table of n, a(n) for n = 4..1000
Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Cf. A000914, for two transpositions, and A253171, for three.

Vec(-x^4*(2*x^8-18*x^7+72*x^6-168*x^5+254*x^4-232*x^3+224*x^2-40*x+11)/(x-1)^9 + O(x^100)) \\ Colin Barker, Dec 30 2014

a(n) = n!*(1/(384*(n-8)!)+1/(24*(n-7)!)+13/(72*(n-6)!)+1/(5*(n-5)!)+1/(8*(n-4)!)+1/(3*(n-3)!)) for n>=8.

A253171 a(n) = number of permutations of (1,2,...,n) producible by an ordered triple of distinct transpositions.

Original entry on oeis.org

3, 12, 60, 240, 756, 1988, 4572, 9495, 18205, 32736, 55848, 91182, 143430, 218520, 323816, 468333, 662967, 920740, 1257060, 1689996, 2240568, 2933052, 3795300, 4859075, 6160401, 7739928, 9643312, 11921610, 14631690, 17836656, 21606288, 26017497, 31154795

Offset: 3

Andrew Woods, Dec 28 2014

			For n=4, the 12 permutations are 0132, 0213, 0321, 1023, 1230, 1302, 2031, 2103, 2310, 3012, 3120, and 3201. For example, 0123 is permuted into 0132 by ((b,d),(c,d), (b,c)).

Colin Barker, Table of n, a(n) for n = 3..1000
Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Cf. A000914, for two transpositions.

Vec(-x^3*(x^6-7*x^5+21*x^4-33*x^3+39*x^2-9*x+3)/(x-1)^7 + O(x^100)) \\ Colin Barker, Dec 30 2014

a(n) = n * (n^5 - 7*n^4 + 17*n^3 - 17*n^2 + 30*n - 24) / 48 for n>=3.
a(n) = C(n,2)*(C(n-2,2)*C(n-4,2)/6 + 1) + 2*C(n,3)*C(n-3,2) + 6*C(n,4) for n>=3.
G.f.: -x^3*(x^6-7*x^5+21*x^4-33*x^3+39*x^2-9*x+3) / (x-1)^7. - Colin Barker, Dec 30 2014

More terms from Colin Barker, Dec 30 2014

cp's OEIS Frontend

User: Andrew Woods

A288348 Spherical growth function of the Lamplighter group L_2 with respect to the standard generators a, t.

Views

Author

Keywords

Comments

Examples

Links

Formula

A249665 The number of permutations p of {1,...,n} such that p(1)=1, p(n)=n, and |p(i)-p(i+1)| is in {1,2,3} for all i from 1 to n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A249019 Number of ternary words of length n in which all digits 0..2 occur in every 6 consecutive digits.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A248960 Number of ternary words of length n in which all digits 0..2 occur in every 5 consecutive digits.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A248959 Number of ternary words of length n in which all digits 0..2 occur in every subword of 4 consecutive digits.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A253409 The number of ways to write an n-bit binary string and then define each run of ones as an element in an equivalence relation, and each run of zeros as an element in a second equivalence relation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A253511 Number of n-bit binary strings in which the length of any run of ones is a power of two.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula