A047909 -id:A047909 - cp's OEIS frontend

A030662 Number of combinations of n things from 1 to n at a time, with repeats allowed.

1, 5, 19, 69, 251, 923, 3431, 12869, 48619, 184755, 705431, 2704155, 10400599, 40116599, 155117519, 601080389, 2333606219, 9075135299, 35345263799, 137846528819, 538257874439, 2104098963719, 8233430727599, 32247603683099, 126410606437751, 495918532948103

Offset: 1

Donald Mintz (djmintz(AT)home.com)

Add terms of an increasingly bigger diamond-shaped part of Pascal's triangle:
.......................... 1
............ 1 .......... 1 1
.. 1 ...... 1 1 ........ 1 2 1
. 1 1 =5 . 1 2 1 =19 .. 1 3 3 1 =69
.. 2 ...... 3 3 ........ 4 6 4
............ 6 ......... 10 10
.......................... 20
-  Ralf Stephan, May 17 2004
The prime p divides a((p-1)/2) for p in A002144 (Pythagorean primes). - Alexander Adamchuk, Jul 04 2006
Also, number of square submatrices of a square matrix. - Jono Henshaw (jjono(AT)hotmail.com), Apr 22 2008
Partial sums of A051924. - J. M. Bergot, Jun 22 2013
Number of partitions with Ferrers diagrams that fit in an n X n box (excluding the empty partition of 0). - Michael Somos, Jun 02 2014
Also number of non-descending sequences with length and last number are less or equal to n, and also the number of integer partitions (of any positive integer) with length and largest part are less or equal to n. - Zlatko Damijanic, Dec 06 2024

			G.f. = x + 5*x^2 + 19*x^3 + 69*x^4 + 251*x^5 + 923*x^6 + 3431*x^7 + ...

T. D. Noe, Table of n, a(n) for n = 1..500
Narcisse G. Bell Bogmis, Guy R. Biyogmam, Hesam Safa, and Calvin Tcheka, Upper bounds on the dimension of the Schur Lie-multiplier of Lie-nilpotent Leibniz n-algebras, arXiv:2403.14884 [math.RA], 2024. See p. 7.
Joseph D. Horton and Andrew Kurn, Counting sequences with complete increasing subsequences, Congress Numerantium, 33 (1981), 75-80. MR 681905
Milan Janjic and Boris Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 13 2013
Milan Janjic and Boris Petkovic, A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers, J. Int. Seq. 17 (2014) # 14.3.5.
Raimundas Vidunas, Counting derangements and Nash equilibria, Ann. Comb. 21, No. 1, 131-152 (2017).
Jianqiang Zhao, Uniform Approach to Double Shuffle and Duality Relations of Various q-Analogs of Multiple Zeta Values via Rota-Baxter Algebras, arXiv preprint arXiv:1412.8044 [math.NT], 2014.

Cf. A000984, A001700, A002144, A051924, A091908, A144660, A322938.
Column k=2 of A047909.
Central column of triangle A014473.
Right-hand column 2 of triangle A102541.

[(n+1)*Catalan(n)-1: n in [1..40]]; // G. C. Greubel, Apr 07 2024

seq(sum((binomial(n,m))^2,m=1..n),n=1..23); # Zerinvary Lajos, Jun 19 2008
f:=n->add( add( binomial(i+j,i), i=0..n),j=0..n); [seq(f(n),n=0..12)]; # N. J. A. Sloane, Jan 31 2009

Table[Sum[Sum[(2n-i-j)!/(n-i)!/(n-j)!,{i,1,n}],{j,1,n}],{n,1,20}] (* Alexander Adamchuk, Jul 04 2006 *)
a[n_] := 2*(2*n-1)!/(n*(n-1)!^2)-1; Table[a[n], {n, 1, 26}] (* Jean-François Alcover, Oct 11 2012, from first formula *)

a(n)=binomial(2*n,n)-1 \\ Charles R Greathouse IV, Jun 26 2013

from math import comb
def a(n): return comb(2*n, n) - 1
print([a(n) for n in range(1, 27)]) # Michael S. Branicky, Jul 11 2023

def a(n) : return binomial(2*n,n) - 1
[a(n) for n in (1..26)] # Peter Luschny, Apr 21 2012

a(n) = A000984(n) - 1.
a(n) = 2*A001700(n-1) - 1.
a(n) = 2*(2*n-1)!/(n!*(n-1)!)-1.
a(n) = Sum_{k=1..n} binomial(n, k)^2. - Benoit Cloitre, Aug 20 2002
a(n) = Sum_{j=0..n} Sum_{i=j..n+j} binomial(i, j). - Klaus Strassburger (strass(AT)ddfi.uni-duesseldorf.de), Jul 23 2003
a(n) = Sum_{i=0..n-1} Sum_{j=0..n-1} binomial(i+j, i). - N. J. A. Sloane, Jan 31 2009
Also for n>1: a(n)=(2*n)!/(n!)^2-1. - Hugo Pfoertner, Feb 10 2004
a(n) = Sum_{j=1..n} Sum_{i=1..n} (2n-i-j)!/((n-i)!*(n-j)!). - Alexander Adamchuk, Jul 04 2006
a(n) = A115112(n) + 1. - Jono Henshaw (jjono(AT)hotmail.com), Apr 22 2008
G.f.: Q(0)*(1-4*x)/x - 1/x/(1-x), where Q(k)= 1 + 4*(2*k+1)*x/( 1 - 1/(1 + 2*(k+1)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 11 2013
D-finite with recurrence: n*a(n) +2*(-3*n+2)*a(n-1) +(9*n-14)*a(n-2) +2*(-2*n+5)*a(n-3)=0. - R. J. Mathar, Jun 25 2013
0 = a(n)*(+16*a(n+1) - 70*a(n+2) + 68*a(n+3) - 14*a(n+4)) + a(n+1)*(-2*a(n+1) + 61*a(n+2) - 96*a(n+3) + 23*a(n+4)) + a(n+2)*(-6*a(n+2) + 31*a(n+3)  - 10*a(n+4)) + a(n+3)*(-2*a(n+3) + a(n+4)) for all n in Z. - Michael Somos, Jun 02 2014
From Ilya Gutkovskiy, Jan 25 2017: (Start)
O.g.f.: (1 - x - sqrt(1 - 4*x))/((1 - x)*sqrt(1 - 4*x)).
E.g.f.: exp(x)*(exp(x)*BesselI(0,2*x) - 1). (End)
a(n) = 3*n*Sum_{k=1..n} (-1)^(k+1)/(2*n+k)*binomial(2*n+k,n-k). - Vladimir Kruchinin, Jul 29 2025
a(n) = n * binomial(2*n, n) * Sum_{k = 1..n} 1/(k*binomial(n+k, k)). - Peter Bala, Aug 05 2025

A269129 Number A(n,k) of sequences with k copies each of 1,2,...,n avoiding the pattern 12...n; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 5, 1, 0, 0, 1, 43, 23, 1, 0, 0, 1, 374, 1879, 119, 1, 0, 0, 1, 3199, 173891, 102011, 719, 1, 0, 0, 1, 26945, 16140983, 117392909, 7235651, 5039, 1, 0, 0, 1, 224296, 1474050783, 142951955371, 117108036719, 674641325, 40319, 1

Offset: 0

Alois P. Heinz, Feb 19 2016

			Square array A(n,k) begins:
  0,   0,      0,         0,            0,               0, ...
  1,   0,      0,         0,            0,               0, ...
  1,   1,      1,         1,            1,               1, ...
  1,   5,     43,       374,         3199,           26945, ...
  1,  23,   1879,    173891,     16140983,      1474050783, ...
  1, 119, 102011, 117392909, 142951955371, 173996758190594, ...

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

Columns k=0-10 give: A057427, A033312, A267532, A269113, A269114, A269115, A269116, A269117, A269118, A269119, A269120.
Rows n=0-10 give: A000004, A000007, A000012, A269121, A269122, A269123, A269124, A269125, A269126, A269127, A269128.
Main diagonal gives: A268751.
Cf. A047909, A089759, A187783, A331562.

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=0, 1, `if`(l[1]=0, 0, `if`(n=1 or l[-1]=1, 1,
    `if`(n=2, binomial(l[1]+l[2], l[1])-1, g(l))))))(nops(l)):
A:= (n, k)-> (k*n)!/k!^n - f([k$n]):
seq(seq(A(n, d-n), n=0..d), d=0..12);
# 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:
A:= (n, k)-> (n*k)!*(1/k!^n-b(n, k-1, 1, 0, irem(n, 2))*n!):
seq(seq(A(n, d-n), n=0..d), d=0..12);  # Alois P. Heinz, Mar 03 2016

