A128831 -id:A128831 - cp's OEIS frontend

A127509 Number of n-tuples where each entry is chosen from the subsets of {1,2,3} such that the intersection of all n entries contains exactly one element.

3, 27, 147, 675, 2883, 11907, 48387, 195075, 783363, 3139587, 12570627, 50307075, 201277443, 805208067, 3221028867, 12884508675, 51538821123, 206156857347, 824630575107, 3298528591875, 13194126950403, 52776532967427

Offset: 1

Peter C. Heinig (algorithms(AT)gmx.de), Apr 17 2007

nonn

There is the following general formula: The number T(n,k,r) of n-tuples where each entry is chosen from the subsets of {1,2,..,k} such that the intersection of all n entries contains exactly r elements is: T(n,k,r) = C(k,r) * (2^n - 1)^(k-r). This may be shown by exhibiting a bijection to a set whose cardinality is obviously C(k,r) * (2^n - 1)^(k-r), namely the set of all k-tuples where each entry is chosen from subsets of {1,..,n} in the following way: Exactly r entries must be {1,..,n} itself (there are C(k,r) ways to choose them) and the remaining (k-r) entries must be chosen from the 2^n-1 proper subsets of {1,..,n}, i.e. for each of the (k-r) entries, {1,..,n} is forbidden (there are, independent of the choice of the full entries, (2^n - 1)^(k-r) possibilities to do that, hence the formula). The bijection into this set is given by (X_1,..,X_n) |-> (Y_1,..,Y_k) where for each j in {1,..,k} and each i in {1,..,n}, i is in Y_j if and only if j is in X_i.

			a(1)=3 because the three sequences of length one are: ({1}), ({2}), ({3}).
a(2)=27 because the twenty-seven sequences of length two are:
  ({1},{1}), ({2},{2}), ({3},{3}), ({1},{1,2}),
  ({1},{1,3}), ({2},{1,2}), ({2},{2,3}), ({3},{1,3}),
  ({3},{2,3}), ({1,2},{1}), ({1,3},{1}), ({1,2},{2}),
  ({2,3},{2}), ({1,3},{3}), ({2,3},{3}), ({1},{1,2,3}),
  ({2},{1,2,3}), ({3},{1,2,3}), ({1,2,3},{1}), ({1,2,3},{2}),
  ({1,2,3},{3}), ({1,2},{1,3}), ({1,3},{1,2}), ({1,2},{2,3}),
  ({2,3},{1,2}), ({1,3},{2,3}), ({2,3},{1,3}).

Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Cf. A128831, A128832, A128833, A095121.

Maple
```
for k from 1 to 41 do 3*(2^k-1)^2; od;
```

LinearRecurrence[{7,-14,8},{3,27,147},22] (* James C. McMahon, Jan 02 2025 *)

a(n) = 3*(2^n-1)^2.

G.f.: 3*x*(1+2*x)/(1-7*x+14*x^2-8*x^3). [Colin Barker, Feb 08 2012]

A245789 Rectangular array A read by upward antidiagonals: A(k,n) = (2^k-1)^n, n,k >= 1.

Original entry on oeis.org

1, 1, 3, 1, 9, 7, 1, 27, 49, 15, 1, 81, 343, 225, 31, 1, 243, 2401, 3375, 961, 63, 1, 729, 16807, 50625, 29791, 3969, 127, 1, 2187, 117649, 759375, 923521, 250047, 16129, 255, 1, 6561, 823543, 11390625, 28629151, 15752961, 2048383, 65025, 511

Offset: 1

L. Edson Jeffery, Aug 22 2014

A(k,n) is the number of sequences (X_1, X_2, ..., X_k) of subsets of the set {1, 2, ..., n} such that intersect_{j=1..k} X_j = null.

			Array A begins:
1      3         7           15              31                 63
1      9        49          225             961               3969
1     27       343         3375           29791             250047
1     81      2401        50625          923521           15752961
1    243     16807       759375        28629151          992436543
1    729    117649     11390625       887503681        62523502209
1   2187    823543    170859375     27512614111      3938980639167
1   6561   5764801   2562890625    852891037441    248155780267521
1  19683  40353607  38443359375  26439622160671  15633814156853823

Richard P. Stanley, Enumerative Combinatorics, Cambridge University Press, Vol. 1, Second edition, 2012, p. 14 (Example 1.1.16).

L. Edson Jeffery, Table of n, a(n) for n = 1..45

Cf. A000225, A060867, A128831, etc. (rows 1-3).
Cf. A000012, A000244, A000420, etc. (columns 1-3).
Cf. A055601 (main diagonal).

(* Array *)
a[k_, n_] := (2^k - 1)^n; Grid[Table[a[k, n], {n, 12}, {k, 12}]]
(* Array antidiagonals flattened *)
Flatten[Table[(2^k - 1)^(n - k + 1), {n, 12}, {k, n}]]

cp's OEIS Frontend

A127509 Number of n-tuples where each entry is chosen from the subsets of {1,2,3} such that the intersection of all n entries contains exactly one element.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula