हम एक परिवर्तनीय संख्या हैं। लक्ष्य [1, num] के बीच संख्याओं के क्रमपरिवर्तन की गिनती का पता लगाना है जिसमें संख्याएँ पहले घट रही हैं फिर बढ़ती जा रही हैं। उदाहरण के लिए यदि num=3 तो संख्याएं 1,2,3 हैं। क्रमपरिवर्तन [3,1,2] और [2,1,3] होंगे और गिनती 2 है।
हम जानते हैं कि प्रत्येक क्रमचय में संख्याओं के घटने से लेकर संख्या के बढ़ने तक का परिवर्तन 1 की स्थिति के आधार पर तय किया जाएगा जो कि सबसे छोटा है। प्रत्येक 1 के बाद संख्या बढ़ने लगेगी। क्रमचय घटने और फिर बढ़ने के लिए, 1 को स्थिति 2 और अंक -1 के बीच स्थित होना चाहिए। [ → ...1…. → ].
यदि 1 शुरू में है तो श्रृंखला पूरी तरह से बढ़ रही है [ 1.. → ], अगर यह अंत में है तो श्रृंखला पूरी तरह से घट जाएगी [… → 1]।
मान लें कि हमारे पास num=4 है तो
1 को दूसरे स्थान पर रखते हुए, [- , 1 , - , - ]। पहली स्थिति के लिए हम (2,3,4) से चुन सकते हैं मान लीजिए कि हम 2 चुनते हैं, तो अनुक्रम [2,1,3,4] होगा। तो इस मामले में 3C1 क्रमपरिवर्तन संभव हैं।
1 को तीसरे स्थान पर रखते हुए, [-, -, 1, -]। पहली और दूसरी स्थिति के लिए तीन में से किन्हीं दो (2,3,4) का चयन करें। कुल क्रमपरिवर्तन 3 . होंगे सी<उप>2 ।
तो कुल क्रमपरिवर्तन होगा = 3 सी<उप>1 + 3 सी<उप>2 num=4
. के लिएकिसी भी अंक x के लिए, गिनती होगी = x-1 सी<उप>1 + x-1 सी<उप>2 +.....+ x-1 सी<उप>सी-2 =2<उप>x-1 - 2 द्विपद प्रमेय से।
आइए उदाहरणों के साथ समझते हैं
इनपुट - संख्या=4
आउटपुट − क्रमपरिवर्तन की संख्या जो पहले घट रही हैं और फिर बढ़ रही हैं:6
स्पष्टीकरण - क्रमपरिवर्तन होंगे -
[ 2, 1, 3, 4 ], [ 3, 1, 2, 4 ], [ 4, 1, 2, 3 ] → 1 at 2nd position [ 2, 3, 1, 4 ], [ 2, 4, 1, 3 ], [ 3, 4, 1, 2 ] → 1 at 3rd position
इनपुट - संख्या=6
आउटपुट − क्रमपरिवर्तन की संख्या जो पहले घट रही है और फिर बढ़ रही है − 30
स्पष्टीकरण - कुछ क्रमपरिवर्तन होंगे -
[ 2, 1, 3, 4, 5, 6 ], [ 3, 1, 2, 4, 5, 6 ], [ 4, 1, 2, 3, 5, 6 ], [ 5, 1, 2, 3, 4, 6 ], [ 6, 1, 2, 3, 4, 5 ] ……[ 6, 5, 4, 3, 1, 2].
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम उपरोक्त सूत्र से सीधे क्रमपरिवर्तन की गणना करने के लिए एक द्विपद प्रमेय का उपयोग करेंगे। साथ ही हम एक फंक्शन वैल्यू (लॉन्ग लॉन्ग i, लॉन्ग लॉन्ग num) बनाएंगे जो i num लौटाता है
-
परिवर्तनीय संख्या को इनपुट के रूप में लें।
-
फ़ंक्शन permutations_increase_decrease(int num) संख्या लेता है और क्रमपरिवर्तन की गिनती देता है जो पहले घटते हैं और फिर संख्या 1 से संख्या तक बढ़ते हैं।
-
फ़ंक्शन मान (लंबी लंबी i, लंबी लंबी संख्या) का उपयोग (इनम)% अस्थायी गणना के लिए किया जाता है। जहां अस्थायी=1000000007.
-
permutations_increase_decrease(int num) के अंदर temp=1000000007 लें।
-
यदि संख्या 1 है तो कोई क्रमपरिवर्तन संभव नहीं है इसलिए 0 लौटाएं।
-
अन्य सेट गिनती =(मान (2, संख्या - 1) - 2)% अस्थायी); सूत्र का उपयोग करना।
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
long long value(long long i, long long num){
int temp = 1000000007;
if (num == 0){
return 1;
}
long long j = value(i, num / 2) % temp;
j = (j * j) % temp;
if(num & 1){
j = (j * i) % temp;
}
return j;
}
int permutations_increase_decrease(int num){
int temp = 1000000007;
if (num == 1){
return 0;
}
int count = (value(2, num - 1) - 2) % temp;
return count;
}
int main(){
int num = 4;
cout<<"Count of permutations that are first decreasing then increasing are: "<<permutations_increase_decrease(num);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of permutations that are first decreasing then increasing are: 6