A000346 -id:A000346 - cp's OEIS frontend

A002054 Binomial coefficient C(2n+1, n-1).

1, 5, 21, 84, 330, 1287, 5005, 19448, 75582, 293930, 1144066, 4457400, 17383860, 67863915, 265182525, 1037158320, 4059928950, 15905368710, 62359143990, 244662670200, 960566918220, 3773655750150, 14833897694226, 58343356817424, 229591913401900

Offset: 1

N. J. A. Sloane

a(n) = number of permutations in S_{n+2} containing exactly one 312 pattern. E.g., S_3 has a_1 = 1 permutations containing exactly one 312 pattern, and S_4 has a_2 = 5 permutations containing exactly one 312 pattern, namely 1423, 2413, 3124, 3142, and 4231. This comment is also true if 312 is replaced by any of 132, 213, or 231 (but not 123 or 321, for which see A003517). [Comment revised by N. J. A. Sloane, Nov 26 2022]
Number of valleys in all Dyck paths of semilength n+1. Example: a(2)=5 because UD*UD*UD, UD*UUDD, UUDD*UD, UUD*UDD, UUUDDD, where U=(1,1), D=(1,-1) and the valleys are shown by *. - Emeric Deutsch, Dec 05 2003
Number of UU's (double rises) in all Dyck paths of semilength n+1. Example: a(2)=5 because UDUDUD, UDU*UDD, U*UDDUD, U*UDUDD, U*U*UDDD, the double rises being shown by *. - Emeric Deutsch, Dec 05 2003
Number of peaks at level higher than one (high peaks) in all Dyck paths of semilength n+1. Example: a(2)=5 because UDUDUD, UDUU*DD, UU*DDUD, UU*DU*DD, UUU*DDD, the high peaks being shown by *. - Emeric Deutsch, Dec 05 2003
Number of diagonal dissections of a convex (n+3)-gon into n regions. Number of standard tableaux of shape (n,n,1) (see Stanley reference). - Emeric Deutsch, May 20 2004
Number of dissections of a convex (n+3)-gon by noncrossing diagonals into several regions, exactly n-1 of which are triangular. Example: a(2)=5 because the convex pentagon ABCDE is dissected by any of the diagonals AC, BD, CE, DA, EB into regions containing exactly 1 triangle. - Emeric Deutsch, May 31 2004
Number of jumps in all full binary trees with n+1 internal nodes. In the preorder traversal of a full binary tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch, Jan 18 2007
a(n) is the total number of nonempty Dyck subpaths in all Dyck paths (A000108) of semilength n. For example, the Dyck path UUDUUDDD has Dyck subpaths stretching over positions 1-8 (the entire path), 2-3, 2-7, 4-7, 5-6 and so contributes 5 to a(4). - David Callan, Jul 25 2008
a(n+1) is the total number of ascents in the set of all n-permutations avoiding the pattern 132. For example, a(2) = 5 because there are 5 ascents in the set 123, 213, 231, 312, 321. - Cheyne Homberger, Oct 25 2013
Number of increasing tableaux of shape (n+1,n+1) with largest entry 2n+1. An increasing tableau is a semistandard tableau with strictly increasing rows and columns, and set of entries an initial segment of the positive integers. Example: a(2) = 5 counts the five tableaux (124)(235), (123)(245), (124)(345), (134)(245), (123)(245). - Oliver Pechenik, May 02 2014
a(n) is the number of noncrossing partitions of 2n+1 into n-1 blocks of size 2 and 1 block of size 3. - Oliver Pechenik, May 02 2014
Number of paths in the half-plane x>=0, from (0,0) to (2n+1,3), and consisting of steps U=(1,1) and D=(1,-1). For example, for n=2, we have the 5 paths: UUUUD, UUUDU, UUDUU, UDUUU, DUUUU. - José Luis Ramírez Ramírez, Apr 19 2015
From Gus Wiseman, Aug 20 2021: (Start)
Also the number of binary numbers with 2n+2 digits and with two more 0's than 1's. For example, the a(2) = 5 binary numbers are: 100001, 100010, 100100, 101000, 110000, with decimal values 33, 34, 36, 40, 48. Allowing first digit 0 gives A001791, ranked by A345910/A345912.
Also the number of integer compositions of 2n+2 with alternating sum -2, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(3) = 21 compositions are:
  (35)  (152)  (1124)  (11141)  (111113)
        (251)  (1223)  (12131)  (111212)
               (1322)  (13121)  (111311)
               (1421)  (14111)  (121112)
               (2114)           (121211)
               (2213)           (131111)
               (2312)
               (2411)
The following pertain to these compositions:
- The unordered version is A344741.
- Ranked by A345924 (reverse: A345923).
- A345197 counts compositions by length and alternating sum.
- A345925 ranks compositions with alternating sum 2 (reverse: A345922).
(End)

			G.f. = x + 5*x^2 + 21*x^3 + 84*x^4 + 330*x^5 + 1287*x^6 + 5005*x^7 + ...

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
George Grätzer, General Lattice Theory. Birkhauser, Basel, 1998, 2nd edition, p. 474, line -3.
A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
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).

