A089041 -id:A089041 - cp's OEIS frontend

A135809 Number of coincidence-free length n lists of 3-tuples with all numbers 1,...,n in tuple position k, for k=1,2,3.

1, 0, 7, 194, 13005, 1660964, 363083155, 125447139558, 64534483387801, 47199368682436040, 47309812970969661471, 63078455495155600593290, 109143265990975402533003877, 240033842542243124391262433004

Offset: 0

Wolfdieter Lang, Jan 21 2008, Feb 22 2008, May 21 2008

a(n) enumerates (ordered) lists of n three-tuples such that every number from 1 to n appears once at each of the three tuple positions and the j-th list member is not the tuple (j,j,j), for every j=1,..,n. Called coincidence-free 3-tuple lists of length n. See the Charalambides reference for this combinatorial interpretation.

			3-tuple combinatorics: a(1)=0 because the only list of 3-tuples with numbers 1 is [(1,1,1)] and this is a coincidence for j=1.
3-tuple combinatorics: the a(2)=7 coincidence-free 3-tuple lists of length n=2 are [(1,1,2),(2,2,1)], [(1,2,1),(2,1,2)], [(2,1,1),(1,2,2)], [(2,2,1), (1,1,2)], [(2,1,2),(1,2,1)], [(1,2,2),(2,1,1)] and [(2,2,2),(1,1, 1)]. The list [(1,1,1),(2,2,2)] has in fact two coincidences (j=1 and j=2).

Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 187, Exercise 13.(a), for r=3.

G. C. Greubel, Table of n, a(n) for n = 0..181

Cf. A089041 (coincidence-free 2-tuples), A135810 (coincidence-free 4-tuples).

Table[Sum[(-1)^k Binomial[n, k](n-k)!^3, {k, 0, n}], {n, 0, 13}] (* Geoffrey Critzer, Jun 17 2013 *)

a(n)=sum(k=0,n,(-1)^k*binomial(n, k)*(n-k)!^3) \\ Charles R Greathouse IV, Nov 17 2016

a(n) = Sum_{j=0,..,n} ( ((-1)^(n-j))*binomial(n,j)*(j!)^3 ). See the Charalambides reference a(n) = B_{n,3}.

a(n) ~ n!^3 ~ (2*Pi)^(3/2) * n^(3*n + 3/2) / exp(3*n). - Vaclav Kotesovec, Nov 19 2016

A135814 Triangle of numbers of coincidence-free length n-m lists of m-tuples with all numbers 1,...,n-m in tuple position k, for k=1..m.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 2, 3, 0, 1, 0, 9, 26, 7, 0, 1, 0, 44, 453, 194, 15, 0, 1, 0, 265, 11844, 13005, 1250, 31, 0, 1, 0, 1854, 439975, 1660964, 326685, 7682, 63, 0, 1, 0, 14833, 22056222, 363083155, 205713924, 7931709, 46466, 127, 0, 1, 0, 133496

Offset: 0

Wolfdieter Lang, Jan 21 2008, Feb 22 2008, May 21 2008

The column sequences (without leading zeros) give A000007, A000166 (subfactorials), A089041, A135809 - A135813, for m=0..7.

a(n,m), n >= m, enumerates (ordered) length n-m lists of m-tuples such that every number from 1 to n-m appears once at each of the n-m tuple positions and the j-th list member is not the tuple (j,j,...,j) (m times j), for every j=1,...,n-m. Called coincidence-free m-tuple lists of length n-m. See the Charalambides reference for this combinatorial interpretation.

			[1]; [0,1]; [0,0,1]; [0,1,0,1]; [,0,2,3,0,1]; [0,9,26,7,0,1]; ...
The a(5,3)=7 lists of length 5-3=2 with coincidence-free 3-tuples are [(1,1,2),(2,2,1)], [(1,2,1),(2,1,2)], [(2,1,1),(1,2,2)], [(1,2,2),(2,1,1)], [(2,1,2),(1,2,1)], [(2,2,1),(1,1,2)] and [(2,2,2),(1,1,1)]. The list [(1,1,1),(2,2,2)] is not coincidence-free because (1,1,1) appears at position 1 and also because (2,2,2) appears at position 2.

Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 187, Exercise 13.(a).

