Permutations, combinations, bijective proofs, generating functions
1
vote
3answers
82 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
57 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
45 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 ...
2
votes
1answer
30 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
44 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 ...
1
vote
2answers
23 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
19 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)$ ...
1
vote
0answers
32 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 ...
11
votes
2answers
87 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
65 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
27 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 ...
11
votes
2answers
81 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
49 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
57 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
67 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
36 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
44 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
23 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
31 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
28 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
40 views
Permutations of $[n]$ with $k$ peaks
Can anyone explain how to enumerate the combinatoric sequence described as the "permutations of $[n]$ with $k$ peaks". I'm interested in understanding better what this actually means and hopefully ...
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
56 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
44 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
54 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 ...
3
votes
4answers
75 views
3
votes
1answer
40 views
Prove that for all positive integer n, the inequality $2n\choose n$ $<4^n$ holds
How do I prove that for all positive integer n, the inequality $2n\choose n$$<4^n$ holds?
Thank you!
0
votes
2answers
30 views
In how many ways can you choose $k$ out of $n$ people standing in line, So there's a space of at least 3 people between them
In how many ways can you choose $k$ out of $n$ people standing in line, So there's a space of at least $3$ people between them.
Actually, I don't even know how to start on this one.
3
votes
3answers
77 views
How many options are there for 15 student to divide into 3 equal sized groups?
How many options are there for 15 student to divide into 3 equal sized groups?
Now i know the soultion is $\;\dfrac {15!}{5!5!5!3!}\;$ but i can't understand why.
Can anyone please enlighten me?
2
votes
1answer
16 views
Combinatorics question in field of characteristic 2…
I'm trying to figure out the number of solutions to a particular system of equations. The variables here are $A_1,A_2,A_3,B_1,B_2,B_3,C_1,C_2,C_3$, all in $\mathbb{F}_2$, constraint to
(a) $B_1^2 = ...
3
votes
0answers
33 views
Non-isomorphic posets
Is there any formula or counting algorithm for the number of non-isomorphic posets (defined on finite n-element set)?
I'm interested how to solve task *5, p.4 in Birkhoff's "Lattice Theory"
the book
...
4
votes
2answers
51 views
How many vertices of degree 1 in a tree?
How many vertices of degree 1 are there in a tree with no vertices of degree more than 4?
The only thing that I have right now is that the number of edges in a tree is n-1 where n is the number of ...
2
votes
3answers
57 views
Ball-counting problem (Combinatorics)
I would like some help on this problem, I just can't figure it out.
In a box there are 5 identical white balls, 7 identical green balls and 10 red balls (the red balls are numbered from 1 to 10). A ...
5
votes
3answers
47 views
Compositions of $n$ with largest part at most $m$
This is a problem from Stanley's Enumerative Combinatorics that I'm failing at a bit (lot):
Let $\bar{c}(m,n)$ denote the number of compositions of $n$ with largest part at most $m$. Show that ...
5
votes
1answer
36 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 ...
2
votes
2answers
23 views
Combinations problem help
Four couples have reserved seats in a row for a concert. In how many different ways can they be seated if the two members of each couple wish to sit together?
At first I thought that this was ...
5
votes
2answers
132 views
What's the intuition behind this equality involving combinatorics? [duplicate]
What is the intuition behind
$$
\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}
$$
? I can't grasp why picking a group of $k$ out of $n$ bijects to first picking a group of $k-1$ out of $n-1$ ...
1
vote
2answers
52 views
Finding $A,B,C,D \subseteq \{1,2,…n\}$ such that $A \cup B \cup C \cup D = \{1,2,…,n\}$
I have this combinatorial question:
Find the number of $(A,B,C,D)$ of sets $A,B,C,D \subseteq \{1,2,...,n\}$ such that $A \cup B \cup C \cup D = \{1,2,...,n\}$
I started by saying:
We choose ...
1
vote
1answer
30 views
Multiples of one number in base-$10$ [duplicate]
How can I prove that all the natural numbers has one multiple in base-$10$ such that this numbers is written just with zeros and ones?
For example, let $n=3$ then, exists al least one number, the ...
3
votes
3answers
262 views
Demonstration using the Pigonhole principle
I was thinking about the following problem:
Let $n\in\mathbb N$ be odd. If I have a symmetric matrix in $M_n(\mathbb{N})$, i.e. a square symmetric matrix of size $n$, for which each column and ...
5
votes
1answer
45 views
In how many ways can n couples (husband and wife) be arranged on a bench so no wife would sit next to her husband?
In how many ways can n couples (husband and wife) be arranged on a bench so no wife would sit next to her husband?
I thought about this:
(Total amount of ways to sit 2n people in 2n sits)-(Using ...
3
votes
1answer
73 views
effective way to get the integer sequence A181392 from oeis
the sequence A181392 are perfect squares and any digit in the sequence says
"I am part of an integer in which you'll find d digits "d"" (see A108571, How can we call them? "digit-valid"?)
How to get ...
3
votes
2answers
59 views
Coloring the 1 x n field
I have a field of 1 x n size. I need to color it using: red, orange, green, blue. Also, I can color red only even amount of blocks, and orange only odd amount of blocks.
Finally I need to find a ...
