A088699 -id:A088699 - cp's OEIS frontend

A002720 Number of partial permutations of an n-set; number of n X n binary matrices with at most one 1 in each row and column.

1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, 234662231, 3405357682, 53334454417, 896324308634, 16083557845279, 306827170866106, 6199668952527617, 132240988644215842, 2968971263911288999, 69974827707903049154, 1727194482044146637521, 44552237162692939114282

Offset: 0

N. J. A. Sloane

a(n) is also the total number of increasing subsequences of all permutations of [1..n] (see Lifschitz and Pittel). - N. J. A. Sloane, May 06 2012
a(n) = A000142 + A001563 + A001809 + A001810 + A001811 + A001812 + ... these sequences respectively give the number of increasing subsequences of length i for i=0,1,2,... in all permutations of [1..n]. - Geoffrey Critzer, Jan 17 2013
a(n) is also the number of matchings in the complete bipartite graph K(n,n). - Sharon Sela (sharonsela(AT)hotmail.com), May 19 2002
a(n) is also the number of 12-avoiding signed permutations in B_n (see Simion ref).
a(n) is also the order of the symmetric inverse semigroup (monoid) I_n. - A. Umar, Sep 09 2008
EXP transform of A001048(n) = n! + (n-1)!. - Franklin T. Adams-Watters, Dec 28 2006
From Peter Luschny, Mar 27 2011: (Start)
Let B_{n}(x) = Sum_{j>=0} exp(j!/(j-n)!*x-1)/j!; then a(n) = 2! [x^2] Taylor(B_{n}(x)), where [x^2] denotes the coefficient of x^2 in the Taylor series for B_{n}(x).
a(n) is column 2 of the square array representation of A090210. (End)
a(n) is the Hosoya index of the complete bipartite graph K_{n,n}. - Eric W. Weisstein, Jul 09 2011
a(n) is also number of non-attacking placements of k rooks on an n X n board, summed over all k >= 0. - Vaclav Kotesovec, Aug 28 2012
Also the number of vertex covers and independent vertex sets in the n X n rook graph. - Eric W. Weisstein, Jan 04 2013
a(n) is the number of injective functions from subsets of [n] to [n] where [n]={1,2,...,n}. For a subset D of size k, there are n!/(n-k)! injective functions from D to [n]. Summing over all subsets, we obtain a(n) = Sum_{k=0..n} C(n,k)*n!/(n-k)! = Sum_{k=0..n} k!*C(n,k)^2. - Dennis P. Walsh, Nov 16 2015
Also the number of cliques in the n X n rook complement graph. - Eric W. Weisstein, Sep 14 2017
a(n)/n! is the expected value of the n-th term of Ulam's "history-dependent random sequence". See Kac (1989), Eq.(2). - N. J. A. Sloane, Nov 16 2019
a(2*n) is odd and a(2*n+1) is even for all n. More generally, for each positive integer k, a(n+k) == a(n) (mod k) for all n. It follows that for each positive integer k, the sequence obtained by reducing a(n) modulo k is periodic, with period dividing k. Various divisibility properties of the sequence follow from this: for example, a(7*n+2) == 0 (mod 7), a(11*n+4) == 0 (mod 11), a(17*n+3) == 0 (mod 17) and a(19*n+4) == 0 (mod 19). - Peter Bala, Nov 07 2022
Conjecture: a(n)*k is the sum of the largest parts in all integer partitions containing their own first differences with n + 1 parts and least part k. - John Tyler Rascoe, Feb 28 2024

			G.f. = 1 + 2*x + 7*x^2 + 34*x^3 + 209*x^4 + 1546*x^5 + 13327*x^6 + 130922*x^7 + ... - _Michael Somos_, Jul 31 2018

J. M. Howie, Fundamentals of semigroup theory. Oxford: Clarendon Press, (1995). [From A. Umar, Sep 09 2008]
J. Ser, Les Calculs Formels des Séries de Factorielles. Gauthier-Villars, Paris, 1933, p. 78.
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).
H. S. Wall, Analytic Theory of Continued Fractions, Chelsea 1973, p. 356.

Alois P. Heinz, Table of n, a(n) for n = 0..443 (first 101 terms from T. D. Noe)
Francesca Aicardi, Diego Arcis, and Jesús Juyumaya, Ramified inverse and planar monoids, arXiv:2210.17461 [math.RT], 2022.
A. I. Aptekarev, On linear forms containing the Euler constant, arXiv:0902.1768 [math.NT], 2009.
T. Banica, The algebraic structure of quantum partial isometries, arXiv:1411.0577 [math.OA], 2014-2015.
C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps, Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
Teo Banica, Algebraic invariants of truncated Fourier matrices, arXiv preprint arXiv:1401.5023 [math.QA], 2014.
D. Borwein, S. Rankin, and L. Renner, Enumeration of injective partial transformations, Discrete Math. (1989), 73: 291-296. [From A. Umar, Sep 09 2008]
D. Castellanos, A generalization of Binet's formula and some of its consequences, Fib. Quart., 27 (1989), 424-438.
Aria Chen, Tyler Cummins, Rishi De Francesco, Jate Greene, Tanya Khovanova, Alexander Meng, Tanish Parida, Anirudh Pulugurtha, Anand Swaroop, and Samuel Tsui, Card Tricks and Information, arXiv:2405.21007 [math.HO], 2024. See p. 14.
Fabio Deelan Cunden, Jakub Czartowski, Giovanni Gramegna, and A. de Oliveira Junior, Relative volume of comparable pairs under semigroup majorization, arXiv:2410.23196 [math-ph], 2024. See pp. 4, 15.
Dan Daly and Lara Pudwell, Pattern avoidance in rook monoids, Special Session on Patterns in Permutations and Words, Joint Mathematics Meetings, 2013. - From _N. J. A. Sloane_, Feb 03 2013
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 598.
Olof Giselsson, The Universal C*-Algebra of the Quantum Matrix Ball and its Irreducible *-Representations, arXiv:1801.10608 [math.QA], 2018.
J. Godbout, Combinatorial Properties of the Mirabolic RSK Algorithm, Thesis presented to The Faculty of the Graduate College of The University of Vermont, May 2013.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 64.
Z. Janelidze, F. van Niekerk, and J. Viljoen, What is the maximal connected partial symmetry index of a connected graph of a given size?, arXiv:2502.00704 [math.CO], 2025. See p. 3.
Mark Kac, A history-dependent random sequence defined by Ulam, Advances in Applied Mathematics 10.3 (1989): 270-277.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 219.
Vaclav Kotesovec, Too many errors around coefficient C1 in asymptotic of sequence A002720, Sep 28 2012. [The bug in program Mathematica was fixed in version 10.2.0.0 / July 2015. _Vaclav Kotesovec_, Jul 25 2015]
V. Lifschitz and P. Pittel, The number of increasing subsequences of the random permutation J. Combin. Theory Ser. A 31 (1981), no. 1, 1--20. MR0626437 (84e:05012)
Mathematica Stack Exchange, Wrong Limit with LaguerreL, May 22 2015
W. D. Munn, The characters of the symmetric inverse semigroup, Proc. Cambridge Philos. Soc. 53 (1957), 13-18. [From A. Umar, Sep 09 2008]
K. A. Penson, P. Blasiak, A. Horzela, G. H. E. Duchamp, and A. I. Solomon, Laguerre-type derivatives: Dobinski relations and combinatorial identities, J. Math. Phys. vol. 50, 083512 (2009).
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.
John Riordan, Letter, Apr 28 1976.
John Riordan, Letter to N. J. A. Sloane, Oct 01 1978.
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
J. Ser, Les Calculs Formels des Séries de Factorielles, Gauthier-Villars, Paris, 1933 [Local copy].
J. Ser, Les Calculs Formels des Séries de Factorielles. (Annotated scans of some selected pages)
R. Simion, Combinatorial statistics on type-B analogues of non-crossing partitions and restricted permutations, Electronic J. of Comb. 7 (2000), Art #R9.
A. Umar, Some combinatorial problems in the theory of symmetric ..., Algebra Disc. Math. 9 (2010) 115-126.
Luis Verde-Star, A Matrix Approach to Generalized Delannoy and Schröder Arrays, J. Int. Seq., Vol. 24 (2021), Article 21.4.1.
D. P. Walsh, Notes on functions from subsets of {1,2,...,n} into {1,2,...,n}.
Eric Weisstein's World of Mathematics, Clique.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Eric Weisstein's World of Mathematics, Independent Vertex Set.
Eric Weisstein's World of Mathematics, Matching.
Eric Weisstein's World of Mathematics, Rook Complement Graph.
Eric Weisstein's World of Mathematics, Rook Graph.
Eric Weisstein's World of Mathematics, Vertex Cover.
Index entries for sequences related to Laguerre polynomials

Main diagonal of A088699. Column of A283500. Row sums of A144084.
Cf. A000110, A020556, A069223, A000712, A001048, A090210, A002793, A073003, A000262.
Column k=1 of A289192.
Cf. A160617, A160618.
Cf. A364673.

[Factorial(n)*Evaluate(LaguerrePolynomial(n), -1): n in [0..25]]; // G. C. Greubel, Aug 11 2022

A002720 := proc(n) exp(-x)*n!*hypergeom([n+1], [1], x); simplify(subs(x=1, %)) end: seq(A002720(n), n=0..25); # Peter Luschny, Mar 30 2011
A002720 := proc(n)
    option remember;
    if n <= 1 then
        n+1 ;
    else
        2*n*procname(n-1)-(n-1)^2*procname(n-2) ;
    end if;
end proc: # R. J. Mathar, Mar 09 2017

Table[n! LaguerreL[n, -1], {n, 0, 25}]
Table[(-1)^n*HypergeometricU[-n, 1, -1], {n, 0, 25}] (* Jean-François Alcover, Jul 15 2015 *)
RecurrenceTable[{(n+1)^2 a[n] - 2(n+2) a[n+1] + a[n+2]==0, a[1]==2, a[2]==7}, a, {n, 25}] (* Eric W. Weisstein, Sep 27 2017 *)

a(n) = sum(k=0, n, k!*binomial(n, k)^2 );

a(n) = suminf ( k=0, binomial(n+k,n)/k! ) / ( exp(1)/n! ) /* Gottfried Helms, Nov 25 2006 */

{a(n)=n!^2*polcoeff(exp(x+x*O(x^n))*sum(m=0,n,x^m/m!^2),n)} /* Paul D. Hanna, Nov 18 2011 */

{a(n)=if(n==0,1,polcoeff(1-sum(m=0, n-1, a(m)*x^m*(1-(m+1)*x+x*O(x^n))^2), n))} /* Paul D. Hanna, Nov 27 2012 */

my(x='x+O('x^22)); Vec(serlaplace((1/(1-x))*exp(x/(1-x)))) \\ Joerg Arndt, Aug 11 2022

from math import factorial, comb
def A002720(n): return sum(factorial(k)*comb(n,k)**2 for k in range(n+1)) # Chai Wah Wu, Aug 31 2023

[factorial(n)*laguerre(n, -1) for n in (0..25)] # G. C. Greubel, Aug 11 2022

a(n) = Sum_{k=0..n} k!*C(n, k)^2.
E.g.f.: (1/(1-x))*exp(x/(1-x)). - Don Knuth, Jul 1995
D-finite with recurrence: a(n) = 2*n*a(n-1) - (n-1)^2*a(n-2).
a(n) = Sum_{k>=0} (k+n)! / ((k!)^2*exp(1)). - Robert G. Wilson v, May 02 2002 [corrected by Vaclav Kotesovec, Aug 28 2012]
a(n) = Sum_{m>=0} (-1)^m*A021009(n, m). - Philippe Deléham, Mar 10 2004
a(n) = Sum_{k=0..n} C(n, k)n!/k!. - Paul Barry, May 07 2004
a(n) = Sum_{k=0..n} P(n, k)*C(n, k); a(n) = Sum_{k=0..n} n!^2/(k!*(n-k)!^2). - Ross La Haye, Sep 20 2004
a(n) = Sum_{k=0..n} (-1)^(n-k)*Stirling1(n, k)*Bell(k+1). - Vladeta Jovovic, Mar 18 2005
Define b(n) by b(0) = 1, b(n) = b(n-1) + (1/n) * Sum_{k=0..n-1} b(k). Then b(n) = a(n)/n!. - Franklin T. Adams-Watters, Sep 05 2005
Asymptotically, a(n)/n! ~ (1/2)*Pi^(-1/2)*exp(-1/2 + 2*n^(1/2))/n^(1/4) and so a(n) ~ C*BesselI(0, 2*sqrt(n))*n! with C = exp(-1/2) = 0.6065306597126334236... - Alec Mihailovs, Sep 06 2005, establishing a conjecture of Franklin T. Adams-Watters
a(n) = (n!/e) * Sum_{k>=0} binomial(n+k,n)/k!. - Gottfried Helms, Nov 25 2006
Integral representation as n-th moment of a positive function on a positive halfaxis (solution of the Stieltjes moment problem): a(n) = Integral_{x=0..oo} x^n*BesselI(0,2*sqrt(x))*exp(-x)/exp(1) dx, n >= 0. - Karol A. Penson and G. H. E. Duchamp (gduchamp2(AT)free.fr), Jan 09 2007
a(n) = n! * LaguerreL[n, -1].
E.g.f.: exp(x) * Sum_{n>=0} x^n/n!^2 = Sum_{n>=0} a(n)*x^n/n!^2. - Paul D. Hanna, Nov 18 2011
From Peter Bala, Oct 11 2012: (Start)
Denominators in the sequence of convergents coming from Stieltjes's continued fraction for A073003, the Euler-Gompertz constant G := Integral_{x = 0..oo} 1/(1+x)*exp(-x) dx:
G = 1/(2 - 1^2/(4 - 2^2/(6 - 3^2/(8 - ...)))). See [Wall, Chapter 18, (92.7) with a = 1]. The sequence of convergents to the continued fraction begins [1/2, 4/7, 20/34, 124/209, ...]. The numerators are in A002793. (End)
G.f.: 1 = Sum_{n>=0} a(n) * x^n * (1 - (n+1)*x)^2. - Paul D. Hanna, Nov 27 2012
E.g.f.: exp(x/(1-x))/(1-x) = G(0)/(1-x) where G(k) = 1 + x/((2*k+1)*(1-x) - x*(1-x)*(2*k+1)/(x + (1-x)*(2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 28 2012
a(n) = Sum_{k=0..n} L(n,k)*(k+1); L(n,k) the unsigned Lah numbers. - Peter Luschny, Oct 18 2014
a(n) = n! * A160617(n)/A160618(n). - Alois P. Heinz, Jun 28 2017
0 = a(n)*(-24*a(n+2) +99*a(n+3) -78*a(n+4) +17*a(n+5) -a(n+6)) +a(n+1)*(-15*a(n+2) +84*a(n+3) -51*a(n+4) +6*a(n+5)) +a(n+2)*(-6*a(n+2) +34*a(n+3) -15*a(n+4)) +a(n+3)*(+10*a(n+3)) for all n>=0. - Michael Somos, Jul 31 2018
a(n) = Sum_{k=0..n} C(n,k)*k!*A000262(n-k). - Geoffrey Critzer, Jan 07 2023
a(n) = A000262(n+1) - n * A000262(n). - Werner Schulte, Mar 29 2024
a(n) = denominator of (1 + n/(1 + n/(1 + (n-1)/(1 + (n-1)/(1 + ... + 1/(1 + 1/(1))))))). See A000262 for the numerators. - Peter Bala, Feb 11 2025

2nd description from R. H. Hardin, Nov 1997

3rd description from Wouter Meeussen, Jun 01 1998

A343832 a(n) = Sum_{k=0..n} k! * binomial(n,k) * binomial(2*n+1,k).

Original entry on oeis.org

1, 4, 31, 358, 5509, 106096, 2456299, 66471826, 2059640713, 71920704124, 2794938616471, 119653108240414, 5595650767265101, 283841520215780008, 15523069639558351459, 910529206043204428426, 57023540590242398853649, 3797750659849704886903156, 268025698704886063968108943

Offset: 0

Seiichi Manyama, May 01 2021

nonn

Let A(x) be the e.g.f. of this sequence, and B(x) be the e.g.f. of A082545, then A(x)/B(x) = C(x) where C(x) = 1 + x*C(x)^2 is the Catalan function (A000108). This follows from the fact that this sequence and A082545 form adjacent semi-diagonals of table A088699. - Paul D. Hanna, Aug 16 2022

Seiichi Manyama, Table of n, a(n) for n = 0..365
Wikipedia, Laguerre polynomials
Index entries for sequences related to Laguerre polynomials

Cf. A000522, A045721, A082545, A152059, A248668, A343830, A343831, A000108.

[Factorial(n)*Evaluate(LaguerrePolynomial(n, n+1), -1): n in [0..40]]; // G. C. Greubel, Aug 11 2022

a := n -> add(k!*binomial(n, k)*binomial(2*n+1, k), k=0..n):
a := n -> n!*add(binomial(2*n+1, k)/(n-k)!, k=0..n):
a := n -> (-1)^n*KummerU(-n, n+2, -1):
a := n -> n!*LaguerreL(n, n+1, -1): # Peter Luschny, May 02 2021

a[n_] := Sum[k! * Binomial[n, k] * Binomial[2*n+1, k], {k, 0, n}]; Array[a, 20, 0] (* Amiram Eldar, May 01 2021 *)
Table[(-1)^n * HypergeometricU[-n, 2 + n, -1], {n, 0, 20}] (* Vaclav Kotesovec, May 02 2021 *)

a(n) = sum(k=0, n, k!*binomial(n, k)*binomial(2*n+1, k));

a(n) = (2*n+1)!*sum(k=0, n, binomial(n, k)/(k+n+1)!);

a(n) = n!*sum(k=0, n, binomial(2*n+1, k)/(n-k)!);

PARI
```
a(n) = n!*pollaguerre(n, n+1, -1);
```

[factorial(n)*gen_laguerre(n, n+1, -1) for n in (0..40)] # G. C. Greubel, Aug 11 2022

a(n) = (2*n+1)! * Sum_{k=0..n} binomial(n,k)/(k+n+1)!.
a(n) = n! * Sum_{k=0..n} binomial(2*n+1,k)/(n-k)!.
a(n) = n! * LaguerreL(n, n+1, -1).
a(n) = n! * [x^n] exp(x/(1 - x))/(1 - x)^(n+2).
a(n) == 1 (mod 3).
a(n) ~ 2^(2*n + 3/2) * n^n / exp(n-1). - Vaclav Kotesovec, May 02 2021
From Paul D. Hanna, Aug 16 2022: (Start)
E.g.f.: exp( (1-2*x - sqrt(1-4*x))/(2*x) ) * (1 - sqrt(1-4*x)) / (2*x*sqrt(1-4*x)), derived from the e.g.f for A082545 given by Mark van Hoeij.
E.g.f.: exp(C(x) - 1) * C(x) / sqrt(1-4*x), where C(x) = (1 - sqrt(1-4*x))/(2*x) is the Catalan function (A000108). (End)

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

A099597 Array T(n,k) read by antidiagonals: expansion of exp(x+y)/(1-xy).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 9, 4, 1, 1, 5, 19, 19, 5, 1, 1, 6, 33, 82, 33, 6, 1, 1, 7, 51, 229, 229, 51, 7, 1, 1, 8, 73, 496, 1313, 496, 73, 8, 1, 1, 9, 99, 919, 4581, 4581, 919, 99, 9, 1, 1, 10, 129, 1534, 11905, 32826, 11905, 1534, 129, 10, 1, 1, 11, 163, 2377, 25733, 137431, 137431, 25733, 2377, 163, 11, 1

Offset: 0

Ralf Stephan, Oct 28 2004

Rows are polynomials in n whose coefficients are in A099599.
From Peter Bala, Aug 19 2013: (Start)
The k-th superdiagonal sequence of this square array occurs as the sequence of numerators in the convergents to a certain continued fraction representation of the constant BesselI(k,2), where BesselI(k,x) is a modified Bessel function of the first kind:
Let d_k(n) = T(n,n+k) = n! * (n+k)! * Sum_{i=0..n} 1/(i!*(i+k)!) denote the sequence of entries on the k-th superdiagonal. It satisfies the first-order recurrence equation d_k(n) = n*(n+k)*d_k(n-1) + 1 with d_k(0) = 1 and also the second-order recurrence d_k(n) = (n*(n+k)+1)*d_k(n-1) - (n-1)*(n-1+k)*d_k(n-2) with initial conditions d_k(0) = 1 and d_k(1) = k+2. This latter recurrence is also satisfied by the sequence n!*(n+k)!. From this observation we obtain the finite continued fraction expansion d_k(n) = n!*(n+k)!*(1/(k! - k!/((k+2) - (k+1)/((2*k+5) - 2*(k+2)/((3*k+10) - ... - n*(n+k)/(((n+1)*(n+k+1)+1) ))))).
Taking the limit as n -> infinity produces a continued fraction representation for the modified Bessel function value BesselI(k,2) = Sum_{i=0..inf} 1/(i!*(i+k)!) = 1/(k! - k!/((k+2) -(k+1)/((2*k+5) - 2*(k+2)/((3*k+10) - ... - n*(n+k)/(((n+1)*(n+k+1)+1) - ...))))). See A070910 for the case k = 0 and A096789 for the case k = 1. (End)

			1, 1,  1,   1,    1,     1,
1, 2,  3,   4,    5,     6,
1, 3,  9,  19,   33,    51,
1, 4, 19,  82,  229,   496,
1, 5, 33, 229, 1313,  4581,
1, 6, 51, 496, 4581, 32826,

E. W. Weisstein, Modified Bessel Function of the First Kind

Rows include A000012, A000027, A058331. Main diagonal is A006040. Antidiagonal sums are in A099598. Cf. A099599.

Cf. A088699. A228229 (main super and subdiagonal).

#A099597
T := proc(n,k) option remember;
if n = 0 then 1 elif k = 0 then 1
else n*k*thisproc(n-1,k-1) + 1
fi
end:
# Diplay entries by antidiagonals
seq(seq(T(n-k,k), k = 0..n), n = 0..10);
# Peter Bala, Aug 19 2013

T[, 0] = T[0, ] = 1;
T[n_, k_] := T[n, k] = n k T[n - 1, k - 1] + 1;
Table[T[n - k, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 02 2019 *)

T(n,k) = Sum_{i=0..min(n,k)} C(n,i)*C(k,i)*i!^2. The LDU factorization of this square array is P * D * transpose(P), where P is Pascal's triangle A007318 and D = diag(0!^2, 1!^2, 2!^2, ... ). Compare with A088699. - Peter Bala, Nov 06 2007
Recurrence equation: T(n,k) = n*k*T(n-1,k-1) + 1 with boundary conditions T(n,0) = T(0,n ) = 1.
Main subdiagonal and main superdiagonal [1, 3, 19, 229, ...] is A228229. - Peter Bala, Aug 19 2013
nth row/column o.g.f.: HypergeometricPFQ[{1,1,-n},{},x/(x-1)]/(1-x) (see comment in A099599). - Natalia L. Skirrow, Jul 18 2025

A287274 Array read by antidiagonals: T(m,n) = number of dominating sets in the lattice (rook) graph K_m X K_n.

Original entry on oeis.org

1, 3, 3, 7, 11, 7, 15, 51, 51, 15, 31, 227, 421, 227, 31, 63, 963, 3615, 3615, 963, 63, 127, 3971, 30517, 59747, 30517, 3971, 127, 255, 16131, 252231, 989295, 989295, 252231, 16131, 255, 511, 65027, 2054941, 16219187, 32260381, 16219187, 2054941, 65027, 511

Offset: 1

Andrew Howroyd, May 22 2017

A set of vertices can be represented as an m X n binary matrix. If all rows contain at least one 1 then regardless of what is in each row the set will form a dominating set giving (2^n-1)^m solutions. Otherwise if only iA183109(i,n) solutions.

			Array begins:
=============================================================================
m\n|   1     2       3         4           5             6               7
---|-------------------------------------------------------------------------
1  |   1     3       7        15          31            63             127...
2  |   3    11      51       227         963          3971           16131...
3  |   7    51     421      3615       30517        252231         2054941...
4  |  15   227    3615     59747      989295      16219187       263425695...
5  |  31   963   30517    989295    32260381    1048220463     33884452717...
6  |  63  3971  252231  16219187  1048220463   67680006971   4358402146791...
7  | 127 16131 2054941 263425695 33884452717 4358402146791 559876911043381...
...

Andrew Howroyd, Table of n, a(n) for n = 1..780
Stephan Mertens, Domination Polynomial of the Rook Graph, JIS 27 (2024) 24.3.7; arXiv:2401.00716 [math.CO], 2024.
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal is A287065.
Row 2 is A191341.
Cf. A183109, A088699 (independent vertex sets), A290632.

b[m_, n_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}];
a[m_, n_] := (2^n - 1)^m + Sum[ b[i, n]*Binomial[m, i], {i, 1, m - 1}];
Table[a[m - n + 1, n], {m, 1, 9}, {n, 1, m}] // Flatten (* Jean-François Alcover, Jun 12 2017, adapted from PARI *)

b(m,n)=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
a(m,n)=(2^n-1)^m + sum(i=1,m-1,b(i,n)*binomial(m,i));
for (i=1,7,for(j=1,7, print1(a(i,j), ",")); print);

T(m, n) = (2^n-1)^m + Sum_{i=1..m-1} binomial(m,i) * A183109(i,n).

A056953 Denominators of continued fraction for alternating factorial.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 34, 73, 209, 501, 1546, 4051, 13327, 37633, 130922, 394353, 1441729, 4596553, 17572114, 58941091, 234662231, 824073141, 3405357682, 12470162233, 53334454417, 202976401213, 896324308634, 3535017524403, 16083557845279, 65573803186921

Offset: 0

Aleksandar Petojevic, Sep 05 2000

Starting (1, 2, 3, ...) with offset 0 = eigensequence of an infinite lower triangular matrix with 1's in the main diagonal and the natural numbers repeated in the subdiagonal. - Gary W. Adamson, Feb 14 2011

a(n) is the number of involutions of [n] such that every 2-cycle contains one odd and one even element; a(4) = 7: 1234, 1243, 1324, 2134, 2143, 4231, 4321. - Alois P. Heinz, Feb 14 2013

Alois P. Heinz, Table of n, a(n) for n = 0..400
Francesca Aicardi, Diego Arcis, and Jesús Juyumaya, Ramified inverse and planar monoids, arXiv:2210.17461 [math.RT], 2022.
Index entries for sequences related to Laguerre polynomials

Bisections are A000262 and A002720.

Cf. A124428, diagonals of A088699.

[(&+[Factorial(k)*Binomial(Floor(n/2),k)*Binomial(Floor((n+1)/2),k): k in [0..Floor(n/2)]]): n in [0..30]]; // G. C. Greubel, May 16 2018

a:= proc(n) option remember; `if`(n<4, [1, 1, 2, 3][n+1],
      ((4*n-2)*a(n-2) +2*a(n-3) -(n-2)*(n-3)*a(n-4)) /4)
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Feb 14 2013

Table[Sum[k!*Binomial[Floor[n/2], k]*Binomial[Floor[(n+1)/2], k] , {k,0,Floor[n/2]}], {n,0,30}] (* G. C. Greubel, May 16 2018 *)

a(n)=sum(k=0,n\2,k!*binomial(n\2,k)*binomial((n+1)\2,k)) \\ Paul D. Hanna, Oct 31 2006

a(0)=1; a(1)=1; a(n) = a(n-1) + n*a(n-2)/2.
a(n) = Sum_{k=0..[n/2]} k!*C([n/2],k)*C([(n+1)/2],k). - Paul D. Hanna, Oct 31 2006
a(n) ~ n^(n/2 + 1/4) / (2^(n/2 + 3/4) * exp(n/2 - sqrt(2*n) + 1/2)) * (1 + (25 + 6*(-1)^n)/(24*sqrt(2*n)) + (397 + 156*(-1)^n)/(2304*n)). - Vaclav Kotesovec, Feb 22 2019

A152059 a(n) is the number of ways 2n-1 seats can be occupied by at most n people for n>=1, with a(0)=1.

Original entry on oeis.org

1, 2, 13, 136, 1961, 36046, 805597, 21204548, 642451441, 22021483546, 842527453421, 35591363004352, 1645373927307673, 82625931422081126, 4478815087922020861, 260648364396903639676, 16208855884741850686817

Offset: 0

Paul D. Hanna, Nov 22 2008

nonn

Let A(x) be the e.g.f. of this sequence, and B(x) be the e.g.f. of A082545, then B(x)/A(x) = C(x) where C(x) = 1 + x*C(x)^2 is the Catalan function (A000108). This follows from the fact that this sequence and A082545 form adjacent semi-diagonals of table A088699. - Paul D. Hanna, Aug 16 2022

Seiichi Manyama, Table of n, a(n) for n = 0..366
Wikipedia, Laguerre polynomials
Index entries for sequences related to Laguerre polynomials

Cf. A082545, A086885, A343832, A088699, A000108.

[Factorial(n)*Evaluate(LaguerrePolynomial(n, n-1), -1): n in [0..40]]; // G. C. Greubel, Aug 11 2022

Table[(-1)^n * HypergeometricU[-n, n, -1], {n, 0, 20}] (* Vaclav Kotesovec, Oct 02 2017 *)

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

a(n) = n!*pollaguerre(n, n-1, -1); \\ Seiichi Manyama, May 01 2021

[factorial(n)*gen_laguerre(n, n-1, -1) for n in (0..40)] # G. C. Greubel, Aug 11 2022

a(n) = Sum_{k=0..n} k! * C(2*n-1,k) * C(n,k).
Central terms of triangle A086885 (after initial term).
a(n) = n! * [x^n] exp(x/(1 - x))/(1 - x)^n. - Ilya Gutkovskiy, Oct 02 2017
a(n) ~ 2^(2*n - 1/2) * n^n / exp(n-1). - Vaclav Kotesovec, Oct 02 2017
a(n) = n! * pollaguerre(n, n-1, -1). - Seiichi Manyama, May 01 2021
From Paul D. Hanna, Aug 16 2022: (Start)
E.g.f.: exp( (1-2*x - sqrt(1-4*x))/(2*x) ) / ((sqrt(1-4*x) - (1-4*x))/(2*x)), derived from the e.g.f for A082545 given by Mark van Hoeij.
E.g.f.: exp(C(x) - 1) / (2 - C(x)), where C(x) = (1 - sqrt(1-4*x))/(2*x) is the Catalan function (A000108). (End)

A216294 Triangular array read by rows: T(n,k) is the number of partial permutations of {1,2,...,n} that have exactly k cycles, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 13, 14, 6, 1, 73, 84, 41, 10, 1, 501, 609, 325, 95, 15, 1, 4051, 5155, 2944, 965, 190, 21, 1, 37633, 49790, 30023, 10689, 2415, 343, 28, 1, 394353, 539616, 340402, 129220, 32179, 5348, 574, 36, 1, 4596553, 6478521, 4246842, 1698374, 455511, 84567, 10794, 906, 45, 1

Offset: 0

Geoffrey Critzer, Sep 04 2012

A partial permutation on a set X is a bijection between two subsets of X.
Row sums are A002720.
First column (corresponding to k=0) is A000262.

			1;
1,     1;
3,     3,   1;
13,   14,   6,  1;
73,   84,  41, 10,  1;
501, 609, 325, 95, 15,  1;

Alois P. Heinz, Rows n = 0..50, flattened
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 132.

Cf. A021009. A000262, A002720, A052852, A062147, A062192, A062266, A088699.

gf := exp(x / (1 - x)) / (1 - x)^y:
serx := series(gf, x, 10): poly := n -> simplify(coeff(serx, x, n)):
seq(print(seq(n!*coeff(poly(n), y, k), k = 0..n)), n = 0..9); # Peter Luschny, Feb 23 2023

nn=10;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];f[list_]:=Select[list,#>0&];Map[f,Range[0,nn]!CoefficientList[Series[Exp[ x/(1-x)]/(1-x)^y,{x,0,nn}],{x,y}]]//Flatten

E.g.f.: exp(x/(1-x))/(1-x)^y.
From Peter Bala, Aug 23 2013: (Start)
Exponential Riordan array [exp(x/(1-x)), log(1/(1-x))].
The row polynomials R(n,y), n > = 0, satisfy the 2nd order recurrence equation R(n,y) = (2*n + y - 1)*R(n-1,y) - (n - 1)*(n + y - 2)*R(n-2,y) with R(0,y) = 1 and R(1,y) = 1 + y.
Modulo variations in offset we have: R(n,0) = A000262, R(n,1) = A002720, R(n,2) = A000262, R(n,3) = A052852, R(n,4) = A062147, R(n,5) = A062266 and R(n,6) = A062192. In general, for fixed k, the sequence {R(n,k)}n>=1 gives the entries on a diagonal of the square array A088699. (End)

A131235 Triangle read by rows: T(n,k) is number of (n-k) X k matrices, k=0..n, with nonnegative integer entries and every row and column sum <= 2.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 6, 6, 1, 1, 10, 26, 10, 1, 1, 15, 79, 79, 15, 1, 1, 21, 189, 451, 189, 21, 1, 1, 28, 386, 1837, 1837, 386, 28, 1, 1, 36, 706, 5776, 12951, 5776, 706, 36, 1, 1, 45, 1191, 15085, 66021, 66021, 15085, 1191, 45, 1, 1, 55, 1889, 34399, 258355, 551681, 258355, 34399, 1889, 55, 1

Offset: 0

Vladeta Jovovic, Jun 20 2007

Row sums give A131236.

			1;
1,1;
1,3,1;
1,6,6,1;
1,10,26,10,1;
1,15,79,79,15,1;
1,21,189,451,189,21,1;
...
or as a symmetric array
1   1    1   1   1  1 1 ...
1   3    6  10  15 21 ...
1   6   26  79 189 ..
1  10   79 451 ..
1  15  189 ..
1  21 ..

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.65(a).

Cf. A049088 (diagonal), A131236, A131237, A088699 and A086885 (sums <= 1), A000217 (column 1)

A131235 := proc(m,n)
   exp((x*y*(3-x*y)+(x+y)*(2-x*y))/2/(1-x*y))/sqrt(1-x*y) ;
   coeftayl(%,y=0,n)*n!;
   coeftayl(%,x=0,m)*m! ;
end proc: # R. J. Mathar, Mar 20 2018

T[n_, k_] := Module[{ex}, ex = Exp[(x*y*(3 - x*y) + (x + y)*(2 - x*y))/2/(1 - x*y)]/Sqrt[1 - x*y]; SeriesCoefficient[ex, {y, 0, k}]*k! // SeriesCoefficient[#, {x, 0, n}]*n!&];
Table[T[n - k, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 14 2023, after R. J. Mathar *)

G.f. column 2: (-1-x-6*x^2+x^3+x^4)/(x-1)^5. -  R. J. Mathar, Mar 20 2018
T(n,2) = (4+8*n+5*n^2+6*n^3+n^4)/4. -  R. J. Mathar, Mar 20 2018
G.f. column 3: -(1+3*x+30*x^2+73*x^3+24*x^4-48*x^5+7*x^6)/(x-1)^7 . -  R. J. Mathar, Mar 20 2018
T(n,3) = (8+58*n^2+3*n^3+n^4+9*n^5+n^6)/8. - R. J. Mathar, Mar 20 2018

A176120 Triangle read by rows: Sum_{j=0..k} binomial(n, j)binomial(k, j)j!.

Original entry on oeis.org

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

Offset: 0

Roger L. Bagula, Apr 09 2010

The number of ways of placing any number k = 0, 1, ..., min(n,m) of non-attacking rooks on an n X m chessboard. - R. J. Mathar, Dec 19 2014

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

O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, Springer, 2009, page 46.

Seiichi Manyama, Rows n = 0..139, flattened
Wikipedia, Rook polynomial

Cf. A086885 (table without column 0), A129833 (row sums).

Cf. A000262, A002061, A002720, A082545, A135859, A343832.

A176120:=func< n,k| (&+[Factorial(j)*Binomial(n,j)*Binomial(k,j): j in [0..k]]) >;
[A176120(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Aug 11 2022

A176120 := proc(i,j)
        add(binomial(i,k)*binomial(j,k)*k!,k=0..j) ;
end proc: # R. J. Mathar, Jul 28 2016

T[n_, m_]:= T[n,m]= Sum[Binomial[n, k]*Binomial[m, k]*k!, {k, 0, m}];
Table[T[n, m], {n,0,12}, {m,0,n}]//Flatten

def A176120(n,k): return sum(factorial(j)*binomial(n,j)*binomial(k,j) for j in (0..k))
flatten([[A176120(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Aug 11 2022

Sum_{k=0..n} T(n, k) = A129833(n).
T(n,m) = A088699(n, m). - Peter Bala, Aug 26 2013
T(n,m) = A086885(n, m). - R. J. Mathar, Dec 19 2014
From G. C. Greubel, Aug 11 2022: (Start)
T(n, k) = Hypergeometric2F1([-n, -k], [], 1).
T(2*n, n) = A082545(n).
T(2*n+1, n) = A343832(n).
T(n, n) = A002720(n).
T(n, n-1) = A000262(n), n >= 1.
T(n, 1) = A000027(n+1).
T(n, 2) = A002061(n+1).
T(n, 3) = A135859(n+1). (End)

cp's OEIS Frontend

A002720 Number of partial permutations of an n-set; number of n X n binary matrices with at most one 1 in each row and column.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Python

SageMath

Formula

Extensions

A343832 a(n) = Sum_{k=0..n} k! * binomial(n,k) * binomial(2*n+1,k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

SageMath

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

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A099597 Array T(n,k) read by antidiagonals: expansion of exp(x+y)/(1-xy).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A287274 Array read by antidiagonals: T(m,n) = number of dominating sets in the lattice (rook) graph K_m X K_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A056953 Denominators of continued fraction for alternating factorial.

A176120 Triangle read by rows: Sum_{j=0..k} binomial(n, j)binomial(k, j)j!.