G. C. Greubel, Table of n, a(n) for n = 1..1000 (terms 1..100 computed by T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, Enumeration of multi-rooted plane trees, arXiv:2301.09765 [math.CO], 2023.
F. R. Bernhart and N. J. A. Sloane, Emails, April-May 1994.
Jean-Luc Baril and Sergey Kirgizov, The pure descent statistic on permutations, Discrete Mathematics, Vol. 340, No. 10 (2017), pp. 2550-2558; preprint, 2017.
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Dyck Paths with catastrophes modulo the positions of a given pattern, Australasian J. Comb. (2022) Vol. 84, No. 2, 398-418.
David Callan, A recursive bijective approach to counting permutations containing 3-letter patterns, arXiv:math/0211380 [math.CO], 2002.
Arthur Cayley, On the partitions of a polygon, Proc. London Math. Soc., Vol. 22 (1891), pp. 237-262 = Collected Mathematical Papers, Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff.
Matteo Cervetti and Luca Ferrari, Pattern avoidance in the matching pattern poset, arXiv:2009.01024 [math.CO], 2020.
Colin Defant, Proofs of Conjectures about Pattern-Avoiding Linear Extensions, arXiv:1905.02309 [math.CO], 2019.
Emeric Deutsch, Dyck path enumeration, Discrete Math., Vol. 204, No. 1-3 (1999), pp. 167-202.
Gennady Eremin, Dyck Numbers, IV. Nested patterns in OEIS A036991, arXiv:2306.10318 [math.CO], 2023. See (5) p. 7.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, J. Int. Seq., Vol. 17 (2014), Article 14.1.5; arXiv preprint, arXiv:1203.6792 [math.CO], 2012.
Xiaoyu He, Emily Huang, Ihyun Nam and Rishubh Thaper, Shuffle Squares and Reverse Shuffle Squares, arXiv:2109.12455 [math.CO], 2021.
Clemens Heuberger, Sarah J. Selkirk, and Stephan Wagner, Enumeration of Generalized Dyck Paths Based on the Height of Down-Steps Modulo k, arXiv:2204.14023 [math.CO], 2022.
Milan Janjic, Two Enumerative Functions.
Werner Krandick, Trees and jumps and real roots, J. Computational and Applied Math., Vol. 162, No. 1 (2004), pp. 51-55.
Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.
Toufik Mansour and Alek Vainshtein, Counting occurrences of 123 in a permutation, arXiv:math/0105073 [math.CO], 2001.
Henri Mühle, Symmetric Chain Decompositions and the Strong Sperner Property for Noncrossing Partition Lattices, arXiv:1509.06942 [math.CO], 2015.
Asamoah Nkwanta and Earl R. Barnes, Two Catalan-type Riordan Arrays and their Connections to the Chebyshev Polynomials of the First Kind, Journal of Integer Sequences, Vol. 15 (2012), Article 12.3.3.
John Noonan and Doron Zeilberger, The Enumeration of Permutations With a Prescribed Number of ``Forbidden'' Patterns, arXiv:math/9808080 [math.CO], 1998.
Oliver Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, arXiv:1209.1355 [math.CO], 2012-2014.
Oliver Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, J. Combin. Theory A, Vol. 125 (2014), pp. 357-378.
Karol Penson, Hausdorff moment problems for combinatorial numbers: heuristics via Meijer G-functions, Nov. 2022.
Ronald C. Read, On general dissections of a polygon, Aequationes Mathematicae, Vol. 18, No. 1-2 (1978), pp. 370-388; Preprint, 1974.
Mark Shattuck, Enumeration of non-crossing partitions according to subwords with repeated letters, arXiv:2303.06300 [math.CO], 2023.
Richard P. Stanley, Polygon dissections and standard Young tableaux, J. Comb. Theory, Ser. A, Vol. 76 , No. 1 (1996), pp. 175-177.
Daniel W. Stasiuk, An Enumeration Problem for Sequences of n-ary Trees Arising from Algebraic Operads, Master's Thesis, University of Saskatchewan-Saskatoon (2018).
A. Vogt, Resummation of small-x double logarithms in QCD: semi-inclusive electron-positron annihilation, arXiv:1108.2993 [hep-ph], 2011.
N. J. Wildberger and Dean Rubine, A Hyper-Catalan Series Solution to Polynomial Equations, and the Geode, Amer. Math. Monthly (2025). See section 12.

Diagonal 4 of triangle A100257. Also a diagonal of A033282.
Equals (1/2) A024483(n+2). Bisection of A037951 and A037955.
Cf. A001263.
Column k=1 of A263771.
Counts terms of A031445 with 2n+2 digits in binary.
Cf. A000097, A000346, A000984, A001622, A001700, A007318, A008549, A031444, A058622, A097805, A116406, A138364, A163493, A202736.
Cf. binomial(2*n+m, n): A000984 (m = 0), A001700 (m = 1), A001791 (m = 2), A002694 (m = 4), A003516 (m = 5), A002696 (m = 6), A030053 - A030056, A004310 - A004318.

List([1..25],n->Binomial(2*n+1,n-1)); # Muniru A Asiru, Aug 09 2018

[Binomial(2*n+1, n-1): n in [1..30]]; // Vincenzo Librandi, Apr 20 2015

with(combstruct): seq((count(Composition(2*n+2), size=n)), n=1..24); # Zerinvary Lajos, May 03 2007

CoefficientList[Series[8/(((Sqrt[1-4x] +1)^3)*Sqrt[1-4x]), {x,0,22}], x] (* Robert G. Wilson v, Aug 08 2011 *)
a[ n_]:= Binomial[2 n + 1, n - 1]; (* Michael Somos, Apr 25 2014 *)

PARI
```
{a(n) = binomial( 2*n+1, n-1)};
```

from _future_ import division
A002054_list, b = [], 1
for n in range(1,10**3):
    A002054_list.append(b)
    b = b*(2*n+2)*(2*n+3)//(n*(n+3)) # Chai Wah Wu, Jan 26 2016

[binomial(2*n+1, n-1) for n in (1..25)] # G. C. Greubel, Mar 22 2019

a(n) = Sum_{j=0..n-1} binomial(2*j, j) * binomial(2*n - 2*j, n-j-1)/(j+1). - Yong Kong (ykong(AT)curagen.com), Dec 26 2000
G.f.: z*C^4/(2-C), where C=[1-sqrt(1-4z)]/(2z) is the Catalan function. - Emeric Deutsch, Jul 05 2003
From Wolfdieter Lang, Jan 09 2004: (Start)
a(n) = binomial(2*n+1, n-1) = n*C(n+1)/2, C(n)=A000108(n) (Catalan).
G.f.: (1 - 2*x - (1-3*x)*c(x))/(x*(1-4*x)) with g.f. c(x) of A000108. (End)
G.f.: z*C(z)^3/(1-2*z*C(z)), where C(z) is the g.f. of Catalan numbers. - José Luis Ramírez Ramírez, Apr 19 2015
G.f.: 2F1(5/2, 2; 4; 4*x). - R. J. Mathar, Aug 09 2015
D-finite with recurrence: a(n+1) = a(n)*(2*n+3)*(2*n+2)/(n*(n+3)). - Chai Wah Wu, Jan 26 2016
From Ilya Gutkovskiy, Aug 30 2016: (Start)
E.g.f.: (BesselI(0,2*x) + (1 - 1/x)*BesselI(1,2*x))*exp(2*x).
a(n) ~ 2^(2*n+1)/sqrt(Pi*n). (End)
a(n) = (1/(n+1))*Sum_{i=0..n-1} (n+1-i)*binomial(2n+2,i), n >= 1. - Taras Goy, Aug 09 2018
G.f.: (x - 1 + (1 - 3*x)/sqrt(1 - 4*x))/(2*x^2). - Michael Somos, Jul 28 2021
From Amiram Eldar, Jan 24 2022: (Start)
Sum_{n>=1} 1/a(n) = 5/3 - 2*Pi/(9*sqrt(3)).
Sum_{n>=1} (-1)^(n+1)/a(n) = 52*log(phi)/(5*sqrt(5)) - 7/5, where phi is the golden ratio (A001622). (End)
a(n) = A001405(2*n+1) - A000108(n+1), n >= 1 (from Eremin link, page 7). - Gennady Eremin, Sep 05 2023
G.f.: x/(1 - 4*x)^2 * c(-x/(1 - 4*x))^3, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. - Peter Bala, Feb 03 2024
From Peter Bala, Oct 13 2024: (Start)
a(n) = Integral_{x = 0..4} x^n * w(x) dx, where the weight function w(x) = 1/(2*Pi) * sqrt(x)*(x - 3)/sqrt(4 - x) (see Penson).
G.f. x*/sqrt(1 - 4*x) * c(x)^3. (End)

A000125 Cake numbers: maximal number of pieces resulting from n planar cuts through a cube (or cake): C(n+1,3) + n + 1.

Original entry on oeis.org

1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299, 378, 470, 576, 697, 834, 988, 1160, 1351, 1562, 1794, 2048, 2325, 2626, 2952, 3304, 3683, 4090, 4526, 4992, 5489, 6018, 6580, 7176, 7807, 8474, 9178, 9920, 10701, 11522, 12384, 13288, 14235, 15226

Offset: 0

N. J. A. Sloane

Note that a(n) = a(n-1) + A000124(n-1). This has the following geometrical interpretation: Define a number of planes in space to be in general arrangement when
(1) no two planes are parallel,
(2) there are no two parallel intersection lines,
(3) there is no point common to four or more planes.
Suppose there are already n-1 planes in general arrangement, thus defining the maximal number of regions in space obtainable by n-1 planes and now one more plane is added in general arrangement. Then it will cut each of the n-1 planes and acquire intersection lines which are in general arrangement. (See the comments on A000124 for general arrangement with lines.) These lines on the new plane define the maximal number of regions in 2-space definable by n-1 straight lines, hence this is A000124(n-1). Each of this regions acts as a dividing wall, thereby creating as many new regions in addition to the a(n-1) regions already there, hence a(n) = a(n-1) + A000124(n-1). - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
More generally, we have: A000027(n) = binomial(n,0) + binomial(n,1) (the natural numbers), A000124(n) = binomial(n,0) + binomial(n,1) + binomial(n,2) (the Lazy Caterer's sequence), a(n) = binomial(n,0) + binomial(n,1) + binomial(n,2) + binomial(n,3) (Cake Numbers). - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
If Y is a 2-subset of an n-set X then, for n>=3, a(n-3) is the number of 3-subsets of X which do not have exactly one element in common with Y. - Milan Janjic, Dec 28 2007
a(n) is the number of compositions (ordered partitions) of n+1 into four or fewer parts or equivalently the sum of the first four terms in the n-th row of Pascal's triangle. - Geoffrey Critzer, Jan 23 2009
{a(k): 0 <= k < 4} = divisors of 8. - Reinhard Zumkeller, Jun 17 2009
a(n) is also the maximum number of different values obtained by summing n consecutive positive integers with all possible 2^n sign combinations. This maximum is first reached when summing the interval [n, 2n-1]. - Olivier Gérard, Mar 22 2010
a(n) contains only 5 perfect squares > 1: 4, 64, 576, 67600, and 75203584. The incidences of > 0 are given by A047694. - Frank M Jackson, Mar 15 2013
Given n tiles with two values - an A value and a B value - a player may pick either the A value or the B value. The particular tiles are [n, 0], [n-1, 1], ..., [2, n-2] and [1, n-1]. The sequence is the number of different final A:B counts. For example, with n=4, we can have final total [5, 3] = [4, ] + [, 1] + [, 2] + [1, ] = [, 0] + [3, ] + [2, ] + [, 3], so a(4) = 2^4 - 1 = 15. The largest and smallest final A+B counts are given by A077043 and A002620 respectively. - Jon Perry, Oct 24 2014
For n>=3, a(n) is also the number of maximal cliques in the (n+1)-triangular graph (the 4-triangular graph has a(3)=8 maximal cliques). - Andrew Howroyd, Jul 19 2017
a(n) is the number of binary words of length n matching the regular expression 1*0*1*0*. Coincidentally, A000124 counts binary words of the form 0*1*0*. See Alexandersson and Nabawanda for proof. - Per W. Alexandersson, May 15 2021
For n > 0, let the n-dimensional cube, {0,1}^n be provided with the Hamming distance, d. Given an element x in {0,1}^n, a(n) is the number of elements y in {0,1}^n such that d(x, y) <= 3. Example: n = 4. Let x = (0,0,0,0) be in {0,1}^4.
d(x,y) = 0: y in {(0,0,0,0)}.
d(x,y) = 1: y in {(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)}.
d(x,y) = 2: y in {(1,1,0,0), (1,0,1,0), (1,0,0,1), (0,1,1,0), (0,1,0,1), (0,0,1,1)}.
d(x,y) = 3: y in {(1,1,1,0), (1,1,0,1), (1,0,1,1), (0,1,1,1)}.
All these y are at a distance <= 3 from (0,0,0,0), so a(4) = 15. (See Peter C. Heinig's formula). - Yosu Yurramendi, Dec 14 2021
For n >= 2, a(n) is the number of distinct least squares regression lines fitted to n points (j,y_j), 1 <= j <= n, where each y_j is 0 or 1. The number of distinct lines with exactly k 1's among y_1, ..., y_n is A077028(n,k). The number of distinct slopes is A123596(n). - Pontus von Brömssen, Mar 16 2024
The only powers of 2 in this sequence are a(0) = 1, a(1) = 2, a(2) = 4, a(3) = 8, and a(7) = 64. - Jianing Song, Jan 02 2025

			a(4)=15 because there are 15 compositions of 5 into four or fewer parts. a(6)=42 because the sum of the first four terms in the 6th row of Pascal's triangle is 1+6+15+20=42. - _Geoffrey Critzer_, Jan 23 2009
For n=5, (1, 3, 5, 7, 9, 11, 13, 17, 19, 21, 23, 25, 35) and their opposite are the 26 different sums obtained by summing 5,6,7,8,9 with any sign combination. - _Olivier Gérard_, Mar 22 2010
G.f. = 1 + 2*x + 4*x^2 + 8*x^3 + 15*x^4 + 26*x^5 + 42*x^6 + 64*x^7 + ... - _Michael Somos_, Jul 07 2022

V. I. Arnold (ed.), Arnold's Problems, Springer, 2004, comments on Problem 1990-11 (p. 75), pp. 503-510. Numbers N_3.
R. B. Banks, Slicing Pizzas, Racing Turtles and Further Adventures in Applied Mathematics, Princeton Univ. Press, 1999. See p. 27.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 72, Problem 2.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 80.
H. E. Dudeney, Amusements in Mathematics, Nelson, London, 1917, page 177.
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).
T. H. Stickels, Mindstretching Puzzles. Sterling, NY, 1994 p. 85.
W. A. Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 30.
A. M. Yaglom and I. M. Yaglom: Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, p. 13, #45 (First published: San Francisco: Holden-Day, Inc., 1964)

T. D. Noe, Table of n, a(n) for n = 0..1000
P. Alexandersson and O. Nabawanda, Peaks are preserved under run-sorting, arXiv:2104.04220 [math.CO], 2021.
Mohamadou Bachabi and Alain S. Togbé, Products of Fermat or Mersenne numbers in some sequences, Math. Comm. (2024) Vol. 29, 265-285.
A. M. Baxter and L. K. Pudwell, Ascent sequences avoiding pairs of patterns, 2014.
M. L. Cornelius, Variations on a geometric progression, Mathematics in School, 4 (No. 3, May 1975), p. 32. (Annotated scanned copy)
F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.
R. K. Guy, Letter to N. J. A. Sloane
Zachary Hoelscher, Semicomplete Arithmetic Sequences, Division of Hypercubes, and the Pell Constant, arXiv:2102.07083 [math.NT], 2021. Mentions this sequence.
Marie Lejeune, On the k-binomial equivalence of finite words and k-binomial complexity of infinite words, Ph. D. Thesis, Université de Liège (Belgium, 2021).
D. A. Lind, On a class of nonlinear binomial sums, Fib. Quart., 3 (1965), 292-298.
Svante Linusson, The number of M-sequences and f-vectors, Combinatorica, vol 19 no 2 (1999) 255-266.
Toufik Mansour, Howard Skogman, and Rebecca Smith, Sorting inversion sequences, arXiv:2401.06662 [math.CO], 2024. See page 7.
R. J. Mathar, The number of binary mxm matrices with at most k 1's in each row or column, (2014) Table 3 column 1.
Ângela Mestre and José Agapito, Square Matrices Generated by Sequences of Riordan Arrays, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.
Sebastian Mizera and Sabrina Pasterski, Celestial Geometry, arXiv:2204.02505 [hep-th], 2022.
Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7.
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
D. J. Price, Some unusual series occurring in n-dimensional geometry, Math. Gaz., 30 (1946), 149-150.
L. Pudwell and A. Baxter, Ascent sequences avoiding pairs of patterns, 2014.
Luis Manuel Rivera, Integer sequences and k-commuting permutations, arXiv preprint arXiv:1406.3081 [math.CO], 2014.
H. P. Robinson, Letter to N. J. A. Sloane, Aug 16 1971, with attachments
Eric Weisstein's World of Mathematics, Cake Number
Eric Weisstein's World of Mathematics, Cube Division by Planes
Eric Weisstein's World of Mathematics, Cylinder Cutting
Eric Weisstein's World of Mathematics, Maximal Clique
Eric Weisstein's World of Mathematics, Space Division by Planes
Eric Weisstein's World of Mathematics, Triangular Graph
Reinhard Zumkeller, Enumerations of Divisors
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Bisections give A100503, A100504.
Row sums of A077028.
Cf. A000124, A003600, A005408, A016813, A086514, A058331, A002522, A161701-A161705, A000127, A161706-A161708, A080856, A161710-A161713, A161715, A006261, A063865, A051601, A077043, A002620, A123596.
Cf. A000027, A047694, A134396, A152947, A283551.

[(n^3+5*n+6)/6: n in [0..50]]; // Vincenzo Librandi, Nov 08 2014

Maple
```
A000125 := n->(n+1)*(n^2-n+6)/6;
```

Table[(n^3 + 5 n + 6)/6, {n, 0, 50}] (* Harvey P. Dale, Jan 19 2013 *)
LinearRecurrence[{4, -6, 4, -1}, {1, 2, 4, 8}, 50] (* Harvey P. Dale, Jan 19 2013 *)
Table[Binomial[n, 3] + n, {n, 20}] (* Eric W. Weisstein, Jul 21 2017 *)

a(n)=(n^2+5)*n/6+1 \\ Charles R Greathouse IV, Jun 15 2011

Vec((1-2*x+2*x^2)/((1-x)^4) + O(x^100)) \\ Altug Alkan, Oct 16 2015

def A000125_gen():  # generator of terms
    a, b, c = 1, 1, 1
    while True:
        yield a
        a, b, c = a+b, b+c, c+1
it = A000125_gen()
A000125_list = [next(it) for  in range(50)]  # _Cole Dykstra, Aug 03 2022

a(n) = (n+1)*(n^2-n+6)/6 = (n^3 + 5*n + 6) / 6.
G.f.: (1 - 2*x + 2x^2)/(1-x)^4. - [Simon Plouffe in his 1992 dissertation.]
E.g.f.: (1 + x + x^2/2 + x^3/6)*exp(x).
a(n) = binomial(n,3) + binomial(n,2) + binomial(n,1) + binomial(n,0). - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
Paraphrasing the previous comment: the sequence is the binomial transform of [1,1,1,1,0,0,0,...]. - Gary W. Adamson, Oct 23 2007
From Ilya Gutkovskiy, Jul 18 2016: (Start)
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4).
a(n) = Sum_{k=0..n} A152947(k+1).
Inverse binomial transform of A134396.
Sum_{n>=0} a(n)/n! = 8*exp(1)/3. (End)
a(n) = -A283551(-n). - Michael Somos, Jul 07 2022
a(n) = A046127(n+1)/2 = A033547(n)/2 + 1. - Jianing Song, Jan 02 2025

Minor typo in comments corrected by Mauro Fiorentini, Jan 02 2018

A008549 Number of ways of choosing at most n-1 items from a set of size 2*n+1.

Original entry on oeis.org

0, 1, 6, 29, 130, 562, 2380, 9949, 41226, 169766, 695860, 2842226, 11576916, 47050564, 190876696, 773201629, 3128164186, 12642301534, 51046844836, 205954642534, 830382690556, 3345997029244, 13475470680616, 54244942336114, 218269673491780, 877940640368572

Offset: 0

N. J. A. Sloane

Area under Dyck excursions (paths ending in 0): a(n) is the sum of the areas under all Dyck excursions of length 2*n (nonnegative walks beginning and ending in 0 with jumps -1,+1).
Number of inversions in all 321-avoiding permutations of [n+1]. Example: a(2)=6 because the 321-avoiding permutations of [3], namely 123,132,312,213,231, have 0, 1, 2, 1, 2 inversions, respectively. - Emeric Deutsch, Jul 28 2003
Convolution of A001791 and A000984. - Paul Barry, Feb 16 2005
a(n) = total semilength of "longest Dyck subpath" starting at an upstep U taken over all upsteps in all Dyck paths of semilength n. - David Callan, Jul 25 2008
[1,6,29,130,562,2380,...] is convolution of A001700 with itself. - Philippe Deléham, May 19 2009
From Ran Pan, Feb 04 2016: (Start)
a(n) is the total number of times that all the North-East lattice paths from (0,0) to (n+1,n+1) bounce off the diagonal y = x to the right. This is related to paired pattern P_2 in Pan and Remmel's link and more details can be found in Section 3.2 in the link.
a(n) is the total number of times that all the North-East lattice paths from (0,0) to (n+1,n+1) horizontally cross the diagonal y = x. This is related to paired pattern P_3 in Pan and Remmel's link and more details can be found in Section 3.3 in the link.
2*a(n) is the total number of times that all the North-East lattice paths from (0,0) to (n+1,n+1) bounce off the diagonal y = x. This is related to paired pattern P_2 and P_4 in Pan and Remmel's link and more details can be found in Section 4.2 in the link.
2*a(n) is the total number of times that all the North-East lattice paths from (0,0) to (n+1,n+1) cross the diagonal y = x. This is related to paired pattern P_3 and P_4 in Pan and Remmel's link and more details can be found in Section 4.3 in the link. (End)
From Gus Wiseman, Jul 17 2021: (Start)
Also the number of integer compositions of 2*(n+1) with alternating sum < 0, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(3) = 29 compositions of 8 are:
  (1,7)  (1,5,2)  (1,1,1,5)  (1,1,1,4,1)  (1,1,1,1,1,3)
  (2,6)  (1,6,1)  (1,1,2,4)  (1,2,1,3,1)  (1,1,1,2,1,2)
  (3,5)  (2,5,1)  (1,2,1,4)  (1,3,1,2,1)  (1,1,1,3,1,1)
                  (1,2,2,3)  (1,4,1,1,1)  (1,2,1,1,1,2)
                  (1,3,1,3)               (1,2,1,2,1,1)
                  (1,3,2,2)               (1,3,1,1,1,1)
                  (1,4,1,2)
                  (1,4,2,1)
                  (1,5,1,1)
                  (2,1,1,4)
                  (2,2,1,3)
                  (2,3,1,2)
                  (2,4,1,1)
Also the number of integer compositions of 2*(n+1) with reverse-alternating sum < 0. For a bijection, keep the odd-length compositions and reverse the even-length ones.
Also the number of 2*(n+1)-digit binary numbers with more 0's than 1's. For example, the a(2) = 6 binary numbers are: 100000, 100001, 100010, 100100, 101000, 110000; or in decimal: 32, 33, 34, 36, 40, 48.
(End)

			a(2) = 6 because there are 6 ways to choose at most 1 item from a set of size 5: You can choose the empty set, or you can choose any of the five one-element sets.
G.f. = x + 6*x^2 + 29*x^3 + 130*x^4 + 562*x^5 + 2380*x^6 + 9949*x^7 + ...

D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.

Indranil Ghosh, Table of n, a(n) for n = 0..1500 (terms 0..200 from T. D. Noe)
José Agapito, Ângela Mestre, Maria M. Torres, and Pasquale Petrullo, On One-Parameter Catalan Arrays, Journal of Integer Sequences, 18 (2015), Article 15.5.1.
Octavio Arizmendi, Daniel Perales, and Josue Vazquez-Becerra, Finite Free Convolution: Infinitesimal Distributions, arXiv:c [math.PR], 2025. See p. 34.
Jean Christophe Aval, Adrien Boussicault, Patxi Laborde-Zubieta, and Mathias Pétréolle, Generating series of Periodic Parallelogram polyominoes, arXiv:1612.03759, 2016.
Roland Bacher, On generating series of complementary plane trees, arXiv:math/0409050 [math.CO], 2004.
Vijay Balasubramanian, Javier M. Magan, and Qingyue Wu, A Tale of Two Hungarians: Tridiagonalizing Random Matrices, arXiv:2208.08452 [hep-th], 2022.
Cyril Banderier, Analytic combinatorics of random walks and planar maps, Ph. D. Thesis, 2001. [Broken link]
Adrien Boussicault and P. Laborde-Zubieta, Periodic Parallelogram Polyominoes, arXiv preprint arXiv:1611.03766 [math.CO], 2016.
AJ Bu, Explicit Generating Functions for the Sum of the Areas Under Dyck and Motzkin Paths (and for Their Powers), arXiv:2310.17026 [math.CO], 2023.
AJ Bu and Doron Zeilberger, Using Symbolic Computation to Explore Generalized Dyck Paths and Their Areas, arXiv:2305.09030 [math.CO], 2023.
Alexander Burstein and Sergi Elizalde, Total occurrence statistics on restricted permutations, arXiv:1305.3177 [math.CO], 2013.
Robin Chapman, Moments of Dyck paths, Discrete Math., 204 (1999), 113-117.
Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, Pinnacle sets of signed permutations, arXiv:2301.02628 [math.CO], 2023.
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
Milan Janjić, Pascal Matrices and Restricted Words, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.
Niklas G. Johansson, Efficient Simulation of the Deutsch-Jozsa Algorithm, Master's Project, Department of Electrical Engineering & Department of Physics, Chemistry and Biology, Linkoping University, April, 2015.
Miles Jones, Sergey Kitaev, and Jeffrey Remmel, Frame patterns in n-cycles, arXiv preprint arXiv:1311.3332 [math.CO], 2013.
James A. Mingo and Josue Vazquez-Becerra, The Asymptotic Infinitesimal Distribution of a Real Wishart Random Matrix, arXiv:2112.15231 [math.PR], 2021.
Henri Mühle, Symmetric Chain Decompositions and the Strong Sperner Property for Noncrossing Partition Lattices, arXiv:1509.06942v1 [math.CO], 2015.
Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.
Elisa Pergola, Two bijections for the area of Dyck paths, Discrete Math., 241 (2001), 435-447.
Wen-jin Woan, Area of Catalan Paths, Discrete Math., 226 (2001), 439-444.

Cf. A038608, A045894, A057571, A109196, A153338.
Odd bisection of A294175 (even is A000346).
For integer compositions of 2*(n+1) with alternating sum k < 0 we have:
- The opposite (k > 0) version is A000302.
- The weak (k <= 0) version is (also) A000302.
- The k = 0 version is A001700 or A088218.
- The reverse-alternating version is also A008549 (this sequence).
- These compositions are ranked by A053754 /\ A345919.
- The complement (k >= 0) is counted by A114121.
- The case of reversed integer partitions is A344743(n+1).
A011782 counts compositions.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
A344610 counts partitions by sum and positive reverse-alternating sum.
A345197 counts compositions by length and alternating sum.
Cf. A000070, A001791, A007318, A025047, A027306, A032443, A058622, A120452, A163493, A239830, A344611.

[4^n-Binomial(2*n+1, n): n in [0..30]]; // Vincenzo Librandi, Feb 04 2016

A008549:=n->4^n-binomial(2*n+1,n): seq(A008549(n), n=0..30);

Table[4^n-Binomial[2n+1,n],{n,0,30}] (* Harvey P. Dale, May 11 2011 *)
a[ n_] := If[ n<-4, 0, 4^n - Binomial[2 n + 2, n + 1] / 2] (* Michael Somos, Jan 25 2014 *)

{a(n)=if(n<0, 0, 4^n - binomial(2*n+1, n))} /* Michael Somos Oct 31 2006 */

{a(n) = if( n<-4, 0, n++; (4^n / 2 - binomial(2*n, n)) / 2)} /* Michael Somos, Jan 25 2014 */

import math
def C(n,r):
    f=math.factorial
    return f(n)/f(r)/f(n-r)
def A008549(n):
    return int((4**n)-C(2*n+1,n)) # Indranil Ghosh, Feb 18 2017

a(n) = 4^n - C(2*n+1, n).
a(n) = Sum_{k=1..n} Catalan(k)*4^(n-k): convolution of Catalan numbers and powers of 4.
G.f.: x*c(x)^2/(1 - 4*x), c(x) = g.f. of Catalan numbers. - Wolfdieter Lang
Note Sum_{k=0..2*n+1} binomial(2*n+1, k) = 2^(2n+1). Therefore, by the symmetry of Pascal's triangle, Sum_{k=0..n} binomial(2*n+1, k) = 2^(2*n) = 4^n. This explains why the following two expressions for a(n) are equal: Sum_{k=0..n-1} binomial(2*n+1, k) = 4^n - binomial(2*n+1, n). - Dan Velleman
G.f.: (2*x^2 - 1 + sqrt(1 - 4*x^2))/(2*(1 + 2*x)*(2*x - 1)*x^3).
a(n) = Sum_{k=0..n} C(2*k, k)*C(2*(n-k), n-k-1). - Paul Barry, Feb 16 2005
Second binomial transform of 2^n - C(n, floor(n/2)) = A045621(n). - Paul Barry, Jan 13 2006
a(n) = Sum_{0 < i <= k < n} binomial(n, k+i)*binomial(n, k-i). - Mircea Merca, Apr 05 2012
D-finite with recurrence (n+1)*a(n) + 2*(-4*n-1)*a(n-1) + 8*(2*n-1)*a(n-2) = 0. - R. J. Mathar, Dec 03 2012
0 = a(n) * (256*a(n+1) - 224*a(n+2) + 40*a(n+3)) + a(n+1) * (-32*a(n+1) + 56*a(n+2) - 14*a(n+3)) + a(n+2) * (-2*a(n+2) + a(n+3)) if n > -5. - Michael Somos, Jan 25 2014
Convolution square is A045894. - Michael Somos, Jan 25 2014
HANKEL transform is [0, -1, 2, -3, 4, -5, ...]. - Michael Somos, Jan 25 2014
BINOMIAL transform of [0, 0, 1, 3, 11, 35,...] (A109196) is [0, 0, 1, 6, 29, 130, ...]. - Michael Somos, Jan 25 2014
(n+1) * a(n) = A153338(n+1). - Michael Somos, Jan 25 2014
a(n) = Sum_{m = n+2..2*n+1} binomial(2*n+1,m), n >= 0. - Wolfdieter Lang, May 22 2015
E.g.f.: (exp(2*x) - BesselI(0,2*x) - BesselI(1,2*x))*exp(2*x). - Ilya Gutkovskiy, Aug 30 2016

Better description from Dan Velleman (djvelleman(AT)amherst.edu), Dec 01 2000

A032443 a(n) = Sum_{i=0..n} binomial(2*n, i).

Original entry on oeis.org

1, 3, 11, 42, 163, 638, 2510, 9908, 39203, 155382, 616666, 2449868, 9740686, 38754732, 154276028, 614429672, 2448023843, 9756737702, 38897306018, 155111585372, 618679078298, 2468152192772, 9848142504068, 39301087452632, 156861290196878, 626155256640188

Offset: 0

J. H. Conway, Dec 11 1999

Array interpretation: first row is filled with 1's, first column with powers of 2, b(i,j) = b(i-1,j) + b(i,j-1); then a(n) = b(n,n). - Benoit Cloitre, Apr 01 2002
   1   1   1   1   1   1   1 ...
   2   3   4   5   6   7   8 ...
   4   7  11  16  22 ...
   8  15  26  42  64 ...
  16  31  ..  99 163 ...
From Gary W. Adamson, Dec 27 2008: (Start)
This is an analog of the Catalan sequence: Let M denote an infinite Cartan matrix (-1's in the super and subdiagonals and (2,2,2,...) in the main diagonal which we modify to (1,2,2,2,...)). Then A000108 can be generated by accessing the leftmost term in M^n * [1,0,0,0,...]. Change the operation to M^n * [1,2,3,...] to get this sequence. Or, take iterates M * [1,2,3,...] -> M * ANS, -> M * ANS,...; accessing the leftmost term. (End)
Convolved with the Catalan sequence, A000108: (1, 1, 2, 5, 14, ...) = powers of 4, A000302: (1, 4, 16, 64, ...). - Gary W. Adamson, May 15 2009
Row sums of A094527. - Paul Barry, Sep 07 2009
Hankel transform of the aeration of this sequence is C(n+2, 2). - Paul Barry, Sep 26 2009
Number of 4-ary words of length n in which the number of 1's does not exceed the number of 0's. - David Scambler, Aug 14 2012
Number of options available to a voter who has up to n (0-n) votes to allot among 2n candidates. - Lorraine Lee, Apr 27 2019
2*a(n-1) is the number of all triangulations that can be obtained from a Möbius strip with n chosen points on its edge. See Bazier-Matte et al. - Michel Marcus, Sep 15 2020

			G.f. = 1 + 3*x + 11*x^2 + 42*x^3 + 163*x^4 + 638*x^5 + 2510*x^6 + 9908*x^7 + ...
According to the second formula, we see the fourth row of Pascal's triangle has the terms 1,4,6,4,1 and the partial sums are 1,5,11,15,16. Using these we get 1*1 + 4*5 + 6*11 + 4*15*1*16 = 1 + 20 + 66 + 60 + 16 = 163 = a(4). - _J. M. Bergot_, Apr 29 2014

D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Véronique Bazier-Matte, Ruiyan Huang, and Hanyi Luo, Number of Triangulations of a Möbius Strip, arXiv:2009.05785 [math.CO], 2020.
A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, Permutations defining convex permutominoes, J. Int. Seq. 10 (2007) # 07.9.7.
Celeste Damiani, Paul Martin, and Eric C. Rowell, Generalisations of Hecke algebras from Loop Braid Groups, arXiv:2008.04840 [math.GT], 2020.
M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.

Binomial transform of A027914. Hankel transform is {1, 2, 3, 4, ..., n, ...}.

Cf. A000108, A000302, A110166.

[(4^n+Binomial(2*n, n))/2:n in [0.. 30]]; // Vincenzo Librandi, Oct 18 2014

A032443:=n->(4^n + binomial(2*n, n))/2; seq(A032443(n), n=0..30); # Wesley Ivan Hurt, Apr 15 2014

a[ n_] := If[ n<-3, 0, (4^n + Binomial[2 n, n]) / 2]; Table[a[n], {n, 0, 30}] (* Michael Somos, Jan 25 2014 *)

A032443 = n->sum(i=0,n,binomial(2*n,i)) \\ M. F. Hasler, Jan 02 2014

A032443 = n->binomial(2*n-1,n)+4^n\2 \\ M. F. Hasler, Jan 02 2014

{a(n) = if( n<-3, 0, (4^n + binomial(2*n, n)) / 2)} /* Michael Somos, Jan 25 2014 */

a(n) = (4^n+binomial(2*n, n))/2. - David W. Wilson
a(n) = Sum_{0 <= i_1 <= i_2 <= n} binomial(n, i_2) * binomial(n, i_1+i_2). - Benoit Cloitre, Oct 14 2004
Sequence with interpolated zeros has a(n) = Sum_{k=0..floor(n/2)} (if((n-2k) mod 2)=0, C(n, k), 0). - Paul Barry, Jan 14 2005
a(n) = Sum_{k=0..n} C(n+k-1, k)*2^(n-k). - Paul Barry, Sep 28 2007
E.g.f.: exp(2*x)*(exp(2*x) + BesselI(0,2*x))/2. For BesselI see Abramowitz-Stegun (reference and link under A008277), p. 375, eq. 9.6.10. See also A000984 for its e.g.f. - Wolfdieter Lang, Jan 16 2012
From Sergei N. Gladkovskii, Aug 13 2012: (Start)
G.f.: (1/sqrt(1-4*x) + 1/(1-4*x))/2 = G(0)/2 where G(k) = 1 + ((2*k)!)/(k!)^2/(4^k - 4*x*(16^k)/( 4*x*(4^k) + ((2*k)!)/(k!)^2/G(k+1))); (continued fraction).
E.g.f.: G(0)/2 where G(k) = 1 + ((2*k)!)/(k!)^2/(4^k - 4*x*(16^k)/( 4*x*(4^k) + (k+1)*((2*k)!)/(k!)^2/G(k+1))); (continued fraction).
(End)
O.g.f.: (1 - x*(2 + c(x)))/(1 - 4*x)^(3/2), with c the o.g.f. of A000108 (Catalan). - Wolfdieter Lang, Nov 22 2012
D-finite with recurrence: n*a(n) + 2*(-4*n+3)*a(n-1) + 8*(2*n-3)*a(n-2) = 0. - R. J. Mathar, Dec 04 2012
a(n) = binomial(2*n-1,n) + floor(4^n/2), or a(n+1) = A001700(n) + A004171(n), for all n >= 0. See A000346 for the difference. - M. F. Hasler, Jan 02 2014
0 = a(n) * (256*a(n+1) - 224*a(n+2) + 40*a(n+3)) + a(n+1) * (-32*a(n+1) + 56*a(n+2) - 14*a(n+3)) + a(n+2) * (-2*a(n+2) + a(n+3)) if n > -4. - Michael Somos, Jan 25 2014
a(n) = coefficient of x^n in (4*x + 1 / (1 + x))^n. - Michael Somos, Jan 25 2014
Binomial transform is A110166. - Michael Somos, Jan 25 2014
Asymptotics: a(n) ~ 2^(2*n-1)*(1+1/sqrt(Pi*n)). - Fung Lam, Apr 13 2014
Self-convolution is A240879. - Fung Lam, Apr 13 2014
a(0) = 1, a(n+1) = A001700(n) + 2^(2n+1). - Philippe Deléham, Oct 11 2014
exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + 3*x + 10*x^2 + 35*x^3 + 126*x^4 + ... is the o.g.f. for A001700. - Peter Bala, Jul 21 2015
a(n) = 4*a(n-1) - A000108(n-1). - Bob Selcoe, Apr 02 2017
a(n) = [x^n] 1/((1 - x)^n*(1 - 2*x)). - Ilya Gutkovskiy, Oct 12 2017
The Gauss congruences a(n*p^k) == a(n*p^(k-1)) (mod p^k) hold for prime p and positive integers n and k. - Peter Bala, Jan 08 2022
O.g.f.: ( hypergeom([1/4, 3/4], [1/2], 4*x) )^2. - Peter Bala, Mar 04 2022
a(n) = binomial(2*n, n) * hypergeom([1, -n], [n + 1], -1). - Peter Luschny, Oct 06 2023

A058622 a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).

Original entry on oeis.org

0, 1, 1, 4, 5, 16, 22, 64, 93, 256, 386, 1024, 1586, 4096, 6476, 16384, 26333, 65536, 106762, 262144, 431910, 1048576, 1744436, 4194304, 7036530, 16777216, 28354132, 67108864, 114159428, 268435456, 459312152, 1073741824, 1846943453

Offset: 0

Yong Kong (ykong(AT)curagen.com), Dec 29 2000

a(n) is the number of n-digit binary sequences that have more 1's than 0's. - Geoffrey Critzer, Jul 16 2009
Maps to the number of walks that end above 0 on the number line with steps being 1 or -1. - Benjamin Phillabaum, Mar 06 2011
Chris Godsil observes that a(n) is the independence number of the (n+1)-folded cube graph; proof is by a Cvetkovic's eigenvalue bound to establish an upper bound and a direct construction of the independent set by looking at vertices at an odd (resp., even) distance from a fixed vertex when n is odd (resp., even). - Stan Wagon, Jan 29 2013
Also the number of subsets of {1,2,...,n} that contain more odd than even numbers.  For example, for n=4, a(4)=5 and the 5 subsets are {1}, {3}, {1,3}, {1,2,3}, {1,3,4}. See A014495 when same number of even and odd numbers. - Enrique Navarrete, Feb 10 2018
Also half the number of length-n binary sequences with a different number of zeros than ones. This is also the number of integer compositions of n with nonzero alternating sum, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. Also the number of integer compositions of n+1 with alternating sum <= 0, ranked by A345915 (reverse: A345916). - Gus Wiseman, Jul 19 2021

			G.f. = x + x^2 + 4*x^3 + 5*x^4 + 16*x^5 + 22*x^6 + 64*x^7 + 93*x^8 + ...
From _Gus Wiseman_, Jul 19 2021: (Start)
The a(1) = 1 through a(5) = 16 compositions with nonzero alternating sum:
  (1)  (2)  (3)      (4)      (5)
            (1,2)    (1,3)    (1,4)
            (2,1)    (3,1)    (2,3)
            (1,1,1)  (1,1,2)  (3,2)
                     (2,1,1)  (4,1)
                              (1,1,3)
                              (1,2,2)
                              (1,3,1)
                              (2,1,2)
                              (2,2,1)
                              (3,1,1)
                              (1,1,1,2)
                              (1,1,2,1)
                              (1,2,1,1)
                              (2,1,1,1)
                              (1,1,1,1,1)
(End)

A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992, Eq. (4.2.1.7)

G. C. Greubel, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Folded Cube Graph
Eric Weisstein's World of Mathematics, Independence Number

The odd bisection is A000302.
The even bisection is A000346.
The following relate to compositions with nonzero alternating sum:
- The complement is counted by A001700 or A138364.
- The version for alternating sum > 0 is A027306.
- The unordered version is A086543 (even bisection: A182616).
- The version for alternating sum < 0 is A294175.
- These compositions are ranked by A345921.
A011782 counts compositions.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A345197 counts compositions by length and alternating sum.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218, ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000070, A000097, A007318, A008549, A034871, A114121, A120452, A163493, A210736, A239830, A344611.

[(2^n -(1+(-1)^n)*Binomial(n, Floor(n/2))/2)/2: n in [0..40]]; // G. C. Greubel, Aug 08 2022

Table[Sum[Binomial[n, Floor[n/2 + i]], {i, 1, n}], {n, 0, 32}] (* Geoffrey Critzer, Jul 16 2009 *)
a[n_] := If[n < 0, 0, (2^n - Boole[EvenQ @ n] Binomial[n, Quotient[n, 2]])/2]; (* Michael Somos, Nov 22 2014 *)
a[n_] := If[n < 0, 0, n! SeriesCoefficient[(Exp[2 x] - BesselI[0, 2 x])/2, {x, 0, n}]]; (* Michael Somos, Nov 22 2014 *)
Table[2^(n - 1) - (1 + (-1)^n) Binomial[n, n/2]/4, {n, 0, 40}] (* Eric W. Weisstein, Mar 21 2018 *)
CoefficientList[Series[2 x/((1-2x)(1 + 2x + Sqrt[(1+2x)(1-2x)])), {x, 0, 40}], x] (* Eric W. Weisstein, Mar 21 2018 *)
ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],ats[#]!=0&]],{n,0,15}] (* Gus Wiseman, Jul 19 2021 *)

a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n\2); \\ Michel Marcus, Dec 30 2015

my(x='x+O('x^100)); concat(0, Vec(2*x/((1-2*x)*(1+2*x+((1+2*x)*(1-2*x))^(1/2))))) \\ Altug Alkan, Dec 30 2015

from math import comb
def A058622(n): return (1<>1)>>1) if n else 0 # Chai Wah Wu, Aug 25 2025

[(2^n - binomial(n, n//2)*((n+1)%2))/2 for n in (0..40)] # G. C. Greubel, Aug 08 2022

a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).
a(n) = Sum_{i=0..floor((n-1)/2)} binomial(n, i).
G.f.: 2*x/((1-2*x)*(1+2*x+((1+2*x)*(1-2*x))^(1/2))). - Vladeta Jovovic, Apr 27 2003
E.g.f: (e^(2x)-I_0(2x))/2 where I_n is the Modified Bessel Function. - Benjamin Phillabaum, Mar 06 2011
Logarithmic derivative of the g.f. of A210736 is a(n+1). - Michael Somos, Nov 22 2014
Even index: a(2n) = 2^(n-1) - A088218(n). Odd index: a(2n+1) = 2^(2n). - Gus Wiseman, Jul 19 2021
D-finite with recurrence n*a(n) +2*(-n+1)*a(n-1) +4*(-n+1)*a(n-2) +8*(n-2)*a(n-3)=0. - R. J. Mathar, Sep 23 2021
a(n) = 2^n-A027306(n). - R. J. Mathar, Sep 23 2021
A027306(n) - a(n) = A126869(n). - R. J. Mathar, Sep 23 2021

A000127 Maximal number of regions obtained by joining n points around a circle by straight lines. Also number of regions in 4-space formed by n-1 hyperplanes.

Original entry on oeis.org

1, 2, 4, 8, 16, 31, 57, 99, 163, 256, 386, 562, 794, 1093, 1471, 1941, 2517, 3214, 4048, 5036, 6196, 7547, 9109, 10903, 12951, 15276, 17902, 20854, 24158, 27841, 31931, 36457, 41449, 46938, 52956, 59536, 66712, 74519, 82993, 92171, 102091, 112792, 124314, 136698

Offset: 1

N. J. A. Sloane

a(n) is the sum of the first five terms in the n-th row of Pascal's triangle. - Geoffrey Critzer, Jan 18 2009
{a(k): 1 <= k <= 5} = divisors of 16. - Reinhard Zumkeller, Jun 17 2009
Equals binomial transform of [1, 1, 1, 1, 1, 0, 0, 0, ...]. - Gary W. Adamson, Mar 02 2010
From Bernard Schott, Apr 05 2021: (Start)
As a(n) = 2^(n-1) for n = 1..5, it is misleading to believe that a(n) = 2^(n-1) for n > 5 (see Patrick Popescu-Pampu link); other curiosities: a(6) = 2^5 - 1 and a(10) = 2^8.
The sequence of the first differences is A000125, the sequence of the second differences is A000124, the sequence of the third differences is A000027 and the sequence of the fourth differences is the all 1's sequence A000012 (see J. H. Conway and R. K. Guy reference, p. 80). (End)
a(n) is the number of binary words of length n matching the regular expression 0*1*0*1*0*. A000124 and A000125 count binary words of the form 0*1*0* and 1*0*1*0*, respectively. - Manfred Scheucher, Jun 22 2023

			a(7)=99 because the first five terms in the 7th row of Pascal's triangle are 1 + 7 + 21 + 35 + 35 = 99. - _Geoffrey Critzer_, Jan 18 2009
G.f. = x + 2*x^2 + 4*x^3 + 8*x^4 + 16*x^5 + 31*x^6 + 57*x^7 + 99*x^8 + 163*x^9 + ...

R. B. Banks, Slicing Pizzas, Racing Turtles and Further Adventures in Applied Mathematics, Princeton Univ. Press, 1999. See p. 28.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 72, Problem 2.
J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, Chap. 3.
J. H. Conway and R. K. Guy, Le Livre des Nombres, Eyrolles, 1998, p. 80.
J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique Des Nombres, Problem 33 pp. 18; 128 Ellipses Paris 2004.
A. Deledicq and D. Missenard, A La Recherche des Régions Perdues, Math. & Malices, No. 22 Summer 1995 issue pp. 22-3 ACL-Editions Paris.
M. Gardner, Mathematical Circus, pp. 177; 180-1 Alfred A. Knopf NY 1979.
M. Gardner, The Colossal Book of Mathematics, 2001, p. 561.
James Gleick, Faster, Vintage Books, NY, 2000 (see pp. 259-261).
M. de Guzman, Aventures Mathématiques, Prob. B pp. 115-120 PPUR Lausanne 1990.
Ross Honsberger; Mathematical Gems I, Chap. 9.
Ross Honsberger; Mathematical Morsels, Chap. 3.
Jeux Mathématiques et Logiques, Vol. 3 pp. 12; 51 Prob. 14 FFJM-SERMAP Paris 1988.
J. N. Kapur, Reflections of a Mathematician, Chap.36, pp. 337-343, Arya Book Depot, New Delhi 1996.
C. D. Miller, V. E. Heeren, J. Hornsby, M. L. Morrow and J. Van Newenhizen, Mathematical Ideas, Tenth Edition, Pearson, Addison-Wesley, Boston, 2003, Cptr 1, 'The Art of Problem Solving, page 6.
I. Niven, Mathematics of Choice, pp. 158; 195 Prob. 40 NML 15 MAA 1965.
C. S. Ogilvy, Tomorrow's Math, pp. 144-6 OUP 1972.
Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, page 252-255.
Alfred S. Posamentier & Ingmar Lehmann, The (Fabulous) Fibonacci Numbers, Prometheus Books, NY, 2007, page 81-87.
A. M. Robert, A Course in p-adic Analysis, Springer-Verlag, 2000; p. 213.
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).

T. D. Noe, Table of n, a(n) for n = 1..1000
Alan Calvitti, Illustration of initial terms
M. L. Cornelius, Variations on a geometric progression, Mathematics in School, 4 (No. 3, May 1975), p. 32. (Annotated scanned copy)
Colin Defant, Meeting Covered Elements in nu-Tamari Lattices, arXiv:2104.03890 [math.CO], 2021.
M. Griffiths, Remodified Bessel Functions via Coincidences and Near Coincidences, Journal of Integer Sequences, Vol. 14 (2011), Article 11.7.1.
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
R. K. Guy, Letter to N. J. A. Sloane
D. A. Lind, On a class of nonlinear binomial sums, Fib. Quart., 3 (1965), 292-298.
Math Forum, Regions of a circle Cut by Chords to n points.
R. J. Mathar, The number of binary nxm matrices with at most k 1's in each row or column, (2014) Table 4 column 1.
Ângela Mestre and José Agapito, Square Matrices Generated by Sequences of Riordan Arrays, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.
Leo Moser and W. Bruce Ross, Mathematical Miscellany, On the Danger of Induction, Mathematics Magazine, Vol. 23, No. 2 (Nov. - Dec., 1949), pp. 109-114.
M. Noy, A Short Solution of a Problem in Combinatorial Geometry, Mathematics Magazine, pp. 52-3 69(1) 1996 MAA.
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
Patrick Popescu-Pampu, Démarrage trompeur, Images des Mathématiques, CNRS, 2017, rediffusion 2021 (in French).
D. J. Price, Some unusual series occurring in n-dimensional geometry, Math. Gaz., 30 (1946), 149-150.
H. P. Robinson, Letter to N. J. A. Sloane, Mar 21 1985
Grant Sanderson, Circle division solution, video, 2015.
Grant Sanderson, Circle division solution, updated video (2023).
K. Uhland, A Blase of Glory
K. Uhland, Moser's Problem
Prasad Balakrishnan Warrier, The physiognomy of the Erdős-Szekeres conjecture (happy ending problem), Math. Student (Indian Math. Soc., 2024) Vol. 93, Nos. 3-4, 28-48.
Eric Weisstein's World of Mathematics, Circle Division by Chords
Eric Weisstein's World of Mathematics, Strong Law of Small Numbers
Reinhart Zumkeller, Enumerations of Divisors
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A000012, A000027, A000124, A000125, A002522, A005408, A016813, A086514, A058331, A161701, A161702, A161703, A161704, A161706, A161707, A161708, A161710, A080856, A161711, A161712, A161713, A161715, A006261, A007318, A008859-A008863, A219531, A223718.

a000127 = sum . take 5 . a007318_row  -- Reinhard Zumkeller, Nov 24 2012

[(n^4-6*n^3+23*n^2-18*n+24)/24: n in [1..50]]; // Vincenzo Librandi, Feb 16 2015

A000127 := n->(n^4 - 6*n^3 + 23*n^2 - 18*n + 24)/24;
with (combstruct):ZL:=[S, {S=Sequence(U, card=1)}, unlabeled]: seq(count(subs(r=6, ZL), size=m), m=0..41); # Zerinvary Lajos, Mar 08 2008

f[n_] := Sum[Binomial[n, i], {i, 0, 4}]; Table[f@n, {n, 0, 40}] (* Robert G. Wilson v, Jun 29 2007 *)
Total/@Table[Binomial[n-1,k],{n,50},{k,0,4}] (* or *) LinearRecurrence[ {5,-10,10,-5,1},{1,2,4,8,16},50] (* Harvey P. Dale, Aug 24 2011 *)
Table[(n^4 - 6 n^3 + 23 n^2 - 18 n + 24) / 24, {n, 100}] (* Vincenzo Librandi, Feb 16 2015 *)
a[ n_] := Binomial[n, 4] + Binomial[n, 2] + 1; (* Michael Somos, Dec 23 2017 *)

a(n)=(n^4-6*n^3+23*n^2-18*n+24)/24 \\ Charles R Greathouse IV, Mar 22 2016

{a(n) = binomial(n, 4) + binomial(n, 2) + 1}; /* Michael Somos, Dec 23 2017 */

def A000127(n): return n*(n*(n*(n - 6) + 23) - 18)//24 + 1 # Chai Wah Wu, Sep 18 2021

a(n) = C(n-1, 4) + C(n-1, 3) + ... + C(n-1, 0) = A055795(n) + 1 = C(n, 4) + C(n-1, 2) + n.
a(n) = Sum_{k=0..2} C(n, 2k). - Joel Sanderi (sanderi(AT)itstud.chalmers.se), Sep 08 2004
a(n) = (n^4 - 6*n^3 + 23*n^2 - 18*n + 24)/24.
G.f.: (1 - 3*x + 4*x^2 - 2*x^3 + x^4)/(1-x)^5. (for offset 0) - Simon Plouffe in his 1992 dissertation
E.g.f.: (1 + x + x^2/2 + x^3/6 + x^4/24)*exp(x) (for offset 0). [Typos corrected by Juan M. Marquez, Jan 24 2011]
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5), n > 4. - Harvey P. Dale, Aug 24 2011
a(n) = A000124(A000217(n-1)) - n*A000217(n-2) - A034827(n), n > 1. - Melvin Peralta, Feb 15 2016
a(n) = A223718(-n). - Michael Somos, Dec 23 2017
For n > 2, a(n) = n + 1 + sum_{i=2..(n-2)}sum_{j=1..(n-i)}(1+(i-1)(j-1)). - Alec Jones, Nov 17 2019

Formula corrected and additional references from torsten.sillke(AT)lhsystems.com

Additional correction from Jonas Paulson (jonasso(AT)sdf.lonestar.org), Oct 30 2003

A345197 Concatenation of square matrices A(n), each read by rows, where A(n)(k,i) is the number of compositions of n of length k with alternating sum i, where 1 <= k <= n, and i ranges from -n + 2 to n in steps of 2.

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 2, 3, 0, 0, 2, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 2, 3, 4, 0, 0, 3, 4, 3, 0, 0, 0, 0, 2, 3, 0, 0, 0, 0, 1, 0, 0, 0

Offset: 0

Gus Wiseman, Jul 03 2021

The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i.

			The matrices for n = 1..7:
  1   0 1   0 0 1   0 0 0 1   0 0 0 0 1   0 0 0 0 0 1   0 0 0 0 0 0 1
      1 0   1 1 0   1 1 1 0   1 1 1 1 0   1 1 1 1 1 0   1 1 1 1 1 1 0
            0 1 0   0 1 2 0   0 1 2 3 0   0 1 2 3 4 0   0 1 2 3 4 5 0
                    0 1 0 0   0 2 2 0 0   0 3 4 3 0 0   0 4 6 6 4 0 0
                              0 0 1 0 0   0 0 2 3 0 0   0 0 3 6 6 0 0
                                          0 0 1 0 0 0   0 0 3 3 0 0 0
                                                        0 0 0 1 0 0 0
