|
|
A030662
|
|
Number of combinations of n things from 1 to n at a time, with repeats allowed.
|
|
31
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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
Also, number of square submatrices of a square matrix. - Jono Henshaw (jjono(AT)hotmail.com), Apr 22 2008
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
|
|
LINKS
|
Joseph D. Horton and Andrew Kurn, Counting sequences with complete increasing subsequences, Congress Numerantium, 33 (1981), 75-80. MR 681905
|
|
FORMULA
|
a(n) = 2*(2*n-1)!/(n!*(n-1)!)-1.
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
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
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)
|
|
EXAMPLE
|
G.f. = x + 5*x^2 + 19*x^3 + 69*x^4 + 251*x^5 + 923*x^6 + 3431*x^7 + ...
|
|
MAPLE
|
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
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(Sage)
def a(n) : return binomial(2*n, n) - 1
(Python)
from math import comb
def a(n): return comb(2*n, n) - 1
(Magma) [(n+1)*Catalan(n)-1: n in [1..40]]; // G. C. Greubel, Apr 07 2024
|
|
CROSSREFS
|
Central column of triangle A014473.
Right-hand column 2 of triangle A102541.
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
Donald Mintz (djmintz(AT)home.com)
|
|
STATUS
|
approved
|
|
|
|