W. Lang, First 10 rows and more.

a(n,m) = Sum_{j=0..n-m} (-1)^(n-m-j)*binomial(n-m,j)*(j!)^m, n >= m >= 0, otherwise 0.

A371767 Triangle read by rows: T(n, k) = (k! * n!)/(n - k)!.

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 1, 3, 12, 36, 1, 4, 24, 144, 576, 1, 5, 40, 360, 2880, 14400, 1, 6, 60, 720, 8640, 86400, 518400, 1, 7, 84, 1260, 20160, 302400, 3628800, 25401600, 1, 8, 112, 2016, 40320, 806400, 14515200, 203212800, 1625702400

Offset: 0

Peter Luschny, Apr 14 2024

			Triangle starts:
  [0] 1;
  [1] 1, 1;
  [2] 1, 2,  4;
  [3] 1, 3, 12,   36;
  [4] 1, 4, 24,  144,   576;
  [5] 1, 5, 40,  360,  2880,  14400;
  [6] 1, 6, 60,  720,  8640,  86400,  518400;
  [7] 1, 7, 84, 1260, 20160, 302400, 3628800, 25401600;

Cf. A000142, A001044 (main diagonal), A010790 (subdiagonal), A046662 (row sums), A089041 (alternating row sums), A010050 (central terms).

T := (n, k) -> (k! * n!)/(n - k)!:
for n from 0 to 6 do seq(T(n, k), k = 0..n) od;

A226780 Triangular array read by rows. T(n,k) is the number of 2 tuple lists of length n that have exactly k coincidences; n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 3, 0, 1, 26, 9, 0, 1, 453, 104, 18, 0, 1, 11844, 2265, 260, 30, 0, 1, 439975, 71064, 6795, 520, 45, 0, 1, 22056222, 3079825, 248724, 15855, 910, 63, 0, 1, 1436236809, 176449776, 12319300, 663264, 31710, 1456, 84, 0, 1

Offset: 0

Geoffrey Critzer, Jun 18 2013

Consider the set (with cardinality n!^2) of (ordered) lists of n two tuples such that all numbers from 1 to n appear as the first as well as the second tuple entry. If the j-th two tuple of the list is (j,j) then call it a coincidence. T(n,k) is the number of such lists that have k coincidences.

			1;
0,        1;
3,        0,       1;
26,       9,       0,      1;
453,      104,     18,     0,     1;
11844,    2265,    260,    30,    0,   1;
439975,   71064,   6795,   520,   45,  0,   1;
22056222, 3079825, 248724, 15855, 910, 63,  0,   1;

Alois P. Heinz, Rows n = 0..100, flattened

Cf. A008290.

b:= proc(n) option remember;
       `if`(n<2, 1-n, n^2*b(n-1)+n*(n-1)*b(n-2)+(-1)^n)
    end:
T:= (n, k)-> binomial(n, k) * b(n-k):
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Jun 21 2013

a = Table[Sum[(-1)^k Binomial[n,k](n-k)!^2, {k,0,n}], {n,0,15}]; Table[Drop[Transpose[Table[Table[Binomial[n,i]*a[[n-i+1]], {n,0,10}], {i,0,10}]][[j]], -11+j], {j, 10}]//Grid

T(n,k) = binomial(n,k) * A089041(n-k).
Row sums = n!^2.
T(n,0) = A089041(n).
The expected number of coincidences, Sum_{k=0..n} T(n,k)*k/n!^2 = 1/n.

cp's OEIS Frontend

A135809 Number of coincidence-free length n lists of 3-tuples with all numbers 1,...,n in tuple position k, for k=1,2,3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A135814 Triangle of numbers of coincidence-free length n-m lists of m-tuples with all numbers 1,...,n-m in tuple position k, for k=1..m.

Views

Author

Keywords

Comments

Examples

References

Links

Formula

A371767 Triangle read by rows: T(n, k) = (k! * n!)/(n - k)!.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

A226780 Triangular array read by rows. T(n,k) is the number of 2 tuple lists of length n that have exactly k coincidences; n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula