

A027465


Cube of lower triangular normalized binomial matrix.


36



1, 3, 1, 9, 6, 1, 27, 27, 9, 1, 81, 108, 54, 12, 1, 243, 405, 270, 90, 15, 1, 729, 1458, 1215, 540, 135, 18, 1, 2187, 5103, 5103, 2835, 945, 189, 21, 1, 6561, 17496, 20412, 13608, 5670, 1512, 252, 24, 1, 19683, 59049, 78732, 61236, 30618, 10206, 2268
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Triangle of coefficients in expansion of (3+x)^n.
Also: Pure Galton board of scheme (3,1). Also: Multiplicity (number) of pairs of ndimensional binary vectors with dot product (overlap) k. There are 2^n = A000079(n) binary vectors of length n and 2^(2n) = 4^n = A000302(n) different pairs to form dot products k = Sum_{i=1..n} v[i]*u[i] between these, 0 <= k <= n. (Since dot products are symmetric, there are only 2^n*(2^n1)/2 different nonordered pairs, actually.)  R. J. Mathar, Mar 17 2006
T(i,j) is the number of ipermutations of 4 objects a,b,c,d, with repetition allowed, containing j a's.  Zerinvary Lajos, Dec 21 2007
The antidiagonals of the sequence formatted as a square array (see Examples section) and summed with alternating signs gives a bisection of Fibonacci sequence, A001906. Example: 81(271)=55. Similar rule applied to rows gives A000079.  Mark Dols, Sep 01 2009
Triangle T(n,k), read by rows, given by (3,0,0,0,0,0,0,0,...)DELTA (1,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938.  Philippe Deléham, Oct 09 2011
T(n,k) = binomial(n,k)*3^(nk), the number of subsets of [2n] with exactly k symmetric pairs, where elements i and j of [2n] form a symmetric pair if i+j=2n+1. Equivalently, if n couples attend a (ticketed) event that offers door prizes, then the number of possible prize distributions that have exactly k couples as dual winners is T(n,k).  Dennis P. Walsh, Feb 02 2012
T(n,k) is the number of ordered pairs (A,B) of subsets of {1,2,...,n} such that the intersection of A and B contains exactly k elements. For example, T(2,1) = 6 because we have ({1},{1}); ({1},{1,2}); ({2},{2}); ({2},{1,2}); ({1,2},{1}); ({1,2},{2}). Sum_{k=0..n} T(n,k)*k = A002697(n) (see comment there by Ross La Haye).  Geoffrey Critzer, Sep 04 2013


LINKS



FORMULA

Numerators of lower triangle of (b^2)[ i, j ] where b[ i, j ] = binomial(i1, j1)/2^(i1) if j <= i, 0 if j > i.
Triangle whose (i, j)th entry is binomial(i, j)*3^(ij).
a(n, m) = 4^(n1)*Sum_{j=m..n} b(n, j)*b(j, m) = 3^(nm)*binomial(n1, m1), n >= m >= 1; a(n, m) := 0, n < m. G.f. for mth column: (x/(13*x))^m (mfold convolution of A000244, powers of 3).  Wolfdieter Lang, Feb 2006
G.f.: 1 / (1  x(3+y)).
a(n,k) = 3*a(n1,k) + a(n1,k1)  R. J. Mathar, Mar 17 2006
From the formalism of A133314, the e.g.f. for the row polynomials of A027465 is exp(x*t)*exp(3x). The e.g.f. for the row polynomials of the inverse matrix is exp(x*t)*exp(3x). p iterates of the matrix give the matrix with e.g.f. exp(x*t)*exp(p*3x). The results generalize for 3 replaced by any number.  Tom Copeland, Aug 18 2008
Let P and P^T be the Pascal matrix and its transpose and H = P^3 = A027465. Then from the formalism of A132440 and A218272,
exp[x*z/(13z)]/(13z) = exp(3z D_z z) e^(x*z)= exp(3D_x x D_x) e^(z*x)
= (1 z z^2 z^3 ...) H (1 x x^2/2! x^3/3! ...)^T
= (1 x x^2/2! x^3/3! ...) H^T (1 z z^2 z^3 ...)^T = Sum_{n>=0} (3z)^n L_n(x/3), where D is the derivative operator and L_n(x) are the regular (not normalized) Laguerre polynomials.  Tom Copeland, Oct 26 2012


EXAMPLE

Example: n = 3 offers 2^3 = 8 different binary vectors (0,0,0), (0,0,1), ..., (1,1,0), (1,1,1). a(3,2) = 9 of the 2^4 = 64 pairs have overlap k = 2: (0,1,1)*(0,1,1) = (1,0,1)*(1,0,1) = (1,1,0)*(1,1,0) = (1,1,1)*(1,1,0) = (1,1,1)*(1,0,1) = (1,1,1)*(0,1,1) = (0,1,1)*(1,1,1) = (1,0,1)*(1,1,1) = (1,1,0)*(1,1,1) = 2.
For example, T(2,1)=6 since there are 6 subsets of {1,2,3,4} that have exactly 1 symmetric pair, namely, {1,4}, {2,3}, {1,2,3}, {1,2,4}, {1,3,4}, and {2,3,4}.
The present sequence formatted as a triangular array:
1
3 1
9 6 1
27 27 9 1
81 108 54 12 1
243 405 270 90 15 1
729 1458 1215 540 135 18 1
2187 5103 5103 2835 945 189 21 1
6561 17496 20412 13608 5670 1512 252 24 1
...
A013610 formatted as a triangular array:
1
1 3
1 6 9
1 9 27 27
1 12 54 108 81
1 15 90 270 405 243
1 18 135 540 1215 1458 729
1 21 189 945 2835 5103 5103 2187
1 24 252 1512 5670 13608 20412 17496 6561
...
A099097 formatted as a square array:
1 0 0 0 0 0 0 0 0 0 0 ...
3 1 0 0 0 0 0 0 0 0 ...
9 6 1 0 0 0 0 0 0 ...
27 27 9 1 0 0 0 0 ...
81 108 54 12 1 0 0 ...
243 405 270 90 15 1 ...
729 1458 1215 540 135 ...
2187 5103 5103 2835 ...
6561 17496 20412 ...
19683 59049 ...
59049 ...


MAPLE

for i from 0 to 12 do seq(binomial(i, j)*3^(ij), j = 0 .. i) od; # Zerinvary Lajos, Nov 25 2007
# Uses function PMatrix from A357368. Adds column 1, 0, 0, ... to the left.


MATHEMATICA

t[n_, k_] := Binomial[n, k]*3^(nk); Table[t[n, nk], {n, 0, 9}, {k, n, 0, 1}] // Flatten (* JeanFrançois Alcover, Sep 19 2012 *)


PROG

(PARI) {T(n, k) = polcoeff( (3 + x)^n, k)}; /* Michael Somos, Feb 14 2002 */
(Haskell)
a027465 n k = a027465_tabl !! n !! k
a027465_row n = a027465_tabl !! n
a027465_tabl = iterate (\row >
zipWith (+) (map (* 3) (row ++ [0])) (map (* 1) ([0] ++ row))) [1]


CROSSREFS

Cf. A000244, A007318, A013610, A013610, A099097, A027471, A027472, A036216, A036217, A036219, A036220, A036221, A036222, A036223.


KEYWORD



AUTHOR



STATUS

approved



