Suppose that $n$ is a natural number. we call the sequence $(x_1,y_1,z_1,t_1),(x_2,y_2,z_2,t_2),.....,(x_s,y_s,z_s,t_s)$ of $\mathbb Z^4$ good if it satisfies these three conditions: i) $x_1=y_1=z_1=t_1=0$. ii) the sequences $x_i,y_i,z_i,t_i$ be strictly increasing. iii) $x_s+y_s+z_s+t_s=n$. (note that $s$ may vary). Find the number of good sequences. proposed by Mohammad Ghiasi
Problem
Source: Iran 3rd round 2011-combinatorics exam-p5
Tags: function, algebra, linear equation, combinatorics proposed, combinatorics
15.09.2011 05:52
I obtained that $ x_{s} \geq s-1 $ so $ x_{s}=s-1+a_{s} $ then if $ a_{s} $ is fixed then are $ (a_{s}+1)^{s-1} $ sequences of $ x_{i} $. is this right?
18.08.2012 10:56
goodar2006 wrote: Suppose that $n$ is a natural number. we call the sequence $(x_1,y_1,z_1,t_1),(x_2,y_2,z_2,t_2),.....,(x_s,y_s,z_s,t_s)$ of $\mathbb Z^4$ good if it satisfies these three conditions: i) $x_1=y_1=z_1=t_1=0$. ii) the sequences $x_i,y_i,z_i,t_i$ be strictly increasing. iii) $x_s+y_s+z_s+t_s=n$. (note that $s$ may vary). Find the number of good sequences. proposed by Mohammad Ghiasi let $a_n$ be the number of good sequences such that $x_s+y_s+z_s+t_s=n$. we call these sequences $n$-good. obviously $a_0=1,a_1=a_2=a_3=0$. we want to find a recurrence relation. the linear equation $x_2+y_2+z_2+t_2=k$, $4\le k\le n$ has got $\binom{k-1}{3}$ positive integer solutions, and the sequence $(0,0,0,0),(x_3-x_2,y_3-y_2,z_3-z_2,t_3-t_2),\dots,(x_s-x_2,y_s-y_2,z_s-z_2,t_s-t_2)$ is a $n-k$-good sequence. so each $n$-good sequence with $x_2+y_2+z_2+t_2=k$ gives us a $n-k$-good sequence, and each $n-k$-good sequence gives us $\binom{k-1}{3}$ $n$-good sequence. so we have that: $(\star)$: $a_n=\sum_{k=4}^{n}\binom{k-1}{3}a_{n-k}=\sum_{k=1}^{n}\binom{k-1}{3}a_{n-k}$ let $F(x)$ be the generating function of the sequence $\{a_i\}$. let $f(x)=\sum_{r\ge 0}\binom{r}{3}x^r$. from $(\star)$ we get that: $F(x)=xf(x)F(x)+1$. so $F(x)=\frac{1}{1-xf(x)}$. but we have that $f(x)=\sum_{r=3}^{\infty}\frac{r(r-1)(r-2)}{6}x^r=\frac{x^3}{6}\left(\frac{d^3}{dx^3}(A(x))\right)$ where $A(x)=1+x+x^2+\dots=\frac{1}{1-x}$ so $f(x)=\frac{x^3}{(1-x)^4}$. so ${F(x)=\frac{1}{1-\frac{x^4}{(1-x)^4}}=\frac{(1-x)^4}{(1-x)^4-x^4}=\frac{5}{8}-\frac{1}{4}x+\frac{-\frac{5}{16}x^2+\frac{5}{16}x-\frac{3}{32}}{(x-\frac{1}{2})(x-\frac{1-i}{2})(x-\frac{1+i}{2})}}$ so $F(x)=\frac{5}{8}-\frac{1}{4}x+\frac{\frac{1}{8}}{1-2x}+\frac{\frac{1-i}{8}}{1-x(1-i)}++\frac{\frac{1+i}{8}}{1-x(1+i)}$ so $\forall n\ge 2: a_n=\frac{1}{8}\left(2^n+(1-i)^{n+1}+(1+i)^{n+1} \right)$ edit: typo fixed, thanks.
21.08.2012 05:09
ArefS wrote: $(\star)$: $a_n=\sum_{k=4}^{n}\binom{k-1}{3}a_k=\sum_{k=1}^{n}\binom{k-1}{3}a_k$ Why is not $(\star)$: $a_n=\sum_{k=4}^{n}\binom{k-1}{3}a_{n-k}=\sum_{k=1}^{n}\binom{k-1}{3}a_{n-k}$