|
|
COMMENTS
|
Let I(n)={1,2,...,n}. Arrange the subsets of I(n) in an
array S(n) of n rows, where row k consists of all the
numbers in all the k-element subsets, including
repetitions. Each i in I(n) occurs C(n-1,k-1) times in
row k of S(n); index these occurrences as
...
(k,1,1),(k,1,2),...,(k,1,r),(k,2,1),...,(k,2,r),...,(k,n,1),...,(k,n,r),
...
where r=C(n-1,k-1). Definitions:
(1) A path through I(n) is an n-tuple of triples,
((1,i(1),j(1)), (2,i(2),j(2)), ..., (n,i(n),j(n)),
formed from the above indexing of the numbers in S(n).
(2) The trace of such a path p is the n-tuple
(i(1),i(2),...,i(n)).
(3) The range of p is the set {i(1),i(2),...,i(n)}.
(4) Path p has property P if its trace or range has
property P.
...
Guide to sequences which count paths according to
selected properties:
property................................sequence
range = {1}.............................A001142(n-1)
constant (range just one element).......A208650
range = {1,2,...,n}.....................A208651
palindromic.............................A208654
palindromic with i(1)=1.................A208655
|
|
|
EXAMPLE
|
Taking n=3:
row 1: {1},{2},{3} ---------> 1,2,3
row 2: {1,2},{1,3},{2,3} ---> 1,1,2,2,3,3
row 3: {1,2,3} -------------> 1,2,3
3 ways to choose a number from row 1,
2 ways to choose same number from row 2,
1 way to choose same number from row 3.
Total: a(3) = 1*2*3 = 6 paths.
|
