A186244 -id:A186244 - cp's OEIS frontend

A028859 a(n+2) = 2a(n+1) + 2a(n); a(0) = 1, a(1) = 3.

1, 3, 8, 22, 60, 164, 448, 1224, 3344, 9136, 24960, 68192, 186304, 508992, 1390592, 3799168, 10379520, 28357376, 77473792, 211662336, 578272256, 1579869184, 4316282880, 11792304128, 32217174016, 88018956288, 240472260608, 656982433792, 1794909388800, 4903783645184, 13397386067968

Offset: 0

N. J. A. Sloane

Number of words of length n without adjacent 0's from the alphabet {0,1,2}. For example, a(2) counts 01,02,10,11,12,20,21,22. - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Jun 12 2001
Individually, both this sequence and A002605 are convergents to 1+sqrt(3). Mutually, both sequences are convergents to 2+sqrt(3) and 1+sqrt(3)/2. - Klaus E. Kastberg (kastberg(AT)hotkey.net.au), Nov 04 2001 [Can someone clarify what is meant by the obscure second phrase, "Mutually..."? - M. F. Hasler, Aug 06 2018]
Add a loop at two vertices of the graph C_3=K_3. a(n) counts walks of length n+1 between these vertices. - Paul Barry, Oct 15 2004
Prefaced with a 1 as (1 + x + 3x^2 + 8x^3 + 22x^4 + ...) = 1 / (1 - x - 2x^2 - 3x^3 - 5x^4 - 8x^5 - 13x^6 - 21x^7 - ...). - Gary W. Adamson, Jul 28 2009
Equals row 2 of the array in A180165, and the INVERTi transform of A125145. - Gary W. Adamson, Aug 14 2010
Pisano period lengths: 1, 1, 3, 1, 24, 3, 48, 1, 9, 24, 10, 3, 12, 48, 24, 1, 144, 9, 180, 24, .... - R. J. Mathar, Aug 10 2012
Also the number of independent vertex sets and vertex covers in the n-centipede graph. - Eric W. Weisstein, Sep 21 2017
From Gus Wiseman, May 19 2020: (Start)
Conjecture: Also the number of length n + 1 sequences that cover an initial interval of positive integers and whose non-adjacent parts are weakly decreasing. For example, (3,2,3,1,2) has non-adjacent pairs (3,3), (3,1), (3,2), (2,1), (2,2), (3,2), all of which are weakly decreasing, so is counted under a(11). The a(1) = 1 through a(3) = 8 sequences are:
  (1)  (11)  (111)
       (12)  (121)
       (21)  (211)
             (212)
             (221)
             (231)
             (312)
             (321)
The case of compositions is A333148, or A333150 for strict compositions, or A333193 for strictly decreasing parts. A version for ordered set partitions is A332872. Standard composition numbers of these compositions are A334966. Unimodal normal sequences are A227038. See also: A001045, A001523, A032020, A100471, A100881, A115981, A329398, A332836, A332872.
(End)
Number of 2-compositions of n+1 restricted to parts 1 and 2 (and allowed zeros); see Hopkins & Ouvry reference. - Brian Hopkins, Aug 16 2020
The number of ternary strings of length n not containing 00. Complement of A186244. - R. J. Mathar, Feb 13 2022

