Байрлал

Тавил:
Тэмдэгтүүдийн дараалал өгөгджээ. (Тэмдэгтүүд бүгд хоорондоо ялгаатай) Тэгвэл уг тэмдэгтүүдээс цагаан толгойн дарааллаар сэлгэмэл үүсгэхэд уг тэмдэгтийн дараалал хэддүгээр гишүүн бэ?
Жишээ:
Оролт: bza:
Гаралт: 4
//(abz,azb,baz,bza,zab,zba)
Эх өгүүлбэр: Байрлал

Бодолт:

i = Оролтын эхнээсээ i дахь үсэг // 1-ээс n хүртэл;
order[i] = (i-дахь үсгийн араас байрлалтай үсэгнүүдээс цагаан толгойн дарааллаар i-аас өмнө орших үсэгнүүдийн тоо) + 1;

Хариу = 1 + order[1]*(n-1)! + order[2]*(n-2)! + order[3]*(n-3)! + ... order[n-1]*1!;

Баталгаа:
i дахь үсгийн ард (n-i) үсэг байгаа ба тэдгээр нь (n-i)! сэлгэмэл үүсгэнэ. Мөн i дахь үсгийн өмнө order[i] ширхэг үсэг байгаа ба тэдгээр нь ардаа тус бүр (n-i) янзын өөр цуваа залгаатай байгаа учраас комбинаторик дахь үржвэрийн дүрмээр order[i]*(n-i) байгаа юм.
Тэгээд мэдээж i маань 1-ээс n хүртэл утга авах ба i=n үед order[i]*0! = 0 байх нь ойлгомжтой билээ.
Дээр нь тоог 1-ээс эхэлж дугаарладаг учраас 1-г нэмж өгөөд болно.

Update: 2 дахь мөрийн эхний өгүүлбэрийн ард "(Тэмдэгтүүд бүгд хоорондоо ялгаатай)" гэж нэмж бичив.