login
A122768
Number of combinations which can be taken from the integer partitions of n. Total number of cases in the (n,m)-fragmentation process.
56
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,3
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
LINKS
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
EXAMPLE
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].
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 *)
PROG
(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 */
(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
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Thomas Wieder, Sep 11 2006
EXTENSIONS
Extended by R. J. Mathar, Aug 25 2008
STATUS
approved