S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 73).

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2025. See p. 14.
Joerg Arndt, Matters Computational (The Fxtbook), section 14.9 "Strings with no two consecutive zeros", pp.318-320.
C. Bautista-Ramos and C. Guillen-Galvan, Fibonacci numbers of generalized Zykov sums, J. Integer Seq., 15 (2012), #12.7.8.
Moussa Benoumhani, On the Modes of the Independence Polynomial of the Centipede, Journal of Integer Sequences, Vol. 15 (2012), #12.5.1.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3 Example 7.
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
P. Z. Chinn, R. Grimaldi, and S. Heubach, Tiling with Ls and Squares, J. Int. Sequences 10 (2007) #07.2.8.
David Garth and Adam Gouge, Affinely Self-Generating Sets and Morphisms, Journal of Integer Sequences, Article 07.1.5, 10 (2007) 1-13.
Juan B. Gil and Jessica A. Tomasko, Fibonacci colored compositions and applications, arXiv:2108.06462 [math.CO], 2021.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
Tanya Khovanova, Recursive Sequences
J. Shallit, Proof of Irvine's conjecture via mechanized guessing, arXiv preprint arXiv:2310.14252 [math.CO], October 22 2023.
Eric Weisstein's World of Mathematics, Centipede Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Vertex Cover
Index entries for linear recurrences with constant coefficients, signature (2,2).

Cf. A180165, A125145, A026150, A030195, A080040, A083337, A106435, A108898.
Cf. A155020 (same sequence with term 1 prepended).
Cf. A002605.

a028859 n = a028859_list !! n
a028859_list =
   1 : 3 : map (* 2) (zipWith (+) a028859_list (tail a028859_list))
-- Reinhard Zumkeller, Oct 15 2011

a[0]:=1:a[1]:=3:for n from 2 to 24 do a[n]:=2*a[n-1]+2*a[n-2] od: seq(a[n],n=0..24); # Emeric Deutsch

a[n_]:=(MatrixPower[{{1,3},{1,1}},n].{{2},{1}})[[2,1]]; Table[a[n],{n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Feb 20 2010 *)
Table[2^(n - 1) Hypergeometric2F1[(1 - n)/2, -n/2, -n, -2], {n, 20}] (* Eric W. Weisstein, Jun 14 2017 *)
LinearRecurrence[{2, 2}, {1, 3}, 20] (* Eric W. Weisstein, Jun 14 2017 *)

a(n)=([1,3;1,1]^n*[2;1])[2,1] \\ Charles R Greathouse IV, Mar 27 2012

A028859(n)=([1,1]*[2,2;1,0]^n)[1] \\ M. F. Hasler, Aug 06 2018

a(n) = a(n-1) + A052945(n) = A002605(n) + A002605(n-1).
G.f.: -(x+1)/(2*x^2+2*x-1).
a(n) = [(1+sqrt(3))^(n+2)-(1-sqrt(3))^(n+2)]/(4*sqrt(3)). - Emeric Deutsch, Feb 01 2005
If p[i]=fibonacci(i+1) and if A is the Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)= det A. - Milan Janjic, May 08 2010
a(n) = 3^n - A186244(n). - Toby Gottfried, Mar 07 2013
E.g.f.: exp(x)*(cosh(sqrt(3)*x) + 2*sinh(sqrt(3)*x)/sqrt(3)). - Stefano Spezia, Mar 02 2024

Definition completed by M. F. Hasler, Aug 06 2018

A008466 a(n) = 2^n - Fibonacci(n+2).

Original entry on oeis.org

0, 0, 1, 3, 8, 19, 43, 94, 201, 423, 880, 1815, 3719, 7582, 15397, 31171, 62952, 126891, 255379, 513342, 1030865, 2068495, 4147936, 8313583, 16655823, 33358014, 66791053, 133703499, 267603416, 535524643, 1071563515, 2143959070, 4289264409, 8580707127

Offset: 0

N. J. A. Sloane, I. J. Kennedy, Eric W. Weisstein