b[k_, p_, j_, l_, t_] := b[k, p, j, l, t] = If[k == 0, (-1)^t/l!, If[p < 0, 0, Sum[b[k-i, p-1, j+1, l + i j, Mod[t + i j, 2]]/(i! p!^i), {i, 0, k}]] ];
A[n_, k_] := (n k)! (1/k!^n - b[n, k-1, 1, 0, Mod[n, 2]] n!); Table[ Table[ A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Apr 07 2016, after Alois P. Heinz *)

A(n,k) = A089759(k,n) - A047909(k,n) = A187783(n,k) - A047909(k,n).

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

Original entry on oeis.org

1, 1, 5, 47, 641, 11389, 248749, 6439075, 192621953, 6536413529, 248040482741, 10407123510871, 478360626529345, 23903857657114837, 1290205338991689821, 74803882225482661259, 4636427218380366565889, 305927317398343461908785, 21410426012751471702223333

Offset: 0

Simon Plouffe and N. J. A. Sloane

Number of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length n. a(2) = 5: 1122, 1212, 1221, 2112, 2121. - Alois P. Heinz, Jan 18 2016

J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congress. Numerantium, 33 (1981), 75-80.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..360 (terms n = 1..100 from T. D. Noe)
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], 2022.

Row n=2 of A047909.
Main diagonal of A267480.
Cf. A082545.

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

a:= proc(n) option remember; `if`(n<3, [1$2, 5][n+1], (
      (n^3+n^2-7*n+4)*a(n-1)-2*(2*n-3)*(n-1)^3*a(n-2))/(n-2))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Jan 15 2016

Table[(-1)^k HypergeometricU[-k, 1+k, 1], {k,0,20}] (* Vladimir Reshetnikov, Feb 16 2011 *)

a(n)=round(hyperu(-n,n+1,1)*(-1)^n) \\ Charles R Greathouse IV, Dec 30 2014

[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). - Vladeta Jovovic, May 11 2003
(n-2)*a(n) - (n^3+n^2-7*n+4)*a(n-1) + 2*(2*n-3)*(n-1)^3*a(n-2) = 0. - Vladeta Jovovic, Jul 16 2004
a(n) ~ n^n*2^(2*n+1/2)/exp(n+1). - Vaclav Kotesovec, Jun 22 2013
a(n) = B_n(n*0!,(n-1)*1!, ..., 1*(n-1)!), where B_n(x1, ..., xn) is the n-th complete Bell polynomial. - Max Alekseyev, Jul 04 2015
a(n) = n!*binomial(2*n,n)*hypergeom([-n], [n+1], 1). - Peter Luschny, May 04 2017
a(n) = n!*Z(S_n; n, n-1, ..., 1) where Z(S_n) is the cycle index of the symmetric group of order n. - Sean A. Irvine, Nov 14 2017
a(n) = n! * [x^n] exp(-x/(1 - x))/(1 - x)^(n+1). - Ilya Gutkovskiy, Nov 21 2017
E.g.f.: exp(1-c(x))/sqrt(1-4*x), where c(x) = (1-sqrt(1-4*x))/(2*x) is the Catalan number generating function. - Ira M. Gessel, Jun 04 2021

a(0)=1 prepended by Alois P. Heinz, Jan 15 2016

A268485 Number of sequences with n copies each of 1,2,...,n and longest increasing subsequence of length n.

Original entry on oeis.org

1, 1, 5, 1306, 46922017, 449363984934526, 1878320344216429026862153, 5078529731893937404909347067888886466, 12324197596430667064913735085330208112438377122058241, 35544813569338447788721757701614208334438136486811525386710064098254294

Offset: 0

Alois P. Heinz, Feb 05 2016

nonn

			a(2) = 5: 1122, 1212, 1221, 2112, 2121.
a(3) = 1306: 111222333, 111223233, 111223323, ..., 332212113, 332212131, 332212311.

Alois P. Heinz, Table of n, a(n) for n = 0..27
J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

Main diagonal of A047909.

Cf. A268667, A268751.

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)):
a:= n-> f([n$n]):
seq(a(n), n=0..8);
# 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:
a:= n-> n!*(n^2)!*b(n, n-1, 1, 0, irem(n, 2)):
seq(a(n), n=0..10);  # Alois P. Heinz, Mar 03 2016

b[k_, p_, j_, l_, t_] := b[k, p, j, l, t] = If[k==0, (-1)^t/l!, If[p<0, 0, Sum[b[k-i, p-1, j+1, l+i*j, Mod[t + i*j, 2]]/(i!*p!^i), {i, 0, k}]]];
a[n_] := n!*(n^2)!*b[n, n - 1, 1, 0, Mod[n, 2]];
Table[a[n], {n, 0, 10}] (* Jean-François Alcover, Jun 18 2018, translated from 2nd Maple program *)

