Chủ đề này có 5 trả lời

[tanlsth]

Cho $ n>p \in N^*,p \in P $
Tìm số cách tô màu các đỉnh của đa giác $ p $ cạnh thỏa mãn điều kiện sau
$ 1. $ Mỗi đỉnh tô đúng $1$ màu
Biết số màu đã cho là $ n $ và nếu cách tô này nhận được từ cách tô kia bởi $ 1 $ phép quay thì coi như là một

Bài viết đã được chỉnh sửa nội dung bởi tanlsth: 05-03-2007 - 19:44

[vnm]

đề này hình như có vấn đề

[tanlsth]

Nếu $ n<p $ thì kết quả là $ \dfrac{n^p-n}{p}+p $
Còn $ n>p $ lại là 1 vấn đề
Mình chỉ giải ra dựa trên công thức truy hồi thôi không ra được kết quả tổng quát

[bluesea]

2 đỉnh cạnhnhau có cần khác màu không
nếu đề chỉ có vậy thì hiển nhiên mỗi đỉnh cón cách tô-> p^n cách tô

Bài viết đã được chỉnh sửa nội dung bởi bluesea: 05-03-2007 - 14:15

[tanlsth]

$ 2 $ cách nhận được từ nhau bởi $ 1 $ phép quay thì coi là $ 1 $ cách
Do đó kết quả bạn nêu trên không đúng

[LvanhTuan]

đề này hình như có vấn đề

Bài này dùng tới cong thức nghịch đảo Mobius
Bài này cũng tương tự như bài ISL Bài này cũ rùi mà nếu như mình không nhầm thì bài này liên quan tới 1 bài ISL đã cũ rùi :
Ta tổng quát cho bài ISL như sau :
Cmr nếu $\sum_{d|n}a_{d}= k^{n}$, thì $ n | a_n $.với mọi $d| n$
Bài này chứng minh bằng nhiều cách cách hay nhất là dùng ct nghịch đảo Mobius
Bài này cũng không phải là ngoại lệ :
Gọi $f(n)$ là số cách .
giả sử tại mỗi đỉnh ta gán các đỉnh bởi các số $ a_{i} $ thoả mãn $ a_{i} $ nhận 1 trong 2 giá trị 0 và 1
gọi M(d) là số dãy $a_{1};..;a_{d} $
Ta có ;
$f(n)= \sum M(d)$ với mọi d|n
và $ \sum dM(d)=2^{n} $
Sử dụng công thức nghịch đảo Mobius ta có:
$nM(n) =\sum_{d|n}\mu(d)^{ 2^{ \dfrac{n}{d} } } $
Từ đây dễ dàng có được :
$f(n)= \dfrac{1}{n}\sum_{d|n}\varphi (\dfrac{n}{d})0.2^d $
nếu n nguyên tố thì công thức là :
$ \dfrac{2^{n}+2n-2 }{n} $