Toss a fair coin n times; a(n) is number of possible outcomes having a run of 2 or more heads.
Also the number of binary words of length n with at least two neighboring 1 digits. For example, a(4)=8 because 8 binary words of length 4 have two or more neighboring 1 digits: 0011, 0110, 0111, 1011, 1100, 1101, 1110, 1111 (cf. A143291). - Alois P. Heinz, Jul 18 2008
Equivalently, number of solutions (x_1, ..., x_n) to the equation x_1*x_2 + x_2*x_3 + x_3*x_4 + ... + x_{n-1}*x_n = 1 in base-2 lunar arithmetic. - N. J. A. Sloane, Apr 23 2011
Row sums of triangle A153281 = (1, 3, 8, 19, 43, ...). - Gary W. Adamson, Dec 23 2008
a(n-1) is the number of compositions of n with at least one part >= 3. - Joerg Arndt, Aug 06 2012
One less than the cardinality of the set of possible numbers of (leaf-) nodes of AVL trees with height n (cf. A143897, A217298). a(3) = 4-1, the set of possible numbers of (leaf-) nodes of AVL trees with height 3 is {5,6,7,8}. - Alois P. Heinz, Mar 20 2013
a(n) is the number of binary words of length n such that some prefix contains three more 1's than 0's or two more 0's than 1's. a(4) = 8 because we have: {0,0,0,0}, {0,0,0,1}, {0,0,1,0}, {0,0,1,1}, {0,1,0,0}, {1,0,0,0}, {1,1,1,0}, {1,1,1,1}. - Geoffrey Critzer, Dec 30 2013
With offset 0: antidiagonal sums of P(j,n) array of j-th partial sums of Fibonacci numbers. - Luciano Ancora, Apr 26 2015

			From _Gus Wiseman_, Jun 25 2020: (Start)
The a(2) = 1 through a(5) = 19 compositions of n + 1 with at least one part >= 3 are:
  (3)  (4)    (5)      (6)
       (1,3)  (1,4)    (1,5)
       (3,1)  (2,3)    (2,4)
              (3,2)    (3,3)
              (4,1)    (4,2)
              (1,1,3)  (5,1)
              (1,3,1)  (1,1,4)
              (3,1,1)  (1,2,3)
                       (1,3,2)
                       (1,4,1)
                       (2,1,3)
                       (2,3,1)
                       (3,1,2)
                       (3,2,1)
                       (4,1,1)
                       (1,1,1,3)
                       (1,1,3,1)
                       (1,3,1,1)
                       (3,1,1,1)
(End)

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd ed. New York: Wiley, p. 300, 1968.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 14, Exercise 1.

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 301 terms from T. D. Noe)
D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic, arXiv:1107.1130 [math.NT], 2001. [Note: we have now changed the name from "dismal arithmetic" to "lunar arithmetic" - the old name was too depressing]
Simon Cowell, A Formula for the Reliability of a d-dimensional Consecutive-k-out-of-n:F System, arXiv preprint arXiv:1506.03580 [math.CO], 2015.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1020
T. Langley, J. Liese, and J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011) # 11.4.2.
B. E. Merkel, Probabilities of Consecutive Events in Coin Flipping, Master's Thesis, Univ. Cincinatti, May 11 2011.
D. J. Persico and H. C. Friedman, Another Coin Tossing Problem, Problem 62-6, SIAM Review, 6 (1964), 313-314.
Eric Weisstein's World of Mathematics, Run.
Index entries for sequences related to dismal (or lunar) arithmetic
Index entries for linear recurrences with constant coefficients, signature (3,-1,-2).

Cf. A050227, A050231, A050232, A050233, A056986.
Cf. A153281, A186244 (ternary words), A335457, A335458, A335516.
The non-contiguous version is A335455.
Row 2 of A340156. Column 3 of A109435.

[2^n-Fibonacci(n+2): n in [0..40]]; // Vincenzo Librandi, Apr 27 2015

a:= n-> (<<3|1|0>, <-1|0|1>, <-2|0|0>>^n)[1, 3]:
seq(a(n), n=0..50); # Alois P. Heinz, Jul 18 2008
# second Maple program:
with(combinat): F:=fibonacci; f:=n->add(2^(n-1-i)*F(i),i=0..n-1); [seq(f(n),n=0..50)]; # N. J. A. Sloane, Mar 31 2014

