Permutations, combinations, bijective proofs, generating functions
0
votes
0answers
4 views
Rolling dices and simple problem
I'm facing the following problem.
Let's say I have N dices in a hand. I need to calculate how much time I should roll my dices to make all of them equal selected (pre-defined) number. Each time when ...
0
votes
0answers
11 views
How to find exponential generating function and simple expression of mappings without fixed points
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
17 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
22 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
15 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
35 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
27 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
22 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
1answer
54 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
28 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
25 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)!}.$$
...
1
vote
0answers
32 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
25 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
31 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
51 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
77 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
41 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
105 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
62 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
55 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
37 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
53 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
131 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
27 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
69 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
30 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
113 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
56 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
59 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
85 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
42 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
37 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
45 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 ...
4
votes
2answers
25 views
Counting Number of Objects - When to Add One Back
I know this might be a very basic question. Sometimes to count objects, we just subtract. For example -- If there are 5 apples and I take away 1, then remaining are $5 - 1 = 4$ apples.
But other ...
5
votes
1answer
58 views
Is there a name for this given type of matrix?
Given a finite set of symbols, say $\Omega=\{1,\ldots,n\}$, is there a name for an $n\times m$ matrix $A$ such that every column of $A$ contains each elements of $\Omega$?
(The motivation for this ...
1
vote
2answers
34 views
Proof of Möbius function on subset poset
Prove that Möbius function of subset poset of $[n]$ is following, given $A,B \subseteq [n]$.
$\mu (A,B)=\left\{
\begin{array}{l} (-1)^{|B|-|A|},& \text{if}\,\, A \subseteq B\\
0,& ...
2
votes
1answer
46 views
If a 3D-cake is cut by $n$ planes yielding the maximum number of pieces, then what is the number of pieces with the cake crust?
It is known that a 3D-cake can be cut by $n$ plane cuts at most into $N$ pieces, defined by Cake Number $N=\frac {1}{6}(n^3+5n+6)$. However, some of the pieces would have a crust of the cake as one of ...
2
votes
1answer
37 views
Is there a rigorous definition of a Young tableau?
In all combinatorics and algebra texts that I have seen so far, the notion of a "Young tableau" is defined in a somewhat informal fashion. The most common approach is stating that a Young tableaux is ...
0
votes
1answer
60 views
probability of divisibility
Let S be the sum of k randomly selected integers between 1 and n.
What is the probability of S being divisible q?
Can this be expressed in a closed form?
This is the generalization of one of the ...