Matrix n = 5 counts the following compositions:
           i=-3:        i=-1:          i=1:            i=3:        i=5:
        -----------------------------------------------------------------
   k=1: |    0            0             0               0          (5)
   k=2: |   (14)         (23)          (32)            (41)         0
   k=3: |    0          (131)       (221)(122)   (311)(113)(212)    0
   k=4: |    0       (1211)(1112)  (2111)(1121)         0           0
   k=5: |    0            0          (11111)            0           0

Gus Wiseman, A raster plot of the zeros in A(16).

The number of nonzero terms in each matrix appears to be A000096.
The number of zeros in each matrix appears to be A000124.
Row sums and column sums both appear to be A007318 (Pascal's triangle).
The matrix sums are A131577.
Antidiagonal sums appear to be A163493.
The reverse-alternating version is also A345197 (this sequence).
Antidiagonals are A345907.
Traces are A345908.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A011782 counts compositions.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
A344610 counts partitions by sum and positive reverse-alternating sum.
A344611 counts partitions of 2n with reverse-alternating sum >= 0.
Other tetrangles: A318393, A318816, A320808, A321912.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218, ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k <= 0: counted by A058622(n-1), ranked by A345915/A345916.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k != 0: counted by A058622, ranked by A345921/A345921.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000070, A000097, A000346, A007318, A008549, A025047, A032443, A034871, A114121, A120452, A238279, A239830, A344604.

ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[#]==k&&ats[#]==i&]],{n,0,6},{k,1,n},{i,-n+2,n,2}]

A008949 Triangle read by rows of partial sums of binomial coefficients: T(n,k) = Sum_{i=0..k} binomial(n,i) (0 <= k <= n); also dimensions of Reed-Muller codes.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 4, 7, 8, 1, 5, 11, 15, 16, 1, 6, 16, 26, 31, 32, 1, 7, 22, 42, 57, 63, 64, 1, 8, 29, 64, 99, 120, 127, 128, 1, 9, 37, 93, 163, 219, 247, 255, 256, 1, 10, 46, 130, 256, 382, 466, 502, 511, 512, 1, 11, 56, 176, 386, 638, 848, 968, 1013, 1023, 1024, 1, 12, 67, 232, 562, 1024, 1486, 1816, 1981, 2036, 2047, 2048

Offset: 0

N. J. A. Sloane

The second-left-from-middle column is A000346: T(2n+2, n) = A000346(n). - Ed Catmur (ed(AT)catmur.co.uk), Dec 09 2006
T(n,k) is the maximal number of regions into which n hyperplanes of co-dimension 1 divide R^k (the Cake-Without-Icing numbers). - Rob Johnson, Jul 27 2008
T(n,k) gives the number of vertices within distance k (measured along the edges) of an n-dimensional unit cube, (i.e., the number of vertices on the hypercube graph Q_n whose distance from a reference vertex is <= k). - Robert Munafo, Oct 26 2010
A triangle formed like Pascal's triangle, but with 2^n for n >= 0 on the right border instead of 1. - Boris Putievskiy, Aug 18 2013
For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 04 2013
Consider each "1" as an apex of two sequences: the first is the set of terms in the same row as the "1", but the rightmost term in the row repeats infinitely. Example: the row (1, 4, 7, 8) becomes (1, 4, 7, 8, 8, 8, ...). The second sequence begins with the same "1" but is the diagonal going down and to the right, thus: (1, 5, 16, 42, 99, 219, 466, ...). It appears that for all such sequence pairs, the binomial transform of the first, (1, 4, 7, 8, 8, 8, ...) in this case; is equal to the second: (1, 5, 16, 42, 99, ...). - Gary W. Adamson, Aug 19 2015
Let T* be the infinite tree with root 0 generated by these rules: if p is in T*, then p+1 is in T* and x*p is in T*. Let q(n) be the sum of polynomials in the n-th generation of T*. For n >= 0, row n of A008949 gives the coefficients of q(n+1); e.g., (row 3) = (1, 4, 7, 8) matches x^3 + 4*x^2 + 7*x + 9, which is the sum of the 8 polynomials in the 4th generation of T*. - Clark Kimberling, Jun 16 2016
T(n,k) is the number of subsets of [n]={1,...,n} of at most size k. Equivalently, T(n,k) is the number of subsets of [n] of at least size n-k. Counting the subsets of at least size (n-k) by conditioning on the largest element m of the smallest (n-k) elements of such a subset provides the formula T(n,k) = Sum_{m=n-k..n} C(m-1,n-k-1)*2^(n-m), and, by letting j=m-n+k, we obtain T(n,k) = Sum_{j=0..k} C(n+j-k-1,j)*2^(k-j). - Dennis P. Walsh, Sep 25 2017
If the interval of integers 1..n is shifted up or down by k, making the new interval 1+k..n+k or 1-k..n-k, then T(n-1,n-1-k) (= 2^(n-1)-T(n-1,k-1)) is the number of subsets of the new interval that contain their own cardinal number as an element. - David Pasino, Nov 01 2018

			Triangle begins:
  1;
  1,  2;
  1,  3,  4;
  1,  4,  7,   8;
  1,  5, 11,  15,  16;
  1,  6, 16,  26,  31,  32;
  1,  7, 22,  42,  57,  63,  64;
  1,  8, 29,  64,  99, 120, 127, 128;
  1,  9, 37,  93, 163, 219, 247, 255,  256;
  1, 10, 46, 130, 256, 382, 466, 502,  511,  512;
  1, 11, 56, 176, 386, 638, 848, 968, 1013, 1023, 1024;
  ...

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 376.

Harvey P. Dale, Table of n, a(n) for n = 0..10000
Milica Andelic, C. M. da Fonseca and A. Pereira, The mu-permanent, a new graph labeling, and a known integer sequence, arXiv:1609.04208 [math.CO], 2016.
Stefan Forcey, Planes and axioms, Univ. Akron (2024). See p. 2.
Stefan Forcey, Counting plane arrangements via oriented matroids, arXiv:2504.11461 [math.HO], 2025. See p. 18.
Rob Johnson, Dividing Space.
Norman Lindquist and Gerard Sierksma, Extensions of set partitions, Journal of Combinatorial Theory, Series A 31.2 (1981): 190-198. See Table I.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
Dennis P. Walsh, A note on counting subsets of restricted size
Wikipedia, Bernoulli's triangle
Index entries for triangles and arrays related to Pascal's triangle

Diagonals are given by A000079, A000225, A000295, A002662, A002663, A002664, A035038-A035042.
Columns are given by A000012, A000027, A000124, A000125, A000127, A006261, A008859, A008860, A008861, A008862, A008863. - Ken Shirriff, Jun 28 2011
Row sums sequence is A001792.
T(n, m)= A055248(n, n-m).
Cf. A110555, A007318, A000346, A171886, A228196, A228576.
Cf. also A027306, A249111, A163866, A261363.
Cf. A000071, A001924

T:=Flat(List([0..11],n->List([0..n],k->Sum([0..k],j->Binomial(n+j-k-1,j)*2^(k-j))))); # Muniru A Asiru, Nov 25 2018

a008949 n k = a008949_tabl !! n !! k
a008949_row n = a008949_tabl !! n
a008949_tabl = map (scanl1 (+)) a007318_tabl
-- Reinhard Zumkeller, Nov 23 2012

[[(&+[Binomial(n,j): j in [0..k]]): k in [0..n]]: n in [0..12]]; // G. C. Greubel, Nov 25 2018

A008949 := proc(n,k) local i; add(binomial(n,i),i=0..k) end; # Typo corrected by R. J. Mathar, Oct 26 2010

Table[Length[Select[Subsets[n], (Length[ # ] <= k) &]], {n, 0, 12}, {k, 0, n}] // Grid (* Geoffrey Critzer, May 13 2009 *)
Flatten[Accumulate/@Table[Binomial[n,i],{n,0,20},{i,0,n}]] (* Harvey P. Dale, Aug 08 2015 *)
T[ n_, k_] := If[ n < 0 || k > n, 0, Binomial[n, k] Hypergeometric2F1[1, -k, n + 1 - k, -1]]; (* Michael Somos, Aug 05 2017 *)

A008949(n)=T8949(t=sqrtint(2*n-sqrtint(2*n)),n-t*(t+1)/2)
T8949(r,c)={ 2*c > r || return(sum(i=0,c,binomial(r,i))); 1<M. F. Hasler, May 30 2010

{T(n, k) = if(k>n, 0, sum(i=0, k, binomial(n, i)))}; /* Michael Somos, Aug 05 2017 */

row(n) = my(v=vector(n+1, k, binomial(n,k-1))); vector(#v, k, sum(i=1, k, v[i])); \\ Michel Marcus, Apr 13 2025

[[sum(binomial(n,j) for j in range(k+1)) for k in range(n+1)] for n in range(12)] # G. C. Greubel, Nov 25 2018

From partial sums across rows of Pascal triangle A007318.
T(n, 0) = 1, T(n, n) = 2^n, T(n, k) = T(n-1, k-1) + T(n-1, k), 0 < k < n.
G.f.: (1 - x*y)/((1 - y - x*y)*(1 - 2*x*y)). - Antonio Gonzalez (gonfer00(AT)gmail.com), Sep 08 2009
T(2n,n) = A032443(n). - Philippe Deléham, Sep 16 2009
T(n,k) = 2 T(n-1,k-1) + binomial(n-1,k) = 2 T(n-1,k) - binomial(n-1,k). - M. F. Hasler, May 30 2010
T(n,k) = binomial(n,n-k)* 2F1(1, -k; n+1-k; -1). - Olivier Gérard, Aug 02 2012
For a closed-form formula for arbitrary left and right borders of Pascal like triangle see A228196. - Boris Putievskiy, Aug 18 2013
T(n,floor(n/2)) = A027306(n). - Reinhard Zumkeller, Nov 14 2014
T(n,n) = 2^n, otherwise for 0 <= k <= n-1, T(n,k) = 2^n - T(n,n-k-1). - Bob Selcoe, Mar 30 2017
For fixed j >= 0, lim_{n -> oo} T(n+1,n-j+1)/T(n,n-j) = 2. - Bob Selcoe, Apr 03 2017
T(n,k) = Sum_{j=0..k} C(n+j-k-1,j)*2^(k-j). - Dennis P. Walsh, Sep 25 2017

More terms from Larry Reeves (larryr(AT)acm.org), Mar 23 2000

A114121 Expansion of (sqrt(1 - 4x) + (1 - 2x))/(2(1 - 4x)).

Original entry on oeis.org

1, 2, 7, 26, 99, 382, 1486, 5812, 22819, 89846, 354522, 1401292, 5546382, 21977516, 87167164, 345994216, 1374282019, 5461770406, 21717436834, 86392108636, 343801171354, 1368640564996, 5450095992964, 21708901408216, 86492546019214

Offset: 0

Paul Barry, Feb 13 2006

Second binomial transform of A032443 with interpolated zeros.
a(n) is the total number of lattice points, taken over all Dyck n-paths (A000108), that (i) lie on or above ground level and (ii) lie on or directly below a peak. For example with n = 2, UUDD has 1 peak contributing 3 lattice points--(2, 0), (2, 1) and (2, 2) when the path starts at the origin--and UDUD has 2 peaks, each contributing 2 lattice points and so a(2) = 3 + 4 = 7. - David Callan, Jul 14 2006
Hankel transform is binomial(n + 2, 2). - Paul Barry, Dec 04 2007
Image of (-1)^n under the Riordan array ((1/2)(1/(1 - 4x) + 1/sqrt(1 - 4x)), c(x) - 1), c(x) the g.f. of A000108. - Paul Barry, Jun 15 2008
From Gus Wiseman, Jun 21 2021: (Start)
Also the even bisection of A116406 = number compositions of n with alternating sum >= 0, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. The a(3) = 26 compositions are:
  (6)  (33)  (114)  (1122)  (11112)  (111111)
       (42)  (123)  (1131)  (11121)
       (51)  (132)  (1221)  (11211)
             (213)  (2112)  (12111)
             (222)  (2121)  (21111)
             (231)  (2211)
             (312)  (3111)
             (321)
             (411)
(End)

			G.f. = 1 + 2*x + 7*x^2 + 26*x^3 + 99*x^4 + 382*x^5 + 1486*x^6 + 5812*x^7 + ...

G. C. Greubel, Table of n, a(n) for n = 0..1000
G.-S. Cheon, H. Kim, L. W. Shapiro, Mutation effects in ordered trees, arXiv:1410.1249 [math.CO], 2014
Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.

Cf. A000984, A081294, A088218.
The case of alternating sum = 0 is A001700.
The case of alternating sum < 0 is A008549.
This is the even bisection of A116406.
The restriction to reversed partitions is A344611.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A124754 gives the alternating sum of standard compositions.
A316524 is the alternating sum of the prime indices of n.
A344611 counts partitions of 2n with reverse-alternating sum >= 0.
Cf. A000041, A000070, A000302, A000346, A003242, A027306, A032443, A058622, A058696, A119899, A344607, A344610.

seq(sum(binomial(2*n,2*k+irem(n,2)),k=0..floor((1/2)*n)),n=0..20)
seq(binomial(2*n-1,n)+4^(n-1)-(1/4)*0^n,n=0..20)

a[ n_] := SeriesCoefficient[((1 + 1/Sqrt[1 - 4 x])/2)^2, {x, 0, n}] (* Michael Somos, Dec 31 2013 *)
ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],ats[#]>=0&]],{n,0,15,2}] (* Gus Wiseman, Jun 21 2021 *)

a(n) = Sum_{k=0..n} C(n, k)*2^(n-k-2)*(2^k + C(k, k/2))*(1 + (-1)^k).
a(n) = (A000984(n) + A081294(n))/2.
From Paul Barry, Jun 15 2008: (Start)
G.f.: (1 - 4*x + (1 - 2*x)*sqrt(1 - 4*x))/(2*(1 - 4*x)^(3/2)).
a(n) = Sum_{k=0..n} ( Sum_{j=0..n} C(2*n, n-k-j)*(-1)^j ). (End)
a(n) = Sum_{k=0..n} C(2*n, n-k)*(1 + (-1)^k)/2. - Paul Barry, Aug 06 2009
From Paul Barry, Sep 07 2009: (Start)
a(n) = C(2*n-1, n-1) + (4^n + 3*0^n)/4.
Integral representation a(n) = (1/(2*pi))*(Integral_{x=0..4} x^n/sqrt(x(4 - x))) + (4^n + 0^n)/4. (End)
a(n) = Sum_{k=0..floor(n/2)} C(2*n, 2*k + (n mod 2)). - Mircea Merca, Jun 21 2011
Conjecture: n*a(n) + 2*(3 - 4*n)*a(n-1) + 8*(2*n-3)*a(n-2) = 0. - R. J. Mathar, Nov 07 2012
Conjecture verified using the differential equation (16*x^2-8*x+1)*g'(x) + (8*x-2)*g(x)-2*x=0 satisfied by the G.f. - Robert Israel, Jul 27 2020
a(n) = Sum_{i=0..n} (sum_{j=0..n} binomial(n, i+j)*binomial(n, j-i)). - Yalcin Aktar, Jan 07 2013.
G.f.: (1 + (1 - 4*x)^(-1/2))^2 / 4. Convolution square of A088218. - Michael Somos, Dec 31 2013
0 = (1 + 2*n)*b(n) - (5 + 4*n)*b(n+1) + (4 + 2*n)*b(n+2) if n > 0 where b(n) = a(n) / 4^n. - Michael Somos, Dec 31 2013
0 = b(n+3) * (2*b(n+2) - 7*b(n+1) + 5*b(n)) + b(n+2) * (-b(n+2) + 7*b(n+1) - 7*b(n)) + b(n+1) * (-b(n+1) + 2*b(n)) if n > 0 where b(n) = a(n) / 4^n. - Michael Somos, Dec 31 2013
For n > 0, a(n) = 2^(2n-1) - A008549(n). - Gus Wiseman, Jun 27 2021
a(n) = [x^n] 1/((1-2*x) * (1-x)^(n-1)). - Seiichi Manyama, Apr 10 2024

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

Original entry on oeis.org

0, 0, 0, 1, 5, 16, 42, 99, 219, 466, 968, 1981, 4017, 8100, 16278, 32647, 65399, 130918, 261972, 524097, 1048365, 2096920, 4194050, 8388331, 16776915, 33554106, 67108512, 134217349, 268435049, 536870476, 1073741358, 2147483151, 4294966767, 8589934030

Offset: 0

N. J. A. Sloane

Number of subsets with at least 3 elements of an n-element set.
For n>4, number of simple rank-(n-1) matroids over S_n.
Number of non-interval subsets of {1,2,3,...,n} (cf. A000124). - Jose Luis Arregui (arregui(AT)unizar.es), Jun 27 2006
The partial sums of the second diagonal of A008292 or third column of A123125. - Tom Copeland, Sep 09 2008
a(n) is the number of binary sequences of length n having at least three 0's. - Geoffrey Critzer, Feb 11 2009
Starting with "1" = eigensequence of a triangle with the tetrahedral numbers (1, 4, 10, 20, ...) as the left border and the rest 1's. - Gary W. Adamson, Jul 24 2010
a(n) is also the number of crossing set partitions of [n+1] with two blocks. - Peter Luschny, Apr 29 2011
The Kn24 sums, see A180662, of triangle A065941 equal the terms (doubled) of this sequence minus the three leading zeros. - Johannes W. Meijer, Aug 14 2011
From L. Edson Jeffery, Dec 28 2011: (Start)
Nonzero terms of this sequence can be found from the row sums of the fourth sub-triangle extracted from Pascal's triangle as indicated below by braces:
                     1;
                  1,    1;
               1,    2,    1;
           {1},   3,    3,    1;
        {1,    4},   6,    4,    1;
     {1,    5,   10},  10,    5,    1;
  {1,    6,   15,   20},  15,    6,    1;
  ... (End)
Partial sums of A000295 (Eulerian Numbers, Column 2).
Second differences equal 2^(n-2) - 1, for n >= 4. - Richard R. Forberg, Jul 11 2013
Starting (0, 0, 1, 5, 16, ...) is the binomial transform of (0, 0, 1, 2, 2, 2, ...). - Gary W. Adamson, Jul 27 2015
a(n - 1) is the rank of the divisor class group of the moduli space of stable rational curves with n marked points, see Keel p. 550. - Harry Richman, Aug 10 2024

			a(4) = 5 is the number of crossing set partitions of {1,2,..,5}, card{13|245, 14|235, 24|135, 25|134, 35|124}. - _Peter Luschny_, Apr 29 2011

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
J. H. Conway and N. J. A. Sloane, Low-Dimensional Lattices VI: Voronoi Reduction of Three-Dimensional Lattices, Proc. Royal Soc. London, Series A, 436 (1992), 55-68. (See Table 1.)
W. M. B. Dukes, On the number of matroids on a finite set, arXiv:math/0411557 [math.CO], 2004.
J. Eckhoff, Der Satz von Radon in konvexen Produktstrukturen II, Monat. f. Math., 73 (1969), 7-30.
R. K. Guy, Letter to N. J. A. Sloane
Sean Keel, Intersection theory of moduli space of stable n-pointed curves of genus zero, Trans. Amer. Math. Soc. 330 (1992), 545-574.
Pablo Hueso Merino , The first problem from the 55th Spanish Mathematical Olympiad asks to find the value of a(2019) (see comment from Jose Luis Arregui).
Ângela Mestre and José Agapito, Square Matrices Generated by Sequences of Riordan Arrays, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.
Sergey V. Muravyov, Liudmila I. Khudonogova, and Ekaterina Y. Emelyanova, Interval data fusion with preference aggregation, Measurement (2017), see page 5.
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 (5,-9,7,-2).

a(n) = A055248(n,3).
First differences are A000295.
Cf. A000079, A000124, A000217, A000225, A000247, A002663, A002664, A035038-A035042, A007318, A342352.
Cf. also A000290, A001045.

a002662 n = a002662_list !! n
a002662_list = map (sum . drop 3) a007318_tabl
-- Reinhard Zumkeller, Jun 20 2015

[2^n - 1 - n*(n+1)/2: n in [0..35]]; // Vincenzo Librandi, May 20 2011

A002662 := z**2/(2*z-1)/(z-1)**3; # conjectured by Simon Plouffe in his 1992 dissertation
A002662 := proc(n): 2^n - 1 - n*(n+1)/2 end: seq(A002662(n), n=0..33); # Johannes W. Meijer, Aug 14 2011

With[{nn=40},Join[{0},First[#]-1-Last[#]&/@Thread[{2^Range[nn], Accumulate[ Range[nn]]}]]] (* Harvey P. Dale, May 10 2012 *)
Table[2^n - Binomial[n, 2] - n - 1, {n, 1, 100}] (* Pablo Hueso Merino, Dec 17 2019 *)

a(n)=2^n-1-n*(n+1)/2 \\ Charles R Greathouse IV, Oct 11 2015

def A002662(n): return (1<>1) # Chai Wah Wu, Aug 29 2023

G.f.: x^3/((1-2*x)*(1-x)^3).
a(n) = Sum_{k=0..n} binomial(n,k+3) = Sum_{k=3..n} binomial(n,k). - Paul Barry, Jul 30 2004
a(n+1) = 2*a(n) + binomial(n,2). - Paul Barry, Aug 23 2004
(1, 5, 16, 42, 99, ...) = binomial transform of (1, 4, 7, 8, 8, 8, ...). - Gary W. Adamson, Sep 30 2007
E.g.f.: exp(x)*(exp(x)-x^2/2-x-1). - Geoffrey Critzer, Feb 11 2009
a(n) = n - 2 + 3*a(n-1) - 2*a(n-2), for n >= 2. - Richard R. Forberg, Jul 11 2013
For n>1, a(n) = (1/4)*Sum_{k=1..n-2} 2^k*(n-k-1)*(n-k). For example, (1/4)*(2^1*(4*5) + 2^2*(3*4) + 2^3*(2*3) + 2^4*(1*2)) = 168/4 = 42. - J. M. Bergot, May 27 2014 [edited by Danny Rorabaugh, Apr 19 2015]
Convolution of A001045 and (A000290 shifted by one place). - Oboifeng Dira,  Aug 16 2016
a(n) = Sum_{k=1..n-2} Sum_{i=1..n} (n-k-1) * C(k,i). - Wesley Ivan Hurt, Sep 19 2017
a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4) for n > 3. - Chai Wah Wu, Apr 03 2021
a(n) = a(n-1) + 1 + A000247(n-1). - Harry Richman, Aug 13 2024

cp's OEIS Frontend

A002054 Binomial coefficient C(2n+1, n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

A000125 Cake numbers: maximal number of pieces resulting from n planar cuts through a cube (or cake): C(n+1,3) + n + 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A008549 Number of ways of choosing at most n-1 items from a set of size 2*n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A032443 a(n) = Sum_{i=0..n} binomial(2*n, i).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

Formula

A058622 a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).

Views

Author

Keywords

Comments

Examples

References

Links

A114121 Expansion of (sqrt(1 - 4x) + (1 - 2x))/(2(1 - 4x)).