Table[2^n-Fibonacci[n+2],{n,0,20}] (* Vladimir Joseph Stephan Orlovsky, Jul 22 2008 *)
MMM = 30;
For[ M=2, M <= MMM, M++,
vlist = Array[x, M];
cl[i_] := And[ x[i], x[i+1] ];
cl2 = False; For [ i=1, i <= M-1, i++, cl2 = Or[cl2, cl[i]] ];
R[M] = SatisfiabilityCount[ cl2, vlist ] ]
Table[ R[M], {M,2,MMM}]
(* Find Boolean values of variables that satisfy the formula x1 x2 + x2 x3 + ... + xn-1 xn = 1; N. J. A. Sloane, Apr 23 2011 *)
LinearRecurrence[{3,-1,-2},{0,0,1},40] (* Harvey P. Dale, Aug 09 2013 *)
nn=33; a=1/(1-2x); b=1/(1-2x^2-x^4-x^6/(1-x^2));
CoefficientList[Series[b(a x^3/(1-x^2)+x^2a),{x,0,nn}],x] (* Geoffrey Critzer, Dec 30 2013 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n+1],Max@@#>2&]],{n,0,10}] (* Gus Wiseman, Jun 25 2020 *)

a(n) = 2^n-fibonacci(n+2) \\ Charles R Greathouse IV, Feb 03 2014

def A008466(n): return 2^n - fibonacci(n+2) # G. C. Greubel, Apr 23 2025

a(1)=0, a(2)=1, a(3)=3, a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3). - Miklos Kristof, Nov 24 2003
G.f.: x^2/((1-2*x)*(1-x-x^2)). - Paul Barry, Feb 16 2004
From Paul Barry, May 19 2004: (Start)
Convolution of Fibonacci(n) and (2^n - 0^n)/2.
a(n) = Sum_{k=0..n} (2^k-0^k)*Fibonacci(n-k)/2.
a(n+1) = Sum_{k=0..n} Fibonacci(k)*2^(n-k).
a(n) = 2^n*Sum_{k=0..n} Fibonacci(k)/2^k. (End)
a(n) = a(n-1) + a(n-2) + 2^(n-2). - Jon Stadler (jstadler(AT)capital.edu), Aug 21 2006
a(n) = 2*a(n-1) + Fibonacci(n-1). - Thomas M. Green, Aug 21 2007
a(n) = term (1,3) in the 3 X 3 matrix [3,1,0; -1,0,1; -2,0,0]^n. - Alois P. Heinz, Jul 18 2008
a(n) = 2*a(n-1) - a(n-3) + 2^(n-3). - Carmine Suriano, Mar 08 2011

A186314 Number of ternary strings of length n which contain 01.

Original entry on oeis.org

0, 0, 1, 6, 26, 99, 352, 1200, 3977, 12918, 41338, 130779, 410048, 1276512, 3950929, 12170598, 37343834, 114209811, 348332320, 1059927312, 3218870105, 9758944470, 29544747706, 89335651851, 269843267456, 814337329344, 2455598257057, 7399746051270

Offset: 0

Toby Gottfried, Feb 17 2011

			The recursive formula is based on extending such a string of length n-1 with {0,1,2} or extending a non-matching string of length (n-2) with "01".  For n=2, there is just 1 string: "01". For n=3, we append {0,1,2} to "01" and append "01" to {"0","1","2"}, the three non-matching strings of length 1, for a total of a(3)=6.

Index entries for linear recurrences with constant coefficients, signature (6,-10,3).

Cf. A186244 (ternary strings which contain 00).

nn=20;CoefficientList[Series[1/(1-3x)-1/(x^2+(1-3x)),{x,0,nn}],x] (* Geoffrey Critzer, Dec 25 2013 *)
LinearRecurrence[{6,-10,3},{0,0,1},30] (* Harvey P. Dale, Jun 14 2020 *)

a(n) = 3*a(n-1) + (3^(n-2) - a(n-2)).

