A172119 -id:A172119 - cp's OEIS frontend

A001949 Solutions of a fifth-order probability difference equation.

0, 0, 0, 0, 0, 1, 2, 4, 8, 16, 32, 63, 124, 244, 480, 944, 1856, 3649, 7174, 14104, 27728, 54512, 107168, 210687, 414200, 814296, 1600864, 3147216, 6187264, 12163841, 23913482, 47012668, 92424472, 181701728, 357216192, 702268543, 1380623604, 2714234540

Offset: 0

N. J. A. Sloane

This sequence is the case r = 5 in the solution to an r-th order probability difference equation that can be found in Eqs. (4) and (3) on p. 356 of Dunkel (1925). (Equation (3) follows equation (4) in the paper!) For r = 2, we get a shifted version of A000071. For r = 3, we get a shifted version of A008937. For r = 4, we get a shifted version of A107066. For r = 6, we get a shifted version of A172316. See also the table in A172119. - Petros Hadjicostas, Jun 15 2019

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
O. Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370; see pp. 356 and 369.
T. Langley, J. Liese, and J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011), Article #11.4.2.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (2,0,0,0,0,-1)

Column k = 1 of A141020 (with a different offset) and second main diagonal of A141021 (with no zeros).
Column k = 5 of A172119.
Partial sums of A001591.

A001949:=1/(z-1)/(z**5+z**4+z**3+z**2+z-1); # Simon Plouffe in his 1992 dissertation

t={0,0,0,0,0};Do[AppendTo[t,t[[-5]]+t[[-4]]+t[[-3]]+t[[-2]]+t[[-1]]+1],{n,40}];t (* Vladimir Joseph Stephan Orlovsky, Jan 21 2012 *)
LinearRecurrence[{2,0,0,0,0,-1},{0,0,0,0,0,1},40] (* Harvey P. Dale, Jan 17 2015 *)

a(n):=sum(sum((-1)^j*binomial(n-5*j-5,k-1)*binomial(n-k-5*j-4,j),j,0,(n-k-4)/5),k,1,n-4); /* Vladimir Kruchinin, Oct 19 2011 */

x='x+O('x^99); concat(vector(5), Vec(x^5/((x-1)*(x^5+x^4+x^3+x^2+x-1)))) \\ Altug Alkan, Oct 04 2017

For n >= 6, a(n+1) = 2*a(n) - a(n-5).
G.f.: x^5 / ( (x-1)*(x^5 + x^4 + x^3 + x^2 + x - 1) ).
a(n) = Sum_{k=1..n-4} Sum_{j=0..floor((n-k-4)/5)} (-1)^j*binomial(n-5*j-5, k-1)*binomial(n-k-5*j-4, j). - Vladimir Kruchinin, Oct 19 2011
4*a(n) = A000322(n+1) - 1. - R. J. Mathar, Aug 16 2017
From Petros Hadjicostas, Jun 15 2019: (Start)
a(n) = 1 + a(n-1) + a(n-2) + a(n-3) + a(n-4) + a(n-5) for n >= 5. (See Eq. (4) and the Theorem with r = 5 on p. 356 of Dunkel (1925).)
a(n) = T(n - 5, 5) for n >= 5, where T(n, k) = Sum_{j = 0..floor(n/(k+1))} (-1)^j * binomial(n - k*j, n - (k+1)*j) * 2^(n - (k+1)*j) for 0 <= k <= n. This is Richard Choulet's formula in A172119.
(End)

Name edited by Petros Hadjicostas, Jun 15 2019

A175105 Triangle T(n,k) read by rows. T(n,1)=1; T(n,k) = Sum_{i=1..k-1} ( T(n-i,k-1) + T(n-i,k) ), k>1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 10, 6, 1, 1, 5, 21, 22, 8, 1, 1, 6, 40, 64, 38, 10, 1, 1, 7, 72, 163, 140, 58, 12, 1, 1, 8, 125, 382, 442, 256, 82, 14, 1, 1, 9, 212, 846, 1259, 954, 420, 110, 16, 1, 1, 10, 354, 1800, 3334, 3166, 1794, 640, 142, 18, 1, 1, 11, 585, 3719, 8366, 9657, 6754, 3074, 924, 178, 20, 1

Offset: 1

Mats Granvik, Feb 10 2010

Are there closed forms for diagonals and columns?
With the definition of the array, I note that the sequence (phi(k)) (phi(k)= g.f. of the column number k) is given by the recurrence relation: phi(k+1)=phi(k)*(1-z^k)/(1-2*z+z^(k+1)). The consequence is: the sequence number k+1 column is the convolution of the k-one and a "-acci like" sequence whose g.f. is given by (1-z^k)/(1-2*z+z^(k+1)). E.g., the 2-column is the convolution of the 1-column and the sequence 1, 2, 3, 5, ... classical Fibonacci sequence without the first 1. The 3-column is the convolution of the 2-column and 1, 2, 4, 7, 13, ... tribonacci like-sequence (exactly: A000073 without beginning 0, 0, 1). - Richard Choulet, Feb 19 2010
Relation to metallic means:
T(n,1)=1, k>1: T(n,k) = Sum_{i=1..k-1} T(n-i,k-1) + 0*Sum_{i=1..k-1} T(n-i,k)
has antidiagonal sums for which the limiting ratio tends to the golden ratio, A001622.
T(n,1)=1, k>1: T(n,k) = Sum_{i=1..k-1} T(n-i,k-1) + 1*Sum_{i=1..k-1} T(n-i,k)
has antidiagonal sums for which the limiting ratio tends to the silver ratio, A014176.
T(n,1)=1, k>1: T(n,k) = Sum_{i=1..k-1} T(n-i,k-1) + 2*Sum_{i=1..k-1} T(n-i,k)
has antidiagonal sums for which the limiting ratio tends to the bronze ratio, A098316.
A similar point can be made about variations of the Pascal triangle.

			Table begins:
  n/k| 1    2    3    4    5    6    7    8    9   10   11
  ---+-----------------------------------------------------
   1 | 1
   2 | 1    1
   3 | 1    2    1
   4 | 1    3    4    1
   5 | 1    4   10    6    1
   6 | 1    5   21   22    8    1
   7 | 1    6   40   64   38   10    1
   8 | 1    7   72  163  140   58   12    1
   9 | 1    8  125  382  442  256   82   14    1
  10 | 1    9  212  846 1259  954  420  110   16    1
  11 | 1   10  354 1800 3334 3166 1794  640  142   18    1
Example: T(8,4) = 163 because it is the sum of the numbers:
  10    6
  21   22
  40   64
For k=1, we obtain phi(k)(z)=1/(1-z) which is clear; for k=2, we obtain phi(k)(z)=1/(1-z)^2. For k=3, we obtain phi(3)(z)=(1+z)/((1-2*z+z^3)*(1-z)); this is A001891 without the beginning zero. - _Richard Choulet_, Feb 19 2010

Wikipedia, Metallic mean

Cf. A172119, A051731, A001891 (column k=3), A176084 (row sums).
(1-((-1)^T(n, k)))/2 = T(n, k) mod 2 = A051731.
Cf. A179807=antidiagonal sums. A179748 has simpler recurrence.

=if(column()=1;1;if(row()>=column();sum(indirect(address(row()-column()+1;column()-1;4)&":"&address(row()-column()+column()-1;column()-1;4);4))+sum(indirect(address(row()-column()+1;column();4)&":"&address(row()-column()+column()-1;column();4);4));0)) ' Mats Granvik, Mar 28 2010

A175105 := proc(n,k) if k =1 then 1; elif k > n or k< 1 then 0 ; else    add(procname(n-i,k-1)+procname(n-i,k),i=1..k-1) ; end if; end proc; # R. J. Mathar, Feb 16 2011

T[_, 1] = 1;
T[n_, k_] /; 1, ] = 0;
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 19 2019 *)

The g.f of the number k column is phi(k)(z) = (1/(1-z))*Product_{i=1..k-1}(1-z^i)/(1-2*z+z^(i+1)). - Richard Choulet, Feb 19 2010

Corrected and edited by Mats Granvik, Jul 28 2010, Dec 09 2010

Choulet formulas indices shifted (to adapt to the new column index) by R. J. Mathar, Dec 13 2010

A144428 Square array read by ascending antidiagonals. A(L, n) is a table of sequences representing the number of valid nodes in level n of a labeled binary tree when the labeling rule forbids 1 of the 2^L states given by the last L digits of the parent label.

Original entry on oeis.org

2, 2, 3, 2, 4, 5, 2, 4, 7, 8, 2, 4, 8, 13, 13, 2, 4, 8, 15, 24, 21, 2, 4, 8, 16, 29, 44, 34, 2, 4, 8, 16, 31, 56, 81, 55, 2, 4, 8, 16, 32, 61, 108, 149, 89, 2, 4, 8, 16, 32, 63, 120, 208, 274, 144, 2, 4, 8, 16, 32, 64, 125, 236, 401, 504, 233, 2, 4, 8, 16, 32, 64, 127, 248, 464, 773, 927, 377, 2, 4, 8, 16, 32, 64, 128, 253

Offset: 1

Ross Drewe, Oct 06 2008

