Displaying 1-10 of 11 results found.
2, 8, 50, 344, 2402, 16808, 117650, 823544, 5764802, 40353608, 282475250, 1977326744, 13841287202, 96889010408, 678223072850, 4747561509944, 33232930569602, 232630513987208, 1628413597910450, 11398895185373144
FORMULA
a(n) = 7*a(n-1) - 6.
a(n) = 8*a(n-1) - 7*a(n-2).
G.f.: 1/(1-x) + 1/(1-7*x).
E.g.f.: exp(x) + exp(7*x). (End)
MATHEMATICA
7^Range[0, 30] +1
LinearRecurrence[{8, -7}, {2, 8}, 20] (* Harvey P. Dale, Aug 18 2018 *)
Q-residue of the (n+1)st Fibonacci polynomial, where Q is the triangular array (t(i,j)) given by t(i,j)=1. (See Comments.)
+10
19
1, 1, 3, 5, 15, 33, 91, 221, 583, 1465, 3795, 9653, 24831, 63441, 162763, 416525, 1067575, 2733673, 7003971, 17938661, 45954543, 117709185, 301527355, 772364093, 1978473511
COMMENTS
Suppose that p=p(0)*x^n+p(1)*x^(n-1)+...+p(n-1)*x+p(n) is a polynomial of positive degree and that Q is a sequence of polynomials: q(k,x)=t(k,0)*x^k+t(k,1)*x^(k-1)+...+t(k,k-1)*x+t(k,k), for k=0,1,2,... The Q-downstep of p is the polynomial given by D(p)=p(0)*q(n-1,x)+p(1)*q(n-2,x)+...+p(n-1)*q(0,x)+p(n).
Since degree(D(p))<degree(p), the result of n applications of D is a constant, which we call the Q-residue of p. If p is a constant to begin with, we define D(p)=p.
Example: let p(x)=2*x^3+3*x^2+4*x+5 and q(k,x)=(x+1)^k.
D(p)=2(x+1)^2+3(x+1)+4(1)+5=2x^2+7x+14
D(D(p))=2(x+1)+7(1)+14=2x+23
D(D(D(p)))=2(1)+23=25;
the Q-residue of p is 25.
We may regard the sequence Q of polynomials as the triangular array formed by coefficients:
t(0,0)
t(1,0)....t(1,1)
t(2,0)....t(2,1)....t(2,2)
t(3,0)....t(3,1)....t(3,2)....t(3,3)
and regard p as the vector (p(0),p(1),...,p(n)). If P is a sequence of polynomials [or triangular array having (row n)=(p(0),p(1),...,p(n))], then the Q-residues of the polynomials form a numerical sequence.
Following are examples in which Q is the triangle given by t(i,j)=1 for 0<=i<=j:
Q.....P...................Q-residue of P
1.....1................... A000079, 2^n
1....(x+1)^n.............. A007051, (1+3^n)/2
1....(x+2)^n.............. A034478, (1+5^n)/2
1....(x+3)^n.............. A034494, (1+7^n)/2
More examples:
Q...........P.............Q-residue of P
(x+1)^n...(x+1)^n......... A000110, Bell numbers
(k+1).....(k+1)........... A001906 (even-ind. Fib. nos.)
(In these last four, (k+1) represents the triangle t(n,k)=k+1, 0<=k<=n.)
Changing the notation slightly leads to the Mathematica program below and the following formulation for the Q-downstep of p: first, write t(n,k) as q(n,k). Define r(k)=Sum{q(k-1,i)*r(k-1-i) : i=0,1,...,k-1} Then row n of D(p) is given by v(n)=Sum{p(n,k)*r(n-k) : k=0,1,...,n}.
FORMULA
Conjecture: G.f.: -(1+x)*(2*x-1) / ( (x-1)*(4*x^2+x-1) ). - R. J. Mathar, Feb 19 2015
EXAMPLE
First five rows of Q, coefficients of Fibonacci polynomials ( A049310):
1
1...0
1...0...1
1...0...2...0
1...0...3...0...1
To obtain a(4)=15, downstep four times:
D(x^4+3*x^2+1)=(x^3+x^2+x+1)+3(x+1)+1: (1,1,4,5) [coefficients]
DD(x^4+3*x^2+1)=D(1,1,4,5)=(1,2,11)
DDD(x^4+3*x^2+1)=D(1,2,11)=(1,14)
DDDD(x^4+3*x^2+1)=D(1,14)=15.
MATHEMATICA
q[n_, k_] := 1;
r[0] = 1; r[k_] := Sum[q[k - 1, i] r[k - 1 - i], {i, 0, k - 1}];
f[n_, x_] := Fibonacci[n + 1, x];
p[n_, k_] := Coefficient[f[n, x], x, k]; (* A049310 *)
v[n_] := Sum[p[n, k] r[n - k], {k, 0, n}]
Table[v[n], {n, 0, 24}] (* A193649 *)
TableForm[Table[q[i, k], {i, 0, 4}, {k, 0, i}]]
Table[r[k], {k, 0, 8}] (* 2^k *)
TableForm[Table[p[n, k], {n, 0, 6}, {k, 0, n}]]
CROSSREFS
Cf. A192872 (polynomial reduction), A193091 (polynomial augmentation), A193722 (the upstep operation and fusion of polynomial sequences or triangular arrays).
T(n,k)=Number of nXk 0..3 arrays with values 0..3 introduced in row major order and no element equal to any horizontal or vertical neighbor.
+10
17
1, 1, 1, 2, 4, 2, 5, 25, 25, 5, 14, 172, 401, 172, 14, 41, 1201, 6548, 6548, 1201, 41, 122, 8404, 107042, 250031, 107042, 8404, 122, 365, 58825, 1749965, 9548295, 9548295, 1749965, 58825, 365, 1094, 411772, 28609241, 364637102, 851787199, 364637102
COMMENTS
Number of colorings of the grid graph P_n X P_k using a maximum of 4 colors up to permutation of the colors. - Andrew Howroyd, Jun 26 2017
EXAMPLE
Table starts
....1........1............2...............5..................14
....1........4...........25.............172................1201
....2.......25..........401............6548..............107042
....5......172.........6548..........250031.............9548295
...14.....1201.......107042.........9548295...........851787199
...41.....8404......1749965.......364637102.........75987485516
..122....58825.....28609241.....13925032958.......6778819400772
..365...411772....467717288....531779578441.....604736581320925
.1094..2882401...7646461682..20307996787865...53948385378521909
.3281.20176804.125007943505.775536991678112.4812720805166620356
...
Some solutions with all values from 0 to 3 for n=6 k=4
..0..1..0..1....0..1..0..1....0..1..0..1....0..1..0..1....0..1..0..1
..1..0..1..0....1..0..1..0....1..0..1..0....1..0..1..0....1..0..1..0
..0..1..2..1....0..1..0..1....0..1..0..1....0..1..0..2....0..1..0..1
..1..2..0..3....2..0..3..0....2..0..1..0....1..2..1..3....1..2..3..0
..2..0..2..0....1..3..0..2....3..2..0..2....0..3..0..2....3..1..2..3
..3..2..0..1....3..2..1..0....0..3..2..1....3..1..3..0....1..3..1..0
Expansion of exp(3*x)*cosh(3*x).
+10
13
1, 3, 18, 108, 648, 3888, 23328, 139968, 839808, 5038848, 30233088, 181398528, 1088391168, 6530347008, 39182082048, 235092492288, 1410554953728, 8463329722368, 50779978334208, 304679870005248, 1828079220031488, 10968475320188928, 65810851921133568
COMMENTS
Binomial transform of A081340. 3rd binomial transform of (1,0,9,0,81,0,729,0,...).
Number of compositions of even natural numbers in n parts <= 5. - Adi Dani, May 29 2011
FORMULA
a(0)=1, a(n) = 6^n/2, n > 0.
G.f.: (1-3*x)/(1-6*x).
E.g.f.: exp(3*x)*cosh(3*x).
a(n) = ((3+sqrt(9))^n + (3-sqrt(9))^n)/2. - Al Hakanson (hawkuu(AT)gmail.com), Dec 08 2008
a(n) = ((8*n-4)*a(n-1) - 12*(n-2)*a(n-2))/n, a(0)=1, a(1)=3.
E.g.f. (exp(6*x) + 1)/2 = 1 + 3*x/(G(0) - 6*x) where G(k) = 6*x + 1 + k - 6*x*(k+1)/G(k+1) (continued fraction, Euler's 1st kind, 1-step). (End)
EXAMPLE
a(2)=18: there are 18 compositions of even natural numbers into 2 parts <= 5:
for 0: (0,0);
for 2: (0,2),(2,0),(1,1);
for 4: (0,4),(4,0),(1,3),(3,1),(2,2);
for 6: (1,5),(5,1),(2,4),(4,2),(3,3);
for 8: (3,5),(5,3),(4,4);
for 10: (5,5). (End)
MAPLE
a:= proc(n) option remember; `if`(n=0, 1,
add(3^j*a(n-j), j=1..n))
end:
MATHEMATICA
Table[Ceiling[1/2(6^n)], {n, 0, 25}]
PROG
(PARI) x='x+O('x^66); /* that many terms */
Vec((1-3*x)/(1-6*x)) /* show terms */ /* Joerg Arndt, May 29 2011 */
T(n,k)=Number of 0..3 colorings of an nx(k+1) array circular in the k+1 direction with new values 0..3 introduced in row major order
+10
12
1, 1, 4, 4, 11, 25, 10, 111, 121, 172, 31, 670, 3502, 1331, 1201, 91, 4994, 44900, 110985, 14641, 8404, 274, 34041, 825105, 3008980, 3517864, 161051, 58825, 820, 241021, 12777541, 136579852, 201647240, 111505491, 1771561, 411772, 2461, 1678940
COMMENTS
Table starts
....1.....1.......4........10..........31............91.............274
....4....11.....111.......670........4994.........34041..........241021
...25...121....3502.....44900......825105......12777541.......214404272
..172..1331..110985...3008980...136579852....4797577911....191154162535
.1201.14641.3517864.201647240.22615881851.1801391900581.170522196557894
FORMULA
Empirical for column k:
k=1: a(n) = 8*a(n-1) -7*a(n-2)
k=2: a(n) = 11*a(n-1)
k=3: a(n) = 35*a(n-1) -107*a(n-2) +73*a(n-3)
k=4: a(n) = 68*a(n-1) -66*a(n-2)
k=5: a(n) = 200*a(n-1) -5769*a(n-2) +11744*a(n-3) +43057*a(n-4) -89856*a(n-5) +40625*a(n-6)
k=6: a(n) = 416*a(n-1) -15454*a(n-2) +89758*a(n-3) +90848*a(n-4) -438718*a(n-5) +62801*a(n-6)
k=7: (order 15)
Empirical for row n:
n=1: a(k)=3*a(k-1)+a(k-2)-3*a(k-3)
n=2: a(k)=4*a(k-1)+22*a(k-2)-4*a(k-3)-21*a(k-4)
n=3: a(k)=11*a(k-1)+123*a(k-2)-509*a(k-3)-1615*a(k-4)+7137*a(k-5)-19*a(k-6)-20571*a(k-7)+13176*a(k-8)+13932*a(k-9)-11664*a(k-10)
n=4: (order 26)
n=5: (order 71)
EXAMPLE
Some solutions for n=4 k=1
..0..1....0..1....0..1....0..1....0..1....0..1....0..1....0..1....0..1....0..1
..1..0....1..2....2..3....1..0....1..0....1..0....1..2....1..0....1..0....1..2
..0..1....0..1....3..1....0..1....2..3....2..1....3..0....0..2....2..3....3..1
..1..2....1..0....1..0....1..0....3..2....3..0....0..1....1..3....3..1....0..2
1, 5, 34, 260, 2056, 16400, 131104, 1048640, 8388736, 67109120, 536871424, 4294968320, 34359740416, 274877911040, 2199023263744, 17592186060800, 140737488388096, 1125899906908160, 9007199254872064, 72057594038190080, 576460752303947776, 4611686018428436480
COMMENTS
5th binomial transform of {1, 0, 9, 0, 81, 0, 729, 0, ...}.
FORMULA
a(n) = (8^n + 2^n)/2.
a(n) = 10*a(n-1) - 16*a(n-2), a(0)=1, a(1)=5.
G.f.: (1-5*x)/((1-2*x)*(1-8*x)).
E.g.f.: exp(5*x)*cosh(3*x).
a(n) = ((5+sqrt(9))^n + (5-sqrt(9))^n)/2. - Al Hakanson (hawkuu(AT)gmail.com), Dec 08 2008
PROG
(Sage) [(8^n + 2^n)/2 for n in (0..30)] # G. C. Greubel, Jan 08 2020
(GAP) List([0..30], n-> (8^n + 2^n)/2); # G. C. Greubel, Jan 08 2020
a(n) = 2^(n-1)*( 2^n + (-1)^n ).
+10
10
1, 1, 10, 28, 136, 496, 2080, 8128, 32896, 130816, 524800, 2096128, 8390656, 33550336, 134225920, 536854528, 2147516416, 8589869056, 34359869440, 137438691328, 549756338176, 2199022206976, 8796095119360, 35184367894528, 140737496743936, 562949936644096, 2251799847239680
COMMENTS
Binomial transform of expansion of cosh(3*x), the aerated version of A001019, 1,0,9,0,81,0,729,... - Paul Barry, Apr 05 2003
Alternatively: start with the fraction 1/1, take the numerators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 9 times the bottom to get the new top. The limit of the sequence of fractions used to generate this sequence is sqrt(9). - Cino Hilliard, Sep 25 2005
This sequence also gives the number of ordered pairs of subsets (A, B) of {1, 2, ..., n} such that |A u B| is even. (Here "u" stands for the set-theoretic union.) The special case n = 13 can be found as in CRUX Problem 3257. - Walther Janous (walther.janous(AT)tirol.com), Mar 01 2008
For n > 0, a(n) is term (1,1) in the n-th power of the 2 X 2 matrix [1,3; 3,1]. - Gary W. Adamson, Aug 06 2010
a(n) is the number of compositions of n when there are 1 type of 1 and 9 types of other natural numbers. - Milan Janjic, Aug 13 2010
a(n) = ((1+3)^n+(1-3)^n)/2. In general, if b(0),b(1),... is the k-th binomial transform of the sequence ((3^n+(-3)^n)/2), then b(n) = ((k+3)^n+(k-3)^n)/2. More generally, if b(0),b(1),... is the k-th binomial transform of the sequence ((m^n+(-m)^n)/2), then b(n) = ((k+m)^n+(k-m)^n)/2. See A034494, A081340- A081342, A034659. - Charlie Marion, Jun 25 2011
Pisano period lengths: 1, 1, 1, 1, 4, 1, 6, 1, 1, 4, 5, 1, 12, 6, 4, 1, 8, 1, 9, 4, ... - R. J. Mathar, Aug 10 2012
Starting with offset 1 the sequence is the INVERT transform of (1, 9, 9, 9, ...). - Gary W. Adamson, Aug 06 2016
REFERENCES
John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, p. 16.
M. Gardner, Riddles of Sphinx, M.A.A., 1987, p. 145.
LINKS
Bill Sands, Problem 3257, Crux Math. 33 (2007), No.5, p. 298.
FORMULA
a(n) = 2*a(n-1) + 8*a(n-2), a(0)=a(1)=1.
a(n) = (4^n + (-2)^n)/2.
G.f.: (1-x)/((1+2*x)*(1-4*x)). (End)
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k)*9^k.
E.g.f. exp(x)*cosh(3*x). (End)
Given a(0)=1, b(0)=1 then for i=1, 2, ..., a(i)/b(i) = (a(i-1) + 9*b(i-1)) / (a(i-1) + b(i-1)). - Cino Hilliard, Sep 25 2005
a(n) = ((1+sqrt(9))^n + (1-sqrt(9))^n)/2. - Al Hakanson (hawkuu(AT)gmail.com), Dec 08 2008
If p[1]=1, and p[i]=9, (i>1), and if A is 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)=det(A). - Milan Janjic, Apr 29 2010
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(9*k-1)/(x*(9*k+8) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 28 2013
MATHEMATICA
CoefficientList[Series[(1+8x)/(1-2x-8x^2), {x, 0, 30}], x] (* or *)
PROG
(PARI) a(n)=2^(n-1)*( 2^n + (-1)^n );
(Sage) [2^(n-1)*(2^n +(-1)^n) for n in (0..30)] # G. C. Greubel, Aug 02 2019
(GAP) List([0..30], n-> 2^(n-1)*(2^n +(-1)^n)); # G. C. Greubel, Aug 02 2019
T(n,k)=Number of nXk 0..5 arrays with no element equal to another within a city block distance of two, and new values 0..5 introduced in row major order
+10
7
1, 1, 1, 1, 1, 1, 2, 4, 4, 2, 5, 25, 26, 25, 5, 15, 172, 206, 206, 172, 15, 51, 1201, 1592, 1931, 1592, 1201, 51, 187, 8404, 12428, 16784, 16784, 12428, 8404, 187, 715, 58825, 96632, 151630, 170796, 151630, 96632, 58825, 715, 2795, 411772, 752552, 1343560
COMMENTS
Table starts
...1.....1......1........2.........5.........15..........51..........187
...1.....1......4.......25.......172.......1201........8404........58825
...1.....4.....26......206......1592......12428.......96632.......752552
...2....25....206.....1931.....16784.....151630.....1343560.....12046648
...5...172...1592....16784....170796....1787258....18574298....193499878
..15..1201..12428...151630...1787258...21983256...268956972...3301485294
..51..8404..96632..1343560..18574298..268956972..3889732730..56960076094
.187.58825.752552.12046648.193499878.3301485294.56960076094.998388746378
EXAMPLE
Some solutions for n=4 k=3
..0..1..2....0..1..2....0..1..2....0..1..2....0..1..2....0..1..2....0..1..2
..2..3..0....2..3..4....2..3..4....3..4..5....3..4..5....2..3..0....2..3..4
..1..4..5....1..0..5....4..5..1....5..0..1....1..0..3....4..5..1....1..5..0
..0..2..1....3..2..1....1..2..0....4..3..2....2..5..1....0..2..3....0..2..3
0, 3, 24, 171, 1200, 8403, 58824, 411771, 2882400, 20176803, 141237624, 988663371, 6920643600, 48444505203, 339111536424, 2373780754971, 16616465284800, 116315256993603, 814206798955224, 5699447592686571, 39896133148806000
COMMENTS
Number of compositions of odd natural numbers into n parts < 7. - Adi Dani, Jun 11 2011
FORMULA
a(n) = 8*a(n-1) - 7*a(n-2), n >= 2.
a(n) = right term in M^n * [1,0], where M is the 2 X 2 matrix [4,3; 3,4].
G.f.: 3*x/((1-x)*(1-7*x)).
E.g.f.: (1/2)*(exp(7*x) - exp(x)). (End)
EXAMPLE
a(2)=24: there are 24 compositions of odd numbers into 2 parts < 7:
1: (0,1), (1,0);
3: (0,3), (3,0), (1,2), (2,1);
5: (0,5), (5,0), (1,4), (4,1), (2,3), (3,2);
7: (1,6), (6,1), (2,5), (5,2), (3,4), (4,3);
9: (3,6), (6,3), (4,5), (5,4);
11: (5,6),(6,5). (End)
a(4) = 1200 = 8*a(3) - 7*a(2) = 8*171 - 7*24.
a(4) = 1200 = right term in M^n * [1,0] = [ A034494(4), a(4)] = [1201, 1200].
MATHEMATICA
Table[1/2*(7^n - 1), {n, 0, 25}]
PROG
(SageMath) [(7^n-1)/2 for n in range(31)] # G. C. Greubel, Nov 11 2022
a(n) = C(3,n) DELTA C(0,n).
+10
3
1, 1, 1, 4, 5, 1, 25, 33, 9, 1, 172, 238, 78, 13, 1, 1201, 1745, 667, 139, 17, 1, 8404, 12807, 5583, 1376, 216, 21, 1, 58825, 93841, 45822, 12950, 2429, 309, 25, 1, 411772, 686288, 370108, 117458, 25366, 3890, 418, 29, 1, 2882401, 5009889, 2951034, 1035834, 251583, 44607, 5823, 543, 33, 1
COMMENTS
Triangle [1,3,3,1,0,0,0,...] DELTA [1,0,0,0,...] with Deléham DELTA as in A084938.
FORMULA
Riordan array ((1-7x+3x^2)/(1-8x+7x^2), x(1-4x)/(1-8x+7x^2).
G.f.: (1 - 7*x + 3*x^2)/(1 - 8*x + 7*x^2 - x*y + 4*x^2*y). - Philippe Deléham , Oct 29 2013
T(n,k) = 8*T(n-1,k) + T(n-1,k-1) - 7*T(n-2,k) - 4*T(n-2,k-1), T(0,0) = T(1,0) = T(1,1) = T(2,2) = 1, T(2,0) = 4, T(2,1) = 5, T(n,k) = 0 if k > n or if k < 0. - Philippe Deléham , Oct 29 2013
EXAMPLE
Triangle begins
1;
1, 1;
4, 5, 1;
25, 33, 9, 1;
172, 238, 78, 13, 1;
MATHEMATICA
nmax=9; Flatten[CoefficientList[Series[CoefficientList[Series[(1 - 7*x + 3*x^2)/(1 - 8*x + 7*x^2 - x*y + 4*x^2*y) , {x, 0, nmax}], x], {y, 0, nmax}], y]] (* Indranil Ghosh, Mar 10 2017 *)
Search completed in 0.011 seconds
|