G.f.: x^2/((1-3*x)*(1-3*x+x^2)). a(n) = 3^n - A001906(n+1). - Bruno Berselli, Feb 23 2011

A231430 Number of ternary sequences which contain 000.

Original entry on oeis.org

0, 0, 0, 1, 5, 21, 81, 295, 1037, 3555, 11961, 39667, 130049, 422403, 1361385, 4359115, 13880129, 43984227, 138795849, 436367131, 1367434577, 4272615603, 13315096089, 41397076939, 128429930465, 397665266595, 1229127726825, 3792875384251, 11686625364785

Offset: 0

Toby Gottfried, Nov 09 2013

nonn

Recurrence formula given below, a(n) = 3*a(n-1) + 2* (3^(n-4) - a(n-4)) based on following recursive construction: To a string of length (n-1) containing 000 add any of {0,1,2}. To a string of length (n-4) NOT containing 000, add 1000 or 2000. These two operations result in the two terms of the formula.

			For n = 3, the only string is 000.
For n = 4, the 5 strings are: 0000,0001,0002,1000,2000.
For n = 5, there are: 1 with 5 0's, 12 with 4 0's, and 8 with just 3; total 21.

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-4,-4,-6).

Cf. A119826 (without 000), A119827 (exactly one 000).

Cf. A186244 (with 00).

t = {0, 0, 0, 1}; Do[AppendTo[t, 3 t[[-1]] + 2*(3^(n - 4) - t[[-4]])], {n, 4, 30}]; t (* T. D. Noe, Nov 11 2013 *)
(* or *)
nn=28;r=Solve[{s==2x s+2x a+2x b+1,a==x s,b==x a,c==3x c+x b},{s,a,b,c}];CoefficientList[Series[c/.r,{x,0,nn}],x] (* Geoffrey Critzer, Jan 14 2014 *)
CoefficientList[Series[x^3/(1-5x+4x^2+4x^3+6x^4),{x,0,40}],x] (* or *) LinearRecurrence[{5,-4,-4,-6},{0,0,0,1},40] (* Harvey P. Dale, Jul 27 2021 *)

a(n) = 3*a(n-1) + 2* (3^(n-4) - a(n-4)).

G.f.: x^3/(1 - 5*x + 4*x^2 + 4*x^3 +6*x^4). - Geoffrey Critzer, Jan 14 2014

A340156 Square array read by upward antidiagonals: T(n, k) is the number of n-ary strings of length k containing 00.

Original entry on oeis.org

1, 1, 3, 1, 5, 8, 1, 7, 21, 19, 1, 9, 40, 79, 43, 1, 11, 65, 205, 281, 94, 1, 13, 96, 421, 991, 963, 201, 1, 15, 133, 751, 2569, 4612, 3217, 423, 1, 17, 176, 1219, 5531, 15085, 20905, 10547, 880, 1, 19, 225, 1849, 10513, 39186, 86241, 92935, 34089, 1815

Offset: 2

Robert P. P. McKone, Dec 29 2020

			For n = 3 and k = 4, there are 21 strings: {0000, 0001, 0002, 0010, 0011, 0012, 0020, 0021, 0022, 0100, 0200, 1000, 1001, 1002, 1100, 1200, 2000, 2001, 2002, 2100, 2200}.
Square table T(n,k):
     k=2:  k=3:  k=4:   k=5:    k=6:     k=7:
n=2:   1     3     8     19      43       94
n=3:   1     5    21     79     281      963
n=4:   1     7    40    205     991     4612
n=5:   1     9    65    421    2569    15085
n=6:   1    11    96    751    5531    39186
n=7:   1    13   133   1219   10513    87199
n=8:   1    15   176   1849   18271   173608
n=9:   1    17   225   2665   29681   317817

Robert P. P. McKone, Antidiagonals n = 2..100, flattened

