2
$\begingroup$

I have come across a sequence but I am facing difficulties finding the general term of it :

1  1 1  3 2 3  5 3 3 5  11 8 10 8 11  21 13 14 14 13 21  43 30 37 36 37 30 43  85 55 61 55 55 61 55 85  171 116 140 140 146 140 140 116 171  341 225 256 232 226 226 232 256 225 341 

Things which I have figured out :

  • Every row is palindromic

  • The first term of each row(>1) can be found out by 2*a[row-1][0]+ (-1)^(row-1)

  • 2nd term of each row(>2) is a[row][0] - a[row-1][1]

Please help me to find the general formula for such series

  • 0
    For the first column: http://oeis.org/search?q=1%2C1%2C3%2C5%2C11%2C21&language=english. For the second column: http://oeis.org/search?q=0%2C1%2C2%2C3%2C8%2C13&sort=&language=english.2012-10-03
  • 0
    @Max : This is just the first and the last terms both of which I have mentioned in the post .2012-10-03
  • 0
    Look at the OEIS entries I've posted. They may be helpful, especially because the first suggests a different recurrence for the first column.2012-10-03
  • 0
    So, how did you come across this sequence?2012-10-03
  • 0
    @Gerry Myerson : I was solving a problem where two players(let them be A ,B ) are playing a game which consists of N coins in a row. Any player can pick up either the starting or the last coin in his turn. Player A begins . The above sequence is the number of times A picks up the jth coin when there are i coins initially in all possibilities.2012-10-03
  • 0
    Nice. There should be some way to relate row $n$ to row $n+2$, since after the first two moves on $n+2$ coins player $A$ faces $n$ coins.2012-10-03
  • 0
    the rowsums, using alternating signs, are [1,0,4,0,16,0,64,0...] Don't know, whether this is of some significance.2012-10-04
  • 0
    Have a look at http://math.stackexchange.com/questions/208126/probability-of-picking-kth-item-at-odd-turn which is essentially the same problem.2012-10-07

3 Answers 3

2

I think the following recursive scheme, reflecting the recursion of the pascal-triangle, shall be helpful. The parentheses contain the pascal-like summands north-east and north-west of an entry:

1                      =                    1-(0+0) 1 1                    =               2-(0+1)   2-(1+0) 3 2 3                  =           4-(0+1)   4-(1+1)   4-(1+0) 5 3 3 5                       8-(0+3)   8-(3+2)   8-(2+3)   8-(3+0)   11 8 10 8 11           = 16-(0+5)  16-(5+3)  16-(3+3)  16-(3+5)  16-(5+0) 21 13 14 14 13 21      = ... 

If the numbers of one row, index it with r beginning at 0, are taken as coefficents of a polynomial in x, call it $P_r(x)$ such that we have

$\qquad \begin{array} {} P_0(x)=1 \\ P_1(x)=1+1x \\ P_2(x)=3+2x+3x^2 \\ \ldots \end{array} $

then

$$ P_r(x) = 2^r \cdot {1-x^{r+1}\over 1-x} - (1+x)P_{r-1}(x) $$
[update:] error in index corrected

To expand the recursion into expressions based on the indexes only needs now only a bit more effort...


Here is the Pari/GP-routine, which produces the rows in terms of a polynomial in x using the recursion :

myPol(r)=if(r==0,return(1));2^r*(1-x^(r+1))/(1-x)  - (1+x)*myPol(r-1,x)   