A complete labeled binary tree has the root as level 0, 2 nodes at level 1 (each labeled with one of the available symbols 1,2) and 2^n nodes at level n (each labeled with a unique n-digit sequence). The tree can be constructed by adopting a rule that at each successive level, each child node forms its label by adding one symbol to the parent's label.
An incomplete tree can be created by forbidding certain child nodes, using on a state-driven rule. If the state of a node is the last L digits of its label, there are 2^L possible states. Let a(L,n) be the single value denoting the number of valid nodes in level n after applying any given rule and A(L,n) is the sequence of values a(L,2), a(L,3), ..., a(L,n).
Assume this rule: for a given L, all of the 2^L states permit the usual dichotomous branching, except for one state which restricts the output to a single child node. The forbidden child of the pair has a label with the same last digit as the parent state.
This rule creates a set of sequences { A(L,n) } which are essentially the same as the standard "n-step Fibonacci" or "n-anacci" sequences. These can be displayed as the rows of a rectangular array in order of increasing L:
2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, ...
2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, ...
2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, ...
2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, ...
2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, ...
2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, ...
Taking the antidiagonals of this table gives the present entry F(n).
Comparison with the standard n-anacci sequences:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, ...
0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, ...
0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, ...
0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, ...
0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, ...
0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, ...
shows that the A(L,n) sequences differ only in the absence of the L+2 start-up values. This is an artifact of the construction method, since a(L,n) is undefined when labels are too short to contain a state sequence - i.e., for all nodes in levels < L.
This method of construction can be generalized (see link) which shows that the output from simple rule definitions is rich in well-known sequences.
From Petros Hadjicostas, Jul 26 2019: (Start)
The author of this array uses F(n) to denote the n-th term of the flattened table (for n >= 1). In addition, it seems that the author uses A(L,n) to denote the term in the L-th row and n-th column of the table. Clearly, L >= 2, but it is not clear whether n starts at 1 or at 2. Thus, in my comments and formulas below I use m to index the columns and start m at 1.
Let A(L, m) be the term in level (row) L and column m, where L >= 2 and m >= 1. Here L is the order of generalized Fibonacci sequence.
We have A(L, m) = 2^m for m = 1,...,L-1, and A(L, L) = 2^L - 1. Also,
A(L, m) = A(L, m-1) + A(L, m-2) + ... + A(L, m-L) for m >= L + 1.
Letting F(n) be the n-th term in the author's sequence (flattened table), we get F((k-1)*(k-2)/2 + i) = A(k-i+1, i) for k >= 2 and i = 1..k-1.
(End)

S. Christensen, Generalized Fibonacci numbers and Blackwell's renewal theorem, arXiv:1012.5006 [math.PR], 2010.
S. Christensen, Generalized Fibonacci numbers and Blackwell's renewal theorem, Statist. Probab. Lett. 82 (2012), 1665-1668.
Ross Drewe, On a generalization of F(n).
O. Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
Wikipedia, Fibonacci number.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

Cf. A172119.

From Petros Hadjicostas, Jul 26 2019: (Start)
Let A(L, m) be the term in level (row) L and column m, where L >= 2 and m >= 1. Then A(L, m) = 2^m for m = 1,...,L-1; A(L, L) = 2^L - 1; and A(L, m) = S(L, m) - S(L, m-L) for m >= L + 1, where
S(L, m) = Sum_{j = 0..floor(m/(L+1))} (-1)^j * binomial(m-L*j, m - (L+1)*j) * 2^(m - (L+1)*j). (See the formula by Richard Choulet for array A172119. It can also be found in Dunkel (1925).)
G.f. for row L >= 2: -1 + (1 - z^L)/(1 - 2*z + z^(L+1)).
(End)

Name clarified by Petros Hadjicostas, Jul 26 2019

More terms from Petros Hadjicostas, Jul 26 2019

A173034 Sequence whose G.f is f such that: f(z)=8/(1-2*z)-12/(1-z)+z+5.

Original entry on oeis.org

1, 5, 20, 52, 116, 244, 500, 1012, 2036, 4084, 8180, 16372, 32756, 65524, 131060, 262132, 524276, 1048564, 2097140, 4194292, 8388596, 16777204, 33554420, 67108852, 134217716, 268435444, 536870900, 1073741812, 2147483636

Offset: 0

Richard Choulet, Feb 07 2010

The Granvik array of A172119 is here written in "square": 1 :: 1 :: 1 :: 1 :: 1 :: 1 :: 1 :: 1 :: 1 :: 1 // 1 :: 2 :: 2 :: 2 :: 2 :: 2 :: 2 :: 2 :: 2 :: 2 // 1 :: 3 :: 4 :: 4 :: 4 :: 4 :: 4 :: 4 :: 4 :: 4 // 1 :: 4 :: 7 :: 8 :: 8 :: 8 :: 8 :: 8 :: 8 :: 8 // This sequence gives the third diagonal under the main diagonal.

			From 1 + 5*z + 20*z^2 + 52*z^3 + 116*z^4 + 244*z^5 + 500*z^6 + O(z^7) we get a(6)=500.

Index entries for linear recurrences with constant coefficients, signature (3,-2)

Cf. A172119, A173033.

a(n) = 8*2^n-12, n>=2. - R. J. Mathar, Apr 20 2011

cp's OEIS Frontend

A001949 Solutions of a fifth-order probability difference equation.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A175105 Triangle T(n,k) read by rows. T(n,1)=1; T(n,k) = Sum_{i=1..k-1} ( T(n-i,k-1) + T(n-i,k) ), k>1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Excel

Maple

Mathematica

Formula

Extensions

A144428 Square array read by ascending antidiagonals. A(L, n) is a table of sequences representing the number of valid nodes in level n of a labeled binary tree when the labeling rule forbids 1 of the 2^L states given by the last L digits of the parent label.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A173034 Sequence whose G.f is f such that: f(z)=8/(1-2*z)-12/(1-z)+z+5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula