Mathematics desk
< February 20	<< Jan \| February \| Mar >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 21

Combinatorics, multisets, elements

Let there be $n$ distinct multisets, each with $m$ identical elements (such as $\overbrace {1,\ldots ,1} ^{m},\overbrace {2,\ldots ,2} ^{m},\ldots ,\overbrace {n,\ldots ,n} ^{m}$ ).
How many ways are there to arrange them in $n$ distinct boxes, such that every box contains exactly $m$ elements and the inner order does not matter? יהודה שמחה ולדמן (talk) 12:57, 21 February 2023 (UTC)[reply]

Does the boxes being "distinct" mean they can be considered to be labelled? Like, {A: {1,2}, B: {1,2}, C: {3,3}} is not the same arrangement as {A: {1,2}, B: {3,3}, C: {1,2}}? Or are these different presentations of the same arrangement {{1,2}, {1,2}, {3,3}}? Using the term bag for "multiset", are the arrangements to be counted sequences of bags or bags of bags? --Lambiam 18:45, 21 February 2023 (UTC)[reply]

Yes. The boxes are labelled. For

1,1,2,2,3,3

I counted 21 arrangements fulfilling these properties. יהודה שמחה ולדמן (talk) 20:09, 21 February 2023 (UTC)[reply]

Here is a table with some partial results:

$m\setminus n$	$0$	$1$	$2$	$3$	$4$	$5$
$0$	$1$	$1$	$1$	$1$	$1$	$1$
$1$	$1$	$1$	$2$	$6$	$24$	$120$
$2$	$1$	$1$	$3$	$21$	$282$	$6210$
$3$	$1$	$1$	$4$	$55$	$2008$
$4$	$1$	$1$	$5$	$120$

Denoting the number of arrangements as

{}_{m}\alpha _{n},

it is apparent that

_{m}\alpha _{0}={}_{m}\alpha _{1}={}_{0}\alpha _{n}=1;

_{m}\alpha _{2}=m+1;

\,_{1}\alpha _{n}=n!\,.

A formula fitting the observed values for

n=3

is:

_{m}\alpha _{3}={\frac {(m+1)(m+2)(m^{2}+3m+4)}{8}}.

--Lambiam 22:09, 21 February 2023 (UTC)[reply]

Just wanted to quickly point out an accidental error for

m=1,n=5

, that should be

120

GalacticShoe (talk) 22:12, 21 February 2023 (UTC)[reply]

Thanks, now corrected. --Lambiam 00:37, 22 February 2023 (UTC)[reply]

Also wanted to point out that

_{m}\alpha _{3}

appears to correspond to A002817,

_{m}\alpha _{4}

to A001496 (funny how it came earlier), and

_{m}\alpha _{5}

to A003438 in OEIS. Similarly, A000681 for

_{2}\alpha _{n}

, A001500 for

_{3}\alpha _{n}

, and A172806 (what a jump!) for

_{4}\alpha _{n}

. If I'm interpreting this right, this would indicate that

_{m}\alpha _{n}

is precisely the number of

m\times m

matrices with nonnegative integer entries and row and column sums equal to

n

. GalacticShoe (talk) 22:25, 21 February 2023 (UTC)[reply]

Let, given a valid assignment,

B_{ij}

stand for the multiplicity of element

j

in the box labelled

i

. Then the row sums give the number of elements in each of the

m

boxes, while the column sums are the original multiplicities of each of the

m

different elements; both equal

n

, and each matrix

B

with nonnegative entries satisfying the marginal constraints corresponds to a different (valid) assignment. --Lambiam 01:03, 22 February 2023 (UTC)[reply]

There are other interpretations as well. if h_m is the complete homogeneous symmetric polynomial of degree m, then these numbers correspond to the coefficient of the monomial symmetric polynomial m_mⁿ in h_mⁿ. For example the coefficient of m₂₂₂ in h₂³ is 21. The general problem can be given in terms of partitions; given λ, μ, how many arrays of non-negative integers have row and column sums equal to the entries in λ, μ respectively. In this case λ and μ are both mⁿ. It's been a while since I studied this; the represention theory of the symmetric group is related as well but I don't remember too many details. --RDBury (talk) 02:53, 22 February 2023 (UTC)[reply]

Using the OEIS sequences, I find:

_{m}\alpha _{0}=1;

_{m}\alpha _{1}=1;

_{m}\alpha _{2}=m+1;

_{m}\alpha _{3}=(m+1)(m+2){\frac {m^{2}+3m+4}{8}};

_{m}\alpha _{4}=(m+1)(m+2)(m+3){\frac {11m^{6}+132m^{5}+683m^{4}+1944m^{3}+3320m^{2}+3360m+1890}{11340}}

_{m}\alpha _{5}=(m+1)(m+2)(m+3)(m+4){\frac {188723m^{12}+5661690m^{11}+78003775m^{10}+652623750m^{9}+3696611709m^{8}+14962790430m^{7}+44526915325m^{6}+98693942250m^{5}+163162497908m^{4}+199040329080m^{3}+174301898400m^{2}+102918816000m+34871316480}{836911595520}}.

I've unsuccessfully attempted to find a recurrence relation such as is known for the partition function. --Lambiam 20:52, 22 February 2023 (UTC)[reply]

I'm pretty sure this is equivalent to finding the Ehrhart polynomials of Birkhoff polytopes. If so then it's a well-studied problem and known to be computationally difficult. See for example Beck & Pixton's paper. --RDBury (talk) 07:35, 23 February 2023 (UTC)[reply]

Shape between an elipse and a circle

Consider an ellipse inscibed within a circle, so that it touches both ends of the circle's diameter. Is there a name for the shape created between the ellipse and the circle, for example the top half of the green circle and dotted red ellipse in this diagram? It isn't a crescent, as the inner part of a crescent is an arc of a circle, not an ellipse. — Voice of Clam (talk) 19:38, 21 February 2023 (UTC)[reply]

I think you’re going to have to make up your own name for this –jacobolus (t) 21:28, 21 February 2023 (UTC)[reply]

These shapes are the planar projections of (rather special) spherical lunes, like the (astronomically correct) crescents of the Moon, so it would not be incorrect to call them crescents – while being aware that this term is commonly also used for emblems with astronomically "incorrect" shapes. --Lambiam 22:18, 21 February 2023 (UTC)[reply]