Number of different groups given a list of repeating digits

94 Views Asked by At

Suppose that you are given the list[1,1,2,2] . The different groups that can be formed with this list are -

[11,22],[1,122],[1,1,22],[1,1,2,2],[1,12,2],[112,2],[11,22],[12,12],[11,2,2]

The total number of different groups is 9.

If I am given an arbitrary number of 1's and 2's, how would I find the number of different groups that can be formed?

1

There are 1 best solutions below

0
On

In your example, $[11,22]$ is listed twice; I'm guessing one of those was supposed to be $[1122].$

The question is not stated very clearly. Here's how I interpret it:

Let $S=\{(m,n)\in\mathbb Z\times\mathbb Z:m,n\ge0\}.$ Given $(m,n)\in S,$ determine $f(m,n),$ the number of ways in which the vector $(m,n)$ can be expressed as an unordered sum of elements of $S\setminus\{(0,0)\}$, i.e., the number of partitions of the "bipartite number" $(m,n).$

Equivalently, if $p,q$ are distinct prime numbers, $f(m,n)$ is the number of factorizations of $p^mq^n,$ where a factorization of a positive integer $x$ is a nonincreasing sequence of integers greater than $1$ whose product is equal to $x.$ For example, if $x=36=2^2\cdot3^2,$ the $f(2,2)=9$ factorizations are $$36=18\cdot2=12\cdot3=9\cdot4=9\cdot2\cdot2=6\cdot6=6\cdot3\cdot2=4\cdot3\cdot3=3\cdot3\cdot2\cdot2.$$

The connection with factorizations is somewhat obscured by the OP's notation, but it will be clearer if we change the OP's $1$ and $2$ to $p$ and $q$ (standing for two distinct primes), after correcting the second $[11,22]$ to $[1122]$, namely: $$[11,22]\sim(p^2)(q^2)$$ $$[1,122]\sim(p)(pq^2)$$ $$[1,1,22]\sim(p)(p)(q^2)$$ $$[1,1,2,2]\sim(p)(p)(q)(q)$$ $$[1,12,2]\sim(p)(pq)(q)$$ $$[112,2]\sim(p^2q)(q)$$ $$[1122]\sim(p^2q^2)$$ $$[12,12]\sim(pq)(pq)$$ $$[11,2,2]\sim(p^2)(q)(q)$$

$f(0,n)=p(n),$ the number of partitions of $n,$ is OEIS sequence A000041.

$f(1,n)=\sum_{k=0}^np(k)$ is OEIS sequence A000070.

$f(2,n)=\sum_{k=0}^n\left\lfloor\frac{k+4}2\right\rfloor p(n-k)$ is OEIS sequence A000291 "Number of bipartite partitions of $n$ white objects and $2$ black ones"; thus, for example, $$f(2,2)=\left\lfloor\frac42\right\rfloor p(2)+\left\lfloor\frac52\right\rfloor p(1)+\left\lfloor\frac62\right\rfloor p(0)=2\cdot2+2\cdot1+3\cdot1=9.$$

$f(3,n)$ is OEIS sequence A000412 "Number of bipartite partitions of $n$ white objects and $3$ black ones".

See OEIS sequence A000465 for $f(4,n),$ A000491 for $f(5,n),$ A002755 for $f(6,n),$ A002756 for $f(7,n),$ A002757 for $f(8,n),$ A002758 for $f(9,n),$ A002759 for $f(10,n).$

$f(n,n)$ is OEIS sequence A002774 "Number of bipartite partitions of $n$ white objects and $n$ black ones"; among the references given by the OEIS is F. C. Auluck, "On partitions of bipartite numbers", Mathematical Proceedings of the Cambridge Philosophical Society, Volume 49, Issue 01, January 1953, pp. 72-83.

The general problem is discussed in a 2008 paper by Shamik Ghosh, "Counting number of factorizations of a natural number" (arXiv:0811.3479) with a bibliography of nine items.