A165817 Number of compositions (= ordered integer partitions) of n into 2n parts.

1, 2, 10, 56, 330, 2002, 12376, 77520, 490314, 3124550, 20030010, 129024480, 834451800, 5414950296, 35240152720, 229911617056, 1503232609098, 9847379391150, 64617565719070, 424655979547800, 2794563003870330, 18412956934908690, 121455445321173600

Offset

0,2

Comments

Number of ways to put n indistinguishable balls into 2*n distinguishable boxes.

Number of rankings of n unlabeled elements for 2*n levels.

Links

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

W. Mlotkowski and K. A. Penson, Probability distributions with binomial moments, arXiv preprint arXiv:1309.0595 [math.PR], 2013.

Formula

a(n) = 9*sqrt(3)*GAMMA(n+5/3)*GAMMA(n+4/3)*27^n/(Pi*GAMMA(2*n+3)).

a(n) = binomial(3*n-1, n);

Let denote P(n) = the number of integer partitions of n,

p(i) = the number of parts of the i-th partition of n,

d(i) = the number of different parts of the i-th partition of n,

m(i,j) = multiplicity of the j-th part of the i-th partition of n.

Then one has:

a(n) = Sum_{i=1..P(n)} (2*n)!/((2*n-p(i))!*(Prod_{j=1..d(i)} m(i,j)!)).

a(n) = rf(2*n,n)/ff(n,n), where rf is the rising factorial and ff the falling factorial. - Peter Luschny, Nov 21 2012

G.f.: A(x) = x*B'(x)/B(x), where B(x) satisfies B(x)^3-2*B(x)^2+B(x)=x, B(x)=A006013(x). - Vladimir Kruchinin, Feb 06 2013

G.f.: A(x) = sqrt(3*x)*cot(asin((3^(3/2)*sqrt(x))/2)/3)/(sqrt(4-27*x)). - Vladimir Kruchinin, Mar 18 2015

a(n) = Sum_{k=0..n}(binomial(n-1,n-k)*binomial(2*n,k)). - Vladimir Kruchinin, Oct 06 2015

From Peter Bala, Nov 04 2015: (Start)

The o.g.f. equals f(x)/g(x), where f(x) is the o.g.f. for A005809 and g(x) is the o.g.f. for A001764. More generally, f(x)*g(x)^k is the o.g.f. for the sequence binomial(3*n + k,n). Cf. A045721 (k = 1), A025174 (k = 2), A004319 (k = 3), A236194 (k = 4), A013698 (k = 5), A117671 (k = -2). (End)

a(n) = [x^n] 1/(1 - x)^(2*n). - Ilya Gutkovskiy, Oct 03 2017

a(n) = A059481(2n,n). - Alois P. Heinz, Oct 17 2022

From Peter Bala, Feb 14 2024: (Start)

a(n) = (-1)^n * binomial(-2*n, n).

a(n) = hypergeom([1 - 2*n, -n], [1], 1).

The g.f. A(x) satisfies A(x/(1 + x)^3) = 1/(1 - 2*x).

Sum_{n >= 0} a(n)/9^n = (1 + 4*cos(Pi/9))/3.

Sum_{n >= 0} a(n)/27^n = (3 + 4*sqrt(3)*cos(Pi/18))/9.

Sum_{n >= 0} a(n)*(2/27)^n = (2 + sqrt(3))/3. (End)

Example

Let [1,1,1], [1,2] and [3] be the integer partitions of n=3.
Then [0,0,0,1,1,1], [0,0,0,0,1,2] and [0,0,0,0,0,3] are the corresponding partitions occupying 2*n = 6 positions.
We have to take into account the multiplicities of the parts including the multiplicities of the zeros.
Then
  [0,0,0,1,1,1] --> 6!/(3!*3!) = 20
  [0,0,0,0,1,2] --> 6!/(4!*1!*1!) = 30
  [0,0,0,0,0,3] --> 6!/(5!*1!) = 6
and thus a(3) = 20+30+6=56.
a(2)=10, since we have 10 ordered partitions of n=2 where the parts are distributed over 2*n=4 boxes:
  [0, 0, 0, 2]
  [0, 0, 1, 1]
  [0, 0, 2, 0]
  [0, 1, 0, 1]
  [0, 1, 1, 0]
  [0, 2, 0, 0]
  [1, 0, 0, 1]
  [1, 0, 1, 0]
  [1, 1, 0, 0]
  [2, 0, 0, 0].

Maple

for n from 0 to 16 do
a[n] := 9*sqrt(3)*GAMMA(n+5/3)*GAMMA(n+4/3)*27^n/(Pi*GAMMA(2*n+3))
end do;

Mathematica

Table[Binomial[3 n - 1, n], {n, 0, 20}] (* Vincenzo Librandi, Aug 07 2014 *)

Prog

(Sage)
def A165817(n):
    return rising_factorial(2*n, n)/falling_factorial(n, n)
[A165817(n) for n in (0..22)]   # Peter Luschny, Nov 21 2012
(Magma) [Binomial(3*n-1, n): n in [0..30]]; // Vincenzo Librandi, Aug 07 2014
(PARI) vector(30, n, n--; binomial(3*n-1, n)) \\ Altug Alkan, Nov 04 2015
(Python)
from math import comb
def A165817(n): return comb(3*n-1, n) if n else 1 # Chai Wah Wu, Oct 11 2023

Crossrefs

Cf. A000079, A001700, A059481, A081204, A001764, A004319, A006013, A005809, A013698, A025174, A045721, A117671, A236194.

Sequence in context: A108490 A323935 A370195 * A243644 A000172 A097971

Adjacent sequences: A165814 A165815 A165816 * A165818 A165819 A165820

Keyword

nonn,easy

Author

Thomas Wieder, Sep 29 2009

Extensions

a(0) prepended and more terms from Alois P. Heinz, Apr 04 2012

Status

approved