Cf. A008466 (row 2), A186244 (row 3), A000567 (column 4).
Cf. A180165 (not containing 00), A340242 (containing 000).
Cf. A000045, A028859, A125145, A086347, A180033, A180167, A322054.
Cf. A005563, A033445.

m[r_] := Normal[With[{p = 1/n}, SparseArray[{Band[{1, 2}] -> p, {i_, 1} /; i <= r -> 1 - p, {r + 1, r + 1} -> 1}]]];
T[n_, k_, r_] := MatrixPower[m[r], k][[1, r + 1]]*n^k;
Reverse[Table[T[n, k - n + 2, 2], {k, 2, 11}, {n, 2, k}], 2] // Flatten (* Robert P. P. McKone, Jan 26 2021 *)

T(n, k) = n^k - A180165(n+1,k-1), where A180165 in the number of strings not containing 00.

m(2) = [1 - 1/n, 1/n, 0; 1 - 1/n, 0, 1/n; 0, 0, 1], is the probability/transition matrix for two consecutive "0" -> "containing 00".

A351530 The number of quinary strings of length n containing 00.

Original entry on oeis.org

0, 0, 1, 9, 65, 421, 2569, 15085, 86241, 483429, 2669305, 14564061, 78699089, 421880725, 2246459881, 11894065549, 62665617345, 328756309701, 1718275598809, 8951067087165, 46492068009521, 240846026714869, 1244719810538185, 6419100507215341

Offset: 0

R. J. Mathar, Feb 13 2022

Michael De Vlieger, Table of n, a(n) for n = 0..1430
Index entries for linear recurrences with constant coefficients, signature (9,-16,-20).

Cf. A008466 (2-ary), A186244 (3-ary), A351529 (4-ary), A086347 (not containing 00).

CoefficientList[Series[x^2/((5*x - 1)*(4*x^2 + 4*x - 1)), {x, 0, 30}], x] (* Wesley Ivan Hurt, Jun 22 2022 *)
LinearRecurrence[{9,-16,-20},{0,0,1},30] (* Harvey P. Dale, Mar 26 2024 *)

G.f.: x^2 / ( (5*x-1)*(4*x^2+4*x-1) ).
a(n) = 5^n - A086347(n).
a(n) = 9*a(n-1) - 16*a(n-2) - 20*a(n-3). - Wesley Ivan Hurt, Jun 22 2022

A338230 Number of ternary strings of length n that contain at least two 0's and at most one 1.

Original entry on oeis.org

0, 0, 1, 7, 27, 81, 213, 519, 1207, 2725, 6033, 13179, 28515, 61257, 130861, 278287, 589551, 1244877, 2621097, 5504643, 11533915, 24116785, 50331141, 104857047, 218103207, 452984181, 939523393, 1946156299, 4026531027, 8321498265, 17179868253, 35433479199, 73014442975, 150323854237

Offset: 0

Enrique Navarrete, Jan 30 2021

			a(4) = 27 since the strings consist of 0000, the 4 permutations of 0001, the 4 permutations of 0002, the 6 permutations of 0022, and the 12 permutations of 0012. The total number of strings is then 1 + 4 + 4 + 6 + 12 = 27.

Index entries for linear recurrences with constant coefficients, signature (7,-19,25,-16,4).

Cf. A186244, A186314.

Cf. A338229, A338232.

CoefficientList[Series[Exp[x](Exp[x]-1-x)(1+x),{x,0,32}],x]Table[i!,{i,0,32}] (* Stefano Spezia, Jan 31 2021 *)

a(n) = 2^n + n*2^(n-1) - 2*binomial(n,2) - 2*n - 1.
E.g.f.: exp(x)*(exp(x) - 1 - x)*(1 + x).
G.f.: x^2*(1 - 3*x^2)/((1 - 2*x)^2*(1 - x)^3). - Stefano Spezia, Jan 31 2021

