A247158 -id:A247158 - cp's OEIS frontend

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

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

A048291 Number of {0,1} n X n matrices with no zero rows or columns.

Original entry on oeis.org

1, 1, 7, 265, 41503, 24997921, 57366997447, 505874809287625, 17343602252913832063, 2334958727565749108488321, 1243237913592275536716800402887, 2630119877024657776969635243647463625, 22170632855360952977731028744522744983195423

Offset: 0

Joe Keane (jgk(AT)jgk.org)

Number of relations on n labeled points such that for every point x there exists y and z such that xRy and zRx.
Also the number of edge covers in the complete bipartite graph K_{n,n}. - Eric W. Weisstein, Apr 24 2017
Counts labeled digraphs (loops allowed, no multiarcs) on n nodes where each indegree and each outdegree is >= 1. The corresponding sequence for unlabeled digraphs (1, 5, 55, 1918,... for n >= 1) seems not to be in the OEIS. - R. J. Mathar, Nov 21 2023
These relations form a subsemigroup of the semigroup of all binary relations on [n].  The zero element is the universal relation (all 1's matrix).  See Schwarz link. - Geoffrey Critzer, Jan 15 2024

			a(2) = 7:  |01|  |01|  |10|  |10|  |11|  |11|  |11|
           |10|  |11|  |01|  |11|  |01|  |10|  |11|.

Brendan McKay, Posting to sci.math.research, Jun 14 1999.

T. D. Noe, Table of n, a(n) for n = 0..32
H. Cheballah, S. Giraudo, and R. Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013.
David Dolžan and Gabriel Verret, The automorphism group of the zero-divisor digraph of matrices over an antiring, arXiv:1908.04614 [math.AC], 2019.
R. J. Mathar, The number of nXm matrices with at most k 1's in each row or column, (2014).
Steven Schlicker, Roman Vasquez, and Rachel Wofford, Integer Sequences from Configurations in the Hausdorff Metric Geometry via Edge Covers of Bipartite Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.6.6.
Stefan Schwarz, The semigroup of fully indecomposable relations and Hall relations, Czechoslovak Mathematical Journal, 23 (1973), 151-163.
R. Tauraso, Edge cover time for regular graphs, JIS 11 (2008) 08.4.4.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Eric Weisstein's World of Mathematics, Edge Cover.

Cf. A054976, A104602, A283624, A287065, A173403.
Cf. A055601, A055599, A104601, A086193 (traceless, no loops), A086206, A322661 (adj. matr. undirected edges).
Diagonal of A183109.

seq(add((-1)^(n+k)*binomial(n, k)*(2^k-1)^n, k=0..n), n=0..15); # Robert FERREOL, Mar 10 2017

Flatten[{1,Table[Sum[Binomial[n,k]*(-1)^k*(2^(n-k)-1)^n,{k,0,n}],{n,1,15}]}] (* Vaclav Kotesovec, Jul 02 2014 *)

a(n)=sum(k=0,n,binomial(n,k)*(-1)^k*(2^(n-k)-1)^n)

import math
f = math.factorial
def A048291(n): return sum([(f(n)/f(s)/f(n - s))*(-1)**s*(2**(n - s) - 1)**n for s in range(0, n+1)]) # Indranil Ghosh, Mar 14 2017

a(n) = Sum_{s=0..n} binomial(n, s)*(-1)^s*2^((n-s)*n)*(1-2^(-n+s))^n.
From Vladeta Jovovic, Feb 23 2008: (Start)
E.g.f.: Sum_{n>=0} (2^n-1)^n*exp((1-2^n)*x)*x^n/n!.
a(n) = Sum_{i=0..n} Sum_{j=0..n} (-1)^(i+j)*binomial(n,i)*binomial(n,j)*2^(i*j). (End)
a(n) ~ 2^(n^2). - Vaclav Kotesovec, Jul 02 2014
a(n) = Sum_{s=0..n-1} binomial(n,s)*(-1)^s*A092477(n,n-s), n > 0. - R. J. Mathar, Nov 18 2023

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

A088699 Array read by antidiagonals of coefficients of generating function exp(x)/(1-y-xy).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 7, 4, 1, 1, 5, 13, 13, 5, 1, 1, 6, 21, 34, 21, 6, 1, 1, 7, 31, 73, 73, 31, 7, 1, 1, 8, 43, 136, 209, 136, 43, 8, 1, 1, 9, 57, 229, 501, 501, 229, 57, 9, 1, 1, 10, 73, 358, 1045, 1546, 1045, 358, 73, 10, 1, 1, 11, 91, 529, 1961, 4051, 4051, 1961

Offset: 0

Michael Somos, Oct 08 2003

A(n,m) is the number of ways to pair the elements of two sets (with respectively n and m elements), where each element of either set may be paired with zero or one elements of the other set; number of n X m matrices of zeros and ones with at most one one in each row and column. E.g., A(2,2)=7 because we can pair {A,B} with {C,D} as {AB,CD}, {AC,BD}, {AC,B,D}, {AD,B,C}, {BC,A,D}, {BD,A,C}, or {A,B,C,D}. - Franklin T. Adams-Watters, Feb 06 2006
Compare with A086885. - Peter Bala, Sep 17 2008
A(n,m) is the number of vertex covers and independent vertex sets in the n X m lattice (rook) graph K_n X K_m. - Andrew Howroyd, May 14 2017

			      1       1       1       1       1       1       1       1       1
      1       2       3       4       5       6       7       8       9
      1       3       7      13      21      31      43      57      73
      1       4      13      34      73     136     229     358     529
      1       5      21      73     209     501    1045    1961    3393
      1       6      31     136     501    1546    4051    9276   19081
      1       7      43     229    1045    4051   13327   37633   93289
      1       8      57     358    1961    9276   37633  130922  394353
      1       9      73     529    3393   19081   93289  394353 1441729

Andrew Howroyd, Table of n, a(n) for n = 0..1274
R. J. Mathar, The number of binary nXm matrices with at most k 1's in each row or column, (2014) Table 1.
Eric Weisstein's World of Mathematics, Rook Graph
Eric Weisstein's World of Mathematics, Vertex Cover
Wikipedia, Rook polynomial

Row sums give A081124.
Main diagonal is A002720.
Cf. A099597, A176120.

A088699 := proc(i,j)
    add(binomial(i,k)*binomial(j,k)*k!,k=0..min(i,j)) ;
end proc: # R. J. Mathar, Feb 28 2015

max = 11; se = Series[E^x/(1 - y - x*y), {x, 0, max}, {y, 0, max}] // Normal // Expand; a[i_, j_] := SeriesCoefficient[se, {x, 0, i}, {y, 0, j}]*i!; Flatten[ Table[ a[i - j, j], {i, 0, max}, {j, 0, i}]] (* Jean-François Alcover, May 15 2012 *)

A(i,j)=if(i<0 || j<0,0,i!*polcoeff(exp(x+x*O(x^i))*(1+x)^j,i))

A(i,j)=if(i<0 || j<0,0,i!*polcoeff(exp(x/(1-x)+x*O(x^i))*(1-x)^(i-j-1),i))

A(i,j)=local(M); if(i<0 || j<0,0,M=matrix(j+1,j+1,n,m,if(n==m,1,if(n==m+1,m))); (M^i)[j+1,]*vectorv(j+1,n,1)) /* Michael Somos, Jul 03 2004 */

E.g.f.: exp(x)/(1-y-xy)=Sum_{i, j} A(i, j) y^j x^i/i!.
A(i, j) = A(i-1, j)+j*A(i-1, j-1)+(i==0) = A(j, i).
T(n, k) = sum{j=0..k, C(n, k-j)*k!/j!} = sum{j=0..k, (k-j)!*C(k, j)C(n, k-j)}. - Paul Barry, Nov 14 2005
A(i,j) = sum_k C(i,k)*C(j,k)*k!. E.g.f.: sum_{i,j} a(i,j)*x^i/i!*y^j/j! = e^{x+y+xy}. - Franklin T. Adams-Watters, Feb 06 2006
The LDU factorization of this array, formatted as a square array, is P * D * transpose(P), where P is Pascal's triangle A007318 and D = diag(0!, 1!, 2!, ... ). Compare with A099597. - Peter Bala, Nov 06 2007
A(i,j) = (-1)^-i HypergeometricU(-i, 1 - i + j, -1). - Eric W. Weisstein, May 10 2017

A197458 Number of n X n binary matrices with at most two 1's in each row and column, other entries 0.

Original entry on oeis.org

1, 2, 16, 265, 7343, 304186, 17525812, 1336221251, 129980132305, 15686404067098, 2297230134084416, 400977650310256537, 82188611938415464231, 19536244019455339261970, 5328019975275896220786388, 1651867356348327784988233291, 577522171260292028520919811777

Offset: 0

Felix A. Pahl, Oct 15 2011

nonn

Filling out an n x n square grid with 0's and 1's at math.stackexchange
R. J. Mathar, The number of binary n X m matrices with at most k 1's in each row or column, (2014) Table 2.

Cf. A001499, A002720. Column of A283500.

import java.math.BigInteger;
public class AtMostTwoOnes {
    public static void main (String [] args) {
        for (int n = 0;n <= 40;n++) {
            BigInteger [] [] [] counts = new BigInteger [n + 1] [n + 1] [n + 1]; // counts [m] [k] [l] : number of mxn matrices with k column sums 0, l column sums 1
            for (int k = 0;k <= n;k++)
                for (int l = 0;l <= n;l++)
                    counts [0] [k] [l] = BigInteger.ZERO;
            counts [0] [n] [0] = BigInteger.ONE; // only one 0xn matrix, with all n column sums 0
            for (int m = 1;m <= n;m++) {
                BigInteger [] [] old = counts [m - 1];
                for (int k = 0;k <= n;k++)
                    for (int l = 0;l <= n;l++) {
                        BigInteger sum = BigInteger.ZERO;
                        // new row contains no 1s
                        sum = sum.add (old [k] [l]);
                        // new row contains one 1
                        //   added to column sum 0
                        if (k < n && l > 0)
                            sum = sum.add (old [k + 1] [l - 1].multiply (BigInteger.valueOf (k + 1)));
                        //   added to column sum 1
                        if (l < n)
                            sum = sum.add (old [k] [l + 1].multiply (BigInteger.valueOf (l + 1)));
                        // new row contains two 1s
                        //   added to two column sums 0
                        if (k < n - 1 && l > 1)
                            sum = sum.add (old [k + 2] [l - 2].multiply (BigInteger.valueOf (((k + 2) * (k + 1)) / 2)));
                        //   added to one column sum 0, one column sum 1
                        if (k < n)
                            sum = sum.add (old [k + 1] [l].multiply (BigInteger.valueOf ((k + 1) * l)));
                        //   added to two column sums 1
                        if (l < n - 1)
                            sum = sum.add (old [k] [l + 2].multiply (BigInteger.valueOf (((l + 2) * (l + 1)) / 2)));
                        counts [m] [k] [l] = sum;
                    }
            }
            BigInteger sum = BigInteger.ZERO;
            for (int k = 0;k <= n;k++)
                for (int l = 0;l <= n;l++)
                    sum = sum.add (counts [n] [k] [l]);
            System.out.println (n + " : " + sum);
        }
    }
}

a(n) = Sum_{k=0}^n Sum_{l=0}^{n-k} a(k,l,n,n) where a(k,l,m,n) is the number of binary m X n matrices with at most two 1's per row, k columns with sum 0, l columns with sum 1 and the remaining n - k - l columns with sum 2.

a(k,l,m,n) = a(k,l,m-1,n) +(k+1)*a(k+1,l-1,m-1,n) +(l+1)*a(k,l+1,m-1,n) +(k+1)*2*a(k+2,l-2,m-1,n)/(k+2) +(k+1)*l*a(k+1,l,m-1,n) +(l+1)*2*a(k,l+2,m-1,n)/(l+2).

A086885 Lower triangular matrix, read by rows: T(i,j) = number of ways i seats can be occupied by any number k (0<=k<=j<=i) of persons.

Original entry on oeis.org

2, 3, 7, 4, 13, 34, 5, 21, 73, 209, 6, 31, 136, 501, 1546, 7, 43, 229, 1045, 4051, 13327, 8, 57, 358, 1961, 9276, 37633, 130922, 9, 73, 529, 3393, 19081, 93289, 394353, 1441729, 10, 91, 748, 5509, 36046, 207775, 1047376, 4596553, 17572114, 11, 111, 1021, 8501

Offset: 1

Hugo Pfoertner, Aug 22 2003

Compare with A088699. - Peter Bala, Sep 17 2008

T(m, n) gives the number of matchings in the complete bipartite graph K_{m,n}. - Eric W. Weisstein, Apr 25 2017

			One person:
T(1,1)=a(1)=2: 0,1 (seat empty or occupied);
T(2,1)=a(2)=3: 00,10,01 (both seats empty, left seat occupied, right seat occupied).
Two persons:
T(2,2)=a(3)=7: 00,10,01,20,02,12,21;
T(3,2)=a(5)=13: 000,100,010,001,200,020,002,120,102,012,210,201,021.
Triangle starts:
  2;
  3  7;
  4 13  34;
  5 21  73 209;
  6 31 136 501 1546;
  ...

Robert Israel, Table of n, a(n) for n = 1..10011 (rows 1 to 141, flattened)
Ed Jones, Number of seatings, discussion in newsgroup sci.math, Aug 9, 2003.
R. J. Mathar, The number of binary nxm matrices with at most k 1's in each row or columns, Table 1.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Luca Zecchini, Tobias Bleifuß, Giovanni Simonini, Sonia Bergamaschi, and Felix Naumann, Determining the Largest Overlap between Tables, Proc. ACM Manag. Data (SIGMOD 2024) Vol. 2, No. 1, Art. 48. See p. 48:6.
Index entries for sequences related to Laguerre polynomials

Diagonal: A002720, first subdiagonal: A000262, 2nd subdiagonal: A052852, 3rd subdiagonal: A062147, 4th subdiagonal: A062266, 5th subdiagonal: A062192, 2nd row/column: A002061. With column 0: A176120.

[Factorial(k)*Evaluate(LaguerrePolynomial(k, n-k), -1): k in [1..n], n in [1..10]]; // G. C. Greubel, Feb 23 2021

A086885 := proc(n,k)
    add( binomial(n,j)*binomial(k,j)*j!,j=0..min(n,k)) ;
end proc: # R. J. Mathar, Dec 19 2014

Table[Table[Sum[k! Binomial[n, k] Binomial[j, k], {k, 0, j}], {j, 1, n}], {n, 1, 10}] // Grid (* Geoffrey Critzer, Jul 09 2015 *)
Table[m! LaguerreL[m, n - m, -1], {n, 10}, {m, n}] // Flatten (* Eric W. Weisstein, Apr 25 2017 *)

T(i, j) = j!*pollaguerre(j, i-j, -1); \\ Michel Marcus, Feb 23 2021

flatten([[factorial(k)*gen_laguerre(k, n-k, -1) for k in [1..n]] for n in (1..10)]) # G. C. Greubel, Feb 23 2021

a(n) = T(i, j) with n=(i*(i-1))/2+j; T(i, 1)=i+1, T(i, j)=T(i, j-1)+i*T(i-1, j-1) for j>1.
The role of seats and persons may be interchanged, so T(i, j)=T(j, i).
T(i, j) = j!*LaguerreL(j, i-j, -1). - Vladeta Jovovic, Aug 25 2003
T(i, j) = Sum_{k=0..j} k!*binomial(i, k)*binomial(j, k). - Vladeta Jovovic, Aug 25 2003

A086601 Triangular numbers + 1 squared.

Original entry on oeis.org

1, 4, 16, 49, 121, 256, 484, 841, 1369, 2116, 3136, 4489, 6241, 8464, 11236, 14641, 18769, 23716, 29584, 36481, 44521, 53824, 64516, 76729, 90601, 106276, 123904, 143641, 165649, 190096, 217156, 247009, 279841, 315844, 355216, 398161

Offset: 0

Jon Perry, Jul 23 2003

Also number of n X 2 0..1 arrays with rows and columns unimodal (cf. A223620, column 2). - Georg Fischer, Nov 03 2021

			a(5) = (t(5)+1)^2 = 16^2 = 256.

Harvey P. Dale, Table of n, a(n) for n = 0..1000
R. J. Mathar, The number of binary nxm matrices with at most k 1's in each row or column, (2014) Table 2 column 2.
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A000124, A000217, A061316, A223620.

A086601 := proc(n)
    (n+2+n^2)^2 /4 ;
end proc:
seq(A086601(n),n=0..20) ; # R. J. Mathar, May 14 2014

(Accumulate[Range[0,40]]+1)^2 (* or *) LinearRecurrence[{5,-10,10,-5,1},{1,4,16,49,121},40] (* Harvey P. Dale, Jan 14 2020 *)

PARI
```
w=vector(40,i,(t(i)+1)^2)
```

a(n) = (A000217(n) + 1)^2.
a(n) = (binomial(2+n,2) - binomial(n,1))^2. - Zerinvary Lajos, May 30 2006, corrected by R. J. Mathar, May 14 2014
a(n) = A000124(n)^2. - Omar E. Pol, Oct 30 2007
a(n) = 1 + A061316(n). Zerinvary Lajos, Apr 25 2008
G.f.: ( -1+x-6*x^2+x^3-x^4 ) / (x-1)^5. - R. J. Mathar, May 14 2014

A135859 Row sums of triangle A135858.

Original entry on oeis.org

1, 4, 13, 34, 73, 136, 229, 358, 529, 748, 1021, 1354, 1753, 2224, 2773, 3406, 4129, 4948, 5869, 6898, 8041, 9304, 10693, 12214, 13873, 15676, 17629, 19738, 22009, 24448, 27061, 29854, 32833, 36004, 39373, 42946, 46729, 50728, 54949

Offset: 1

Gary W. Adamson, Dec 01 2007

Number of binary 3 X (n-1) matrices such that each row and column has at most one 1. - Dmitry Kamenetsky, Jan 20 2018

			a(3) = 13 = sum of row 3 terms of triangle A135858: (7, + 5 + 1).
a(4) = 34 = (1, 3, 3, 1) dot (1, 3, 6, 6) = (1 + 9 + 18 + 6).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
R. J. Mathar, The number of binary matrices..., Table 1 column 3.
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A135858.

List([1..10^4], n-> 5*n - 2 + n^3 - 3*n^2); # Muniru A Asiru, Jan 24 2018

I:=[1, 4, 13, 34]; [n le 4 select I[n] else 4*Self(n-1)-6*Self(n-2)+4*Self(n-3)-Self(n-4): n in [1..50]]; // Vincenzo Librandi, Jun 29 2012

seq(5*n - 2 + n^3 - 3*n^2, n=1..10^2); # Muniru A Asiru, Jan 24 2018

CoefficientList[Series[(1+3*x^2+2*x^3)/(x-1)^4,{x,0,40}],x] (* Vincenzo Librandi, Jun 29 2012 *)

[n^3 -3*n^2 +5*n -2 for n in (1..50)] # G. C. Greubel, Aug 11 2022

Row sums of triangle A135858. Binomial transform of [1, 3, 6, 6, 0, 0, 0, ...].
G.f.: x*(1+3*x^2+2*x^3) / (1-x)^4. - R. J. Mathar, Apr 04 2012
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - Vincenzo Librandi, Jun 29 2012
a(n) = n^3 - 3*n^2 + 5*n - 2. - R. J. Mathar, Oct 20 2017
E.g.f.: 2 - (2 - 3*x - x^3)*exp(x). - G. C. Greubel, Aug 11 2022

cp's OEIS Frontend

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

A048291 Number of {0,1} n X n matrices with no zero rows or columns.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A088699 Array read by antidiagonals of coefficients of generating function exp(x)/(1-y-xy).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

A197458 Number of n X n binary matrices with at most two 1's in each row and column, other entries 0.

Views

Author

Keywords

Links

Crossrefs

Programs

Java

Formula

A086885 Lower triangular matrix, read by rows: T(i,j) = number of ways i seats can be occupied by any number k (0<=k<=j<=i) of persons.

Views

Author