A122768 Number of combinations which can be taken from the integer partitions of n. Total number of cases in the (n,m)-fragmentation process.

0, 1, 3, 7, 15, 29, 54, 95, 163, 270, 439, 696, 1088, 1669, 2530, 3780, 5591, 8173, 11845, 17000, 24215, 34210, 48008, 66895, 92660, 127554, 174651, 237830, 322297, 434625, 583524, 779972, 1038356, 1376787, 1818755, 2393775, 3139812, 4104433, 5348375, 6947545, 8998201, 11620313, 14965126, 19220569

Offset: 0

Author

Thomas Wieder, Sep 11 2006

Keywords

• nonn

Comments

Consider a fragmentation process of an n-object which consists of n unlabeled elements (= 1-parts). By definition the n-object can scatter into up to n m-parts where an m-part consists of 1 up to n elements. A 4-object can split up for example into 4 1-parts which corresponds to the integer partition [1,1,1,1], or it can, for example, rest unfragmented which corresponds to [4]. Since the number of integer partitions of n=4 equals 5, there are 5 n=4-fragmentation processes.

Now we ask for the probability of getting an m-part after an n-fragmentation. Think of a Greek statue which had been broken into n parts and covered by earth. We could find several m-parts, in the most lucky case we would find all m-parts which add up to m_1+m_2+...+m_n=n. Then the statue could be restored.

For example for n=4 we could ask for the probability prob(n=4,m=2) of just a single 2-part. We have 2 cases for a 2-part and we have 15 cases in total, thus prob(n=4,m=2)=2/15 (the 2 cases come from [1,1,2] and [2,2]). The chances to find the two 2-parts from the [2,2]-fragmentation are 1/15 only. The chances to find the n=4-object unsplitted are also 1/15 only.

This sequence is generated over the unordered partitions; for example, when n = 4 there are 1+3+2+5+4 = 15 cases. If we allow a null case for each of the five partitions then we have 15+5 = 20 which is A000712(4). - Alford Arnold, Dec 12 2006

Number of partitions into two kinds of parts with the first kind of parts used in each partition. - Joerg Arndt, Jun 21 2011

Examples

			a(n=4) = 15 because the possible combinations of all five integer partitions of n=4 are: [1], [1, 1], [1, 1, 1], [1, 1, 1, 1], [1], [2], [1, 1], [1, 2], [1, 1, 2], [2], [2, 2], [1], [3], [1, 3], [4].
		

Links

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

Crossrefs

Cf. A000041, A000079, A000262.

Cf. A000712, A074139, A074141.

Cf. A048574, A144064.

Programs

Haskell

a122768 n = a122768_list !! n
a122768_list = 0 : f (tail a000041_list) [1] where
   f (p:ps) rs = (sum $ zipWith (*) rs $ tail a000041_list) : f ps (p : rs)
-- Reinhard Zumkeller, Nov 09 2015

Maple

A122768 := proc(n::integer) local i,j,prttnlst,prttn,ZahlTeile,H; prttnlst:=partition(n); H := NULL; for i from 1 to nops(prttnlst) do prttn := prttnlst[i]; ZahlTeile := nops(prttn); for j from 1 to ZahlTeile do H := H,op(choose(prttn,j)); od; od; print(n,H,nops([H])); end proc;
A000712 := proc(n) option remember ; add(combinat[numbpart](k)*combinat[numbpart](n-k),k=0..n) ; end: A000041 := proc(n) combinat[numbpart](n) ; end: A122768 := proc(n::integer) RETURN( A000712(n)-A000041(n)) ; end: for n from 0 to 80 do printf("%d,",A122768(n)) ; od: # R. J. Mathar, Aug 25 2008
# third Maple program:
b:= proc(n, k) option remember; `if`(n=0, 1, add(
      k*numtheory[sigma](j)*b(n-j, k), j=1..n)/n)
    end:
a:= n-> b(n,2)-b(n,1):
seq(a(n), n=0..50);  # Alois P. Heinz, Mar 31 2017

Mathematica

1/QPochhammer[x]^2 - 1/QPochhammer[x] + O[x]^50 // CoefficientList[#, x]& (* Jean-François Alcover, Feb 05 2017, after Joerg Arndt *)

PARI

x='x+O('x^66); /* that many terms */
Vec(1/eta(x)^2-1/eta(x)) /* show terms (omitting initial zero) */
/* Joerg Arndt, Jun 21 2011 */

Python

from sympy import npartitions
def A122768(n): return (sum(npartitions(k)*npartitions(n-k) for k in range(1,n+1>>1))<<1) + (0 if n&1 else npartitions(n>>1)**2) + npartitions(n) if n else 0 # Chai Wah Wu, Sep 25 2023

Formula

G.f.: 1/P(x)^2 - 1/P(x) where P(x)=prod(k>=1, 1-x^k ). - Joerg Arndt, Jun 21 2011

With sum_i^P(n) = the sum over all P(n) integer partitions of n, sum_j^p(i) = the sum over all p(i) parts of the i-th integer partition, prttn(i) = the i-th partition whereat prttn(i) is a list, choose(L,k) = construct the list LC of combinations of a list L (see Maple), |LC| = number of elements of list LC (=Maple's nops command) we have a(n) = sum_i^P(n) sum_j^p(i) |choose(prttn,j)|

a(n) = A000712(n) - A000041(n). - Alford Arnold, Dec 12 2006

a(n) = A144064(n,2)-A144064(n,1). - Alois P. Heinz, Mar 31 2017

a(n) ~ exp(2*Pi*sqrt(n/3)) / (4*3^(3/4)*n^(5/4)) * (1 - (Pi/12 + 45/(16*Pi))/sqrt(3*n)). - Vaclav Kotesovec, Mar 31 2017

Extensions

Extended by R. J. Mathar, Aug 25 2008