Skip to main content
deleted 6 characters in body
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

More information would be nice. The answer by JBL above is perfectly fine but there might be other forms for the answer. In the special case $k=n$ the answer is $n^n$, that is indeed $\sum_{i = 0}^n (-1)^{n - i} \binom{in}{n} \binom{n}{i}$ but I like the first form better.For $k$ past $n^2-n$ the answer is just $\binom{n^2}{k}$. In this case the given formula given quickly reduces to that.

One could do the sum over all ordered partitions $k=\sum_1^nk_j$ of $k$ into $n$ positive parts of $\prod\binom{n}{k_j}$. That would be practical if $k-n$ is small. One can collect like terms so essentially use unordered partitions with appropriate multinomial coefficients. Hence for $k=n+3$ (if I made no errors) one either has a row with 4 OR a row with 3 and one with 2 OR three rows with 2 things in them (and one thing in each other row). $$\binom{n}{1,n-1}\binom{n}{4}^1\binom{n}{1}^{n-1}+\binom{n}{1,1,n-2}\binom{n}{3}^1\binom{n}{2}^1\binom{n}{1}^{n-1}+\binom{n}{3,n-3}\binom{n}{2}^3\binom{n}{1}^{n-3}$$ $$=n^n\left(\binom{n}{4}+(n-1)\binom{n}{3}\binom{n}{2}+\binom{n}{3}\left(\frac{n-1}{2}\right)^3\right)$$ $$=n^n\binom{n}{3}\frac{5n^3-11n^2+9n-7}{8}$$

A similar thing would work for $k $ slightly less than $n^2-n.$

So what kind of answer are you looking for and what can you say about $k$.?

More information would be nice. The answer by JBL above is perfectly fine but there might be other forms for the answer. In the special case $k=n$ the answer is $n^n$, that is indeed $\sum_{i = 0}^n (-1)^{n - i} \binom{in}{n} \binom{n}{i}$ but I like the first form better.For $k$ past $n^2-n$ the answer is just $\binom{n^2}{k}$. In this case the given formula given quickly reduces to that.

One could do the sum over all ordered partitions $k=\sum_1^nk_j$ of $k$ into $n$ positive parts of $\prod\binom{n}{k_j}$. That would be practical if $k-n$ is small. One can collect like terms so essentially use unordered partitions with appropriate multinomial coefficients. Hence for $k=n+3$ (if I made no errors) one either has a row with 4 OR a row with 3 and one with 2 OR three rows with 2 things in them (and one thing in each other row). $$\binom{n}{1,n-1}\binom{n}{4}^1\binom{n}{1}^{n-1}+\binom{n}{1,1,n-2}\binom{n}{3}^1\binom{n}{2}^1\binom{n}{1}^{n-1}+\binom{n}{3,n-3}\binom{n}{2}^3\binom{n}{1}^{n-3}$$ $$=n^n\left(\binom{n}{4}+(n-1)\binom{n}{3}\binom{n}{2}+\binom{n}{3}\left(\frac{n-1}{2}\right)^3\right)$$ $$=n^n\binom{n}{3}\frac{5n^3-11n^2+9n-7}{8}$$

A similar thing would work for $k $ slightly less than $n^2-n.$

So what kind of answer are you looking for and what can you say about $k$.

More information would be nice. The answer by JBL above is perfectly fine but there might be other forms for the answer. In the special case $k=n$ the answer is $n^n$, that is indeed $\sum_{i = 0}^n (-1)^{n - i} \binom{in}{n} \binom{n}{i}$ but I like the first form better.For $k$ past $n^2-n$ the answer is just $\binom{n^2}{k}$. In this case the formula given quickly reduces to that.

One could do the sum over all ordered partitions $k=\sum_1^nk_j$ of $k$ into $n$ positive parts of $\prod\binom{n}{k_j}$. That would be practical if $k-n$ is small. One can collect like terms so essentially use unordered partitions with appropriate multinomial coefficients. Hence for $k=n+3$ (if I made no errors) one either has a row with 4 OR a row with 3 and one with 2 OR three rows with 2 things in them (and one thing in each other row). $$\binom{n}{1,n-1}\binom{n}{4}^1\binom{n}{1}^{n-1}+\binom{n}{1,1,n-2}\binom{n}{3}^1\binom{n}{2}^1\binom{n}{1}^{n-1}+\binom{n}{3,n-3}\binom{n}{2}^3\binom{n}{1}^{n-3}$$ $$=n^n\left(\binom{n}{4}+(n-1)\binom{n}{3}\binom{n}{2}+\binom{n}{3}\left(\frac{n-1}{2}\right)^3\right)$$ $$=n^n\binom{n}{3}\frac{5n^3-11n^2+9n-7}{8}$$

A similar thing would work for $k $ slightly less than $n^2-n.$

So what kind of answer are you looking for and what can you say about $k$?

Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

More information would be nice. The answer by JBL above is perfectly fine but there might be other forms for the answer. In the special case $k=n$ the answer is $n^n$, that is indeed $\sum_{i = 0}^n (-1)^{n - i} \binom{in}{n} \binom{n}{i}$ but I like the first form better.For $k$ past $n^2-n$ the answer is just $\binom{n^2}{k}$. In this case the given formula given quickly reduces to that.

One could do the sum over all ordered partitions $k=\sum_1^nk_j$ of $k$ into $n$ positive parts of $\prod\binom{n}{k_j}$. That would be practical if $k-n$ is small. One can collect like terms so essentially use unordered partitions with appropriate multinomial coefficients. Hence for $k=n+3$ (if I made no errors) one either has a row with 4 OR a row with 3 and one with 2 OR three rows with 2 things in them (and one thing in each other row). $$\binom{n}{1,n-1}\binom{n}{4}^1\binom{n}{1}^{n-1}+\binom{n}{1,1,n-2}\binom{n}{3}^1\binom{n}{2}^1\binom{n}{1}^{n-1}+\binom{n}{3,n-3}\binom{n}{2}^3\binom{n}{1}^{n-3}$$ $$=n^n\left(\binom{n}{4}+(n-1)\binom{n}{3}\binom{n}{2}+\binom{n}{3}\left(\frac{n-1}{2}\right)^3\right)$$ $$=n^n\binom{n}{3}\frac{5n^3-11n^2+9n-7}{8}$$

A similar thing would work for $k $ slightly less than $n^2-n.$

So what kind of answer are you looking for and what can you say about $k$.