Displaying 1-10 of 34 results found.
Symmetric square array, read by antidiagonals, where the inverse binomial transform of row n equals: [C(n,0)*1, C(n,1)*2,..., C(n,k)* A051163(k), ..., C(n,n)* A051163(n)] and where A051162 equals the antidiagonal sums.
+20
3
1, 1, 1, 1, 3, 1, 1, 5, 5, 1, 1, 7, 14, 7, 1, 1, 9, 28, 28, 9, 1, 1, 11, 47, 76, 47, 11, 1, 1, 13, 71, 163, 163, 71, 13, 1, 1, 15, 100, 301, 435, 301, 100, 15, 1, 1, 17, 134, 502, 971, 971, 502, 134, 17, 1, 1, 19, 173, 778, 1909, 2577, 1909, 778, 173, 19, 1, 1, 21, 217, 1141
FORMULA
T(n, k) = Sum_{j=0..n} C(k, j)*C(n, j)* A051162(j), with T(0, 0) = 1 and where Sum_{i=0..n} T(n-i, i) = A051162(n).
EXAMPLE
Rows begin:
[1,1,1,1,1,1,1,1,1,...],
[1,3,5,7,9,11,13,15,17,...],
[1,5,14,28,47,71,100,134,...],
[1,7,28,76,163,301,502,778,...],
[1,9,47,163,435,971,1909,3417,...],
[1,11,71,301,971,2577,5917,12167,...],
[1,13,100,502,1909,5917,15678,36744,...],
[1,15,134,778,3417,12167,36744,97272,...],...
Antidiagonal sums form A051163: [1,2,5,12,30,76,194,496,1269,3250,8337,...]. The inverse binomial transform of the rows form the respective rows of the triangle B:
[1*1],
[1*1,1*2],
[1*1,2*2,1*5],
[1*1,3*2,3*5,1*12],
[1*1,4*2,6*5,4*12,1*30],...
where B(n,k) = binomial(n,k)* A051163(k).
PROG
(PARI) T(n, k)=if(n==0 || k==0, 1, sum(j=0, n, binomial(k, j)*binomial(n, j)*sum(i=0, j, T(j-i, i))); )
Q-residue of the triangle A051162, where Q is the triangular array (t(i,j)) given by t(i,j)=1. (See Comments.)
+20
2
1, 1, 3, 15, 83, 503, 3403, 25807, 218451, 2049687, 21160667, 238690847, 2923054435, 38641535143, 548635554795, 8328494925615, 134634766604915, 2309386642312631, 41897258229334267, 801610384425038911, 16132033041827096451
COMMENTS
For the definition of Q-residue, see A193649.
FORMULA
Conjecture: a(n) +(-n-4)*a(n-1) +(4*n-1)*a(n-2) +5*(-n+2)*a(n-3) +2*(n-3)*a(n-4)=0. - R. J. Mathar, Feb 19 2015
MATHEMATICA
r[0] = 1; r[k_] := Sum[q[k - 1, i] r[k - 1 - i], {i, 0, k - 1}]
p[n_, k_] := n!/(k! (n - k)!);
v[n_] := Sum[p[n, k] r[n - k], {k, 0, n}]
Table[v[n], {n, 0, 20}] (* A193658 *) TableForm[Table[q[i, k], {i, 0, 4}, {k, 0, i}]]
Table[r[k], {k, 0, 20}] (* A001340 *) TableForm[Table[p[n, k], {n, 0, 4}, {k, 0, n}]]
Expansion of Product_{m >= 1} (1 + x^m); number of partitions of n into distinct parts; number of partitions of n into odd parts.
(Formerly M0281 N0100)
+10
1785
1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296, 340, 390, 448, 512, 585, 668, 760, 864, 982, 1113, 1260, 1426, 1610, 1816, 2048, 2304, 2590, 2910, 3264, 3658, 4097, 4582, 5120, 5718, 6378
COMMENTS
Partitions into distinct parts are sometimes called "strict partitions".
The result that number of partitions of n into distinct parts = number of partitions of n into odd parts is due to Euler.
Bijection: given n = L1* 1 + L2*3 + L3*5 + L7*7 + ..., a partition into odd parts, write each Li in binary, Li = 2^a1 + 2^a2 + 2^a3 + ... where the aj's are all different, then expand n = (2^a1 * 1 + ...)*1 + ... by removing the brackets and we get a partition into distinct parts. For the reverse operation, just keep splitting any even number into halves until no evens remain.
Euler transform of period 2 sequence [1,0,1,0,...]. - Michael Somos, Dec 16 2002 Number of different partial sums 1+[1,2]+[1,3]+[1,4]+..., where [1,x] indicates a choice. E.g., a(6)=4, as we can write 1+1+1+1+1+1, 1+2+3, 1+2+1+1+1, 1+1+3+1. - Jon Perry, Dec 31 2003 a(n) is the sum of the number of partitions of x_j into at most j parts, where j is the index for the j-th triangular number and n-T(j)=x_j. For example; a(12)=partitions into <= 4 parts of 12-T(4)=2 + partitions into <= 3 parts of 12-T(3)=6 + partitions into <= 2 parts of 12-T(2)=9 + partitions into 1 part of 12-T(1)=11 = (2)(11) + (6)(51)(42)(411)(33)(321)(222) + (9)(81)(72)(63)(54)+(11) = 2+7+5+1 = 15. - Jon Perry, Jan 13 2004 Number of partitions of n where if k is the largest part, all parts 1..k are present. - Jon Perry, Sep 21 2005 Jack Grahl and Franklin T. Adams-Watters prove this claim of Jon Perry's by observing that the Ferrers dual of a "gapless" partition is guaranteed to have distinct parts; since the Ferrers dual is an involution, this establishes a bijection between the two sets of partitions. - Allan C. Wechsler, Sep 28 2021 The number of connected threshold graphs having n edges. - Michael D. Barrus (mbarrus2(AT)uiuc.edu), Jul 12 2007
Starting with offset 1 = row sums of triangle A146061 and the INVERT transform of A000700 starting: (1, 0, 1, -1, 1, -1, 1, -2, 2, -2, 2, -3, 3, -3, 4, -5, ...). - Gary W. Adamson, Oct 26 2008 Number of partitions of n in which the largest part occurs an odd number of times and all other parts occur an even number of times. (Such partitions are the duals of the partitions with odd parts.) - David Wasserman, Mar 04 2009 Considering all partitions of n into distinct parts: there are A140207(n) partitions of maximal size which is A003056(n), and A051162(n) is the greatest number occurring in these partitions. - Reinhard Zumkeller, Jun 13 2009 Number of symmetric unimodal compositions of n+1 where the maximal part appears once. Also number of symmetric unimodal compositions of n where the maximal part appears an odd number of times. - Joerg Arndt, Jun 11 2013 Because for these partitions the exponents of the parts 1, 2, ... are either 0 or 1 (j^0 meaning that part j is absent) one could call these partitions also 'fermionic partitions'. The parts are the levels, that is the positive integers, and the occupation number is either 0 or 1 (like Pauli's exclusion principle). The 'fermionic states' are denoted by these partitions of n. - Wolfdieter Lang, May 14 2014 The set of partitions containing only odd parts forms a monoid under the product described in comments to A047993. - Richard Locke Peterson, Aug 16 2018 a(n) equals the number of permutations p of the set {1,2,...,n+1}, written in one line notation as p = p_1p_2...p_(n+1), satisfying p_(i+1) - p_i <= 1 for 1 <= i <= n, (i.e., those permutations that, when read from left to right, never increase by more than 1) whose major index maj(p) := Sum_{p_i > p_(i+1)} i equals n. For example, of the 16 permutations on 5 letters satisfying p_(i+1) - p_i <= 1, 1 <= i <= 4, there are exactly two permutations whose major index is 4, namely, 5 3 4 1 2 and 2 3 4 5 1. Hence a(4) = 2. See the Bala link in A007318 for a proof. - Peter Bala, Mar 30 2022 Conjecture: Each positive integer n can be written as a_1 + ... + a_k, where a_1,...,a_k are strict partition numbers (i.e., terms of the current sequence) with no one dividing another. This has been verified for n = 1..1350. - Zhi-Wei Sun, Apr 14 2023 Conjecture: For each integer n > 7, a(n) divides none of p(n), p(n) - 1 and p(n) + 1, where p(n) is the number of partitions of n given by A000041. This has been verified for n up to 10^5. - Zhi-Wei Sun, May 20 2023 [Verified for n <= 2*10^6. - Vaclav Kotesovec, May 23 2023] The g.f. Product_{k >= 0} 1 + x^k = Product_{k >= 0} 1 - x^k + 2*x^k == Product_{k >= 0} 1 - x^k == Sum_{k in Z} (-1)^k*x^(k*(3*k-1)/2) (mod 2) by Euler's pentagonal number theorem. It follows that a(n) is odd iff n = k*(3*k - 1)/2 for some integer k, i.e., iff n is a generalized pentagonal number A001318. - Peter Bala, Jan 07 2025 The 2023 New Zealand Mathematical Olympiad, Round Two, Problem 4, asks whether there are infinitely many positive integers m such that a(m) = a(m+1). In fact, a(n) = a(n+1) iff n = 0, 1, 3, while a(n) < a(n+1) for every n >= 4. See the official problem and solution in link. - Bernard Schott, Oct 08 2026
REFERENCES
George E. Andrews, The Theory of Partitions, Cambridge University Press, 1998, p. 19.
George E. Andrews, Number Theory, Dover Publications, 1994, Theorem 12-3, pp. 154-5, and (13-1-1) p. 163.
Raymond Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; see p. 196.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education, Vol. 31, No. 1, pp. 24-28, Winter 1997. MathEduc Database (Zentralblatt MATH, 1997c.01891).
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17. Zentralblatt MATH, Zbl 1071.05501.
T. J. I'a. Bromwich, Introduction to the Theory of Infinite Series, Macmillan, 2nd. ed. 1949, p. 116, Problem 18.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 99.
William Dunham, The Mathematical Universe, pp. 57-62, J. Wiley, 1994.
Leonhard Euler, De partitione numerorum, Novi commentarii academiae scientiarum Petropolitanae 3 (1750/1), 1753, reprinted in: Commentationes Arithmeticae. (Opera Omnia. Series Prima: Opera Mathematica, Volumen Secundum), 1915, Lipsiae et Berolini, 254-294.
Ian P. Goulden and David M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (2.5.1).
G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, p. 86.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 277, Theorems 344, 346.
Carlos J. Moreno and Samuel S. Wagstaff, Jr., Sums of Squares of Integers, Chapman and Hall, 2006, p. 253.
Srinivasa Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962. See Table V on page 309.
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).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 288-290.
LINKS
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009; see pages 48 and 499. James Mc Laughlin, Andrew V. Sills, and Peter Zimmer, Rogers-Ramanujan-Slater Type Identities, Electronic J. Combinatorics, DS15, 1-59, May 31, 2008; see also arXiv version, arXiv:1901.00946 [math.NT], 2019. Donald J. Newman, A Problem Seminar, pp. 18;93;102-3 Prob. 93 Springer-Verlag NY 1982.
FORMULA
G.f.: Product_{m>=1} (1 + x^m) = 1/Product_{m>=0} (1-x^(2m+1)) = Sum_{k>=0} Product_{i=1..k} x^i/(1-x^i) = Sum_{n>=0} x^(n*(n+1)/2) / Product_{k=1..n} (1-x^k).
G.f.: Sum_{n>=0} x^n*Product_{k=1..n-1} (1+x^k) = 1 + Sum_{n>=1} x^n*Product_{k>=n+1} (1+x^k). - Joerg Arndt, Jan 29 2011 Product_{k>=1} (1+x^(2k)) = Sum_{k>=0} x^(k*(k+1))/Product_{i=1..k} (1-x^(2i)) - Euler (Hardy and Wright, Theorem 346).
Asymptotics: a(n) ~ exp(Pi l_n / sqrt(3)) / ( 4 3^(1/4) l_n^(3/2) ) where l_n = (n-1/24)^(1/2) (Ayoub).
For n > 1, a(n) = (1/n)*Sum_{k=1..n} b(k)*a(n-k), with a(0)=1, b(n) = A000593(n) = sum of odd divisors of n; cf. A000700. - Vladeta Jovovic, Jan 21 2002 a(n) = t(n, 0), t as defined in A079211. Expansion of 1 / chi(-x) = chi(x) / chi(-x^2) = f(-x) / phi(x) = f(x) / phi(-x^2) = psi(x) / f(-x^2) = f(-x^2) / f(-x) = f(-x^4) / psi(-x) in powers of x where phi(), psi(), chi(), f() are Ramanujan theta functions. - Michael Somos, Mar 12 2011 G.f. is a period 1 Fourier series which satisfies f(-1 / (1152 t)) = 2^(-1/2) / f(t) where q = exp(2 Pi i t). - Michael Somos, Aug 16 2007 Expansion of q^(-1/24) * eta(q^2) / eta(q) in powers of q.
Expansion of q^(-1/24) 2^(-1/2) f2(t) in powers of q = exp(2 Pi i t) where f2() is a Weber function. - Michael Somos, Oct 18 2007 Given g.f. A(x), then B(x) = x * A(x^3)^8 satisfies 0 = f(B(x), B(x^2)) where f(u, v) = v - u^2 + 16*u*v^2. - Michael Somos, May 31 2005 Given g.f. A(x), then B(x) = x * A(x^8)^3 satisfies 0 = f(B(x), B(x^3)) where f(u, v) = (u^3 - v) * (u + v^3) - 9 * u^3 * v^3. - Michael Somos, Mar 25 2008 From Evangelos Georgiadis, Andrew V. Sutherland, Kiran S. Kedlaya (egeorg(AT)mit.edu), Mar 03 2009: (Start)
a(0)=1; a(n) = 2*(Sum_{k=1..floor(sqrt(n))} (-1)^(k+1) a(n-k^2)) + sigma(n) where sigma(n) = (-1)^j if (n=(j*(3*j+1))/2 OR n=(j*(3*j-1))/2) otherwise sigma(n)=0 (simpler: sigma = A010815). (End) The product g.f. = (1/(1-x))*(1/(1-x^3))*(1/(1-x^5))*...; = (1,1,1,...)*
(1,0,0,1,0,0,1,0,0,1,...)*(1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,...) * ...; =
a*b*c*... where a, a*b, a*b*c, ... converge to A000009: 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ... = a*b
1, 1, 1, 2, 2, 3, 4, 4, 5, 6, ... = a*b*c
1, 1, 1, 2, 2, 3, 4, 5, 6, 7, ... = a*b*c*d
1, 1, 1, 2, 2, 3, 4, 5, 6, 8, ... = a*b*c*d*e
1, 1, 1, 2, 2, 3, 4, 5, 6, 8, ... = a*b*c*d*e*f
... (cf. analogous example in A000041). (End) a(n) = P(n) - P(n-2) - P(n-4) + P(n-10) + P(n-14) + ... + (-1)^m P(n-2p_m) + ..., where P(n) is the partition function ( A000041) and p_m = m(3m-1)/2 is the m-th generalized pentagonal number ( A001318). - Jerome Malenfant, Feb 16 2011 G.f.: 1/2 (-1; x)_{inf} where (a; q)_k is the q-Pochhammer symbol. - Vladimir Reshetnikov, Apr 24 2013 More precise asymptotics: a(n) ~ exp(Pi*sqrt((n-1/24)/3)) / (4*3^(1/4)*(n-1/24)^(3/4)) * (1 + (Pi^2-27)/(24*Pi*sqrt(3*(n-1/24))) + (Pi^4-270*Pi^2-1215)/(3456*Pi^2*(n-1/24))). - Vaclav Kotesovec, Nov 30 2015 a(n) ~ exp(Pi*sqrt(n/3))/(4*3^(1/4)*n^(3/4)) * (1 + (Pi/(48*sqrt(3)) - (3*sqrt(3))/(8*Pi))/sqrt(n) + (Pi^2/13824 - 5/128 - 45/(128*Pi^2))/n).
a(n) ~ exp(Pi*sqrt(n/3) + (Pi/(48*sqrt(3)) - 3*sqrt(3)/(8*Pi))/sqrt(n) - (1/32 + 9/(16*Pi^2))/n) / (4*3^(1/4)*n^(3/4)).
(End)
a(n) ~ Pi*BesselI(1, Pi*sqrt((n+1/24)/3)) / sqrt(24*n+1). - Vaclav Kotesovec, Nov 08 2016 G.f.: (1 + x)*Sum_{n >= 0} x^(n*(n+3)/2)/Product_{k = 1..n} (1 - x^k) =
(1 + x)*(1 + x^2)*Sum_{n >= 0} x^(n*(n+5)/2)/Product_{k = 1..n} (1 - x^k) = (1 + x)*(1 + x^2)*(1 + x^3)*Sum_{n >= 0} x^(n*(n+7)/2)/Product_{k = 1..n} (1 - x^k) = ....
G.f.: (1/2)*Sum_{n >= 0} x^(n*(n-1)/2)/Product_{k = 1..n} (1 - x^k) =
(1/2)*(1/(1 + x))*Sum_{n >= 0} x^((n-1)*(n-2)/2)/Product_{k = 1..n} (1 - x^k) = (1/2)*(1/((1 + x)*(1 + x^2)))*Sum_{n >= 0} x^((n-2)*(n-3)/2)/Product_{k = 1..n} (1 - x^k) = ....
G.f.: Sum_{n >= 0} x^n/Product_{k = 1..n} (1 - x^(2*k)) = (1/(1 - x)) * Sum_{n >= 0} x^(3*n)/Product_{k = 1..n} (1 - x^(2*k)) = (1/((1 - x)*(1 - x^3))) * Sum_{n >= 0} x^(5*n)/Product_{k = 1..n} (1 - x^(2*k)) = (1/((1 - x)*(1 - x^3)*(1 - x^5))) * Sum_{n >= 0} x^(7*n)/Product_{k = 1..n} (1 - x^(2*k)) = .... (End)
G.f.: A(x) = Sum_{n >= 0} x^(n*(2*n-1))/Product_{k = 1..2*n} (1 - x^k). (Set z = x and q = x^2 in Mc Laughlin et al. (2019 ArXiv version), Section 1.3, Identity 7.)
Similarly, A(x) = Sum_{n >= 0} x^(n*(2*n+1))/Product_{k = 1..2*n+1} (1 - x^k). (End)
G.f.: A(x) = exp ( Sum_{n >= 1} x^n/(n*(1 - x^(2*n))) ) = exp ( Sum_{n >= 1} (-1)^(n+1)*x^n/(n*(1 - x^n)) ). - Peter Bala, Dec 23 2021 Sum_{n>=0} a(n)/exp(Pi*n) = exp(Pi/24)/2^(1/8) = A292820. - Simon Plouffe, May 12 2023 [Proof: Sum_{n>=0} a(n)/exp(Pi*n) = phi(exp(-2*Pi)) / phi(exp(-Pi)), where phi(q) is the Euler modular function. We have phi(exp(-2*Pi)) = exp(Pi/12) * Gamma(1/4) / (2 * Pi^(3/4)) and phi(exp(-Pi)) = exp(Pi/24) * Gamma(1/4) / (2^(7/8) * Pi^(3/4)), see formulas (14) and (13) in I. Mező, 2013. - Vaclav Kotesovec, May 12 2023] a(2*n) = Sum_{j=1..n} p(n+j, 2*j) and a(2*n+1) = Sum_{j=1..n+1} p(n+j,2*j-1), where p(n, s) is the number of partitions of n having exactly s parts. - Gregory L. Simay, Aug 30 2023
EXAMPLE
G.f. = 1 + x + x^2 + 2*x^3 + 2*x^4 + 3*x^5 + 4*x^6 + 5*x^7 + 6*x^8 + 8*x^9 + ...
G.f. = q + q^25 + q^49 + 2*q^73 + 2*q^97 + 3*q^121 + 4*q^145 + 5*q^169 + ...
The partitions of n into distinct parts (see A118457) for small n are: 1: 1
2: 2
3: 3, 21
4: 4, 31
5: 5, 41, 32
6: 6, 51, 42, 321
7: 7, 61, 52, 43, 421
8: 8, 71, 62, 53, 521, 431
...
MAPLE
N := 100; t1 := series(mul(1+x^k, k=1..N), x, N); A000009 := proc(n) coeff(t1, x, n); end; # Alternative:
spec := [ P, {P=PowerSet(N), N=Sequence(Z, card>=1)} ]: [ seq(combstruct[count](spec, size=n), n=0..58) ];
# Alternative:
spec := [ P, {P=PowerSet(N), N=Sequence(Z, card>=1)} ]: combstruct[allstructs](spec, size=10); # to get the actual partitions for n=10
# Alternative:
local x, m;
product(1+x^m, m=1..n+1) ;
expand(%) ;
coeff(%, x, n) ;
# Alternative:
lim := 99; # Enlarge if more terms are needed.
simplify(expand(QDifferenceEquations:-QPochhammer(-1, x, lim)/2, x)):
# Alternative:
a:= proc(n) option remember; `if`(n=0, 1, add(a(n-j)*add(
`if`(d::odd, d, 0), d=numtheory[divisors](j)), j=1..n)/n)
end:
# Alternative:
f := proc(i) option remember; local d;
add(`if`(irem(d, 2) = 1, d, 0), d in NumberTheory:-Divisors(i))
end proc:
A000009 := proc(n) option remember; local i;
`if`(n = 0, 1, add( A000009(n - i)*f(i), i = 1 .. n)/n) end proc:
MATHEMATICA
PartitionsQ[Range[0, 60]] (* _Harvey Dale_, Jul 27 2009 *)
(* Alternative: *)
a[ n_] := SeriesCoefficient[ Product[ 1 + x^k, {k, n}], {x, 0, n}]; (* Michael Somos, Jul 06 2011 *) (* Alternative: *)
a[ n_] := SeriesCoefficient[ 1 / Product[ 1 - x^k, {k, 1, n, 2}], {x, 0, n}]; (* Michael Somos, Jul 06 2011 *) (* Alternative: *)
a[ n_] := With[ {t = Log[q] / (2 Pi I)}, SeriesCoefficient[ q^(-1/24) DedekindEta[2 t] / DedekindEta[ t], {q, 0, n}]]; (* Michael Somos, Jul 06 2011 *) (* Alternative: *)
a[ n_] := SeriesCoefficient[ 1 / QPochhammer[ x, x^2], {x, 0, n}]; (* Michael Somos, May 24 2013 *) (* Alternative: *)
a[ n_] := SeriesCoefficient[ Series[ QHypergeometricPFQ[ {q}, {q x}, q, - q x], {q, 0, n}] /. x -> 1, {q, 0, n}]; (* Michael Somos, Mar 04 2014 *) (* Alternative: *)
a[ n_] := SeriesCoefficient[ QHypergeometricPFQ[{}, {}, q, -1] / 2, {q, 0, n}]; (* Michael Somos, Mar 04 2014 *) (* Alternative: *)
nmax = 60; CoefficientList[Series[Exp[Sum[(-1)^(k+1)/k*x^k/(1-x^k), {k, 1, nmax}]], {x, 0, nmax}], x] (* Vaclav Kotesovec, Aug 25 2015 *) (* Alternative: *)
nmax = 100; poly = ConstantArray[0, nmax + 1]; poly[[1]] = 1; poly[[2]] = 1; Do[Do[poly[[j + 1]] += poly[[j - k + 1]], {j, nmax, k, -1}]; , {k, 2, nmax}]; poly (* Vaclav Kotesovec, Jan 14 2017 *)
PROG
(PARI) {a(n) = if( n<0, 0, polcoeff( prod( k=1, n, 1 + x^k, 1 + x * O(x^n)), n))}; /* Michael Somos, Nov 17 1999 */ (PARI) {a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( eta(x^2 + A) / eta(x + A), n))};
(PARI) {a(n) = my(c); forpart(p=n, if( n<1 || p[1]<2, c++; for(i=1, #p-1, if( p[i+1] > p[i]+1, c--; break)))); c}; /* Michael Somos, Aug 13 2017 */ (PARI) lista(nn) = {q='q+O('q^nn); Vec(eta(q^2)/eta(q))} \\ Altug Alkan, Mar 20 2018 (Magma) Coefficients(&*[1+x^m:m in [1..100]])[1..100] where x is PolynomialRing(Integers()).1; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
(Haskell)
import Data.MemoCombinators (memo2, integral)
a000009 n = a000009_list !! n
a000009_list = map (pM 1) [0..] where
pM = memo2 integral integral p
p _ 0 = 1
p k m | m < k = 0
| otherwise = pM (k + 1) (m - k) + pM (k + 1) m
(Maxima)
h(n):=if oddp(n)=true then 1 else 0;
S(n, m):=if n=0 then 1 else if n<m then 0 else if n=m then h(n) else sum(h(k)*S(n-k, k), k, m, n/2)+h(n);
(SageMath) # uses[EulerTransform from A166861] a = BinaryRecurrenceSequence(0, 1)
b = EulerTransform(a)
from functools import lru_cache
from math import isqrt
@lru_cache(maxsize=None)
(Python)
import numpy as np
n = 1000
arr = np.zeros(n, dtype=object)
arr[0] = 1
for i in range(1, n):
arr[i:] += arr[:n-i]
using Memoize
n == 0 && return 1
s = sum((-1)^k* A000009(n - k^2) for k in 1:isqrt(n))
CROSSREFS
Apart from the first term, equals A052839-1. The rows of A053632 converge to this sequence. When reduced modulo 2 equals the absolute values of A010815. The positions of odd terms given by A001318. a(n) = Sum_{n=1..m} A097306(n, m), row sums of triangle of number of partitions of n into m odd parts. Cf. A001318, A000041, A000700, A003724, A004111, A007837, A010815, A035294, A068049, A078408, A081360, A088670, A109950, A109968, A132312, A146061, A035363, A010054, A057077, A089806, A091602, A237515, A118457 (the partitions), A118459 (partition lengths), A015723 (total number of parts), A230957 (boustrophedon transform). Number of r-regular partitions for r = 2 through 12: A000009, A000726, A001935, A035959, A219601, A035985, A261775, A104502, A261776, A328545, A328546.
Octagonal numbers: n*(3*n-2). Also called star numbers.
(Formerly M4493 N1901)
+10
268
0, 1, 8, 21, 40, 65, 96, 133, 176, 225, 280, 341, 408, 481, 560, 645, 736, 833, 936, 1045, 1160, 1281, 1408, 1541, 1680, 1825, 1976, 2133, 2296, 2465, 2640, 2821, 3008, 3201, 3400, 3605, 3816, 4033, 4256, 4485, 4720, 4961, 5208, 5461, 5720, 5985, 6256, 6533, 6816
COMMENTS
Write 0,1,2,3,4,... in a hexagonal spiral around 0; then a(n) is the sequence found by reading the line from 0 in the direction 0,1,....
The spiral begins:
.
85--84--83--82--81--80
/ \
86 56--55--54--53--52 79
/ / \ \
87 57 33--32--31--30 51 78
/ / / \ \ \
88 58 34 16--15--14 29 50 77
/ / / / \ \ \ \
89 59 35 17 5---4 13 28 49 76
/ / / / / \ \ \ \ \
90 60 36 18 6 0 3 12 27 48 75
/ / / / / / / / / / /
91 61 37 19 7 1---2 11 26 47 74
\ \ \ \ \ . / / / /
92 62 38 20 8---9--10 25 46 73
\ \ \ \ . / / /
93 63 39 21--22--23--24 45 72
\ \ \ . / /
94 64 40--41--42--43--44 71
\ \ . /
95 65--66--67--68--69--70
\ .
96
.
(End)
Also the number of distinct three-cell blocks that may be removed out of A000217(n+1) square cells arranged in a stepping triangular array of side (n+1). A 5-layer triangular array of square cells, for instance, has vertices outlined thus: x x
x x x
x x x x
x x x x x
x x x x x x
x x x x x x (End)
Starting from n=1, the sequence corresponds to the Wiener index of K_{n,n} (the complete bipartite graph wherein each independent set has n vertices). - Kailasam Viswanathan Iyer, Mar 11 2009
a(n) = A001399(6n-5), number of partitions of 6*n - 5 into parts < 4. For example a(2)=8 and partitions of 6*2 - 5 = 7 into parts < 4 are: [1,1,1,1,1,1,1], [1,1,1,1,1,2],[1,1,1,1,3], [1,1,1,2,2], [1,1,2,3], [1,2,2,2], [1,3,3], [2,2,3]. - Adi Dani, Jun 07 2011 Also, sequence found by reading the line from 0 in the direction 0, 8, ..., and the parallel line from 1 in the direction 1, 21, ..., in the square spiral whose vertices are the generalized octagonal numbers A001082. - Omar E. Pol, Sep 10 2011 Generate a Pythagorean triple using Euclid's formula with (n, n-1) to give A,B,C. a(n) = B + (A + C)/2. - J. M. Bergot, Jul 13 2013 The number of active (ON, black) cells in n-th stage of growth of two-dimensional cellular automaton defined by "Rule 773", based on the 5-celled von Neumann neighborhood. - Robert Price, May 23 2016 For n >= 1, the continued fraction expansion of sqrt(27*a(n)) is [9n-4; {1, 2n-2, 3, 2n-2, 1, 18n-8}]. For n=1, this collapses to [5; {5, 10}]. - Magus K. Chu, Oct 10 2022 a(n)*a(n+1) + 1 = (3n^2 + n - 1)^2. In general, a(n)*a(n+k) + k^2 = (3n^2 + (3k-2)n - k)^2. - Charlie Marion, May 23 2023
REFERENCES
Albert H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 189.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 38.
Elena Deza and Michel Marie Deza, Figurate numbers, World Scientific Publishing (2012), pages 2, 6, 92.
L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 2, p. 1.
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).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 19-20.
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 11.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 123.
FORMULA
a(n) = n*(3*n-2).
a(n) = (3n-2)*(3n-1)*(3n)/((3n-1) + (3n-2) + (3n)), i.e., (the product of three consecutive numbers)/(their sum). a(1) = 1*2*3/(1+2+3), a(2) = 4*5*6/(4+5+6), etc. - Amarnath Murthy, Aug 29 2002 E.g.f.: exp(x)*(x+3*x^2). - Paul Barry, Jul 23 2003 a(n) = Sum_{k=1..n} (5*n - 4*k). - Paul Barry, Sep 06 2005 a(n) = C(n+1,2) + 5*C(n,2).
Starting (1, 8, 21, 40, 65, ...) = binomial transform of [1, 7, 6, 0, 0, 0, ...]. - Gary W. Adamson, Apr 30 2008 a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3), a(0)=0, a(1)=1, a(2)=8. - Jaume Oliver Lafont, Dec 02 2008 a(n) = 2*a(n-1) - a(n-2) + 6. - Ant King, Sep 01 2011 a(6*a(n) + 16*n + 1) = a(6*a(n) + 16*n) + a(6*n + 1). - Vladimir Shevelev, Jan 24 2014 Sum_{n>=1} 1/a(n) = (sqrt(3)*Pi + 9*log(3))/12 = 1.2774090575596367311949534921... . - Vaclav Kotesovec, Apr 27 2016 Inverse binomial transform of A084857. Sum_{n>=1} (-1)^(n+1)/a(n) = Pi/(2*sqrt(3)) = A093766. (End) Product_{n>=2} (1 - 1/a(n)) = 3/4. - Amiram Eldar, Jan 21 2021 P(4k+4,n) = ((k+1)*n - k)^2 - (k*n - k)^2 where P(m,n) is the n-th m-gonal number (a generalization of the Apr 10 2013 formula, a(n) = (2*n-1)^2 - (n-1)^2). - Charlie Marion, Oct 07 2021 a(n) = A000384(n) + 2* A000217(n-1). See Twin Rectangular Rays illustration.
MATHEMATICA
(* Alternative: *)
(* Alternative: *)
(* Alternative: *)
LinearRecurrence[{3, -3, 1}, {1, 8, 21}, {0, 20}] (* Eric W. Weisstein, Sep 07 2017 *)
PROG
(PARI) vector(50, n, n--; n*(3*n-2)) \\ G. C. Greubel, Nov 15 2018 (GAP) List([0..50], n -> n*(3*n-2)); # G. C. Greubel, Nov 15 2018 (Haskell)
(SageMath) [n*(3*n-2) for n in range(50)] # G. C. Greubel, Nov 15 2018 (Python) # Intended to compute the initial segment of the sequence, not isolated terms.
def aList():
x, y = 1, 1
yield 0
while True:
yield x
x, y = x + y + 6, y + 6
Triangle read by rows: T(n, k) = n-k, for 0 <= k <= n.
+10
165
0, 1, 0, 2, 1, 0, 3, 2, 1, 0, 4, 3, 2, 1, 0, 5, 4, 3, 2, 1, 0, 6, 5, 4, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0, 8, 7, 6, 5, 4, 3, 2, 1, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3
COMMENTS
Decreasing integers m to 0 followed by decreasing integers m+1 to 0, etc.
The PARI functions t1, t2 can be used to read a square array T(n,k) (n >= 0, k >= 0) by antidiagonals upwards: n -> T(t1(n), t2(n)). - Michael Somos, Aug 23 2002 Sequence B is called a reverse reluctant sequence of sequence A if B is a triangular array read by rows such that row number k lists the first k terms of the sequence A in reverse order. This sequence is the reverse reluctant sequence of sequence 0,1,2,3,..., the nonnegative integers A001477. - Boris Putievskiy, Dec 13 2012 A problem posed by François Viète (Vieta) in his book Zeteticorum liber quinque (1593), liber 2, problem 19 (quoted in the Alten et al. reference, on p. 292) is to find for a rectangle (a >= b >= 1) with given a^3 - b^3, name it C, and a*b, name it F, the difference a-b, name it x. This is a simple exercise which Viète found remarkable. It reduces to a standard cubic equation for x, namely x^3 + 3*F*x = C. Proof: Use the square of the diagonal d^2 = a^2 + b^2. Then (i) C = a^3 - b^3 = (a - b)*(a^2 + b^2 + a*b) = x*(d^2 + F). (ii) use the trivial relation d^2 = (a-b)^2 + 2*a*b = x^2 + 2*F, to eliminate d^2 in (i). End of the Proof. Here for positive integers a = n and b = k: (T(n, k)^2 + 3* A079904(n, k))*T(n, k) = A257238(n, k) (also true for n = k = 0). - Wolfdieter Lang, May 12 2015 See a comment on A051162 on the cubic equation for S = a+b in terms of Cplus = a^3 + b^3 and D = a - b. This equation leads to a - b = sqrt((4*Cplus -S^3)/(3*S)). - Wolfdieter Lang, May 15 2015 The entries correspond to the first of the 2 coordinates of the Cantor Pairs, specifically x=w-(CPKey-(w^2+w)/2), where w=floor((sqrt(8*CPKey+1)-1)/2) and CPKey=Cantor Pair key ( A001477). The second of the coordinate pairs is A002262. - Bill McEachen, Sep 12 2015
REFERENCES
H.-W. Alten et al., 4000 Jahre Algebra, 2. Auflage, Springer, 2014, p. 203.
FORMULA
T(n, k) = n-k, for 0 <= k <= n.
As a sequence: a(n) = (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n), with trinv(n) = floor((1+sqrt(1+8*n))/2). Cf. A002262. G.f. for T(n,k): y / ((1-x)^2 * (1-x*y)). - Ralf Stephan, Jan 25 2005 For the cubic equation satisfied by T(n, k) see the comment on a problem by Viète above. - Wolfdieter Lang, May 12 2015 G.f. for a(n): -(1-x)^(-2) + (1-x)^(-1) * Sum_{n>=0} (n+1)*x^(n*(n+1)/2). The sum is related to Jacobi theta functions. - Robert Israel, May 12 2015 a(n) = (1/2)*(t^2 + t - 2*n - 2), where t = floor(sqrt(2*n+1) + 1/2) = round(sqrt(2*n+1)). - Ridouane Oudra, Dec 01 2019 a(n) = ((1/2) * ceiling((-1 + sqrt(9 + 8 * n))/2) * ceiling((1 + sqrt(9 + 8 * n))/2)) - n - 1. - Ryan Jean, Apr 22 2022
EXAMPLE
The triangle T(n, k) begins (note that one could use l <= k <= n, for any integer l, especially 1):
n\k 0 1 2 3 4 5 6 7 8 9 10 ...
0: 0
1: 1 0
2: 2 1 0
3: 3 2 1 0
4: 4 3 2 1 0
5: 5 4 3 2 1 0
6: 6 5 4 3 2 1 0
7: 7 6 5 4 3 2 1 0
8: 8 7 6 5 4 3 2 1 0
9: 9 8 7 6 5 4 3 2 1 0
10: 10 9 8 7 6 5 4 3 2 1 0
MAPLE
A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))), 2) - (n+1): seq( A025581(n), n=0..100);
MATHEMATICA
(* Alternative: *)
With[{nn=20}, Flatten[Table[Join[{0}, Reverse[Range[i]]], {i, nn}]]] (* Harvey P. Dale, Dec 31 2014 *) (* Alternative: *)
Table[Range[n, 0, -1], {n, 0, 15}]//Flatten (* Harvey P. Dale, Aug 01 2020 *)
PROG
(PARI) a(n)=binomial(1+floor(1/2+sqrt(2+2*n)), 2)-(n+1) /* produces a(n) */
(PARI) t1(n)=binomial(floor(3/2+sqrt(2+2*n)), 2)-(n+1) /* A025581 */ (PARI) t2(n)=n-binomial(floor(1/2+sqrt(2+2*n)), 2) /* A002262 */ (PARI) apply( { A025581(n)=binomial(sqrtint(8*n+1)\/2+1, 2)-n-1}, [0..90]) \\ M. F. Hasler, Dec 06 2019 (Haskell)
a025581 n k = n - k
a025581_row n = [n, n-1 .. 0]
a025581_tabl = iterate (\xs@(x:_) -> (x + 1) : xs) [0]
(Magma) /* As triangle */ [[(n-k): k in [1..n]]: n in [1.. 15]]; // Vincenzo Librandi, Sep 13 2015 (Python)
from math import isqrt, comb
def A025581(n): return comb((m:=isqrt(k:=n+1<<1))+(k>m*(m+1))+1, 2)-n-1 # Chai Wah Wu, Nov 08 2024
CROSSREFS
Cf. A141418 (partial sums per row).
EXTENSIONS
Edited (part of name moved to first comment; definition of trinv added in formula) by Wolfdieter Lang, May 12 2015
Triangular matchstick numbers: a(n) = 3*n*(n+1)/2.
+10
140
0, 3, 9, 18, 30, 45, 63, 84, 108, 135, 165, 198, 234, 273, 315, 360, 408, 459, 513, 570, 630, 693, 759, 828, 900, 975, 1053, 1134, 1218, 1305, 1395, 1488, 1584, 1683, 1785, 1890, 1998, 2109, 2223, 2340, 2460, 2583, 2709, 2838, 2970, 3105, 3243, 3384, 3528
COMMENTS
Also, 3 times triangular numbers, a(n) = 3* A000217(n). In the 24-bit RGB color cube, the number of color-lattice-points in r+g+b = n planes at n < 256 equals the triangular numbers. For n = 256, ..., 765 the number of legitimate color partitions is less than A000217(n) because {r,g,b} components cannot exceed 255. For n = 256, ..., 511, the number of non-color partitions are computable with A045943(n-255), while for n = 512, ..., 765, the number of color points in r+g+b planes equals A000217(765-n). - Labos Elemer, Jun 20 2005 If a 3-set Y and an (n-3)-set Z are disjoint subsets of an n-set X then a(n-3) is the number of 3-subsets of X intersecting both Y and Z. - Milan Janjic, Sep 19 2007 a(n) is also the smallest number that may be written both as the sum of n-1 consecutive positive integers and n consecutive positive integers. - Claudio Meller, Oct 08 2010 For n >= 3, a(n) equals 4^(2+n)*Pi^(1 - n) times the coefficient of zeta(3) in the following integral with upper bound Pi/4 and lower bound 0: int x^(n+1) tan x dx. - John M. Campbell, Jul 17 2011 Sequence found by reading the line from 0, in the direction 0, 3, ..., and the same line from 0, in the direction 0, 9, ..., in the square spiral whose vertices are the generalized pentagonal numbers A001318. This is one of the orthogonal axes of the spiral; the other is A032528. - Omar E. Pol, Sep 08 2011 A005449(a(n)) = A000332(3n + 3) = C(3n + 3, 4), a second pentagonal number of triangular matchstick number index number. Additionally, a(n) - 2n is a pentagonal number ( A000326). - Raphie Frank, Dec 31 2012
Number of orbits of Aut(Z^7) as function of the infinity norm (n+1) of the representative integer lattice point of the orbit, when the cardinality of the orbit is equal to 5376 or 17920 or 20160. - Philippe A.J.G. Chevalier, Dec 28 2015 Also the number of 4-cycles in the (n+4)-triangular honeycomb acute knight graph. - Eric W. Weisstein, Jul 27 2017 Number of terms less than 10^k, k=0,1,2,3,...: 1, 3, 8, 26, 82, 258, 816, 2582, 8165, 25820, 81650, 258199, 816497, 2581989, 8164966, ... - Muniru A Asiru, Jan 24 2018 Numbers of the form 3*m*(2*m + 1) for m = 0, -1, 1, -2, 2, -3, 3, ... - Bruno Berselli, Feb 26 2018 Column 1 of A273464. (Number of ways to select a unit lozenge inside an isosceles triangle of side length n; all vertices on a hexagonal lattice.) - R. J. Mathar, Jul 10 2019 Total number of pips in the n-th suit of a double-n domino set. - Ivan N. Ianakiev, Aug 23 2020
REFERENCES
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 543.
LINKS
Milan Janjic and Boris Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550 [math.CO], 2013.
FORMULA
a(n) is the sum of n+1 integers starting from n, i.e., 1+2, 2+3+4, 3+4+5+6, 4+5+6+7+8, etc. - Jon Perry, Jan 15 2004 a(n) = T(2*n) - T(n-1), where T(n) = A000217(n). In general, T(k)*T(n) = Sum_{i=0..k-1} (-1)^i*T((k-i)*(n-i)). - Charlie Marion, Dec 06 2020 Sum_{n>=1} 1/a(n) = 2/3.
Sum_{n>=1} (-1)^(n+1)/a(n) = 2*(2*log(2)-1)/3. (End)
Product_{n>=1} (1 - 1/a(n)) = -(3/(2*Pi))*cos(sqrt(11/3)*Pi/2). - Amiram Eldar, Feb 21 2023
EXAMPLE
T(n), the triangular numbers = number of nodes,
a(n-1) = number of edges in the T(n) graph:
o (T(1) = 1, a(0) = 0)
o
/ \ (T(2) = 3, a(1) = 3)
o - o
o
/ \
o - o (T(3) = 6, a(2) = 9)
/ \ / \
o - o - o
MATHEMATICA
(* Alternative: *)
(* Alternative: *)
CoefficientList[Series[-3 x/(x - 1)^3, {x, 0, 47}], x] (* Robert G. Wilson v, Jan 29 2015 *) (* Alternative: *)
PROG
(Common Lisp) (defun tri (i) (if (eq i 0) 0 (+ (* 3 (- i 1)) (tri (- i 1))))) // Stephen Balaban, Jul 25 2011 (Haskell) a n = sum [x | x <- [n..2*n]] -- Peter Kagey, Jul 27 2015 (GAP) List([0..10^4], n -> 3*n*(n+1)/2); # Muniru A Asiru, Jan 24 2018
CROSSREFS
The generalized pentagonal numbers b*n+3*n*(n-1)/2, for b = 1 through 12, form sequences A000326, A005449, A045943, A115067, A140090, A140091, A059845, A140672, A140673, A140674, A140675, A151542. Cf. A002378 (3-cycles in triangular honeycomb acute knight graph), A028896 (5-cycles), A152773 (6-cycles). This sequence: Sum_{k = n..2*n} k.
Cf. A304993: Sum_{k = n..2*n} k*(k+1)/2. Similar sequences are listed in A316466.
Triangle read by rows: T(n, k) = binomial(n + k, 2*k).
+10
64
1, 1, 1, 1, 3, 1, 1, 6, 5, 1, 1, 10, 15, 7, 1, 1, 15, 35, 28, 9, 1, 1, 21, 70, 84, 45, 11, 1, 1, 28, 126, 210, 165, 66, 13, 1, 1, 36, 210, 462, 495, 286, 91, 15, 1, 1, 45, 330, 924, 1287, 1001, 455, 120, 17, 1, 1, 55, 495, 1716, 3003, 3003, 1820, 680, 153, 19, 1
COMMENTS
Coefficient array for Morgan-Voyce polynomial b(n,x). A053122 (unsigned) is the coefficient array for B(n,x). Reversal of A054142. - Paul Barry, Jan 19 2004 This triangle is formed from even-numbered rows of triangle A011973 read in reverse order. - Philippe Deléham, Feb 16 2004 T(n,k) is the number of nondecreasing Dyck paths of semilength n+1, having k+1 peaks. T(n,k) is the number of nondecreasing Dyck paths of semilength n+1, having k peaks at height >= 2. T(n,k) is the number of directed column-convex polyominoes of area n+1, having k+1 columns. - Emeric Deutsch, May 31 2004 Riordan array (1/(1-x), x/(1-x)^2). - Paul Barry, May 09 2005 The n-th row gives absolute values of coefficients of reciprocal of g.f. of bottom-line of n-wave sequence. - Floor van Lamoen (fvlamoen(AT)planet.nl), Sep 24 2006
T(n, k) is also the number of idempotent order-preserving full transformations (of an n-chain) of height k >=1 (height(alpha) = |Im(alpha)|) and of waist n (waist(alpha) = max(Im(alpha))). - Abdullahi Umar, Oct 02 2008 A085478 is jointly generated with A078812 as a triangular array of coefficients of polynomials u(n,x): initially, u(1,x) = v(1,x) = 1; for n>1, u(n,x) = u(n-1,x)+x*v(n-1)x and v(n,x) = u(n-1,x)+(x+1)*v(n-1,x). See the Mathematica section. - Clark Kimberling, Feb 25 2012
Subtriangle of the triangle given by (0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (1, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Mar 26 2012 T(n,k) is also the number of compositions (ordered partitions) of 2*n+1 into 2*k+1 parts which are all odd. Proof: The o.g.f. of column k, x^k/(1-x)^(2*k+1) for k >= 0, is the o.g.f. of the odd-indexed members of the sequence with o.g.f. (x/(1-x^2))^(2*k+1) (bisection, odd part). Thus T(n,k) is obtained from the sum of the multinomial numbers A048996 for the partitions of 2*n+1 into 2*k+1 parts, all of which are odd. E.g., T(3,1) = 3 + 3 from the numbers for the partitions [1,1,5] and [1,3,3], namely 3!/(2!*1!) and 3!/(1!*2!), respectively. The number triangle with the number of these partitions as entries is A152157. - Wolfdieter Lang, Jul 09 2012 The matrix elements of the inverse are T^(-1)(n,k) = (-1)^(n+k)* A039599(n,k). - R. J. Mathar, Mar 12 2013 The n-th row polynomial in descending powers of x is the n-th Taylor polynomial of the algebraic function F(x)*G(x)^n about 0, where F(x) = (1 + sqrt(1 + 4*x))/(2*sqrt(1 + 4*x)) and G(x) = ((1 + sqrt(1 + 4*x))/2)^2. For example, for n = 4, (1 + sqrt(1 + 4*x))/(2*sqrt(1 + 4*x)) * ((1 + sqrt(1 + 4*x))/2)^8 = (x^4 + 10*x^3 + 15*x^2 + 7*x + 1) + O(x^5). - Peter Bala, Feb 23 2018 Row n also gives the coefficients of the characteristc polynomial of the tridiagonal n X n matrix M_n given in A332602: Phi(n, x) := Det(M_n - x*1_n) = Sum_{k=0..n} T(n, k)*(-x)^k, for n >= 0, with Phi(0, x) := 1. - Wolfdieter Lang, Mar 25 2020 It appears that the largest root of the n-th degree polynomial is equal to the sum of the distinct diagonals of a (2*n+1)-gon including the edge, 1. The largest root of x^3 - 6*x^2 + 5*x - 1 is 5.048917... = the sum of (1 + 1.80193... + 2.24697...). Alternatively, the largest root of the n-th degree polynomial is equal to the square of sigma(2*n+1). Check: 5.048917... is the square of sigma(7), 2.24697.... Given N = 2*n+1, sigma(N) (N odd) can be defined as 1/(2*sin(Pi/(2*N))). Relating to the 9-gon, the largest root of x^4 - 10*x^3 + 15*x^2 - 7*x + 1 is 8.290859..., = the sum of (1 + 1.879385... + 2.532088... + 2.879385...), and is the square of sigma(9), 2.879385... Refer to A231187 for a further clarification of sigma(7). - Gary W. Adamson, Jun 28 2022 For n >=1, the n-th row is given by the coefficients of the minimal polynomial of -4*sin(Pi/(4*n + 2))^2. - Eric W. Weisstein, Jul 12 2023 Denoting this lower triangular array by L, then L * diag(binomial(2*k,k)^2) * transpose(L) is the LDU factorization of A143007, the square array of crystal ball sequences for the A_n X A_n lattices. - Peter Bala, Feb 06 2024 T(n, k) is the number of occurrences of the periodic substring (01)^k in the periodic string (01)^n (see Proposition 4.7 at page 7 in Fang). - Stefano Spezia, Jun 09 2024
FORMULA
T(n, k) = (n+k)!/((n-k)!*(2*k)!).
Row sums are A001519 (Fibonacci(2n+1)). Diagonal sums are A011782. Binomial transform of A026729 (product of lower triangular matrices). - Paul Barry, Jun 21 2004 T(n, 0) = 1, T(n, k) = 0 if n<k; T(n, k) = Sum_{j>=0} T(n-1-j, k-1)*(j+1). T(0, 0) = 1, T(0, k) = 0 if k>0; T(n, k) = T(n-1, k-1) + T(n-1, k) + Sum_{j>=0} (-1)^j*T(n-1, k+j)* A000108(j). For the column k, g.f.: Sum_{n>=0} T(n, k)*x^n = (x^k) / (1-x)^(2*k+1). - Philippe Deléham, Feb 15 2004 Sum_{k=0..n} T(n,k)*x^(2*k) = A000012(n), A001519(n+1), A001653(n), A078922(n+1), A007805(n), A097835(n), A097315(n), A097838(n), A078988(n), A097841(n), A097727(n), A097843(n), A097730(n), A098244(n), A097733(n), A098247(n), A097736(n), A098250(n), A097739(n), A098253(n), A097742(n), A098256(n), A097767(n), A098259(n), A097770(n), A098262(n), A097773(n), A098292(n), A097776(n) for x=0,1,2,...,27,28 respectively. - Philippe Deléham, Dec 31 2007 O.g.f. for column k: x^k/(1-x)^(2*k+1), k >= 0. [See the o.g.f. of the triangle above, and a comment on compositions. - Wolfdieter Lang, Jul 09 2012] E.g.f.: (2/sqrt(x + 4))*sinh((1/2)*t*sqrt(x + 4))*cosh((1/2)*t*sqrt(x)) = t + (1 + x)*t^3/3! + (1 + 3*x + x^2)*t^5/5! + (1 + 6*x + 5*x^2 + x^3)*t^7/7! + .... Cf. A091042. - Peter Bala, Jul 29 2013 The n-th row polynomial b(n, x) = (-1)^n * U(2*n, (i/2)*sqrt(x)), where U(n,x) is the n-th Chebyshev polynomial of the second kind.
b(n, x) = (-1)^n * Dir(n, -1 - x/2), where Dir(n, x) is the n-th row polynomial of the triangle A244419. b(n, -1 - x) is the n-th row polynomial of A098493. (End)
EXAMPLE
Triangle begins as:
1;
1 1;
1 3 1;
1 6 5 1;
1 10 15 7 1;
1 15 35 28 9 1;
1 21 70 84 45 11 1;
1 28 126 210 165 66 13 1;
1 36 210 462 495 286 91 15 1;
1 45 330 924 1287 1001 455 120 17 1;
1 55 495 1716 3003 3003 1820 680 153 19 1;
...
(0, 1, 0, 1, 0, 0, 0, ...) DELTA (1, 0, 1, -1, 0, 0, 0, ...) begins:
1
0, 1
0, 1, 1
0, 1, 3, 1
0, 1, 6, 5, 1
0, 1, 10, 15, 7, 1
0, 1, 15, 35, 28, 9, 1
0, 1, 21, 70, 84, 45, 11, 1
0, 1, 28, 126, 210, 165, 66, 13, 1. (End)
MAPLE
T := (n, k) -> binomial(n+k, 2*k): seq(seq(T(n, k), k=0..n), n=0..11);
MATHEMATICA
u[1, x_]:= 1; v[1, x_]:= 1; z = 13;
u[n_, x_]:= u[n-1, x] + x*v[n-1, x];
v[n_, x_]:= u[n-1, x] + (x+1)*v[n-1, x];
Table[Expand[u[n, x]], {n, 1, z/2}]
Table[Expand[v[n, x]], {n, 1, z/2}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Table[Expand[v[n, x]], {n, 1, z}]
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
(* Alternative: *)
Table[Binomial[n + k, 2 k], {n, 0, 12}, {k, 0, n}] // Flatten (* G. C. Greubel, Aug 01 2019 *) (* Alternative: *)
CoefficientList[Table[Fibonacci[2 n + 1, Sqrt[x]], {n, 0, 10}], x] // Flatten (* Eric W. Weisstein, Jul 03 2023 *) (* Alternative: *)
Join[{{1}}, CoefficientList[Table[MinimalPolynomial[-4 Sin[Pi/(4 n + 2)]^2, x], {n, 20}], x]] (* Eric W. Weisstein, Jul 12 2023 *)
PROG
(PARI) T(n, k) = binomial(n+k, n-k)
(Haskell)
a085478 n k = a085478_tabl !! n !! k
a085478_row n = a085478_tabl !! n
a085478_tabl = zipWith (zipWith a007318) a051162_tabl a025581_tabl
(Magma) [Binomial(n+k, 2*k): k in [0..n], n in [0..12]]; // G. C. Greubel, Aug 01 2019 (SageMath) [[binomial(n+k, 2*k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Aug 01 2019 (GAP) Flat(List([0..12], n-> List([0..n], k-> Binomial(n+k, 2*k) ))); # G. C. Greubel, Aug 01 2019
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).
b + c + d where b >= c >= d >= 0 ordered by b then c then d.
+10
12
0, 1, 2, 3, 2, 3, 4, 4, 5, 6, 3, 4, 5, 5, 6, 7, 6, 7, 8, 9, 4, 5, 6, 6, 7, 8, 7, 8, 9, 10, 8, 9, 10, 11, 12, 5, 6, 7, 7, 8, 9, 8, 9, 10, 11, 9, 10, 11, 12, 13, 10, 11, 12, 13, 14, 15, 6, 7, 8, 8, 9, 10, 9, 10, 11, 12, 10, 11, 12, 13, 14, 11, 12, 13, 14, 15, 16, 12, 13, 14, 15, 16, 17, 18, 7
EXAMPLE
Triangle begins:
0,
;
1;
2, 3;
;
2;
3, 4;
4, 5, 6;
;
3;
4, 5,
5, 6, 7;
6, 7, 8, 9;
;
4;
5, 6;
6, 7, 8;
7, 8, 9, 10;
8, 9, 10, 11, 12;
;
...
MAPLE
seq(seq(seq(b+c+d, d=0..c), c=0..b), b=0..10); # Robert Israel, Jun 21 2018
PROG
(Python)
from math import isqrt, comb
from sympy import integer_nthroot
def A070770(n): return (m:=integer_nthroot(6*(n+1), 3)[0])+(a:=n>=comb(m+2, 3))+(k:=isqrt(b:=(c:=n+1-comb(m+a+1, 3))<<1))-((b<<2)<=(k<<2)*(k+1)+1)+c-2-comb(k+(b>k*(k+1)), 2) # Chai Wah Wu, Dec 11 2024
b+c+d+e where b>=c>=d>=e>=0 ordered by b then c then d then e.
+10
8
0, 1, 2, 3, 4, 2, 3, 4, 5, 4, 5, 6, 6, 7, 8, 3, 4, 5, 6, 5, 6, 7, 7, 8, 9, 6, 7, 8, 8, 9, 10, 9, 10, 11, 12, 4, 5, 6, 7, 6, 7, 8, 8, 9, 10, 7, 8, 9, 9, 10, 11, 10, 11, 12, 13, 8, 9, 10, 10, 11, 12, 11, 12, 13, 14, 12, 13, 14, 15, 16, 5, 6, 7, 8, 7, 8, 9, 9, 10, 11, 8, 9, 10, 10, 11, 12, 11
Search completed in 0.007 seconds
| 