A341050 Cube array read by upward antidiagonals ignoring zero and empty terms: T(n, k, r) is the number of n-ary strings of length k, containing r consecutive 0's.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 3, 1, 5, 8, 1, 1, 3, 1, 5, 8, 1, 7, 21, 19, 1, 1, 3, 1, 5, 8, 1, 7, 21, 20, 1, 9, 40, 81, 43, 1, 1, 3, 1, 5, 8, 1, 7, 21, 20, 1, 9, 40, 81, 47, 1, 11, 65, 208, 295, 94, 1, 1, 3, 1, 5, 8, 1, 7, 21, 20, 1, 9, 40, 81, 48, 1, 11, 65, 208, 297, 107, 1, 13, 96, 425, 1024, 1037, 201

Offset: 2

Robert P. P. McKone, Feb 04 2021

			For n = 5, k = 6 and r = 4, there are 65 strings: {000000, 000001, 000002, 000003, 000004, 000010, 000011, 000012, 000013, 000014, 000020, 000021, 000022, 000023, 000024, 000030, 000031, 000032, 000033, 000034, 000040, 000041, 000042, 000043, 000044, 010000, 020000, 030000, 040000, 100000, 100001, 100002, 100003, 100004, 110000, 120000, 130000, 140000, 200000, 200001, 200002, 200003, 200004, 210000, 220000, 230000, 240000, 300000, 300001, 300002, 300003, 300004, 310000, 320000, 330000, 340000, 400000, 400001, 400002, 400003, 400004, 410000, 420000, 430000, 440000}
The first seven slices of the tetrahedron (or pyramid) are:
-----------------Slice 1-----------------
  1
-----------------Slice 2-----------------
    1
  1  3
-----------------Slice 3-----------------
      1
    1  3
  1  5  8
-----------------Slice 4-----------------
        1
      1  3
    1  5   8
  1  7  21  19
-----------------Slice 5-----------------
          1
        1  3
      1  5   8
    1  7  21  20
  1  9  40  81  43
-----------------Slice 6-----------------
              1
           1    3
        1    5     8
      1   7    21    20
    1   9   40    81    47
  1  11  65   208   295   94
-----------------Slice 7-----------------
                 1
              1     3
           1     5     8
         1    7     21    20
      1    9    40     81      48
    1   11   65    208     297     107
  1  13   96   425    1024    1037    201

Robert P. P. McKone, Antidiagonals n = 2..50, flattened

Cf. A340156 (r=2), A340242 (r=3).
Cf. A008466 (n=2, r=2), A186244 (n=3, r=2), A050231 (n=2, r=3), A231430 (n=3, r=3).
Cf. A005408, A003215, A005917, A022521, A022522, A022523, A022524, A022525, A022526, A022527, A022528, A022529, A022530, A022531, A022532, A022533, A022534, A022535, A022536, A022537, A022538, A022539, A022540 (k=x, r=1, where x is the x-th Nexus Number).
Cf. A000567 [(k=4, r=2),(k=5, r=3),(k=6, r=4),...,(k=x, r=x-2)].
Cf. A103532 [(k=6, r=3),(k=7, r=4),(k=8, r=5),...,(k=x, r=x-3)].

m[r_, n_] := Normal[With[{p = 1/n}, SparseArray[{Band[{1, 2}] -> p, {i_, 1} /; i <= r -> 1 - p, {r + 1, r + 1} -> 1}]]]; T[n_, k_, r_] := MatrixPower[m[r, n], k][[1, r + 1]]*n^k; DeleteCases[Transpose[PadLeft[Reverse[Table[T[n, k, r], {k, 2, 8}, {r, 2, k}, {n, 2, r}], 2]], 2 <-> 3], 0, 3] // Flatten

A351529 The number of quaternary strings of length n containing 00.

Original entry on oeis.org

