login
Number of constant paths through the subset array of {1,2,...,n}; see Comments.
5

%I #7 Mar 30 2012 18:58:13

%S 1,2,6,36,480,15000,1134000,211768200,99131719680,117595223746560,

%T 356467003200000000,2779532232516963000000,56049508602150185041920000,

%U 2935889842347365340037522521600

%N Number of constant paths through the subset array of {1,2,...,n}; see Comments.

%C Let I(n)={1,2,...,n}. Arrange the subsets of I(n) in an

%C array S(n) of n rows, where row k consists of all the

%C numbers in all the k-element subsets, including

%C repetitions. Each i in I(n) occurs C(n-1,k-1) times in

%C row k of S(n); index these occurrences as

%C ...

%C (k,1,1),(k,1,2),...,(k,1,r),(k,2,1),...,(k,2,r),...,(k,n,1),...,(k,n,r),

%C ...

%C where r=C(n-1,k-1). Definitions:

%C (1) A path through I(n) is an n-tuple of triples,

%C ((1,i(1),j(1)), (2,i(2),j(2)), ..., (n,i(n),j(n)),

%C formed from the above indexing of the numbers in S(n).

%C (2) The trace of such a path p is the n-tuple

%C (i(1),i(2),...,i(n)).

%C (3) The range of p is the set {i(1),i(2),...,i(n)}.

%C (4) Path p has property P if its trace or range has

%C property P.

%C ...

%C Guide to sequences which count paths according to

%C selected properties:

%C property................................sequence

%C range = {1}.............................A001142(n-1)

%C constant (range just one element).......A208650

%C range = {1,2,...,n}.....................A208651

%C palindromic.............................A208654

%C palindromic with i(1)=1.................A208655

%F (See the Mathematica section.)

%e Taking n=3:

%e row 1: {1},{2},{3} ---------> 1,2,3

%e row 2: {1,2},{1,3},{2,3} ---> 1,1,2,2,3,3

%e row 3: {1,2,3} -------------> 1,2,3

%e 3 ways to choose a number from row 1,

%e 2 ways to choose same number from row 2,

%e 1 way to choose same number from row 3.

%e Total: a(3) = 1*2*3 = 6 paths.

%t p[n_]:=Product[Binomial[n-1,k],{k,1,n-1}]

%t Table[p[n],{n,1,20}] (* A001142(n-1) *)

%t Table[p[n]*n,{n,1,20}] (* A208650 *)

%t Table[p[n]*n!,{n,1,20}] (* A208651 *)

%Y Cf. A208651.

%K nonn

%O 1,2

%A _Clark Kimberling_, Mar 01 2012