A268698 Total number of sequences with p_j copies of j and longest increasing subsequence of length k summed over all partitions [p_1, p_2, ..., p_k] of n.

Original entry on oeis.org

1, 1, 2, 4, 13, 36, 157, 554, 2800, 12530, 70772, 362188, 2370564, 13658713, 95366064, 642861687, 4774830263, 34769374156, 288999332899, 2255537559077, 19693313843687, 172690825379198, 1572921138465599, 14538979953843188, 145980379536597239

Offset: 0

Alois P. Heinz, Feb 11 2016

nonn

			The partitions of 4 are [1,1,1,1], [2,1,1], [2,2], [3,1], [4] giving the a(4) = 13 sequences: 1234, 1123, 1213, 1231, 1122, 1212, 1221, 2112, 2121, 1112, 1121, 1211, 1111.

Alois P. Heinz, Table of n, a(n) for n = 0..60
J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

Cf. A047909, A268699, A268700, A268701.

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, i, l)-> `if`(n=0 or i=1, f([1$n, l[]]), h(n, i-1, l)+
                `if`(i>n, 0, h(n-i, i, [i, l[]]))):
a:= n-> h(n$2, []):
seq(a(n), n=0..25);

g[l_] := g[l] = Function[n, f[Most[l]]*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_, i_, l_] := h[n, i, l] = If[n == 0 || i == 1, f[Join[Array[1&, n], l]], h[n, i - 1, l] + If[i>n, 0, h[n-i, i, Prepend[l, i]]]]; a[n_] := h[n, n, {}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 02 2017, translated from Maple *)

A268699 Total number of sequences with c_j copies of j and longest increasing subsequence of length k summed over all compositions [c_1, c_2, ..., c_k] of n.

Original entry on oeis.org

1, 1, 2, 6, 22, 95, 471, 2618, 16052, 107313, 775045, 6002106, 49536510, 433485429, 4004680967, 38912323570, 396393445096, 4221367056961, 46878865762185, 541660919690866, 6498811587848690, 80818650742133717, 1040037672241415947, 13829246515918840106

Offset: 0

Alois P. Heinz, Feb 11 2016

nonn

			The compositions of 4 are [1,1,1,1], [2,1,1], [1,2,1], [1,1,2], [2,2], [3,1], [1,3], [4] giving the a(4) = 22 sequences: 1234, 1123, 1213, 1231, 1223, 2123, 1232, 1233, 1323, 3123, 1122, 1212, 1221, 2112, 2121, 1112, 1121, 1211, 1222, 2122, 2212, 1111.

Alois P. Heinz, Table of n, a(n) for n = 0..60
J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

Cf. A047909, A268698, A268700, A268701.

c:= l-> f(l)*nops(l)!/(v-> mul(coeff(v, x, j)!,
        j=0..degree(v)))(add(x^i, i=l)):
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, i, l)-> `if`(n=0 or i=1, c([1$n, l[]]), h(n, i-1, l)+
                `if`(i>n, 0, h(n-i, i, [i, l[]]))):
a:= n-> h(n$2, []):
seq(a(n), n=0..25);

c[l_] := f[l]*Length[l]!/Function[v, Product[Coefficient[v, x, j]!, {j, 0, Exponent[v, x]}]][Sum[x^i, {i, l}]];
g[l_] := g[l] = Function[n, f[Most@l]*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_, i_, l_] := If[n == 0 || i == 1, c[Join[Array[1&, n], l]], h[n, i-1, l] + If[i > n, 0, h[n-i, i, Join[{i}, l]]]];
a[n_] := h[n, n, {}];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Sep 06 2022, after Alois P. Heinz *)

A268700 Total number of sequences with p_j copies of j and longest increasing subsequence of length k summed over all partitions [p_1, p_2, ..., p_k] of n into distinct parts.

Original entry on oeis.org

1, 1, 1, 3, 4, 14, 46, 111, 330, 1614, 7348, 21340, 98145, 379405, 2633085, 14871033, 57284558, 278927415, 1609313975, 8289565670, 74945364815, 522977754235, 2403799401259, 14180489136597, 83964652635668, 623008803758260, 3918144764978718, 46950727351392315

Offset: 0

Alois P. Heinz, Feb 11 2016

nonn

			The partitions of 4 into distinct parts are [3,1], [4] giving the a(4) = 4 sequences: 1112, 1121, 1211, 1111.

