combinatoricsinteger-partitions
I have a number x and want to find how many ways there are to add up to that number using the y numbers from numbers 1-z.
for example, for x=15 y=3, z=9, there are 8 ways to add up to 15 using 3 numbers chosen from 1-9 without repetition (and order does not matter):
1,5,9
1,6,8
2,4,9
2,5,8
2,6,7
3,4,8
3,5,7
4,5,6
How can i generalize this formula?
What you are looking for is the Stars and Bars method. This method is used to count things where order does not matter and repetition is allowed.
We are choosing $9$ digits from $\{1,2,3,4,5,6\}$
Let me explain how we can get to the answer.
For example, let's say we want to pick the combination $123456123$. This can be "arranged" as such:
$$••|••|••|•|•|•$$
We picked $2$ ones, $2$ twos, $2$ threes, and $1$ of the rest.
Let's look at another possibility: $111222456$ $$•••|•••| |•|•|•$$
We have three ones, three twos, and one $4$, $5$, and $6$.
Look at what these pictures are showing: we have $14$ symbols and we are choosing $5$ of them to be a bar. Or we could look at it as choosing $9$ of them to be a dot (star)
So the answer to our original question is $$\binom{14}{9} = \binom{14}{5} = 2002$$
TL;DR (or for those unfamiliar with group theory) A brief summary of the results, without proofs.
Any pair of such $n\times n$-matrices with the same unordered set of rows, columns, diagonals and antidiagonals differ by a permutation of their entries, and hence by a permutation of the index set $$\{(i,j):\ 1\leq i,j\leq n\}.$$ It turns out that any permutation that preserves the set of rows, columns, diagonals and antidiagonals is in fact an affine map, i.e. it is some combination of a rotation, reflection, stretching and translation${}^{\ast}$, but in general not all affine maps preserve the set of rows, columns, diagonals and antidiagonals.
You had already found that the translations, reflections and rotations by a quarter turn preserve the set of rows, columns, diagonals and antidiagonals; that's almost everything! What remains are sometimes more rotations, and a lot of stretchings. The stretching of a matrix $M=(m_{ij})_{1\leq i,j\leq n}$ by a factor $1\leq c\leq n$ is the matrix $$N=(n_{i,j})_{1\leq i,j\leq n}\qquad\text{ with }\qquad n_{i,j}:=m_{ci,cj},$$ where we take $ci$ and $cj$ modulo $n$. For example, for $n=5$ and $c=2$ the matrix $$\begin{pmatrix} 1&2&3&4&5\\ 6&7&8&9&10\\ 11&12&13&14&15\\ 16&17&18&19&20\\ 21&22&23&24&25 \end{pmatrix} \qquad\text{ becomes }\qquad \begin{pmatrix} 13&11&14&12&15\\ 3&1&4&2&5\\ 18&16&19&17&20\\ 8&6&9&7&10\\ 23&21&24&22&25 \end{pmatrix}. $$ Such a stretching is well-defined only if $c$ is coprime to $n$, i.e. if $\gcd(c,n)=1$. It turns out that all such stretching with $\gcd(c,n)$ preserve the set of rows, columns, diagonals and antidiagonals.
The question then remains; which rotations preserve the set of rows, columns, diagonals and antidiagonals? The results are fundamentally different depending on whether $n$ is even or odd.
While it is clear what a quarter turn of a matrix is, I should clarify a one-eighth turn. The one-eighth turn of a matrix $M=(m_{ij})_{1\leq i,j\leq n}$ by a factor $1\leq c\leq n$ is the matrix $$N=(n_{i,j})_{1\leq i,j\leq n}\qquad\text{ with }\qquad n_{i,j}:=m_{i+j,-i+j},$$ where again we take $i+j$ and $-i+j$ modulo $n$. For example, the one-eighth turn of the matrix $$\begin{pmatrix} 1&2&3&4&5\\ 6&7&8&9&10\\ 11&12&13&14&15\\ 16&17&18&19&20\\ 21&22&23&24&25 \end{pmatrix} \qquad\text{ is }\qquad \begin{pmatrix} 21&9&17&5&13\\ 14&22&10&18&1\\ 2&15&23&6&19\\ 20&3&11&24&7\\ 8&16&4&12&25 \end{pmatrix}. $$ Combining all these symmetries quickly becomes confusing, some group theory is essential to get a clear picture. But it turns out the symmetries go together quite well; only rotations and stretching get mixed up, because a half-turn is the same as stretching by a factor $-1$.
To generate all matrices with the same set of rows, columns, diagonals and antidiagonals as a given matrix $M$, simply apply all the symmetries as follows:
$\ast$ There are also the shear maps, but these preserve the set of rows, columns, diagonals and antidiagonals only if these are all lines in the $n\times n$-plane, which is the case if and only $n\leq3$.
Here follows the original proof for odd $n$.
Observation: Any two rows, columns, diagonals or antidiagonals that are not in the same category (e.g. that are not both rows) meet in precisely one point if and only if $n$ is odd.
I will use this observation throughout the proof without mention, as the proof concerns only odd $n$. Because this fails for even $n$ the geometry is significantly less intuitive, so I will not consider this case for now.
Observation: The set of $n\times n$-matrices whose entries are precisely the integers from $1$ to $n^2$ inclusive, is naturally in bijection group of symmetries of the affine $n$-plane $\Bbb{A}_2(n):=(\Bbb{Z}/n\Bbb{Z})^2$.
The question then becomes
Which symmetries of $\Bbb{A}_2(n)$ preserve the set of horizontal, vertical, diagonal and antidiagonal lines?
Proposition 1. For odd $n>3$ the set of horizontal, vertical, diagonal and antidiagonal lines is preserved by all symmetries of the form $$\Bbb{A}_2(n)\ \longrightarrow\ \Bbb{A}_2(n):\ \binom{i}{j}\ \longmapsto\ uA\binom{i}{j}+B,$$ with $u\in(\Bbb{Z}/n\Bbb{Z})^{\times}$, $B\in(\Bbb{Z}/n\Bbb{Z})^2$ and $A\in\langle\rho,\mu\rangle$ where $$\rho:=\begin{pmatrix} \hphantom{-}1&1\\ -1&1 \end{pmatrix} \qquad\textit{ and }\qquad \mu:=\begin{pmatrix} 1&\hphantom{u}0\\ 0&-1 \end{pmatrix}. $$
Proof. It is clear that translation by any element of $(\Bbb{Z}/n\Bbb{Z})^2$ sends rows to rows, columns to columns, diagonals to diagonals and antidiagonals to antidiagonals. To see that the same is true for multiplication by any $u\in(\Bbb{Z}/n\Bbb{Z})^{\times}$, note that any line in $\Bbb{A}_2(n)$ is of the form $$L_{a,b,c}:=\{ax+by=c:\ x,y\in\Bbb{Z}/n\Bbb{Z}\},$$ and so multiplication by $u\in(\Bbb{Z}/n\Bbb{Z})^{\times}$ maps this line to the line $L_{a,b,uc}$; in particular the slope of the line is preserved, so this scaling also sends rows to rows, columns to columns, diagonals to diagonals and antidiagonals to antidiagonals. It remains to show that $\rho$ and $\mu$ preserve the set of rows, columns, diagonals and antidiagonals.
Geometrically, multiplication by $\mu$ is a reflection in the first row. This sends rows to rows and columns to columns, and swaps diagonals and antidiagonals. Similarly, multiplication by $\rho$ is a rotation around the point $(0,0)$ over an angle of $-\tfrac{\pi}{4}$. This sends rows to diagonals, diagonals to columns, columns to antidiagonals, and antidiagonals to rows. $\hspace{20pt}\square$
Theorem 2. For odd $n>3$, every symmetry of $\Bbb{A}_2(n)$ that preserves the set of rows, columns, diagonals and antidiagonals is of the form described in Proposition 1.
Proof. See below.
Corollary 3. For any $n\times n$-matrix whose entries are precisely the integers from $1$ to $n^2$ inclusive, there are precisely $8\varphi(n)n^2$ such matrices with the same set of rows, columns, diagonals and antidiagonals, where $\varphi(n)$ denotes Eulers totient function.
Lemma 1: Let $n$ be an odd positive integer. Let $\sigma$ be a symmetry of $\Bbb{A}_2(n)$ that preserves the set of rows, columns, diagonals and antidiagonals such that $\sigma((0,0))=(0,0)$ and $\sigma((0,1))$ is on the first row. Then there exists some $d\in(\Bbb{Z}/n\Bbb{Z})^{\times}$ such that $$\forall k\in\Bbb{Z}/n\Bbb{Z}:\qquad\sigma((0,k))=(0,dk).$$
Proof. Let $d\in\Bbb{Z}/n\Bbb{Z}$ be such that $\sigma((0,1))=(0,d)$, and note that $d\neq0$. Because $\sigma$ preserves the set of rows, columns, diagonals and antidiagonals, there are at most six candidates for $\sigma((1,1))$. After all, the point $(1,1)$ is in the same column as $(0,1)$ and on the same diagonal as $(0,0)$, and $\sigma$ maps these to a column, diagonal or antidiagonal through $(0,d)$ and $(0,0)$. The following picture clarifies the situation:
This picture shows the points $(0,0)$ and $(0,d)$ in black, their columns, diagonals and antidiagonals in blue, and the possible positions of $\sigma((1,1))$ also in blue.
The point $(0,2)$ is the unique point on the line through $(0,0)$ and $(0,1)$ that is on a line with $(1,1)$, and that is distinct from $(0,0)$ and $(0,1)$. For each candidate point for $\sigma((1,1))$ this unique point and corresponding line are shown in red in the picture above. Some elementary algebra shows that these points are $(0,-d)$, $(0,\tfrac{d}{2})$ and $(0,2d)$, just as the picture suggests, where $(0,\tfrac{d}{2})=(0,\frac{n+1}{2}d)$ and $(0,-d)=(0,(n-1)d)$.
We will prove that $\sigma((0,2))=(0,2d)$. Note that for $n=3$ we have $2d=-d=\frac{n+1}{2}d$ and so there is nothing to prove. So suppose $n>3$.
Consider the possible positions for $\sigma((1,2))$. Note that $(1,2)$ is the unique point that is on a line with $(0,1)$, $(0,2)$ and $(1,1)$ but not on a line with any pair of them. Also note that $(1,2)$ is not on a line with $(0,0)$ because $n>3$, and it is on the unique line through $(1,1)$ that does not contain $(0,0)$, $(0,1)$ or $(0,2)$.
If $\sigma((1,1))=(d,0)$, which is the bottom left blue point in the picture above, then $\sigma((0,2))=(0,-d)$. Then $\sigma((1,2))$ is on the unique line through $\sigma((1,1))=(d,0)$ that does not contain $(0,0)$, $(0,d)$ and $(0,-d)$, and it is on one of the two lines through $(0,-d)$ that does not contain $(0,0)$ , $(0,d)$ or $(d,0)$. These lines are shown in green in the following picture:
Because $\sigma((1,2))$ is not on a line with $\sigma((0,0))=(0,0)$, we must have $\sigma((1,2))=(-2d,d)$. This point is shown in green in the picture above. But for $n>3$ this point is not on a line with $\sigma((0,1))=(0,d)$, a contradiction. This proves that $\sigma((1,1))\neq(d,0)$, and by symmetry also that $\sigma((1,1))\neq((-d,0))$. This implies that $\sigma((0,2))\neq(0,-d)$, as the first picture shows.
A similar geometrical argument shows that if $\sigma((1,1))=(\pm\tfrac{d}{2},\tfrac{d}{2})$ then the point $(-1,1)$ has nowhere to go, from which it follows that $\sigma((0,2))\neq(0,\tfrac{d}{2})$. I omit the details.
This proves that $\sigma((0,2))=(0,2d)$, and a simple induction argument then shows that $\sigma((0,k))=(0,dk)$ for all $k\in\Bbb{Z}/n\Bbb{Z}$. Because $\sigma$ is injective we have $d\in(\Bbb{Z}/n\Bbb{Z})^{\times}$.$\hspace{20pt}\square$
Corollary: In the situation above we have $\sigma((1,1))=(\pm d,d)$.$\hspace{20pt}\square$
Lemma 2: Let $n$ be an odd positive integer. Let $\sigma$ be a symmetry of $\Bbb{A}_2(n)$ that preserves the set of rows, columns, diagonals and antidiagonals that is the identity on $(0,0)$, $(0,1)$ and $(1,1)$. Then $\sigma$ is the identity on $\Bbb{A}_2(n)$.
Proof. To be supplied; similar geometrical arguments as before.$\hspace{20pt}\square$
Proof of Theorem 1. Let $\sigma$ be a symmetry of $\Bbb{A}_2(n)$ that preserves the set of rows, columns, diagonals and antidiagonals. Let $(i,j)=\sigma((0,0))$ and let $\tau$ denote the translation by $(-i,-j)$. Then the permutation $\tau\sigma$ fixes the point $(0,0)$, and $\tau$ is the unique translation for which this holds.
Because $\tau\sigma$ preserves lines we know that $\tau\sigma((0,1))$ is on a horizontal, vertical or diagonal line through $\tau\sigma((0,0))=(0,0)$. Then there is a unique $k\in\{0,1,2,3\}$ such that $\rho^k\tau\sigma((0,1))$ is on the horizontal line through $(0,0)$, and hence by Lemma 1 the restriction of $\rho^k\tau\sigma$ to the first row is given by multiplication by some $d\in(\Bbb{Z}/n\Bbb{Z})^{\times}$. Let $\gamma_d(i,j):=(di,dj)$ denote the scaling by $d$, which preserves the sets of rows, columns, diagonals and antidiagonals. Then $\gamma_d\rho^k\tau\sigma$ is the identity on the first row, and by the Corollary we have $$\gamma_d\rho^k\tau\sigma((1,1))=(\pm1,1).$$ Then there is a unique $l\in\{0,1\}$ such that $$\mu^l\gamma_d\rho^k\tau\sigma((1,1))=(1,1).$$ Now it follows from Lemma 2 that this map is the identity, and hence $$\sigma((x,y))=(\tau^{-1}\rho^{-k}\gamma_d^{-1}\mu^{-l})(x,y)=d^{-1}\rho^{-k}\mu^l\binom{x}{y}-\binom{i}{j},$$ for all $(x,y)\in\Bbb{A}_2(n)$. This shows that $\sigma$ is a symmetry of the form described in Theorem 1.$\hspace{20pt}\square$
Best Answer
@jenny :I do not a see a formula in your post that you expect to generalize.
We are counting partitions of $x$ with $y$ parts and the largest part not exceeding $z$.
One way is to use recursive formulation as pointed out by @Kevin Carlson.
Another quick way on a computer is to use the generating function: $$\sum_{\text{over }y\text{-element subsets of }[z-1]}\left( \prod_{\text{over elements of a y-element subset}}\frac{1}{1-n^s} \right)$$and then look at the coefficient of $n^{x-y}$ where $[z-1]=\{1,2,\dots, z-1\}$