Permutations, combinations, bijective proofs, generating functions
1
vote
1answer
18 views
Proving $\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$
Prove that $$\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$$ by computing the coefficient of $z^M$ in the identity $$(1 + z + z^2 + \cdots ) \cdot \frac{1}{(1-z)^{k+1}} = \frac1{(1-z)^{k+2}}.$$
I ...
1
vote
4answers
38 views
Proving an identity using formal power series
4.
(a) Prove that $\dfrac{1-x^2}{1+x^3}=\dfrac{1}{1+\frac{x^2}{1-x}}$.
(b) By expanding each side of the identity in (a) as a power series, and considering the coefficient of $x^N$, prove ...
-1
votes
1answer
30 views
Express the following power series as a raional function
Consider the following power series:
$f(x) = \sum\limits_{i>=1} 2^{i-1}x^{3i}$ = $\ x^3 + 2x^6 + 4x^9 + ...$
$g(x) = \sum\limits_{i=2}^{20} f(x)^{i}$
Express both f(x) and g(x) as rational ...
2
votes
1answer
14 views
Factor-critical graphs
$G$ is factor-critical $\Leftrightarrow$ $c_o(G-U) \leq |U|$, $\forall U \subseteq V(G)$ except when $U = \emptyset$ (where $c_o$ is the number of odd components - basically, the RHS means that $U = ...
0
votes
2answers
39 views
Words counting problem
What is the number of words, which are made by shifting all lower case letters in the english alphabet and none of them contains any of the four subwords (null, one, two, three)?
2
votes
2answers
50 views
How many ways to colour a tetrahedron with monochromatic triangles.
I'm trying to find how many different ways there are to colour the edges of a regular tetrahedron with n colours such that there are no monochromatic triangles.
Certainly for one triangle there must ...
4
votes
1answer
37 views
Can anyone help me finding recurrence relation in combinatoric?
Guys, I am having trouble finding recurrent relation.
A codeword is made up of the digits $0,1,2,3$ (order is important!). A codeword is defined as legitimate if and only if it has an even number of ...
0
votes
0answers
22 views
How to find exponential generating function and simple expression of mappings without fixed points [duplicate]
Anyone can help to solve this problem?
Derive the exponential generating function, $L(z)$, of mappings without xed points. Find a very simple expression for
$Ln = n![z^n]L(z)$ (by any means). Then ...
0
votes
1answer
39 views
How to derive this exponential generating function?
Anyone can help to solve this problem?
Let $\mathcal{F}$ be the combinatorial class of all functions $f : [1,n] \rightarrow [1,n]$. Derive the exponential generating function and use
it to compute ...
0
votes
0answers
43 views
graphs where distance between every two vertices is $\geq$2.
Are there any class of graphs where distance between every two vertices is $\geq$2.
I was wondering about the existence of such graphs. Because for counter examples I have Paths $P_n$.
Thank you ...
1
vote
1answer
16 views
Calculating the probabilities of different lengths of repetitions of X length numbers
I'm trying to calculate the probabilities of different lengths of repetitions of X length number however I know I'm doing it incorrectly since when I add all the probabilities together they don't ...
1
vote
1answer
41 views
In how many ways can 4 couples sit in a row if no 2 women sit next to each other?
The Numbers of ways?
I am so confussed- I have looked at it tones of different ways and its not working.
The previous question was the same thing but using 7 couples and the answer was 203,212,800 ...
-2
votes
0answers
37 views
Solve $ z= \frac{2a^2}{-4+z} + \frac{2a^4}{(-4+z)^2(-16+z)} + \cdots $.
I am trying to solve $z\in \mathbb{C}$ in terms of $a\in \mathbb{C}$, where
$$
z= \frac{2a^2}{-4+z} + \frac{2a^4}{(-4+z)^2(-16+z)} + \cdots.
$$
I plugged $z= \sum_{k=0}^\infty c_k a^k $ into the ...
0
votes
0answers
25 views
Changing the weight function of a generating function?
Let $S$ be a set of objects, and suppose $w$ is a weight function on $S$ with generating function $\Phi_S(x)$. Let $w^*$ be a new weight function for $S$ defined by $w^*(a)=5w(a)+3$ for all $a\in S$, ...
1
vote
2answers
65 views
number of ways to make $2.00
How many different ways can you make $2.00 using only 1 cent, 5 cent, 10 cent, and 25 cent pieces, and 1 and 2 dollar bills (there are 100 cents in a dollar)? I have worked out an equation:
$$p + 5n ...
2
votes
0answers
30 views
Number of ways to partition n fixed points using cubic grids
What is the number of different ways to partition $n$ points in $\mathbb{R}^d$ using cubic grid partitions of given cube size h?
Notation: $n$ is a positive integer. The class of cubic grid ...
1
vote
0answers
27 views
On a sum related to alternating sign matrices
I'm trying to prove that
$$A_{n,k} = \binom{n+k-2}{k-1}\frac{(2n-k-1)!}{(n-k)!}\prod_{j=0}^{n-2}\frac{(3j+1)!}{(n+j)!}$$
implies
$$A_n = \sum_{k=1}^nA_{n,k}=\prod_{j=0}^{n-1}\frac{(3j+1)!}{(n+j)!}.$$
...
4
votes
1answer
79 views
A generalization of Kirkman's schoolgirl problem
A friend of mine asked me this question. "I have $3n$ elements, and I want to know which is the maximum number of triplets $(a,b,c)$ so that no two triplets have more than one element in common".
The ...
0
votes
1answer
35 views
Calculating a coefficient for a formal power series
My textbook has a whole bunch of exercises on finding some coefficient inside a formal power series. Unfortunately, there aren't any examples on how to do so, especially since many of the series ...
2
votes
1answer
33 views
Number of subsets the cardinality of whose intersections with some other subsets are known
$A$ is a non-empty finite set. $A_1,A_2,\ldots,A_n$ are subsets of $A$. How many subsets $B$'s of $A$ are there that satisfy that $|B\cap A_i|=a_i,\forall 1\leq i\leq n$, where $a_i\geq 0$'s are given ...
1
vote
2answers
53 views
Is my solution correct? Generating functions question: How many non-negative solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have?
so we began studying this subject, and I tried solving this question: How many non-negative and whole ($\in \Bbb Z$) solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have?
I would like to ...
0
votes
1answer
83 views
How to use generating functions to prove that $n^n=\sum\limits^{n-1}_{k=0}\binom{n}{k}k^k(n-k)^{n-k-1}$
Can anyone help? How can we use generating functions to prove the following identity:
$$n^n=\sum^{n-1}_{k=0}\binom{n}{k}k^k(n-k)^{n-k-1}$$
1
vote
1answer
43 views
MATLAB code to find distance and eccentricity in graphs
I was trying to find the distances between vertices in graphs. But as the number of vertices are increasing up to 25 vertices or more, its becoming a tedious job for me to calculate $distance$ and ...
3
votes
3answers
107 views
How many functions $f:\{1,2,3,4\}→\{1,2,3,4\}$ satisfy $f(1)=f(4)$?
I just need a hint or a way to think a about this problem: $f(1)$ can be $1, 2, 3, 4$ and $f(4)$ can be $1,2,3,4.$
1
vote
3answers
63 views
How many functions $ f: \{1, 2, 3, \dots, 10\} \to \{0,1\}$ satisfy $f(1) + f(2) + \dots + f(10) = 2$?
How many functions $ f: \{1, 2, 3, \dots, 10\} \to \{0,1\}$ have this property: $$f(1) + f(2) + \dots + f(10) = 2.$$
I understand just $2$ functions can be $1$, the rest have to be $0$, in total ...
2
votes
0answers
57 views
History of Hindman's Theorem
At this blogpost about Hindman's Theorem, I read the following lines:
'I love the odd history so allow me to digress... etc. '
This sentence made me curious to know what this history looks ...
3
votes
1answer
39 views
About two equinumerous partitions of the same set.
Let $\mathcal {A,B}$ be partitions of a set $X$ into $m$ subsets. Suppose that for any $k\leq m$ and any $A_1,\ldots,A_k \in\mathcal A$ there are at most $k$ elements of $\mathcal B$ contained in ...
3
votes
1answer
38 views
An equality involving binomial coefitients
I am wondering why formula
$$\sum_{j=k}^n\binom{n}{j}(-1)^j = (-1)^k\binom{n-1}{k-1} $$
is correct only for $1<k<n+1$. Could it be extended to $0<k<n+1$?
I found this formula here.
2
votes
2answers
56 views
Using generating functions, Find a closed formula to next expression: $\sum_{k=0}^m{k(k+2)}$
Using generating functions, Find a closed formula to next expression:
$\sum_{k=0}^m{k(k+2)}$
If i use calculus power series rules, The question is fairly simple. But how can i find the proper ...
9
votes
0answers
138 views
A contest question
$p$ is an odd prime,denote $$f(x)=\sum_{k=0}^{p-1}\binom{2k}{k}^2x^k.$$
Prove that for every $x\in Z$,$$(-1)^\frac{p-1}2f(x)\equiv f(\frac{1}{16}-x)\pmod{p^2}.$$
This is a contest question,I do not ...
1
vote
2answers
28 views
How many different sandwiches are possible?
The canteen sells sandwiches on white, brown, or grain bread. The filling can either be egg, cheese, chicken, or ham. These can be served with tomato sauce, BBQ, or no sauce. How many different types ...
1
vote
1answer
21 views
Question about inverse with respect to convolution product.
Let $\mathcal{I}(X)$ be the collection of real valued functions $f:X\times X\to \mathbb{R}$ with the property that $f(x,y)=0$ when $x>y$. The convolution product $f*g$ for $f,g\in \mathcal{I}(X)$ ...
2
votes
0answers
36 views
Testing combinatorial species for isomorphism
Given a system of species equations that specifies two species, is there an algorithm to test if they are isomorphic?
Testing for isomorphism can be done by testing the equality of the coefficients ...
12
votes
2answers
96 views
Simplifying $\sqrt{\underbrace{11\dots1}_{2n\ 1's}-\underbrace{22\dots2}_{n\ 2's}}$
How do I simplify:
$$\sqrt{\underbrace{11\dots1}_{2n\ 1's}-\underbrace{22\dots2}_{n\ 2's}}$$
Should I use modulos or should I factor them? Or any I suppose to use combinatorics? Any one have a ...
1
vote
3answers
70 views
“Set of all formal products” - what does this mean?
List the set of all formal products of $(1+x^2+x^4)^2(1+x+x^2)^2$ with exponents summing to $4$.
What is this question asking exactly? What is a "formal product"? Does it have anything to do with ...
1
vote
0answers
32 views
decomposition of products of monomial symmeric polynomials into sums of them
I'm trying to make sense of the answer given in: this question
I am stuck at the phrase 'where the partitions γ result from adding, respectively, from α all distinct partitions obtained by permuting ...
0
votes
1answer
37 views
Combinations, Expected Values and Random Variables
A community consists of $100$ married couples ($200$ people). If during a given year, $50$ of the members of the community die, what is the expected number of marriages that remain intact?
Assume ...
13
votes
2answers
114 views
The smallest nontrivial conjugacy class in $S_n$
Find the smallest nontrivial conjugacy class in $S_n$.
For small $n$, the answer is not hard to find:
$$\begin{array}{cc}
n & \text{smallest nontrivial class(es)} \\
1 & \text{none} \\
2 ...
1
vote
2answers
57 views
Expected number of pieces of a chessboard
If n squares are randomly removed from a $p \ \cdot \ q$ chessboard, what will be the expected number of pieces the chessboard is divided into?
Can anybody please provide how can I approach the ...
4
votes
1answer
60 views
$\sum_{k=1}^{n} \binom{n}{k}k^{r}$
Find:$$\sum_{k=1}^{n} \binom{n}{k}k^{r}$$
For r=0 the sum is obviously $2^{n}$.
For r=1 the sum is $n2^{n-1}$.
For r=2 the sum is $n(n+1)2^{n-2}$.
Here's what I've tried:
...
4
votes
1answer
87 views
Prove that in a graph a group of even nodes there are two of degree at least $2$
We have just started learning graphs, and I understand the concept clearly, but when it comes to proving something I just don't know how to start!
Prove that in in a group of an even number of ...
2
votes
1answer
43 views
Power series of $f(x)=\sqrt{\frac{1+x}{1-x}}$
How do I find the power series form of $\,f(x)\,$:
$$\displaystyle f(x)=\sqrt{\frac{1+x}{1-x}}$$
I tried to multiply the fraction by $\,\dfrac{1+x}{1+x}\,$ but it didn't help...
5
votes
0answers
39 views
Combinatorial proof of a Stirling number identity.
Consider the identity
$$\sum_{k=0}^n (-1)^kk!{n \brace k} = (-1)^n$$
where ${n\brace k}$ is a Stirling number of the second kind. This is slightly reminiscent of the binomial identity
...
2
votes
5answers
66 views
Finding the number of non-neg integer solutions?
How would I find the number of non negative integer solutions to this problem?
$$x_1 + x_2 + x_3 + x_4 = 12$$ if $0 \leq x_1 \leq 2$.
2
votes
2answers
46 views
Counting Problem - N unique balls in K unique buckets w/o duplication $\mid$ at least one bucket remains empty and all balls are used
I am trying to figure out how many ways one can distribute $N$ unique balls in $K$ unique buckets without duplication such that all of the balls are used and at least one bucket remains empty in each ...
1
vote
1answer
24 views
possible combinations of 3-digit
How many possible combinations can a 3-digit safe code have?
Because there are 10 digits and we have to choice 3 digits from this,
then we may get $10^P3$ but A author used the formula $n^r$, why is ...
0
votes
1answer
26 views
Drawing balls with replacement, until I have one of each.
A urn has (n+1) types of balls, n of unique colors and the rest black. When picking a ball randomly from the urn, a colored (non black) ball has a probability of p of being picked. Each ball of color ...
0
votes
0answers
32 views
Partition integer into n parts, with constraint on each part [duplicate]
$x_1,x_2,...,x_n$ are integer numbers in the range [0,B-1]. Count the number of solution for
$x_1+x_2+...+x_n=k$.
I know this problem is similar to the one here
Number of ways of partitioning a sum ...
0
votes
3answers
29 views
permutation/combination problem
There are 3 doors to a lecture room. In how many ways can a lecturer enter the room from one door and leave from another door?
I have done like this: They way of entering is 3 and exiting is also
...
1
vote
1answer
59 views
Permutations of $[n]$ with $k$ peaks
Is there a formula for the number of permutations of $[n]$ with $k$ peaks?
Here is some information on the OEIS about these numbers, but no such formula is given. I'm sure such a formula exists due ...
