OFFSET
0,2
COMMENTS
Rows of A013610 reversed. - Michael Somos, Feb 14 2002
Row sums are powers of 4 (A000302), antidiagonal sums are A006190 (a(n) = 3*a(n-1) + a(n-2)). - Gerald McGarvey, May 17 2005
Triangle of coefficients in expansion of (3+x)^n.
Also: Pure Galton board of scheme (3,1). Also: Multiplicity (number) of pairs of n-dimensional 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^n-1)/2 different non-ordered pairs, actually.) - R. J. Mathar, Mar 17 2006
Mirror image of A013610. - Zerinvary Lajos, Nov 25 2007
T(i,j) is the number of i-permutations 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-(27-1)=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^(n-k), 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
Also the convolution triangle of A000244. - Peter Luschny, Oct 09 2022
LINKS
Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
B. N. Cyvin et al., Isomer enumeration of unbranched catacondensed polygonal systems with pentagons and heptagons, Match, No. 34 (Oct 1996), pp. 109-121.
Erich Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 No. 1-3, 33-51 (2001).
FORMULA
Numerators of lower triangle of (b^2)[ i, j ] where b[ i, j ] = binomial(i-1, j-1)/2^(i-1) if j <= i, 0 if j > i.
Triangle whose (i, j)-th entry is binomial(i, j)*3^(i-j).
a(n, m) = 4^(n-1)*Sum_{j=m..n} b(n, j)*b(j, m) = 3^(n-m)*binomial(n-1, m-1), n >= m >= 1; a(n, m) := 0, n < m. G.f. for m-th column: (x/(1-3*x))^m (m-fold convolution of A000244, powers of 3). - Wolfdieter Lang, Feb 2006
G.f.: 1 / (1 - x(3+y)).
a(n,k) = 3*a(n-1,k) + a(n-1,k-1) - 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
T(n,k) = A164942(n,k)*(-1)^k. - Philippe Deléham, Oct 09 2011
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/(1-3z)]/(1-3z) = 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
E.g.f. for column k: x^k/k! * exp(3x). - Geoffrey Critzer, Sep 04 2013
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^(i-j), j = 0 .. i) od; # Zerinvary Lajos, Nov 25 2007
# Uses function PMatrix from A357368. Adds column 1, 0, 0, ... to the left.
PMatrix(10, n -> 3^(n-1)); # Peter Luschny, Oct 09 2022
MATHEMATICA
t[n_, k_] := Binomial[n, k]*3^(n-k); Table[t[n, n-k], {n, 0, 9}, {k, n, 0, -1}] // Flatten (* Jean-Franç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]
-- Reinhard Zumkeller, May 26 2013
CROSSREFS
KEYWORD
AUTHOR
STATUS
approved