cp's OEIS Frontend

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

%I A030662 #116 Aug 05 2025 16:14:43
%S A030662 1,5,19,69,251,923,3431,12869,48619,184755,705431,2704155,10400599,
%T A030662 40116599,155117519,601080389,2333606219,9075135299,35345263799,
%U A030662 137846528819,538257874439,2104098963719,8233430727599,32247603683099,126410606437751,495918532948103
%N A030662 Number of combinations of n things from 1 to n at a time, with repeats allowed.
%C A030662 Add terms of an increasingly bigger diamond-shaped part of Pascal's triangle:
%C A030662 .......................... 1
%C A030662 ............ 1 .......... 1 1
%C A030662 .. 1 ...... 1 1 ........ 1 2 1
%C A030662 . 1 1 =5 . 1 2 1 =19 .. 1 3 3 1 =69
%C A030662 .. 2 ...... 3 3 ........ 4 6 4
%C A030662 ............ 6 ......... 10 10
%C A030662 .......................... 20
%C A030662 -  _Ralf Stephan_, May 17 2004
%C A030662 The prime p divides a((p-1)/2) for p in A002144 (Pythagorean primes). - _Alexander Adamchuk_, Jul 04 2006
%C A030662 Also, number of square submatrices of a square matrix. - Jono Henshaw (jjono(AT)hotmail.com), Apr 22 2008
%C A030662 Partial sums of A051924. - _J. M. Bergot_, Jun 22 2013
%C A030662 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
%C A030662 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
%H A030662 T. D. Noe, <a href="/A030662/b030662.txt">Table of n, a(n) for n = 1..500</a>
%H A030662 Narcisse G. Bell Bogmis, Guy R. Biyogmam, Hesam Safa, and Calvin Tcheka, <a href="https://arxiv.org/abs/2403.14884">Upper bounds on the dimension of the Schur Lie-multiplier of Lie-nilpotent Leibniz n-algebras</a>, arXiv:2403.14884 [math.RA], 2024. See p. 7.
%H A030662 Joseph D. Horton and Andrew Kurn, Counting sequences with complete increasing subsequences, Congress Numerantium, 33 (1981), 75-80. <a href="http://www.ams.org/mathscinet-getitem?mr=681905">MR 681905</a>
%H A030662 Milan Janjic and Boris Petkovic, <a href="http://arxiv.org/abs/1301.4550">A Counting Function</a>, arXiv preprint arXiv:1301.4550 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 13 2013
%H A030662 Milan Janjic and Boris Petkovic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Janjic/janjic45.html">A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers</a>, J. Int. Seq. 17 (2014) # 14.3.5.
%H A030662 Raimundas Vidunas, <a href="https://doi.org/10.1007/s00026-017-0344-2">Counting derangements and Nash equilibria</a>, Ann. Comb. 21, No. 1, 131-152 (2017).
%H A030662 Jianqiang Zhao, <a href="http://arxiv.org/abs/1412.8044">Uniform Approach to Double Shuffle and Duality Relations of Various q-Analogs of Multiple Zeta Values via Rota-Baxter Algebras</a>, arXiv preprint arXiv:1412.8044 [math.NT], 2014.
%F A030662 a(n) = A000984(n) - 1.
%F A030662 a(n) = 2*A001700(n-1) - 1.
%F A030662 a(n) = 2*(2*n-1)!/(n!*(n-1)!)-1.
%F A030662 a(n) = Sum_{k=1..n} binomial(n, k)^2. - _Benoit Cloitre_, Aug 20 2002
%F A030662 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
%F A030662 a(n) = Sum_{i=0..n-1} Sum_{j=0..n-1} binomial(i+j, i). - _N. J. A. Sloane_, Jan 31 2009
%F A030662 Also for n>1: a(n)=(2*n)!/(n!)^2-1. - _Hugo Pfoertner_, Feb 10 2004
%F A030662 a(n) = Sum_{j=1..n} Sum_{i=1..n} (2n-i-j)!/((n-i)!*(n-j)!). - _Alexander Adamchuk_, Jul 04 2006
%F A030662 a(n) = A115112(n) + 1. - Jono Henshaw (jjono(AT)hotmail.com), Apr 22 2008
%F A030662 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
%F A030662 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
%F A030662 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
%F A030662 From _Ilya Gutkovskiy_, Jan 25 2017: (Start)
%F A030662 O.g.f.: (1 - x - sqrt(1 - 4*x))/((1 - x)*sqrt(1 - 4*x)).
%F A030662 E.g.f.: exp(x)*(exp(x)*BesselI(0,2*x) - 1). (End)
%F A030662 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
%F A030662 a(n) = n * binomial(2*n, n) * Sum_{k = 1..n} 1/(k*binomial(n+k, k)). - _Peter Bala_, Aug 05 2025
%e A030662 G.f. = x + 5*x^2 + 19*x^3 + 69*x^4 + 251*x^5 + 923*x^6 + 3431*x^7 + ...
%p A030662 seq(sum((binomial(n,m))^2,m=1..n),n=1..23); # _Zerinvary Lajos_, Jun 19 2008
%p A030662 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
%t A030662 Table[Sum[Sum[(2n-i-j)!/(n-i)!/(n-j)!,{i,1,n}],{j,1,n}],{n,1,20}] (* _Alexander Adamchuk_, Jul 04 2006 *)
%t A030662 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 *)
%o A030662 (Sage)
%o A030662 def a(n) : return binomial(2*n,n) - 1
%o A030662 [a(n) for n in (1..26)] # _Peter Luschny_, Apr 21 2012
%o A030662 (PARI) a(n)=binomial(2*n,n)-1 \\ _Charles R Greathouse IV_, Jun 26 2013
%o A030662 (Python)
%o A030662 from math import comb
%o A030662 def a(n): return comb(2*n, n) - 1
%o A030662 print([a(n) for n in range(1, 27)]) # _Michael S. Branicky_, Jul 11 2023
%o A030662 (Magma) [(n+1)*Catalan(n)-1: n in [1..40]]; // _G. C. Greubel_, Apr 07 2024
%Y A030662 Cf. A000984, A001700, A002144, A051924, A091908, A144660, A322938.
%Y A030662 Column k=2 of A047909.
%Y A030662 Central column of triangle A014473.
%Y A030662 Right-hand column 2 of triangle A102541.
%K A030662 nonn,nice
%O A030662 1,2
%A A030662 Donald Mintz (djmintz(AT)home.com)