The generated table of polcoeffs: $$ \small \begin{array} {rrrrrrrrrrr} 1 & . & . & . & . & . & . & . & . & . & . & . \\ 1 & 1 & . & . & . & . & . & . & . & . & . & . \\ 3 & 2 & 3 & . & . & . & . & . & . & . & . & . \\ 5 & 3 & 3 & 5 & . & . & . & . & . & . & . & . \\ 11 & 8 & 10 & 8 & 11 & . & . & . & . & . & . & . \\ 21 & 13 & 14 & 14 & 13 & 21 & . & . & . & . & . & . \\ 43 & 30 & 37 & 36 & 37 & 30 & 43 & . & . & . & . & . \\ 85 & 55 & 61 & 55 & 55 & 61 & 55 & 85 & . & . & . & . \\ 171 & 116 & 140 & 140 & 146 & 140 & 140 & 116 & 171 & . & . & . \\ 341 & 225 & 256 & 232 & 226 & 226 & 232 & 256 & 225 & 341 & . & . \\ 683 & 458 & 543 & 536 & 566 & 572 & 566 & 536 & 543 & 458 & 683 & . \\ 1365 & 907 & 1047 & 969 & 946 & 910 & 910 & 946 & 969 & 1047 & 907 & 1365 \end{array} $$

1

I tried deriving $ S _{n+2} $ from $ S _{n} $, and got something.
There are 4 ways to go $ S _{n+2} $ to $ S _{n} $ :
1) A selects first coin, B selects second coin $\space\space$:: [1,0] . $S_n$ (concat)
2) A select last one, B selects second last one :: $S_n$ . [0,1]
3) A selects first, first, B selects last $\space\space\space\space\space\space\space\space\space\space\space\space\space\space$ :: [1] . $S_n$ . [0]
4) A selects last, first, B selects first $\space\space\space\space\space\space\space\space\space\space\space\space\space\space$ :: [0] . $S_n$ . [1]

for eg, operating on [5 3 3 5] gives:
[1 0 5 3 3 5] + [5 3 3 5 0 1] + [1 5 3 3 5 0] + [0 5 3 3 5 1]
$\equiv$ [7 13 14 14 13 7]

Tried on othe examples, all numbers except the last and the first ones are coming correct (can somebody point out why?) Otherwise the first terms can be calculated by the formula $\frac{2^n - (-1)^n}{3}$

  • 0
    That's good! The trouble is that wherever you have 1, you should have the number of different ways the length $n$ game can go. E.g., there are 8 ways that $n=4$ can go (abab, abba, aabb, abab when 1st player starts on the left, 4 more where 1st player starts on the right), so you want 8 0 5 3 3 5 + 5 3 3 5 0 8 + 8 5 3 3 5 0 + 0 5 3 3 5 8 = 21 13 14 14 13 21.2012-10-04
  • 0
    Oh yes! You add your answer, mine is anyways more of a comment =)2012-10-04
  • 0
    Done.${}{}{}{}$2012-10-04
1

Let $f(n,k)$ be the number of times A picks up the $k$th coin when the game starts with $n$ coins. Note that the total number of ways an $n$ coin game can go is $2^{n-1}$, since each player has 2 options at each move, except the last move, which is forced. Then by the reasoning in the answer by piyush and my comment, we have the following equations. $$\eqalign{f(n+2,1)&=2^n+f(n,1)\cr f(n+2,2)&=2f(n,1)+f(n,2)\cr f(n+2,k)&=f(n,k)+2f(n,k-1)+f(n,k-2)\cr}$$ The third equation holds for $3\le k\le n-2$. Also, $f(n+2,n+1)=f(n+2,2)$, and $f(n+2,n+2)=f(n+2,1)$.

This gives a formula for the numbers in the table, but of course it's a recursive formula. Whether this system of equations can be solved in closed form, I don't know.

EDIT: For any fixed $k$ it shouldn't be too hard to get a formula for $f(n,k)$ as a function of $n$. Let's just take the case $n$ odd. From $$f(n+2,1)=2^n+f(n,1)$$ we get $$f(n,1)=2^{n-2}+2^{n-4}+\cdots+2^1+f(1,1)$$ and summing the geometric series we get $$f(n,1)={2^n+1\over3}$$ Then from $$f(n+2,2)=2f(n,1)+f(n,2)$$ we get $$f(n,2)=(2/3)(2^{n-2}+1+2^{n-4}+1+\cdots+2^1+1)$$ and there's another geometric series to sum. Now you can play the same game with $$f(n+2,3)=f(n,3)+2f(n,2)+f(n,1)$$ and so on. Perhaps a pattern emerges if you do enough of these.