Permutations, combinations, bijective proofs, generating functions
3
votes
1answer
59 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 ...
1
vote
1answer
27 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 ...
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
3answers
463 views
Exponential Generating Functions For Derangements
I have been introduced to the concept of exponential generating functions a few days ago. However, my understanding of them are still quite limited, and I would like to see some examples. Earlier this ...
0
votes
2answers
32 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)?
4
votes
4answers
97 views
4
votes
1answer
35 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
1answer
36 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 ...
1
vote
1answer
156 views
Regressive injective function in a set of infinite cardinals
This is also from Kunen, Set Theory, ch. II:
Let $A$ be a set of infinite cardinals such that for each $\lambda$ regular $A\cap\lambda$ is not stationary in $\lambda$. Show that there is an ...
0
votes
0answers
20 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
0answers
40 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 ...
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 ...
3
votes
4answers
154 views
Counting the number of surjections.
How many functions from set $\{1,2,3,\ldots,n\}$ to $\{A,B,C\}$ are surjections? $n \geq 3$
Attempt
I was hoping to count the number of surjections by treating $A,B,C$ like bins, and counting the ...
3
votes
1answer
270 views
+500
Conjecture regarding trapping rational numbers in some special intervals
Conjecture:
Let $b\in\mathbb{N}_{\geq3}$ and $\{x_i\}$ be a collection of $b−2$ rational numbers greater than $1$. Does there always exist a natural number $a$ such that for all $i$ there exists some ...
1
vote
1answer
40 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 ...
0
votes
1answer
32 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 ...
3
votes
3answers
46 views
Probability/Combinatorics Problem - Old Maid Cards
A special deck of Old Maid cards consist of 25 pairs and a single old maid card. All 51 cards evenly between you and two other players – 17 cards for each player.
(a) how many different ...
-2
votes
0answers
34 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
24 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
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)!}.$$
...
0
votes
1answer
80 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}$$
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 ...
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
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 ...
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 ...
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 ...
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 ...
7
votes
3answers
1k views
Find the number of all four-digit positive integers that are divisible by four and are formed by the digits 0,1,2,3,4,5
Find the number of all four-digit positive integers that are divisible by four and are formed by the digits 0,1,2,3,4,5.
The combination for all numbers would be $6^4$, but we have a few roadblocks ...
9
votes
0answers
133 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
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 ...
9
votes
1answer
138 views
What are the analogues of Littlewood-Richardson coefficients for monomial symmetric polynomials?
The product of monomial symmetric polynomials can be expressed as
$m_{\lambda} m_{\mu} = \Sigma c_{\lambda\mu}^{\nu}m_{\nu}$
for some constants $c_{\lambda\mu}^{\nu}$.
In the case of Schur ...
3
votes
3answers
106 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
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
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 ...
0
votes
1answer
126 views
Combinatorics: How many subsets of size k are there in a group of N elements?
Updating the question after some comments.
If I have a multiset consisting of elements {1, 1, 2, 2, 3}. How can I mathematically find the number of distinct sub-multisets with size 2?
The answer for ...
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 ...
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.
6
votes
1answer
37 views
Grouping natural numbers into arithmetic progression
I need to find the number of ways of dividing the first 12 natural numbers into 3 equal groups (4 numbers each), so that the numbers in any particular group can be arranged in AP (Arithmetic ...
1
vote
1answer
17 views
Even weighted codewords and puncturing
My question is below:
Prove that if a binary $(n,M,d)$-code exists for which $d$ is even, then a binary $(n,M,d)$-code exists for which each codeword has even weight.
(Hint: Do some puncturing ...
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 ...
2
votes
2answers
59 views
Partitions of $n$: proving $p(n+2)+ p(n) \geq 2p(n+1)$
For $n \geq 2$ give an alternative description of $p(n) - p(n-1)$ as the number of partitions of $n$ which have a certain property.
I have done that part, it is fine. I have not included it here ...
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 ...
20
votes
7answers
656 views
How are we able to calculate specific numbers in the Fibonacci Sequence?
I was reading up on the Fibonacci Sequence when I've noticed some were able to calculate specific numbers. So far I've only figured out creating an array and counting to the value, which is incredibly ...
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)$ ...
7
votes
1answer
154 views
combinatorial geometry: covering a square
I'm stuck with this problem. can anyone help me?
A finite collection of squares has total area 4. show that they can be arranged to cover a square of side 1.
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 ...
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 ...
