A006902 -id:A006902 - cp's OEIS frontend

A047909 Array read by antidiagonals upwards: h(n,k) = number of sequences with n copies each of 1,2,...,k and longest increasing subsequence of length k (n>=1, k>=1).

1, 1, 1, 1, 5, 1, 1, 19, 47, 1, 1, 69, 1306, 641, 1, 1, 251, 31451, 195709, 11389, 1, 1, 923, 729811, 46922017, 50775091, 248749, 1, 1, 3431, 16928840, 10258694241, 162588279629, 20117051281, 6439075, 1, 1, 12869, 397222288, 2176464012941, 449363984934526, 1077273394836829, 11260558754404, 192621953, 1

Offset: 1

N. J. A. Sloane

Old name was: Triangle of numbers arising from problem of complete increasing subsequences.
Table h_p(k) on page 80 in the Horton & Kurn reference has two typos. - Alois P. Heinz, Feb 05 2016
Conjecture: Column k > 1 is asymptotic to k^(k*n + 1/2) / (2*Pi*n)^((k-1)/2). - Vaclav Kotesovec, Feb 21 2016
Conjecture: Row k > 1 is asymptotic to sqrt(k) * (k^k/(k-1)!)^n * n^((k-1)*n) / exp((k-1)*(n+1)). - Vaclav Kotesovec, Feb 21 2016

			First few antidiagonals are:
  1;
  1,   1;
  1,   5,      1;
  1,  19,     47,        1;
  1,  69,   1306,      641,        1;
  1, 251,  31451,   195709,    11389,      1;
  1, 923, 729811, 46922017, 50775091, 248749,   1;
  ...
First few rows are:
  1,   1,        1,             1,                   1, ...
  1,   5,       47,           641,               11389, ...
  1,  19,     1306,        195709,            50775091, ...
  1,  69,    31451,      46922017,        162588279629, ...
  1, 251,   729811,   10258694241,     449363984934526, ...
  1, 923, 16928840, 2176464012941, 1162145520205261219, ...
  ...

Alois P. Heinz, Antidiagonals n = 1..50, flattened
J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

Columns k=1-10 give: A000012, A030662, A047911, A268840, A268841, A268842, A268843, A268844, A268845, A268846.
Rows n=1-10 give: A000012, A006902, A047910, A268847, A268848, A268849, A268850, A268851, A268852, A268853.
Main diagonal gives A268485.

g:= proc(l) option remember; (n-> f(l[1..nops(l)-1])*
      binomial(n-1, l[-1]-1)+ add(f(sort(subsop(j=l[j]
      -1, l))), j=1..nops(l)-1))(add(i, i=l))
    end:
f:= l-> (n-> `if`(n<2 or l[-1]=1, 1, `if`(l[1]=0, 0, `if`(
         n=2, binomial(l[1]+l[2], l[1])-1, g(l)))))(nops(l)):
h:= (n, k)-> f([n$k]):
seq(seq(h(1+d-k, k), k=1..d), d=1..10);  # Alois P. Heinz, Feb 11 2016
# second Maple program:
b:= proc(k, p, j, l, t) option remember;
      `if`(k=0, (-1)^t/l!, `if`(p<0, 0, add(b(k-i, p-1,
       j+1, l+i*j, irem(t+i*j, 2))/(i!*p!^i), i=0..k)))
    end:
h:= (p, k)-> k!*(p*k)!*b(k, p-1, 1, 0, irem(k, 2)):
seq(seq(h(1+d-k, k), k=1..d), d=1..10);  # Alois P. Heinz, Mar 03 2016

g[l_] := g[l] = Function[n, f[l[[1 ;; -2]]]*Binomial[n-1, l[[-1]]-1] + Sum[ f[Sort[ReplacePart[l, j -> l[[j]] - 1]]], {j, 1, Length[l] -1}]][ Total[ l]]; f[l_] := Function [n, If[n<2 || l[[-1]]==1, 1, If[l[[1]]==0, 0, If[n == 2, Binomial[l[[1]] + l[[2]], l[[1]] ] - 1, g[l]]]]][Length[l]]; h[n_, k_] := f[Array[n&, k]]; Table[Table[h[1+d-k, k], {k, 1, d}], {d, 1, 10}] // Flatten (* Jean-François Alcover, Feb 19 2016, after Alois P. Heinz *)

Reference gives explicit formula.

New name, two terms corrected and more terms from Alois P. Heinz, Feb 08 2016

A082545 a(n) = (2n)! Sum_{k=0..n} binomial(n,k)/(n+k)!.

Original entry on oeis.org

1, 3, 21, 229, 3393, 63591, 1442173, 38398641, 1174226049, 40558249963, 1561734494661, 66335687785533, 3081211226192641, 155369391396527439, 8452596370942940973, 493494408990278911561, 30777323181433121541633, 2042075395611656190239571

Offset: 0

Vladeta Jovovic, May 11 2003

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..365

Cf. A006902, A343832.

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

a:= n-> simplify(n!*LaguerreL(n$2, -1)):
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 27 2017

Table[n!*LaguerreL[n, n, -1], {n,0,17}] (* Jean-François Alcover, Jun 04 2019 *)

a(n) = sum(k=0, n, k!*binomial(n, k)*binomial(2*n, k)); \\ Seiichi Manyama, May 01 2021

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

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

a(n) = n!*LaguerreL(n, n, -1).
n*a(n) + (n^3-5*n^2-n+2)*a(n-1) - 2*(n+1)*(2*n-3)*(n-1)^2*a(n-2) = 0. - Vladeta Jovovic, Jul 16 2004
E.g.f.: exp((-2*x+1-(1-4*x)^(1/2))/(2*x))/(1-4*x)^(1/2). - Mark van Hoeij, Oct 31 2011
a(n) ~ n^n*2^(2*n+1/2)/exp(n-1). - Vaclav Kotesovec, Sep 27 2012
a(n) = n!*binomial(2*n,n)*hypergeom([-n], [1+n], -1). - Peter Luschny, May 04 2017
a(n) = n! * [x^n] exp(x/(1 - x))/(1 - x)^(n+1). - Ilya Gutkovskiy, Nov 21 2017

A267480 Number T(n,k) of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 5, 0, 1, 42, 47, 0, 1, 351, 1527, 641, 0, 1, 3113, 43910, 54987, 11389, 0, 1, 29003, 1302660, 3844840, 2059147, 248749, 0, 1, 280220, 40970298, 265777225, 285588543, 82025038, 6439075, 0, 1, 2782475, 1364750889, 19104601915, 37783672691, 19773928713, 3507289363, 192621953

Offset: 0

Alois P. Heinz, Jan 15 2016

			Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,      5;
  0, 1,     42,       47;
  0, 1,    351,     1527,       641;
  0, 1,   3113,    43910,     54987,     11389;
  0, 1,  29003,  1302660,   3844840,   2059147,   248749;
  0, 1, 280220, 40970298, 265777225, 285588543, 82025038, 6439075;

Alois P. Heinz, Rows n = 0..18, flattened
Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, arXiv:1505.01389, 2015
Shalosh B. Ekhad and Doron Zeilberger, The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r, 2014

Main diagonal gives A006902.
Row sums give A000680.
Cf. A267479, A267532.

T(n,0) = A267479(n,0), T(n,k) = A267479(n,k) - A267479(n,k-1) for k>0.

Sum_{k=0..n-1} T(n,k) = A267532(n).

A267532 Number of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length < n.

Original entry on oeis.org

0, 0, 1, 43, 1879, 102011, 7235651, 674641325, 81537026047, 12498099730471, 2375632826877259, 548818073236649129, 151476182218777630655, 49229890784448694885163, 18608906461974462064310179, 8094874797394331233877338741, 4015057931973886657462193434111

Offset: 0

Alois P. Heinz, Jan 16 2016

nonn

Or number of words on {1,1,2,2,...,n,n} avoiding the pattern 12...n.

			a(2) = 1: 2211.
a(3) = 43: 113322, 131322, 133122, 133212, 133221, 211332, 213132, 213312, 213321, 221133, 221313, 221331, 223113, 223131, 223311, 231132, 231312, 231321, 232113, 232131, 232311, 233112, 233121, 233211, 311322, 313122, 313212, 313221, 321132, 321312, 321321, 322113, 322131, 322311, 323112, 323121, 323211, 331122, 331212, 331221, 332112, 332121, 332211.

Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A000079, A000142, A000680, A006902, A010050, A267479, A267480, A269042.

Column k=2 of A269129.

b:= proc(n) option remember; `if`(n<3, [1$2, 5][n+1], (
      (n^3+n^2-7*n+4)*b(n-1)-2*(2*n-3)*(n-1)^3*b(n-2))/(n-2))
    end:
a:= n-> (2*n)!/(2^n)-b(n):
seq(a(n), n=0..20);

a(n) = (2*n)! * ( 1/(2^n) - Sum_{k=0..n} (-1)^k * C(n,k) / (n+k)! ).
a(n) = A000680(n) - A006902(n).
a(n) = A267479(n,n-1) for n>0.
a(n) = Sum_{k=0..n-1} A267480(n,k).

A295384 a(n) = n!Sum_{k=0..n} (-1)^kbinomial(2n,n-k)n^k/k!.

Original entry on oeis.org

1, 1, 0, -15, -112, -135, 9504, 152425, 610560, -27692847, -765107200, -6289891839, 213472972800, 9380264146825, 129378550468608, -3294028613874375, -226623617585053696, -4707649131227927775, 83803818828756418560, 9446689798312021406353, 277055229100887244800000

Offset: 0

Ilya Gutkovskiy, Nov 21 2017

sign

G. C. Greubel, Table of n, a(n) for n = 0..400
Eric Weisstein's World of Mathematics, Laguerre Polynomial
Wikipedia, Laguerre polynomials
Index entries for sequences related to Laguerre polynomials

Cf. A006902, A277373, A277423, A295385.

[Factorial(n)*(&+[(-1)^k*Binomial(2*n,n-k)*n^k/Factorial(k): k in [0..n]]): n in [0..30]]; // G. C. Greubel, Feb 06 2018

a := n -> pochhammer(n, n)*hypergeom([1 - n], [n], n):
seq(simplify(a(n)), n = 0..20); # Peter Luschny, Mar 23 2023

Table[n! SeriesCoefficient[Exp[-n x/(1 - x)]/(1 - x)^(n + 1), {x, 0, n}], {n, 0, 20}]
Table[n! LaguerreL[n, n, n], {n, 0, 20}]
Table[(-1)^n HypergeometricU[-n, n + 1, n], {n, 0, 20}]
Join[{1}, Table[n! Sum[(-1)^k Binomial[2 n, n - k] n^k/k!, {k, 0, n}], {n, 1, 20}]]

for(n=0,30, print1(n!*sum(k=0,n, (-1)^k*binomial(2*n,n-k)*n^k/k!), ", ")) \\ G. C. Greubel, Feb 06 2018

a(n) = n! * [x^n] exp(-n*x/(1 - x))/(1 - x)^(n+1).
a(n) = n!*Laguerre(n,n,n).
a(n) = Pochhammer(n, n)*hypergeom([1 - n], [n], n). - Peter Luschny, Mar 23 2023

A343861 Coefficient triangle of generalized Laguerre polynomials n!*L(n,n,x) (rising powers of x).

Original entry on oeis.org

1, 2, -1, 12, -8, 1, 120, -90, 18, -1, 1680, -1344, 336, -32, 1, 30240, -25200, 7200, -900, 50, -1, 665280, -570240, 178200, -26400, 1980, -72, 1, 17297280, -15135120, 5045040, -840840, 76440, -3822, 98, -1, 518918400, -461260800, 161441280, -29352960, 3057600, -188160, 6720, -128, 1

Offset: 0

Seiichi Manyama, May 01 2021

			The triangle begins:
       1;
       2,      -1;
      12,      -8,      1;
     120,     -90,     18,     -1;
    1680,   -1344,    336,    -32,    1;
   30240,  -25200,   7200,   -900,   50,  -1;
  665280, -570240, 178200, -26400, 1980, -72, 1;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened
Wikipedia, Laguerre polynomials
Index entries for sequences related to Laguerre polynomials

For k=0..1 the (unsigned) columns give A001813, A092956(n-1).
Row sums (signed) give A006902, row sums (unsigned) give A082545.
Cf. A066667, A062137, A062138, A062139, A062140.

[(-1)^k*Factorial(n-k)*Binomial(n,k)*Binomial(2*n, n+k): k in [0..n], n in [0..12]]; // G. C. Greubel, Aug 11 2022

T[n_, k_] := (-1)^k * (2*n)! * Binomial[n, k]/(k + n)!; Table[T[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Amiram Eldar, May 11 2021 *)

T(n, k) = (-1)^k*(2*n)!*binomial(n,k)/(k+n)!;

PARI
```
row(n) = Vecrev(n!*pollaguerre(n, n));
```

def A343861(n,k): return (-1)^k*factorial(n-k)*binomial(n,k)*binomial(2*n,n+k)
flatten([[A343861(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Aug 11 2022

T(n, k) = (-1)^k * n! * binomial(2*n,n-k)/k! = (-1)^k * (2*n)! * binomial(n,k)/(k+n)!.
T(n, 0) = A001813(n).
T(n, 1) = -A092956(n-1).
Sum_{k=0..n} T(n, k) = A006902(n).
Sum_{k=0..n} (-1)^k * T(n, k) = A082545(n).

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

Original entry on oeis.org

1, 2, 11, 104, 1405, 24694, 534223, 13719404, 407730041, 13760958410, 519827337331, 21726980525392, 995403499490101, 49600090942276094, 2670566242480261175, 154500457959360271124, 9557826199486960327153, 629586464929967678553874, 43994787057844036765113691

Offset: 0

Seiichi Manyama, May 03 2021

nonn

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

Cf. A006902, A343832, A343890.

a[n_] := n!*LaguerreL[n, n + 1, 1]; Array[a, 19, 0] (* Amiram Eldar, May 11 2021 *)

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

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

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

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

a(n) = (2*n+1)! * Sum_{k=0..n} (-1)^k * binomial(n,k)/(k+n+1)!.
a(n) = n! * Sum_{k=0..n} (-1)^(n-k) * 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) ~ 2^(2*n + 3/2) * n^n / exp(n+1). - Vaclav Kotesovec, May 03 2021

A358112 Table read by rows. A statistic of permutations of the multiset {1,1,2,2,...,n,n}.

Original entry on oeis.org

1, 5, 1, 47, 42, 1, 641, 1659, 219, 1, 11389, 72572, 28470, 968, 1, 248749, 3610485, 3263402, 357746, 4017, 1, 6439075, 204023334, 371188155, 95559940, 3853617, 16278, 1, 192621953, 12989570167, 43844432805, 22448025251, 2216662051, 38270373, 65399, 1

Offset: 1

Peter Luschny, Oct 30 2022

Table 1, page 12 in Maazouz and Pitman (note a typo in T(2, 0)).

			[n\d]    0            1           2           3           4           5     6
-----------------------------------------------------------------------------
[1]         1;
[2]         5,           1;
[3]        47,          42,           1;
[4]       641,        1659,         219,           1;
[5]     11389,       72572,       28470,         968,          1;
[6]    248749,     3610485,     3263402,      357746,       4017,        1;
[7]   6439075,   204023334,   371188155,    95559940,    3853617,    16278, 1
[8] 192621953, 12989570167, 43844432805, 22448025251, 2216662051, 38270373,
65399, 1

Yassine El Maazouz and Jim Pitman, The Bernoulli clock: probabilistic and combinatorial interpretations of the Bernoulli polynomials by circular convolution, arXiv:2210.02027 [math.PR], Oct. 2022.

Cf. A006902 (row 0), A000680 (row sums).

P := (n, x) -> (2*n)!*add(add(binomial(n, k)*binomial(n-k, j)*
(-1)^(n-k-j)*max(x - k, 0)^(2*n - j)/(2*n - j)!, j = 0..n-k), k = 0..n):
Trow := n -> seq(P(n, k+1) - P(n, k), k = 0..n-1):
seq(print(Trow(n)), n = 1..8);

T(n, k) = P(n, k+1) - P(n, k), where P(n, x) = (2*n)!*Sum_{k=0..n} Sum_{j=0..n-k} binomial(n, k)*binomial(n-k, j)*(-1)^(n-k-j)*max(x - k, 0)^(2*n - j)/(2*n - j)!.

cp's OEIS Frontend

A047909 Array read by antidiagonals upwards: h(n,k) = number of sequences with n copies each of 1,2,...,k and longest increasing subsequence of length k (n>=1, k>=1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

A267480 Number T(n,k) of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A267532 Number of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A295384 a(n) = n!*Sum_{k=0..n} (-1)^k*binomial(2*n,n-k)*n^k/k!.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A343861 Coefficient triangle of generalized Laguerre polynomials n!*L(n,n,x) (rising powers of x).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

SageMath

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

A082545 a(n) = (2n)! Sum_{k=0..n} binomial(n,k)/(n+k)!.

A295384 a(n) = n!Sum_{k=0..n} (-1)^kbinomial(2n,n-k)n^k/k!.