0, 0, 1, 7, 40, 205, 991, 4612, 20905, 92935, 407056, 1762117, 7556095, 32148940, 135892321, 571232647, 2389810360, 9956870845, 41335010911, 171055514452, 705891052825, 2905717608775, 11934337612576, 48918212175157, 200149835407615, 817572886925980

Offset: 0

R. J. Mathar, Feb 13 2022

Index entries for linear recurrences with constant coefficients, signature (7,-9,-12).

Cf. A008466 (2-ary), A186244 (3-ary), A351530 (5-ary), A125145 (not containing 00).

LinearRecurrence[{7,-9,-12},{0,0,1},30] (* Harvey P. Dale, Feb 27 2023 *)

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

a(n) = 4^n - A125145(n).

A309000 Number of strings of length n from a 3-symbol alphabet (A,B,C, say) containing at least one "A" and at least two "B"s.

Original entry on oeis.org

3, 22, 105, 416, 1491, 5034, 16365, 51892, 161799, 498686, 1524705, 4635528, 14037627, 42391378, 127763925, 384536924, 1156232175, 3474201510, 10434138825, 31326533680, 94029932643, 282194655482, 846802070205, 2540859195396, 7623517110231, 22872497487694

Offset: 3

Adam Vellender, Jul 04 2019

This sequence can be thought of as the number of ways of rolling n 3-sided dice (with sides "A", "B", and "C") and obtaining at least one A and at least two B's.

The general formula is readily proved true by counting arguments.

			Suppose three-sided dice each have sides labeled A,B,C.
If there are three dice, then ABB, BAB, and BBA are the three strings resulting from rolling the dice satisfying the property of at least one A and at least two B's, hence a(3)=3 [Note a(0)=a(1)=a(2)=0].
If there are four such dice, there are 22 such permutations, hence a(4)=22: AABB, ABAB, ABBA, ABBB, ABBC, ABCB, ACBB, BAAB, BABA, BABB, BABC, BACB, BBAA, BBAB, BBAC, BBBA, BBCA, BCAB, BCBA, CABB, CBAB, CBBA.

Index entries for linear recurrences with constant coefficients, signature (9,-31,51,-40,12).

Cf. A269914, A269915, A269916, A269917, A186244, A186314.

[3^n-2^(n+1)-n*2^(n-1)+n+1: n in [3..40]]; // Vincenzo Librandi, Jul 05 2019

Array[3^# - 2^(# + 1) - # 2^(# - 1) + # + 1 &, 27, 3] (* or *)
CoefficientList[Series[(-3 + 5 x)/((-1 + 3 x) (1 - 3 x + 2 x^2)^2), {x, 0, 26}], x] (* Michael De Vlieger, Jul 04 2019 *)

[3**n-2**(n+1)-n*2**(n-1)+n+1 for n in range(3,20)]

a(n) = 3^n - 2^(n+1) - n*2^(n-1) + n + 1.
G.f.: x^3*(-3 + 5*x)/((-1 + 3*x)*(1 - 3*x + 2*x^2)^2). - Michael De Vlieger, Jul 04 2019.
a(n) = 9*a(n-1) - 31*a(n-2) + 51*a(n-3) - 40*a(n-4) + 12*a(n-5) for n > 7. - Stefano Spezia, Jul 05 2019

cp's OEIS Frontend

A028859 a(n+2) = 2*a(n+1) + 2*a(n); a(0) = 1, a(1) = 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

Extensions

A008466 a(n) = 2^n - Fibonacci(n+2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A186314 Number of ternary strings of length n which contain 01.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A231430 Number of ternary sequences which contain 000.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A340156 Square array read by upward antidiagonals: T(n, k) is the number of n-ary strings of length k containing 00.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A351530 The number of quinary strings of length n containing 00.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A338230 Number of ternary strings of length n that contain at least two 0's and at most one 1.

Views

Author

Keywords

Examples

Links

Crossrefs

A028859 a(n+2) = 2a(n+1) + 2a(n); a(0) = 1, a(1) = 3.