A078760 Combinations of a partition: number of ways to label a partition (of size n) with numbers 1 to n.

1, 1, 1, 2, 1, 3, 6, 1, 4, 6, 12, 24, 1, 5, 10, 20, 30, 60, 120, 1, 6, 15, 30, 20, 60, 120, 90, 180, 360, 720, 1, 7, 21, 42, 35, 105, 210, 140, 210, 420, 840, 630, 1260, 2520, 5040, 1, 8, 28, 56, 56, 168, 336, 70, 280, 420, 840, 1680, 560, 1120, 1680, 3360, 6720, 2520

Offset: 0

Author

Franklin T. Adams-Watters, Jan 08 2003

Keywords

• nice
• easy
• nonn
• tabf
• look

Comments

This is a function of the individual partitions of an integer. The number of values in each line is given by A000041; thus lines 0 to 5 of the sequence are (1), (1), (1,2), (1,3,6), (1,4,6,12,24). The partitions in each line are ordered with the largest part sizes first, so the line 4 indices are [4], [3,1], [2,2], [2,1,1] and [1,1,1,1]. Note that exponents are often used to represent repeated values in a partition, so the last index could instead be written [1^4]. The combination function (sequence A007318) C(n,m) = C([m,n-m]).

This sequence is also the sequence of multinomial coefficients for partitions ordered lexicographically, matching partition sequence A080577. This is different ordering than in sequence A036038 of multinomial coefficients. - Sergei Viznyuk, Mar 15 2012

Examples

			The irregular table starts:
  [0] {1},
  [1] {1},
  [2] {1, 2},
  [3] {1, 3,  6},
  [4] {1, 4,  6, 12, 24},
  [5] {1, 5, 10, 20, 30, 60, 120},
  [6] {1, 6, 15, 30, 20, 60, 120, 90, 180, 360, 720}
  ...
C([2,1]) = 3 for the labelings ({1,2},{3}), ({1,3},{2}) and ({2,3},{2}).
		

Links

• T. D. Noe, Rows n=0..25 of triangle, flattened
• S.-H. Cha, E. G. DuCasse, and L. V. Quintas, Graph Invariants Based on the Divides Relation and Ordered by Prime Signatures, arxiv:1405.5283 [math.NT], 2014.
• Sergei Viznyuk, C Program
• Index entries for triangles and arrays related to Pascal's triangle.

Crossrefs

Different from A036038.

Cf. A000041, A008480, A063008, A080577.

Programs

Maple

g:= n-> (l-> add(i, i=l)!/mul(i!, i=l))(map(i-> i[2], ifactors(n)[2])):
b:= (n, i)-> `if`(n=0 or i=1, [[1$n]], [map(x->
    [i, x[]], b(n-i, min(n-i, i)))[], b(n, i-1)[]]):
T:= n-> map(x-> g(mul(ithprime(i)^x[i], i=1..nops(x))), b(n$2))[]:
seq(T(n), n=0..9);  # Alois P. Heinz, Mar 25 2020

Mathematica

Flatten[Table[Apply[Multinomial, IntegerPartitions[i], {1}], {i,0,25}]] (* T. D. Noe, Oct 14 2007 *)
Flatten[ Multinomial @@@ IntegerPartitions @ # & /@ Range[ 0, 8]] (* Michael Somos, Feb 05 2011 *)
g[n_] := With[{ee = FactorInteger[n][[All, 2]]}, Total[ee]!/Times@@(ee!)];
b[n_, i_] := b[n, i] = If[n == 0 || i == 1, {Table[1, {n}]}, Join[ Prepend[#, i] & /@ b[n - i, Min[n - i, i]], b[n, i - 1]]];
row[n_] := Product[Prime[i]^#[[i]], {i, 1, Length[#]}] & /@ b[n, n];
T[n_] := g /@ row[n];
T /@ Range[0, 9] // Flatten (* Jean-François Alcover, Jun 09 2021, after Alois P. Heinz *)

PARI

C(sig)={vecsum(sig)!/vecprod(apply(k->k!, sig))}
Row(n)={apply(C, vecsort([Vecrev(p) | p<-partitions(n)], , 4))}
{ for(n=0, 8, print(Row(n))) }  \\ Andrew Howroyd, Mar 25 2020

SageMath

def A070289_row(n): return [multinomial(x) for x in Partitions(n)]
print(flatten([A070289_row(n) for n in range(8)]))  # Peter Luschny, Jun 24 2025

Formula

C([]) = (Sum a(i))! / Product a(i) !.

T(n,k) = A008480(A063008(n,k)). - Andrew Howroyd, Mar 25 2020