[seqfan] Re: Peculiarity of A130595, Inverse Pascal Triangle
Dale Gerdemann
dale.gerdemann at gmail.com
Tue Jan 6 01:31:51 CET 2015
Dear SeqFans,
Thanks Frank for answering such an easy question. Sometimes my Parkinsons
medication causes me to lose concentration and miss the most obvious things.
Anyway, for compensation, I now feel obliged to say something which I hope
will be less trivial.
I'm working on a tiling method as a combinatorial model for a wide range of
Pascal-like triangles. I call this: Up-Down Tiling. The rules are as
follows:
There are two kinds of tiles, called "up" tiles and "down" tiles. Each of
these tiles comes in multiple number of colors. If the number of "colors"
is negative, you may think of it more abstractly as a weight. There are,
for example, 6 ways to concatenate a 2-color tile with a 3-color tile.
All tiles are squares (at least that is the case for what I want to
describe here). Triangle entry T(n,k) counts the number of ways to tile a
1xn board with k up tiles and n-k down tiles. To do this, you need to know
how many colors each tile has, and this is determined by a given function f
and a value that I call "shift". As an example:
f(n) = -n
s = 1
The coloring rules are:
1. An up tile with k down tiles to the left receives f(k+s) colors.
2. A down tile with k up tiles to the left receives f(k-s) colors
The mnemonic is that an "up" tile is shifted upwards and a "down" tile is
shifted downward. The situation is reversed, of course, if s < 0.
With the given values for f(n) and s, you get A130595.
I end this post with a list of OEIS triangles that apparently can be
counted with up-down tiling, followed by some examples for one of these
triangles. But first, as an aside, let me return to what I found peculiar
about A1305959. Using the given value of f(n) = -1, the following identity
holds:
f(n-k) * T(n,k) = f(k)*T(n-1,k)
For Pascal's Triangle f(n) = 1, as seen in my list below, and this identity
clearly does not hold. In fact, the identity only holds for one other
triangle on my list. I don't know if this is a very deep or important
observation, but anyway I noticed it ...
So, returning from the "aside," here is the list. It's all unproven, of
course, but I expect to have some results when this is written up (possibly
with a co-author, who I will leave unnamed for now).
A007318 Pascal's Triangle
f(n) = 1
s = 0
A130595 Inverse Pascal's Triangle
f(n) = -n
s = 1
A110555 Triangle of partial sums of alternating binomial coefficients
f(n) = n
s = -1
A008292 Triangle of Eulerian numbers
f(n) = n + 1
s = 0
A120434 permutations by number of big descents.
f(n) = n + 1
s = -1
A144697 Triangle of 3-restricted Eulerian numbers
f(n) = n + 2
s = 1
A144699 Triangle 5-restricted Eulerian numbers
f(n) = n + 3
s = 2
A060187 Eulerian numbers of type B
f(n) = 2n + 1
s = 0
A142458 T(n,k) = 1 if k=1 or k=n, else T(n,k) = (3*n-3*k+1)*T(n-1,k-1) +
(3*k-2)*T(n-1,k).
f(n) = 3n + 1
s = 0
A142459 T(n,k) = (4n-4k+1) * T(n-1,k-1) + (4k-3) * T(n-1,k).
f(n) = 4n + 1
s = 0
A142460 T(n, 1) = T(n,n) = 1, otherwise T(n, k) =
(m*n-m*k+1)*T(n-1,k-1)+(m*k-m+1)*T(n-1,k), where m = 5
f(n) = 5n + 1
s = 0
A142461 T(n, 1) = T(n,n) = 1, otherwise T(n, k) =
(m*n-m*k+1)*T(n-1,k-1)+(m*k-m+1)*T(n-1,k), where m = 6
f(n) = 6n + 1
s = 0
A142462 T(n, 1) = T(n,n) = 1, otherwise T(n, k) =
(m*n-m*k+1)*T(n-1,k-1)+(m*k-m+1)*T(n-1,k), where m = 5
f(n) = 7n + 1
s = 0
A167884 T(n, 1) = T(n,n) = 1, otherwise T(n, k) =
(m*n-m*k+1)*T(n-1,k-1)+(m*k-m+1)*T(n-1,k), where m = 8
f(n) = 8n + 1
s = 0
A038221 Triangle whose (i,j)-th entry is binomial(i,j)*3^(i-j)*3^j.
f(n) = |n|
s = 3
A038234 Triangle whose (i,j)-th entry is binomial(i,j)*4^(i-j)*4^j
f(n) = |n|
s = 4
A038247 Triangle whose (i,j)-th entry is binomial(i,j)*5^(i-j)*5^j.
f(n) = |n|
s = 5
A038260 T(n,k) = binomial(n,k)*6^(n-k)*6^k
f(n) = |n|
s = 6
A038273 Triangle whose (i,j)-th entry is binomial(i,j)*7^(i-j)*7^j
f(n) = |n|
s = 7
A038286 Triangle whose (i,j)-th entry is binomial(i,j)*8^(i-j)*8^j.
f(n) = |n|
s = 8
A038299 Triangle whose (i,j)-th entry is binomial(i,j)*9^(i-j)*9^j
f(n) = |n|
s = 9
A010048 Fibonomial
f(n) = Fibonacci(n) (with F(-1) = 1, F(0) = 0, F(1) = 1, F(2) = 1, etc)
s = 1
Here are some examples of tilings for the Fibonomial. I write, for example,
"d2" for a down tile with 2 colors, and "u5" for an up tile with 5 colors:
Fibonomial( 0 , 0 ) = 1 = 1 Fibonomial( 1 , 0 ) = 1 u1 = 1 Fibonomial( 1 ,
1 ) = 1 d1 = 1 Fibonomial( 2 , 0 ) = 1 u1 u1 = 1 Fibonomial( 2 , 1 ) = 1 d1
u1 = 1 u1 d0 = 0 Fibonomial( 2 , 2 ) = 1 d1 d1 = 1 Fibonomial( 3 , 0 ) = 1
u1 u1 u1 = 1 Fibonomial( 3 , 1 ) = 2 d1 u1 u1 = 1 u1 d0 u1 = 0 u1 u1 d1 = 1
Fibonomial( 3 , 2 ) = 2 d1 d1 u2 = 2 d1 u1 d0 = 0 u1 d0 d0 = 0 Fibonomial(
3 , 3 ) = 1 d1 d1 d1 = 1 Fibonomial( 4 , 0 ) = 1 u1 u1 u1 u1 = 1
Fibonomial( 4 , 1 ) = 3 d1 u1 u1 u1 = 1 u1 d0 u1 u1 = 0 u1 u1 d1 u1 = 1 u1
u1 u1 d1 = 1 Fibonomial( 4 , 2 ) = 6 d1 d1 u2 u2 = 4 d1 u1 d0 u2 = 0 u1 d0
d0 u2 = 0 d1 u1 u1 d1 = 1 u1 d0 u1 d1 = 0 u1 u1 d1 d1 = 1 Fibonomial( 4 , 3
) = 3 d1 d1 d1 u3 = 3 d1 d1 u2 d0 = 0 d1 u1 d0 d0 = 0 u1 d0 d0 d0 = 0
Fibonomial( 4 , 4 ) = 1 d1 d1 d1 d1 = 1 Fibonomial( 5 , 0 ) = 1 u1 u1 u1 u1
u1 = 1 Fibonomial( 5 , 1 ) = 5 d1 u1 u1 u1 u1 = 1 u1 d0 u1 u1 u1 = 0 u1 u1
d1 u1 u1 = 1 u1 u1 u1 d1 u1 = 1 u1 u1 u1 u1 d2 = 2 Fibonomial( 5 , 2 ) = 15
d1 d1 u2 u2 u2 = 8 d1 u1 d0 u2 u2 = 0 u1 d0 d0 u2 u2 = 0 d1 u1 u1 d1 u2 = 2
u1 d0 u1 d1 u2 = 0 u1 u1 d1 d1 u2 = 2 d1 u1 u1 u1 d1 = 1 u1 d0 u1 u1 d1 = 0
u1 u1 d1 u1 d1 = 1 u1 u1 u1 d1 d1 = 1 Fibonomial( 5 , 3 ) = 15 d1 d1 d1 u3
u3 = 9 d1 d1 u2 d0 u3 = 0 d1 u1 d0 d0 u3 = 0 u1 d0 d0 d0 u3 = 0 d1 d1 u2 u2
d1 = 4 d1 u1 d0 u2 d1 = 0 u1 d0 d0 u2 d1 = 0 d1 u1 u1 d1 d1 = 1 u1 d0 u1 d1
d1 = 0 u1 u1 d1 d1 d1 = 1 Fibonomial( 5 , 4 ) = 5 d1 d1 d1 d1 u5 = 5 d1 d1
d1 u3 d0 = 0 d1 d1 u2 d0 d0 = 0 d1 u1 d0 d0 d0 = 0 u1 d0 d0 d0 d0 = 0
Fibonomial( 5 , 5 ) = 1 d1 d1 d1 d1 d1 = 1 Fibonomial( 6 , 0 ) = 1 u1 u1 u1
u1 u1 u1 = 1 Fibonomial( 6 , 1 ) = 8 d1 u1 u1 u1 u1 u1 = 1 u1 d0 u1 u1 u1
u1 = 0 u1 u1 d1 u1 u1 u1 = 1 u1 u1 u1 d1 u1 u1 = 1 u1 u1 u1 u1 d2 u1 = 2 u1
u1 u1 u1 u1 d3 = 3 Fibonomial( 6 , 2 ) = 40 d1 d1 u2 u2 u2 u2 = 16 d1 u1 d0
u2 u2 u2 = 0 u1 d0 d0 u2 u2 u2 = 0 d1 u1 u1 d1 u2 u2 = 4 u1 d0 u1 d1 u2 u2
= 0 u1 u1 d1 d1 u2 u2 = 4 d1 u1 u1 u1 d1 u2 = 2 u1 d0 u1 u1 d1 u2 = 0 u1 u1
d1 u1 d1 u2 = 2 u1 u1 u1 d1 d1 u2 = 2 d1 u1 u1 u1 u1 d2 = 2 u1 d0 u1 u1 u1
d2 = 0 u1 u1 d1 u1 u1 d2 = 2 u1 u1 u1 d1 u1 d2 = 2 u1 u1 u1 u1 d2 d2 = 4
Fibonomial( 6 , 3 ) = 60 d1 d1 d1 u3 u3 u3 = 27 d1 d1 u2 d0 u3 u3 = 0 d1 u1
d0 d0 u3 u3 = 0 u1 d0 d0 d0 u3 u3 = 0 d1 d1 u2 u2 d1 u3 = 12 d1 u1 d0 u2 d1
u3 = 0 u1 d0 d0 u2 d1 u3 = 0 d1 u1 u1 d1 d1 u3 = 3 u1 d0 u1 d1 d1 u3 = 0 u1
u1 d1 d1 d1 u3 = 3 d1 d1 u2 u2 u2 d1 = 8 d1 u1 d0 u2 u2 d1 = 0 u1 d0 d0 u2
u2 d1 = 0 d1 u1 u1 d1 u2 d1 = 2 u1 d0 u1 d1 u2 d1 = 0 u1 u1 d1 d1 u2 d1 = 2
d1 u1 u1 u1 d1 d1 = 1 u1 d0 u1 u1 d1 d1 = 0 u1 u1 d1 u1 d1 d1 = 1 u1 u1 u1
d1 d1 d1 = 1 Fibonomial( 6 , 4 ) = 40 d1 d1 d1 d1 u5 u5 = 25 d1 d1 d1 u3 d0
u5 = 0 d1 d1 u2 d0 d0 u5 = 0 d1 u1 d0 d0 d0 u5 = 0 u1 d0 d0 d0 d0 u5 = 0 d1
d1 d1 u3 u3 d1 = 9 d1 d1 u2 d0 u3 d1 = 0 d1 u1 d0 d0 u3 d1 = 0 u1 d0 d0 d0
u3 d1 = 0 d1 d1 u2 u2 d1 d1 = 4 d1 u1 d0 u2 d1 d1 = 0 u1 d0 d0 u2 d1 d1 = 0
d1 u1 u1 d1 d1 d1 = 1 u1 d0 u1 d1 d1 d1 = 0 u1 u1 d1 d1 d1 d1 = 1
Fibonomial( 6 , 5 ) = 8 d1 d1 d1 d1 d1 u8 = 8 d1 d1 d1 d1 u5 d0 = 0 d1 d1
d1 u3 d0 d0 = 0 d1 d1 u2 d0 d0 d0 = 0 d1 u1 d0 d0 d0 d0 = 0 u1 d0 d0 d0 d0
d0 = 0 Fibonomial( 6 , 6 ) = 1 d1 d1 d1 d1 d1 d1 = 1
Dale
On Mon, Jan 5, 2015 at 10:18 PM, Frank Adams-Watters <franktaw at netscape.net>
wrote:
> One can make the same kind of calculation for the Pascal triangle; just
> replace the (k-n-1) with (n-k+1). Or if you prefer,
>
> C(n,k) = n/k * C(n-1,k-1)
>
> This is not a difficult result; it follows immediately from C(n,k) =
> n!/(k! * (n-k)!).
>
> Franklin T. Adams-Watters
>
>
> -----Original Message-----
> From: Dale Gerdemann <dale.gerdemann at gmail.com>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Sent: Mon, Jan 5, 2015 2:04 pm
> Subject: [seqfan] Peculiarity of A130595, Inverse Pascal Triangle
>
>
> Hello Seqfans,
>
> In the usual Pascal recursion
>
> T(n,k) = T(n-1,k-1) + T(n-1.k)
>
> each entry in the triangle is dependent on two neighbors above.
>
> But in A130595, you can generate an entry given only one entry above:
>
> T(n,k) = (n+1)/(k-n-1) * T(n-1,k)
>
> Try for example T(8,5). First locate T(8,5) in the triangle:
>
> Triangle begins:
>
> 1;
>
> -1, 1;
>
> 1, -2, 1;
>
> -1, 3, -3, 1;
>
> 1, -4, 6, -4, 1;
>
> -1, 5, -10, 10, -5, 1;
>
> 1, -6, 15, -20, 15, -6, 1;
>
> -1, 7, -21, 35, -35, 21, -7, 1;
>
> 1, -8, 28, -56, 70, -56, 28, -8, 1;
>
> -1, 9, -36, 84, -126, 126, -84, 36, -9, 1
>
>
> So T(8,5) = -56, and -56 * 9/-4 = 126, just as you can see in the triangle.
>
>
> Has this been discussed anywhere?
>
>
> Dale
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list