login
Irregular triangle read by rows. Preferred multisets: numbers refining A007318 using format described in A036038.
37

%I #91 Feb 14 2024 14:39:32

%S 1,1,1,1,1,2,1,1,2,1,3,1,1,2,2,3,3,4,1,1,2,2,1,3,6,1,4,6,5,1,1,2,2,2,

%T 3,6,3,3,4,12,4,5,10,6,1,1,2,2,2,1,3,6,6,3,3,4,12,6,12,1,5,20,10,6,15,

%U 7,1,1,2,2,2,2,3,6,6,3,3,6,1,4,12,12,12,12,4,5,20,10,30,5,6,30,20,7,21,8,1

%N Irregular triangle read by rows. Preferred multisets: numbers refining A007318 using format described in A036038.

%C This array gives in row n>=1 the multinomial numbers (call them M_0 numbers) m!/product((a_j)!,j=1..n) with the exponents of the partitions of n with number of parts m:=sum(a_j,j=1..n), given in the Abramowitz-Stegun order. See p. 831 of the given reference. See also the arrays for the M_1, M_2 and M_3 multinomial numbers A036038, A036039 and A036040 (or A080575).

%C For a signed version see A111786.

%C These M_0 multinomial numbers give the number of compositions of n >= 1 with parts corresponding to the partitions of n (in A-St order). See an n = 5 example below. The triangle with the summed entries of like number of parts m is A007318(n-1, m-1) (Pascal). - _Wolfdieter Lang_, Jan 29 2021

%H Andrew Howroyd, <a href="/A048996/b048996.txt">Table of n, a(n) for n = 0..2713</a> (rows 0..20)

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards Applied Math. Series 55, 1972.

%H Wolfdieter Lang, <a href="/A048996/a048996_2.pdf">First 10 rows and more.</a>

%F T(n,k) = A036040(n,k) * Factorial(A036043(n,k)) / A036038(n,k) = A049019(n,k) / A036038(n,k).

%F If the n-th partition is P, a(n) is the multinomial coefficient of the signature of P. - _Franklin T. Adams-Watters_, May 30 2006

%F T(n,k) = A309004(A036035(n,k)). - _Andrew Howroyd_, Oct 19 2020

%e Table starts:

%e [1]

%e [1]

%e [1, 1]

%e [1, 2, 1]

%e [1, 2, 1, 3, 1]

%e [1, 2, 2, 3, 3, 4, 1]

%e [1, 2, 2, 1, 3, 6, 1, 4, 6, 5, 1]

%e [1, 2, 2, 2, 3, 6, 3, 3, 4, 12, 4, 5, 10, 6, 1]

%e .

%e T(5,6) = 4 because there are four multisets using the first four digits {0,1,2,3}: 32100, 32110, 32210 and 33210

%e T(5,6) = 4 because there are 4 compositions of 5 that can be formed from the partition 2+1+1+1. - _Geoffrey Critzer_, May 19 2013

%e These 4 compositions 2+1+1+1, 1+2+1+1, 1+1+2+1 and 1+1+1+2 of 5 correspond to the 4 set partitions of [5] :={1,2,3,4,5}, with 4 blocks of consecutive numbers, namely {1,2},{3},{4},{5} and {1},{2,3},{4},{5} and {1},{2},{3,4},{5} and {1},{2},{3},{4,5}. - _Wolfdieter Lang_, May 30 2018

%p nmax:=9: with(combinat): for n from 1 to nmax do P(n):=sort(partition(n)): for r from 1 to numbpart(n) do B(r):=P(n)[r] od: for m from 1 to numbpart(n) do s:=0: j:=0: while s<n do j:=j+1: s:=s+B(m)[j]: x(j):=B(m)[j]: end do; jmax:=j; for r from 1 to n do q(r):=0 od: for r from 1 to n do for j from 1 to jmax do if x(j)=r then q(r):=q(r)+1 fi: od: od: A036040(n, m) := (add(q(t), t=1..n))!/(mul(q(t)!, t=1..n)); od: od: seq(seq(A036040(n, m), m=1..numbpart(n)), n=1..nmax); # _Johannes W. Meijer_, Jul 14 2016

%o (SageMath) from collections import Counter

%o def ASPartitions(n, k):

%o Q = [p.to_list() for p in Partitions(n, length=k)]

%o for q in Q: q.reverse()

%o return sorted(Q)

%o def A048996_row(n):

%o h = lambda p: product(map(factorial, Counter(p).values()))

%o return [factorial(len(p))//h(p) for k in (0..n) for p in ASPartitions(n, k)]

%o for n in (1..10): print(A048996_row(n)) # _Peter Luschny_, Nov 02 2019 [corrected on notice from _Sean A. Irvine_, Apr 30 2022]

%o (PARI)

%o C(sig)={my(S=Set(sig)); (#sig)!/prod(k=1, #S, (#select(t->t==S[k], sig))!)}

%o Row(n)={apply(C, [Vecrev(p) | p<-partitions(n)])}

%o { for(n=0, 7, print(Row(n))) } \\ _Andrew Howroyd_, Oct 18 2020

%Y Cf. A000670, A007318, A036035, A036038, A019538, A115621, A309004, A000079 (row sums), A000041 (row lengths).

%K nonn,tabf

%O 0,6

%A _Alford Arnold_

%E More terms from Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Jun 17 2001

%E a(0)=1 prepended by _Andrew Howroyd_, Oct 19 2020