Alois P. Heinz, Table of n, a(n) for n = 0..90
J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

Cf. A047909, A268698, A268699, A268701.

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, i, l)-> `if`(n>i*(i+1)/2, 0, `if`(n=0, f(l), h(n, i-1, l)
               +`if`(i>n, 0, h(n-i, i-1, [i, l[]])))):
a:= n-> h(n$2, []):
seq(a(n), n=0..30);

g[l_] := g[l] = Function[n, f[Most[l]]*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_, i_, l_] := If[n>i*(i+1)/2, 0, If[n==0, f[l], h[n, i-1, l] + If[i>n, 0, h[n-i, i-1, Join[{i}, l]]]]]; a[n_] := h[n, n, {}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 11 2017, translated from Maple *)

A268701 Total number of sequences with c_j copies of j and longest increasing subsequence of length k summed over all compositions [c_1, c_2, ..., c_k] of n into distinct parts.

Original entry on oeis.org

1, 1, 1, 5, 7, 27, 195, 421, 1619, 8675, 105757, 274029, 1402193, 6625987, 55349787, 975068069, 3137395939, 17960895375, 101880880461, 696011551909, 7596647200175, 197122787505191, 723879298052695, 4905597865756059, 29537689035766501, 227793692735075911

Offset: 0

Alois P. Heinz, Feb 11 2016

nonn

			The compositions of 4 into distinct parts are [3,1], [1,3], [4] giving the a(4) = 7 sequences: 1112, 1121, 1211, 1222, 2122, 2212, 1111.

Alois P. Heinz, Table of n, a(n) for n = 0..90
J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

Cf. A047909, A268698, A268699, A268700.

c:= l-> f(l)*nops(l)!/(v-> mul(coeff(v, x, j)!,
        j=0..degree(v)))(add(x^i, i=l)):
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, i, l)-> `if`(n>i*(i+1)/2, 0, `if`(n=0, c(l), h(n, i-1, l)
               +`if`(i>n, 0, h(n-i, i-1, [i, l[]])))):
a:= n-> h(n$2, []):
seq(a(n), n=0..30);

c[l_] := f[l]*Length[l]!/Function[v, Product[Coefficient[v, x, j]!,{j, 0, Exponent[v, x]}]][Sum[x^i, {i, l}]];
g[l_] := g[l] = Function[n, f[Most[l]]*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_, i_, l_] := If[n > i (i + 1)/2, 0, If[n == 0, c[l], h[n, i - 1, l] + If[i > n, 0, h[n - i, i - 1, Join[{i}, l]]]]];
a[n_] := h[n, n, {}];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jul 12 2021, after Alois P. Heinz *)

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

Original entry on oeis.org

1, 1, 19, 1306, 195709, 50775091, 20117051281, 11260558754404, 8445885515991841, 8167981106765263789, 9891092676022013399311, 14655352586540027231760166, 26075763312196388476329754309, 54857291862194079908910267234631, 134685123389924834385817028487259189

Offset: 0

N. J. A. Sloane

nonn

Old name was: Row 3 of A047909.

			a(2) = 19: 111222, 112122, 112212, 112221, 121122, 121212, 121221, 122112, 122121, 122211, 211122, 211212, 211221, 212112, 212121, 212211, 221112, 221121, 221211. - _Alois P. Heinz_, Jan 18 2016

Alois P. Heinz, Table of n, a(n) for n = 0..200
J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

Cf. A047909.

a:= proc(n) option remember; `if`(n<4, [1$2, 19, 1306][n+1],
      ((8*(-2970*n^3-7712*n^2+13777*n-25581+1700*n^4))*a(n-1)
      -(27*(3*n-7))*(3*n-10)*(3*n-8)*(3*n-11)*(1279*n-2397)*
      (n-2)^2*(n-3)^2*a(n-4) +(18*(3*n-7))*(3*n-8)*(1530*n^5
      -7569*n^4+16757*n^3-12919*n^2-34332*n+56657)*(n-2)^2*
      a(n-3) -(12*(-76223*n-62066*n^5+1530*n^7-474622*n^3
      +1611*n^6-161700+242849*n^4+474957*n^2))*a(n-2))/
      (2720*n-8016))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Feb 04 2016

Table[Sum[Sum[k!*(3*k)!*(-1)^j / (i!*j! * (k-i-j)! * (k+j+2*i)! * 2^(k-i-j)), {j, 0, k-i}], {i, 0, k}], {k, 0, 20}] (* Vaclav Kotesovec, Mar 02 2016, after Horton and Kurn *)

Reference gives explicit formula (see page 79): a(k) = h3(k) = Sum_{i=0..k} (Sum_{j=0..k-i} k! * (3*k)! * (-1)^j / (i! * j! * (k-i-j)! * (k+j+2*i)! * 2^(k-i-j))), independently obtained by D. Jackson.
Recurrence: 8*(n-3)*(n-2)^2*a(n) = 4*(n-3)*(10*n^5 - 28*n^4 - 18*n^3 + 117*n^2 - 111*n + 32)*a(n-1) - 6*(n-1)^3*(3*n - 5)*(3*n - 4)*(n^4 + 3*n^3 - 37*n^2 + 71*n - 36)*a(n-2) + 9*(n-2)^3*(n-1)^4*(3*n - 8)*(3*n - 7)*(3*n - 5)*(3*n - 4)*a(n-3). - Vaclav Kotesovec, Feb 21 2016
a(n) ~ 3^(3*n+1/2) * n^(2*n) / (2^n * exp(2*n+2)). - Vaclav Kotesovec, Feb 21 2016

Terms a(0), a(5)-a(14) and new name from Alois P. Heinz, Jan 18 2016

A047911 Number of sequences with n copies each of 1, 2, 3 and longest increasing subsequence of length 3.

Original entry on oeis.org

1, 47, 1306, 31451, 729811, 16928840, 397222288, 9450343019, 227749730869, 5549991941777, 136518857557006, 3384666013449308, 84477567863100244, 2120568396642137720, 53494945450407470656, 1355345188539405424235, 34469856482096766083833, 879619709716580703808739

Offset: 1

N. J. A. Sloane

nonn

Old name was: Column 3 of A047909.

			a(2) = 47: 112233, 112323, 112332, 113223, 113232, 121233, 121323, 121332, 122133, 122313, 122331, 123123, 123132, 123213, 123231, 123312, 123321, 131223, 131232, 132123, 132132, 132213, 132231, 132312, 132321, 211233, 211323, 212133, 212313, 212331, 213123, 213213, 213231, 231123, 231213, 231231, 311223, 311232, 312123, 312132, 312213, 312231, 312312, 312321, 321123, 321213, 321231. - _Alois P. Heinz_, Feb 05 2016

Alois P. Heinz, Table of n, a(n) for n = 1..700
J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

Cf. A047909.

Reference gives explicit formula.
a(n) ~ 3^(3*n+1/2) / (2*Pi*n). - Vaclav Kotesovec, Feb 21 2016
Recurrence: 2*(n-1)*n^2*(2*n - 1)*(285*n^5 - 3103*n^4 + 13059*n^3 - 26689*n^2 + 26560*n - 10304)*a(n) = (n-1)*(47595*n^8 - 576626*n^7 + 2865154*n^6 - 7617380*n^5 + 11803635*n^4 - 10846922*n^3 + 5730080*n^2 - 1580640*n + 172800)*a(n-1) - 3*(3*n - 5)*(3*n - 4)*(19095*n^7 - 201061*n^6 + 842141*n^5 - 1814447*n^4 + 2160932*n^3 - 1410228*n^2 + 459104*n - 55296)*a(n-2) + 72*(3*n - 8)*(3*n - 7)*(3*n - 5)*(3*n - 4)*(285*n^5 - 1678*n^4 + 3497*n^3 - 3280*n^2 + 1372*n - 192)*a(n-3). - Vaclav Kotesovec, Mar 03 2016

a(7)-a(18) from Alois P. Heinz, Jan 19 2016

New name from Alois P. Heinz, Feb 11 2016

cp's OEIS Frontend

A030662 Number of combinations of n things from 1 to n at a time, with repeats allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

A269129 Number A(n,k) of sequences with k copies each of 1,2,...,n avoiding the pattern 12...n; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A268485 Number of sequences with n copies each of 1,2,...,n and longest increasing subsequence of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A268698 Total number of sequences with p_j copies of j and longest increasing subsequence of length k summed over all partitions [p_1, p_2, ..., p_k] of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A268699 Total number of sequences with c_j copies of j and longest increasing subsequence of length k summed over all compositions [c_1, c_2, ..., c_k] of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A268700 Total number of sequences with p_j copies of j and longest increasing subsequence of length k summed over all partitions [p_1, p_2, ..., p_k] of n into distinct parts.

Views

Author

Keywords

Examples

Links